可重入车间作为半导体系统中最复杂的调度, 其基本特性是一个工件多次进入某些工作站^[1-2].在半导体晶圆制造过程中, 晶圆需多次经过相同的设备进行加工, 重入加工的次数取决于晶圆的层数.晶圆重入这一制造过程即为可重入混合流水车间(reentrant hybrid flow shops, RHFS)问题.

RHFS自1983年被Graves提出以来^[3], 已取得较大研究进展.Hekmatfar等^[4]研究了只含两道工序, 以最小makespan为优化目标提出了一种混合遗传算法.Dugardin等^[5]以瓶颈利用率最大化和最大完成时间最小化为调度目标, 提出一种新的L-NSGA算法.Cho等^[6]提出了基于局部搜索的帕累托遗传算法求解RHFS调度问题.Jeong等^[7]以最小化延迟时间为目标函数, 提出了启发式算法和分支定界算法.Choi等^[8]针对两阶段RHFS问题, 以最小化makespan为目标提出了分支定界和启发式算法.

上述文献能够为RHFS调度问题提供良好的借鉴, 但未考虑实际生产中存在的队列约束^[9-10].队列约束是指工件完成某工序加工后, 需在一定时间内到达下个工作站进行加工, 否则工件将会报废或返工^[11].其次上述文献多使用智能优化算法, 未体现工件不同层次间对于机器耦合这一特性, 且未使用列生成这类能够在合理时间内找到可量化指标的近优解算法.因此本文将队列约束考虑进RHFS调度问题中, 并使用列生成算法求解问题的近优解.

1 问题描述

为便于描述, 对符号做如下定义.i, i′为工件索引; l为加工层索引; j为工作站1上的机器索引; o为批的索引; H为批的总数; N为工件的总数; L为工件的层数; M为工作站1上的机器总数; t_l为工件的l层在专用机器上加工的时间; t′_l为工件的l层在普通机器上加工的时间; S_{i, l, 2}为工件i的l层在工作站2上开始加工的时间; C_{l, i, 1}为工件i的l层在工作站1上的完成时间; C_{l, i, 2}为工件i的l层在工作站2上的完成时间; C_o表示批o的完成时间; w_l为工件l层等待时间的阈值; Z_{i, i′, l}为工件i及工件i′的l层在工作站2上的同一批中加工; x_{l, i, j, k}为工件i的l层在机器j的可行排序的第k个位置加工; t_{l, 2}为工件的l层在工作站2的加工时间; t_{l, i, 1}为工件i的l层在工作站1上的加工时间; φ_{j, l, i}表示工件i的l层在机器j上加工; B为批容量的上限值.

本文所研究的RHFS调度问题中, 由2个工作站组成, N个工件需重复进入2个工作站加工L次, 如图 1所示.工作站1由M¹台机器组成, 每台机器同一时间只能加工1个工件; 工作站2由1台批处理的机器组成, 机器同一时间只能加工一个批.

工件每一层都有专用的加工机器, 工件在专用机器上加工的时间为普通机器上加工的时间的μ倍, 如式(1)所示:

(1)

工件在工作站1完成加工后, 即进入队列等待在工作站2上进行加工.为保证产品质量, 工件在工作站1完成加工后至下一个工作站加工的等待时间不能超过规定的阈值, 即需满足式(2):

(2)

只有加工相同层的工件才能形成一个批, 批的容量不能超过上限B, 且同一批加工的工件具有相同的完成时间, 即满足式(3), 式(4).本文将处理同一层上的相同工序定义为同一作业.

(3)

(4)

定义κ_m(m=1, 2, …, M)为工作站1中机器m的可行排序, 可行排序的每个位置表示需要加工的作业, 其长度设为N×L.任一位置至多分配一个作业, 位置为空表示无作业分配, 只有上一位置被分配后才能分配下一个位置, 即需满足式(5)~式(7).

(5)

(6)

(7)

作业只能安排在一个可行排序的一个位置上, 即需满足式(8).

(8)

任一工件, 只有在前一层加工完成后, 后一层才能开始加工, 需满足式(9)：

(9)

