基于多智能体和混合遗传算法的车间调度模型的应用分析

《基于多智能体和混合遗传算法的车间调度模型的应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江理_l二大学硕士学位论文合优化问题，从计算时间复杂度看是一个NP．Hard问题，随调度规模的增大，问题可行解的数量呈指数级增加，因而求解非常困难。在现有计算条件下，一般优化方法对于车间调度问题是低效甚至是无能为力的。(3)离散性：车间生产系统是个典型的离散系统，其中工件的加工发生在不同的时间和资源上，并且任务的到达、订单的更改、设备的增添和故障等都是离散事件。这样，就有可能用数学规划、离散系统建模与仿真的方式，通过排序理论研究车间调度问题。(4)动态性：在真实的车间中，有很多动态事件发生。这些事件主要有新任务到达、紧急任务插入、交货期改变、订单被取消、设备故障或修复等。

2、这些事件的发生通常是随机的。动态事件的发生，可能导致整个系统的性能大大降低，或是在原有的调度方案下生产任务将无法完成。在这种情况下，必须对动态事件做出响应，调整现有的调度方案，以保证任务的顺利完成，并使车间性能处于较好的状态。(5)多目标性：车间生产中，针对不同的加工任务，相应地有其特定的调度目标，待优化的性能指标有很多。例如生产周期、平均流通时间、平均延误率、设备利用率等。如何使车间调度系统适应不同的任务类型和规模，一直是车间调度中面临的难题，迄今为止还没有一个通用并且实用的车间调度系统。1．2．3车间调度的优化目标车间调度的目的就是使资源得到最优的利用，关键问题也是瓶颈

3、问题就是调度模型和算法的建立，不同规模的企业，考虑的优化目标是不同的，在不同的优化目标下建立模型与算法就不尽相同，考虑目标越多的调度算法和模型就越复杂，一般的优化目标有以下几种：(1)在一定时间周期内系统的产出最高。(2)系统生产所花的成本最少。(3)系统内设备的利用率最高。(4)系统内的在制品最少。(5)加工单个零件时通过系统的时间最短。制造系统车间调度建模的复杂性还体现在随着系统规模的扩大，所要考虑的信息呈爆炸性增长的趋势，与此同时，又要兼顾到调度方案的实时性和良好的调度效果，非常难于解决，目前尚未见到好的解决方案和实例。1．3传统的调度技术与模型存在的问题调度问题的研

4、究从二十世纪五十年代起就受到应用数学、运筹学、自动化和人工智能3基于多智能体和混合遗传算法的车间调度模型的应用研究等领域的科学家的重视，因其重要的理论和应用价值始终都是研究的热点。据不完全统计，从调度问题研究的文章首次发表以来，至今已有二万多篇关于生产调度问题的文章公开发表，提出了各种各样的研究方法同。在这些研究工作中最有影响的是二十世纪六十年代由Conway、Maxwell和Miller所提出的调度理论。按照他们的定义，所谓调度是指“如何分配一系列资源去完成一系列任务"。在生产系统中，调度被定义为“如何分配一系列机器，使它们在一定的时间内完成一系列的任务订单’’。于是，生

5、产调度表现为一个排序问题。为区别起见，他们把工件在一台机器上的排产定义为“排序”，而将对于多个不同机器上工件的排序问题命名为“调度”。调度的结果是调度时序表。它是一个“任务一时间”表，是一个“关于每一个项目以及为完成这些项目所采取的必须操作的执行序列随时间分配的计划"。这样，生产调度问题被描述为一个“在一定的初始条件和约束条件下寻求使某一性能指标最优”的数学问题，即一个最优化计算或最优控制问题。研究证明，这是一类难以解决的NP完全问题。然而，传统的调度技术和模型无论所使用具体的计算技术是属于数学优化方法的。还是运筹学的、抑或是人工智能方法，调度的研究工作始终是从应用数学的分

6、析与研究角度展开的。由于这种调度模型和概念是对实际生产调度问题的抽象，在实际制造系统开放的、动态的环境下，生产调度问题呈现极强的动态性，例如机器的损坏、加工计划的改变以及紧急订单的处理等，这就使得传统的调度技术和模型很难直接运用于解决实际的生产调度问题。1．4车问调度研究的历史与现状1．4．1车间调度研究的历史与现状在过去的40年中，大量关于车间调度的书籍文献出版与发表，当然也不乏很多关于工作车间调度的优秀文章。其中，1967年肯韦首先系统地撰写了关于调度理论的书籍，起到了里程碑的作用。随后，大量学者也竟相研究起来。在研究的过程中，由玛斯、汤普森(1963)和卡夫I'-J(

7、1976)编审的书籍以及派度(1995)等人的文章都为生产调度问题提供了更加广阔的理论解决空间。在多年的研究中，车间调度领域取得了丰硕的成果，这一时期产生了很多重要的调度方法。这些方法主要有：运筹学方法，基于规则的方法，系统仿真的方法，解析模型方法，邻域搜索方法，人工智能方法【8】【91。(1)基于启发式规则的方法对生产加工任务进行调度的最传统的方法是使用调度规则，因为启发式调度规则简4浙江理工人学硕士学位论文单，易于实现，计算复杂度低等原因，故在生产中得到了广泛的应用。但启发式规则一般不具备全局优化的特点。许多年