Page 93 - 机械自动化设计与制造研究

三、基于遗传算法的半导体生产线调度方法

（一）遗传算法
遗传算法由密切根大学的 Holland 等首先提出，其思想源于 Darwin 的进化论

和 Mendel 的遗传学说。该算法是一个迭代过程，在每次迭代过程中都保留一组
候选解，按其解的质量优劣进行排序，并按某种指标从中选出一些解，利用一些
遗传算子或遗传操作（如交叉和变异等）对其进行计算，产生新一代的一组候选
解，重复此过程，直至满足某种收敛指标为止。遗传算法与普通搜索算法的主要

差别在于：
（1）普通搜索算法的迭代是从一个解改进到另一个解，而遗传算法是从一
组解更新到另一组解。（2）普通搜索算法中解的表达可根据问题领域的情形做

任意的表达，而遗传算法的解是通过对原问题的编码用染色体表达的。（3）普
通搜索算法解的过程常常依赖解问题的领域知识，而遗传算法解的过程是基于染
色体进行的，可与领域知识无关。（4）普通搜索算法的迭代过程一般采用确定
性的搜索策略，而遗传算法在搜索过程中则利用结构化和随机性的信息，使问题

的优化解能获得最大的生存可能，这符合了“适者生存”的规律。由于遗传算法
是一种全局搜索算法，能使算法避免陷于局部最优，而且搜索速度快，因此得到
了很多领域的关注，如自动控制、计算机科学、工程设计等。目前该方法在 flow

shop 和 job shop 中已经得到了广泛的运用，但在半导体生产线这一特殊的调度上
还未见到相关的报告。
（二）基于遗传算法的半导体生产线调度方法
半导体生产线与 flow shop 有很多相似之处，前面所提到的约束条件也同样

适用于半导体生产线。但除此之外，它有个最显著特点，即工件在加工过程中的
不同阶段重复访问某些机器，不同加工阶段的工件可能在同一机器前同时等待加
工。

虽然半导体生产线与 flow shop 有显著的区别，但也要看到其相似处，那就
是工件都有固定的加工顺序，相比较而言，flow shop 没有可重入的特性，对半导
体的调度问题可以借鉴 flow shop 中的成功的例子，如混合 flow shop 的一些算法，

将其作适当改变，以满足半导体生产线的特性。
将半导体生产线的调度问题简化为：需要加工多个工件，所有工件的加工

81
81