任一工件, 只有在工作站1完成加工后, 才能到工作站2进行加工, 需满足式(10):

(10)

调度目标为所有工件的完成时间之和最小化, 如式(11)所示:

(11)

2 列生成算法

为使用列生成方法进行求解, 需要把上述模型建成基于时间-设备二维列的集合分割模型的形式.

2.1 主问题SP模型的建立

为方便运用列生成, 做如下定义:s为单个工件在各台机器上的调度; t为时间刻度; T为满足调度需要的总时间长度; f_s=C_s为调度s的成本; y_s表示某一工件按照调度s加工, 则为1, 否则为0;a_jts表示调度s于时间t在工作站1的机器j上加工, 则为1, 否则为0;b_os表示调度s分配到批o加工则为1, 否则为0;通过D-W方法, 上述问题可以分解为集合分割模型的主问题和子问题^[12].

主问题: .

(12)

(13)

(14)

(15)

上述SP模型中, y_s的取值为0或1.将约束(15)修改为y_s≥0时, 得到原问题的线性松弛问题LSP, 求解LSP问题, 将得到原问题的下界.

构造列时需将可行调度s中机器和时间的信息集成到一列中.每一列由[a_jts, b_os, 1]^T构成, 表示一个工件可行调度.

Ω表示符合条件的工件可行调度的集合.运用列生成算法求解LSP问题时, 只需给定部分可行的列Ω′⊆Ω, 即求解限制性松弛问题(RLMP).

记u_jt(t=1, 2, …, T, j=1, 2, …, M)为对应于等式约束(12)的对偶变量值, δ_o(o=1, 2, …, H)为对应于约束(13)的对偶变量值, v为对应于约束(14)的对偶变量值.因为所有的工件都相同, 只需解决一个低级子问题.

(16)

若存在调度s, 使RC_s < 0, 则说明主问题还未达到最优解.通常需将RC_s值最小的列添加到RLMP中.本文对列生成算法进行改进, 采用自适应加速策略.

对于调度s, 若满足RC_s且RC_s>minRC, 则以一定概率被接收作为主问题的列.由于前期RLMP中的列相对较少, 算法注重宽度搜索, 后期列较多, 为避免计算冗杂, 被接收的概率下降.因此设置接收模型为

当调度s被接收作为主问题的列, R_s为1, 否则为0;Rand_s为调度s产生的介于0与1之间的随机数; rnd为自适应算子; G为当前的迭代次数.

2.2 求解工件级子问题

工件级子问题即寻找使得式(16)最小的列.工件级子问题为

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

工件级子问题就是以式(17)为目标函数, 约束(18)~(20)表示工件需要满足的时间约束; 约束(21)表示工件的每一层在工作站1上加工时只能在1台机器上加工; 约束(22)表示工件任一层在工作站2上进行加工时选择的批的约束; 约束(23)表示工件在工作站2上完成的加工的时间与该批完成的时间相同; 式(24)表示工件在工作站1上的加工时间的约束.

2.3 工件级子问题动态规划算法

按工件层数划分阶段, 阶段变量取l=1, 2, …, L.每个阶段的状态变量集合与其工作站2上加工的批相对应, 即X_l={o|b_oli=1}, l=1, 2, …, L.

定义工件i的第l层在工作站1上的机器j在时间t完成加工的阶段指标为χ_iljt.定义Γ为满足调度时间要求的最小时间刻度.

定义工件i的第l层在工作站2的批o上进行加工的指标为ξ_ilo：

其中T_o={t|C_o-t_{l, 2}-w_l≤t < C_o-t_{l, 2}+1}.

建立递归方程如下:

其中:X′_l-1={o′|b_o′(l-1)i=1且C_o′ < C_o}; f_il(X_l, o)表示工件i的l层采用策略o达到状态为X_l-1的最优值.

工件i在加工l层时获得的最优状态通过回溯法获得.

工件i在加工l层时在工作站1所选择最优的机器j^*与时间t^*为(j^*, t^*)=arg ξ_ilo.

2.4 分支定界整数化最优解

上面过程得到的解往往为非整数的解, 而实际调度问题中, 往往需要整数解.因此就需要设计分支定界的规则使最终得到的解为整数^[13].

