一种有效的遗传算法在重入式生产调度问题中的应用

An effective genetic optimization approach for re-entrant flowshop problem

在半导体生产中,圆晶的制造过程无疑是最复杂也是最重要的环节。这种大规模独立的处理过程包含上百台机器和处理步骤是高度重入式的。关于重入式生产调度的优化问题通常来说都是属于NP难问题。本论文提出了一个基于遗传进化算法的重入式流水车间调度问题的优化算法,即通过对变异方式的范围限定来有效地减小产品的总滞留时间。尤其地,此方法对于流水线中突发情况的产生有很好的适应性,能够根绝突变有效地进行重新排序。并且我们还将改进的遗传算法与局部搜索算法和FIFO算法分别进行了比较。最后实验结果表明,本文提出的改进算法能够有效地保证维种群多样和计算时间之间的平衡。

In semiconductor manufacturing, the process of wafer fabrication is arguably the most technologically complex and capital intensive stage. This large-scale discrete-event process is highly re-entrant with hundreds of machines and processing steps. These optimization problems fall into the class of NP-hard problems. This paper addresses an optimized approach for the re-entrant flow shop scheduling problem （RFSP） by using genetic algorithm （GA）. An effective mutation method with range restriction is proposed to minimize total turn around time （TTAT）, especially dealing with the accidents effectively when re-scheduling is needed. Then we compare the modified genetic method with local search method and FIFO method. Experimental results indicated that the proposed method can efficiently balance the population variety and computing rate