基于遗传算法的车间调度优化及其仿真

《基于遗传算法的车间调度优化及其仿真》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉理工大学硕士学位论文单机调度问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队问题；多台并行机的调度问题更复杂，因而优化问题更突出；FlowShop型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序；JobShop是最一般的调度类型，不同的作业具有不同的加工操作和加工顺序，并不限制作业的加工设备。现代车间调度类型往往是JobShop类型的。2．根据性能指标，分为基于调度费用和调度性能的指标两大类。3．根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。4．根据作业的加

2、工特点，可将调度问题分为静态调度和动态调度。静态调度是指所有待安排加工的工作均处于待加工状态，因而进行一次调度后，各作业的加工时间被确定，在以后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的损坏等。因此动态调度要根据系统中作业、设备等的状况，不断地进行调度。实际调度的类型往往是JobShop型，且是动态的。实际的调度问题有以下特点：1．复杂性由于装卸作业、装卸设备、库场、搬运系统

3、之间相互影响、相互作用，每个作业又要考虑它的到达时间、装卸时间、准备时间、操作顺序、交货期等，因而相当复杂。而且调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是NP完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。2．动态随机性在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶然事件，如设备的损坏／修复、作业交货期的改变等。3．多目标性实际的计划调度往往

4、是多目标的，并且这些目标间可能发生冲突。Kiran等人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标。这种多目标性导致调度的复杂性和计算量急剧增加。武汉理工大学硕士学位论文1．3国内外车间调度问题研究现状和存在的问题1．国内外车间调度问题研究现状调度问题的研究始于20世纪50年代，Johnson提出了解决车间调度部分特殊问题的优化算法，代表调度理论研究的开始。60．70年代建立了调度理论的主体(经典调度理论)并重视调度复杂性的研究。大量的研究促使车间调度领域取得了丰硕的成果，产

5、生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法。Davis是最早把GA(GeneticAlgorithm，遗传算法)应用于车间调度问题的学者之一，他在使用GA求解车间调度的研究中取得了近似最优解。1985年，Davis发表了关于把GA成功应用于车间调度问题的论文，充分展示了GA在解决车问调度问题中的前景。此后，很多学者就遗传算法在车间调度问题方面的应用做了大量研究，发表了大量卓有成效的论文，使车间调度这类NP--hard问题的解决崭露曙光。例如

6、，以DavidEGoldberg，Yamada，Nakano，w11iuey，Fang，Kobayashi等为代表的一些学者在他们的论文中提出了一些具有突破性的新思想，改进并完善了传统GA车间调度中的应用方法，同时在解决一些著名的标准检测问题(Benchmark)中取得了最优(或接近最优)解，进一步证明了遗传算法在解决NP问题方面的有效性。㈦国内对车间调度的研究起步较晚，由于技术上的制约，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，国内也掀起了一股应用遗传算法研究车间调度的热

7、潮：研究工作主要集中在清华大学等等CIMS国家重点实验室，而目前这些实验室的系统开发基本上还处在刚投入试运行阶段，离开发出成熟的软件系统还有很长一段距离，因此各实验室还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业调度算法的研究方面，目前尚处在实验研究阶段。2．存在的问题由于大多调度问题属于一类NP困难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。各种近似／启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得的调度解的次优

8、性不能进行评估。在这方面有必要探索更好的近似最优调度算法，可以考虑增加合理的计算时间为代价，提高解的次优性。各4武汉理工大学硕士学位论文种基于统计优化的方法、诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但同别的优化算法类似，其也存在着一定程度的枚举、一般来说收敛到最优解较慢，并且对于判断解的最优性也很困难。在这方面也需要做进一步的研究。在调度问题的理论