毕业论文资料
武汉理工大学硕士学位论文
1.3国内外车间调度问题研究现状和存在的问题
1.国内外车间调度问题研究现状
调度问题的研究始于20世纪50年代,Johnson提出了解决车间调度部分特殊问题的优化算法,代表调度理论研究的开始。60.70年代建立了调度理论的主体(经典调度理论)并重视调度复杂性的研究。大量的研究促使车间调度领域取得了丰硕的成果,产生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展,又涌现出了许多新的车间调度理论与方法。Davis是最早把GA(GeneticAlgorithm,遗传算法)应用于车间调度问题的学者之一,他在使用GA求解车间调度的研究中取得了近似最优解。1985年,Davis发表了关于把GA成功应用于车间调度问题的论文,充分展示了GA在解决车问调度问题中的前景。此后,很多学者就遗传算法在车间调度问题方面的应用做了大量研究,发表了大量卓有成效的论文,使车间调度这类NP--hard问题的解决崭露曙光。例如,以DavidEGoldberg,Yamada,Nakano,w11iuey,Fang,Kobayashi等为代表的一些学者在他们的论文中提出了一些具有突破性的新思想,改进并完善了传统GA车间调度中的应用方法,同时在解决一些著名的标准检测问题(Benchmark)中取得了最优(或接近最优)解,进一步证明了遗传算法在解决NP问题方面的有效性。㈦
国内对车间调度的研究起步较晚,由于技术上的制约,基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用,国内也掀起了一股应用遗传算法研究车间调度的热潮:研究工作主要集中在清华大学等等CIMS国家重点实验室,而目前这些实验室的系统开发基本上还处在刚投入试运行阶段,离开发出成熟的软件系统还有很长一段距离,因此各实验室还在投入大量的人力和物力进行该方面的研究,特别是在开展对车间作业调度算法的研究方面,目前尚处在实验研究阶段。
2.存在的问题
由于大多调度问题属于一类NP困难组合问题,因此寻找具有多项式复杂性的最优算法几乎是不可能的。各种近似/启发式方法、诸如基于规则的算法等,由于能在合理的时间内产生比较满意的调度,因此广泛应用于实际调度中,但其往往对所得的调度解的次优性不能进行评估。在这方面有必要探索更好的近似最优调度算法,可以考虑增加合理的计算时间为代价,提高解的次优性。各