在分支的过程中, 若存在多个非整数解, 选择分支的解需满足min{|y_s-0.5|}.通过将y_s进行分支, 把原问题分成两个子问题(即对应y_s=1和y_s=0两个节点), 针对这两个子问题需做如下调整.

1) 限制性主问题的初始列, y_s=1的分支在产生初始列时不考虑分配给y_s的任意时刻, 式(13)中分配给y_s的批相应减1, 式(14)右边的N值相应减1;y_s=0在产生初始列时不产生与y_s一致的列.

2) 求解子问题时, y_s=1的分支在新增列时不考虑已经分配给y_s的任意时刻; y_s=0分支在产生新列时不产生与y_s一致的列.由于很难保证不产生与y_s一致的列, 因此本文使用列池来存放需要避免的列.当求解子问题得到的列与列池中的列相同时, 则将该列进行局部变异.变异分两种形式:1)对机器上的处理时间进行变异; 2)对批进行变异.对机器上的处理时间进行变异时, 将工件的处理时间往邻近的区域偏移一个时间单位; 对批进行变异时, 即改变工件所分配的批, 同时需要根据式(18)~式(20)调整工件在机器上的处理时间.

3 数值实验

为验证列生成算法的有效性, 设计具体算例进行求解.第一阶段的机器数量m=3, 工件数量n=10, 工件层数l=3, 每个工件不同层在各机器的加工时间见表 1.不同层组成的批在第二阶段的加工时间t_{l, 2}=rand(3, 5), l=1, 2, 3, 批的上限值B为3, 工件在第二阶段的等待时间w_l=5, l=1, 2, 3.

通过MATLAB语言进行编程后, 在英特尔酷睿2.5 GHz处理器上运行, 得到总完成时间变化见图 2.

当检验数非正时, 得到该算例的LSP问题的最优解, 表明本文设计的列生成算法可以有效求解LSP问题.

用列生成算法对随机产生的实例进行了仿真实验.分别考虑工作站1配置3~6台机器环境下, 对任意工件个数和机器台数的组合, 随机产生10组不同的实例数据, 结果取平均值.将列生成算法得到解和分支定界运行后得到的解分别与启发式给出的初始解做比, 如表 2所示.

从表 2可以看出, 本文算法对中等规模的问题是有效的, 在可接受的时间范围能进行求解.但随着工件个数的增加, 算法所产生的列和计算时间会急剧增加.列生成算法的列数和计算时间主要受工件个数的影响, 受机器数量的影响不明显.

本文在RHFS调度中考虑了队列约束, 因此对不同的问题分析了队列约束的影响.对机器台数为3台(M3), 工件层数为3层(L3), 工件个数为20, 30, 40(J20/J30/J40)的情况下进行了仿真.将运行的结果与不考虑队列约束情况下得到的结果做对比, 如图 3所示.

由图 3可知, 队列约束对RHFS调度具有比较明显的影响, 随着队列时间的增大, 队列约束的影响逐渐减少, 并在一定范围之后, 队列约束对调度不再影响.

对于RHFS调度问题的求解, 大多文献使用遗传算法(GA)或改进的GA对调度问题进行求解.通过将GA和列生成算法(CG)对多个RHFS调度问题进行求解, 从调度目标总完成时间(TC)及算法的运行时间两个维度进行对比, 如表 3所示.

从表 3可以发现, 遗传算法可以在小规模问题的求解上得到近优解, 但随着问题规模的增大, 其与最优解之间的差距(gap)也逐渐增大; 同时在求解大规模问题上易于陷入局部收敛, 导致无法得到全局较优的解.列生成算法较GA算法有明显的优势.

4 结语

本文研究的RHFS调度问题, 考虑了实际生产中的队列约束, 以及不同处理类型的机器.在使用列生成算法求解问题时, 采用自适应加速策略改进算法, 并建立多重决策的动态规划算法求解子问题, 在分支定界的过程中构造列池并设计变异规则.最后对各种规模的实例进行仿真实验, 验证算法的可行性.实验结果表明, 本文所设计的列生成算法对中等规模的问题是有效的.