基于改进遗传算法的集束型装备调度研究

邹咏楠++罗钧元++李林瑛

摘要：考虑机械手在输入装载室、加工模块和输出装载室三者间搬运时间和空载时间下，求解半导体制造中具有滞留时间约束的集束型装备调度问题，提出基于机械手搬运作业顺序编码的改进遗传算法，包括种群初始化、选择操作、变异操作和适应度函数计算等。仿真实验结果验证了提出算法的有效性。

关键词：遗传算法； 集束型装备； 半导体制造； 滞留时间约束

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2017）04-0263-02

Improved Genetic Algorithm for Cluster Tool Scheduling Problem

ZHOU Yong-nan，LUO Jun-yuan， LI Lin-ying

（School of Software， Dalian University of Foreign Languages， Liaoning 116044， China）

Abstract： Considering the robot transport time among the loadlock and the processing modules， for cluster tools with residency time constraints in semiconductor manufactory， this paper studied improved genetic algorithm based on single-arm robot move sequence coding， including population initialization， selection operation， mutation operation and fitness function calculation. Experimental examples showed that the proposed algorithm is effective.

Key words：Genetic Algorithm， Cluster Tools， Semiconductor Manufactory， Residency Time Constraints

1 概述

半導体制造集束型装备是集成电路生产线上的常见装备，由晶圆加工设备、物料搬运机械手和输入装载室组成。集成电路生产线对工艺和加工环境的严格要求，使得加工模块间的晶圆搬运作业必须由计算机控制的单臂或双臂机械手来完成。与经典的流水车间调度问题相比，集束型装备的调度问题不仅要合理地调度晶圆加工作业顺序，还要有效地规划机构手搬运作业顺序，因此更加复杂[1，2]。本文该对这类调度问题，在考虑滞留时间约束的前提下，提出一种基于机械手搬运作业顺序编码的改进的遗传算法。

2 问题描述

图1所示的集束型装备包括三个部分：单晶圆加工模块、单臂/双臂机械手和输入输出装载室。晶圆在加工过程中，首先依照预先制定的加工配方，晶圆从输入装载室进入；在经过激光或图像定位后，进入加工模块1，2，…，N完成加工；并在输出装载室冷却后离开系统。集束型装备调度问题的特点可有如下描述：1）晶圆在各个加工模块间没有缓冲，晶圆在上一加工晶圆被搬离后才能完成加载；2）各加工模块一次只能加工一片晶圆；3）晶圆在加工模块的停留时间具有滞留时间约束；4）物料运输模块为单臂机械手，执行晶圆的移动、空载、装载和卸载任务。

晶圆的加工过程是批量的周期性过程，相邻两个晶圆进入系统的时间间隔称为生产周期。其调度问题的目标是在满足滞留时间约束的前提下，确定机械手在一个生产周期内的搬动作业顺序，并使生产周期最小化。

3 改进遗传算法

遗传算法是一类基于概率而面向全局优化的随机搜索算法，以生物进化为原型，具有收敛速度快、计算时间少、鲁棒性高等优点[3]。虽然如此，由于无法全面地描述约束，遗传算法在解决实际问题中还有很多局限性。本文针对这一局限性，结合求解问题的特殊性，对遗传算法的编码方式、初始种群产生方式和交叉变异操作进行改进。

3.1 编码和解码

根据集束型装备的特点，提出了一种基于机械手搬运作业顺序的整数编码。该编码方式以有限的加工模块数作为染色体搜索空间维度，缩小了问题的搜索空间。设[Y={y0，y1，…，yN}]为染色体，基因[yi]表示机械手在工位[i]执行的搬运作业号[4，5]。

对染色体进行编码后，要按照编码规则将种群中的每个染色体进行解码，将染色体的基因信息再次解释为机械手搬运作业信息。对于给定的一组机械手搬运作业顺序，通过求解不等式即可获知对应的调度方案，即求出最优生产周期[T]以及调度方案。适应度函数定义为[Fit=s/T]，[s]为固定常数。

3.2 交叉操作

交叉操作可以使群体中优良个体的基因特性在一定程度上得以保持。集束型装备调度问题要求生成的机械手作业排序不能有重复的作业，对此选择了单点交叉、顺序交叉、部分映射交叉和两点交叉四种可行的交叉方法。通过分析和实验确定最终的交叉方案为两点交叉[6]。

3.3 变异操作

变异可以使算法跳出局部最优值，在更广的范围内搜索全局值。反序变异操作在搜索空间中搜索到的领域聚集度较高，本算法采用反序变异操作。

3.4 选择操作

采用经典轮盘赌选择方法能够保证优良基因得到延续，而且保证基因的多样性。将种群中的最优个体随机替换掉下一代中的某个体，以保持遗传算法的寻优能够不断进行[5]。

3.5改进遗传算法流程

如图2所示，将遗传算法与初始种群、交叉操作、变异操作、适应度函数计算等相结合，得到求解有晶圆滞留时间约束的集束型装备调度问题的改进遗传算法。

4 仿真实验

改进遗传算法的参数设置如下：种群规模100，最大迭代次数为150，交叉率为0.4，变异率为0.7。集束型装备的生产数据如表1所示，其中任意机械手搬运作业的空载时间为cij=5|i-j|，其中i和j为工位号，ai为加工时间，bi为滞留时间上界，di为机械手负载搬运时间。经过不到1秒计算得到最优解为165秒。

[工位号＼&ai＼&bi＼&di＼&0＼&30＼&1000＼&10＼&1＼&100＼&110＼&10＼&3＼&30＼&60＼&10＼&4＼&125＼&130＼&20＼&]

5 结论

本文提出的算法有效地解决了在具有晶圆滞留时间约束的集束型装备的调度过程中，由于滞留约束限制而产生的冲突和死锁的問题，为此类集束型装备的调度问题提供了一个可行的方法。实验结果验证了提出方法的有效性。

参考文献：

[1] 李林瑛，卢睿，臧洁. 加工多类型晶圆的集束型装备调度模型[J]. 数学的实践与认识， 2016， 46（16）：152-161.

[2] 周炳海， 黎明. 考虑多晶圆流的集束型设备群调度方法[J]. 东北大学学报自然科学版， 2016， 37（5）：697-701.

[3] 刘晓冰， 焦璇， 宁涛，等. 基于双链量子遗传算法的柔性作业车间调度[J]. 计算机集成制造系统， 2015， 21（2）：495-502.

[4] 王跃岗， 车阿大. 基于混合量子进化算法的自动化制造单元调度[J]. 计算机集成制造系统， 2013， 19（9）：2193-2201.

[5] Pengyu Yan， Ada Che， Naiding Yang， et al. A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem[J]. International Journal of Production Research， 2012， 50（22）：6403-6418.

[6] 杨煜俊， 龙传泽， 陶宇. 作业车间类型多机器人制造单元调度算法[J]. 计算机集成制造系统， 2015， 21（12）：3239-3248.