基于遗传算法的流水车间调度的方法及实际应用

《基于遗传算法的流水车间调度的方法及实际应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江1=业大学硕士学位论文国涌现出联想集团有限公司、海尔集团公司、黑龙江斯达造纸有限公司等一批先行企业，通过管理信息化，提高了管理水平，改善了经济效益，增强了市场竞争力。所以吉利集团豪情汽车制造有限公司的发动机金加工车间的生产调度问题就在这种背景下进行研究的。1．2国内外车间调度问题研究现状和存在的问题1．2．1国内外车间调度问题研究现状调度问题的研究始于20世纪50年代，Johnson提出了解决车间调度部分特殊问题的优化算法，代表调度理论研究的开始。60．70年代建立了调度理论的主体(经典调度理论)

2、并重视调度复杂性的研究。大量的研究促使车间调度领域取德了丰硕的成果，产生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车问调度理论与方法。Davis是最早把遗传算法GA(GeneticAlgorithm)应用于车l’BJ调度问题的学者之一，他在使用GA求解车间调度的研究中取得了近似虽优解。】985年，Davis发表了关于把GA成功应用于车间调度问题的论文，充分展示了GA在解决车间调度问题中的前景。此后，很多学者就遗传算法在车间调度问题方面的应用做了大量

3、研究发表了大量卓有成效的论文，使车间调度这NP．hard完全问题的解决崭露曙光。t，,bn，以DavidEGoldberg，Yamada，Nakano，wlliuey，Fang，Kobayashi等为代表的一些学者在他们的论文中提出了一些具有突破性的新思想，改进并完善了传统GA车间调度中的应用方法，同时在解决一些著名的标准检测问题(Benchmark)中取得了最优(或接近最优)解，进一步证明了遗传算法在解决NP问题方面的有效性。国内对车间调度的研究起步较晚，由于技术上的制约，基本上是靠调度人员的经验进

4、行车间作业分配和调度。随着遗传算法在车间调度方面的应用，国内也掀起了一股应用遗传算法研究车间调度的热潮，研究工作主要集中在清华大学等CIMS国家重点实验室，而目前这些实验室的系统开发基本上还处在剐投入试运行阶段，离开发出成熟的软件系统还有很长一段距离，因此各实验室还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业调度算法的研究方面，目前尚处在实验研究阶段。堑翌三些奎堂堡主堂篁堡奎1．2．2研究中存在的问题由于大多调度问题属于～类NP困难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不

5、可能的。各种近似／启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得的调度解的次优性不能进行评估。在这方面有必要探索更好的近似最优调度算法，可以考虑增加合理的计算时间为代价，提高解的次优性。各种基于统计优化的方法、诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但同别的优化算法类似，其也存在着一定程度的枚举、一般来说收敛到最优解较慢，并且对于判断解的最优性也很困难。在这方面也需要做进一步的研究。在调度问题的理论研究中，大多

6、数还是集中在针对经典的调度问题设计优化算法，而经典调度问题与实际相差较大，尤其在目前柔性制造环境下，柔性车间作业调度问题将是～个研究的重点和进一步研究的方向，而目前对于这方面研究的文献相对来说较少。在实际车间调度中，车间计划与车间调度往往是分层进行的，但这可能造成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，以求总体的优化也是需要进一步研究的。1．3进化计算与遗传算法近年来，一类基于生物界的选择和遗传机制的计算方法，包含如遗传算法(Gas，GeneticAlgorithms)、进化策略(ES

7、，EvolutionStrategies)和进化规划(EP,EvolutionProgramming)等方法，在科研和实际工程中的应用越来越广泛，并取得了一定的效果。这些方法模拟生物演化思想来实现数学建模、仿真，并由此设计、控制和优化人工系统。一般称为进化计算(EC，EvolutionaryComputation)。EC是计算智能的一方面，主要有Holland等创立的遗传算法。Schwefel等创立的进化策略以及Fogel等创立的进化规划。生物进化理论表明，复杂结构的生命是在相当短的时间进化而来的，这

8、种机制目前尚未完全弄清楚，但某些特征已被人们所掌握。大多数生物的进化是通过有性繁殖和自然选择这两种基本过程进行的。有性繁殖完成了对后代基因的重组，重组的结果产生了群体中对自然环境具有不同适应能力的个体，自然选择的机制决定了那些适应性较强的个体可以存活下去，而较弱的将要被淘汰。自然选择的塑坚三些丕兰堡主兰堡丝苎原则是适者生存。进化算法就是基于上述思想发展起来的一类随机搜索技术，他们模拟了群体的进化过程。其中每个个体表示给定问题搜索空问的一点，进化计算从任一