, 王科同济大学 机械与能源工程学院, 上海 201804
收稿日期：2017-05-18
基金项目：国家自然科学基金资助项目(71471135)。
作者简介：周炳海(1965-), 男, 浙江浦江人, 同济大学教授, 博士生导师。
摘要：为有效提升多重入车间的生产效率, 考虑实际生产中队列约束, 提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述, 以最小化工件总完成时间为优化目标, 建立数学规划模型.针对该调度模型提出列生成算法, 设计带多重决策的动态规划方法来求解工件级子问题, 为更快收敛, 主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中, 构造列池并设计局部变异.最后, 对各种不同问题规模进行了数值实验, 结果表明所提出的调度算法是有效可行的.
关键词：队列可重入列生成动态规划分支定界
Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints
ZHOU Bing-hai
, WANG KeSchool of Mechanical Engineering, Tongji University, Shanghai 201804, China
Corresponding author: ZHOU Bing-hai, E-mail: bhzhou@tongji.edu.cn
Abstract: To effectively enhance the production efficiency of multi-reentrant workshop, the queue constraint was considered where products were processed layer by layer, and then a scheduling method of reentrant hybrid flow shops(RHFS)was proposed based on column generation algorithm. Firstly, a two-stage scheduling model of RHFS was described and a mathematical programming model was built with an objective of minimizing the total completion time. A column generation algorithm was developed and dynamic programming with multiple decision-making was designed to solve each sub-problem. Further, the adaptive accelerating strategy was applied to effectively improve the algorithm convergence. In the process of generating integral solutions by using branch-and-bound method, column pool was built and neighborhood mutation method was emploied. Finally, numerical experiments in different problem scales were carried out to analyze the proposed algorithm. Results verify the validness and feasibility of the proposed algorithm.
Key words: queuereentrantcolumn generationdynamic programmingbranch-and-bound
可重入车间作为半导体系统中最复杂的调度, 其基本特性是一个工件多次进入某些工作站[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上的机器总数; tl为工件的l层在专用机器上加工的时间; t′l为工件的l层在普通机器上加工的时间; Si, l, 2为工件i的l层在工作站2上开始加工的时间; Cl, i, 1为工件i的l层在工作站1上的完成时间; Cl, i, 2为工件i的l层在工作站2上的完成时间; Co表示批o的完成时间; wl为工件l层等待时间的阈值; Zi, i′, l为工件i及工件i′的l层在工作站2上的同一批中加工; xl, i, j, k为工件i的l层在机器j的可行排序的第k个位置加工; tl, 2为工件的l层在工作站2的加工时间; tl, i, 1为工件i的l层在工作站1上的加工时间; φj, l, i表示工件i的l层在机器j上加工; B为批容量的上限值.
本文所研究的RHFS调度问题中, 由2个工作站组成, N个工件需重复进入2个工作站加工L次, 如图 1所示.工作站1由M1台机器组成, 每台机器同一时间只能加工1个工件; 工作站2由1台批处理的机器组成, 机器同一时间只能加工一个批.
图 1(Fig. 1)
 | 图 1 考虑队列约束的RHFS问题Fig.1 Problem of RHFS with queue constraints |
工件每一层都有专用的加工机器, 工件在专用机器上加工的时间为普通机器上加工的时间的μ倍, 如式(1)所示:
 | (1) |
 | (2) |
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
 | (10) |
 | (11) |
2.1 主问题SP模型的建立为方便运用列生成, 做如下定义:s为单个工件在各台机器上的调度; t为时间刻度; T为满足调度需要的总时间长度; fs=Cs为调度s的成本; ys表示某一工件按照调度s加工, 则为1, 否则为0;ajts表示调度s于时间t在工作站1的机器j上加工, 则为1, 否则为0;bos表示调度s分配到批o加工则为1, 否则为0;通过D-W方法, 上述问题可以分解为集合分割模型的主问题和子问题[12].
主问题:
 | (12) |
 | (13) |
 | (14) |
 | (15) |
构造列时需将可行调度s中机器和时间的信息集成到一列中.每一列由[ajts, bos, 1]T构成, 表示一个工件可行调度.
Ω表示符合条件的工件可行调度的集合.运用列生成算法求解LSP问题时, 只需给定部分可行的列Ω′?Ω, 即求解限制性松弛问题(RLMP).
记ujt(t=1, 2, …, T, j=1, 2, …, M)为对应于等式约束(12)的对偶变量值, δo(o=1, 2, …, H)为对应于约束(13)的对偶变量值, v为对应于约束(14)的对偶变量值.因为所有的工件都相同, 只需解决一个低级子问题.
 | (16) |
对于调度s, 若满足RCs且RCs>minRC, 则以一定概率被接收作为主问题的列.由于前期RLMP中的列相对较少, 算法注重宽度搜索, 后期列较多, 为避免计算冗杂, 被接收的概率下降.因此设置接收模型为
 |
2.2 求解工件级子问题工件级子问题即寻找使得式(16)最小的列.工件级子问题为
 | (17) |
 | (18) |
 | (19) |
 | (20) |
 | (21) |
 | (22) |
 | (23) |
 | (24) |
2.3 工件级子问题动态规划算法按工件层数划分阶段, 阶段变量取l=1, 2, …, L.每个阶段的状态变量集合与其工作站2上加工的批相对应, 即Xl={o|boli=1}, l=1, 2, …, L.
定义工件i的第l层在工作站1上的机器j在时间t完成加工的阶段指标为χiljt.定义Γ为满足调度时间要求的最小时间刻度.
 |
 |
建立递归方程如下:
 |
工件i在加工l层时获得的最优状态通过回溯法获得.
 |
2.4 分支定界整数化最优解上面过程得到的解往往为非整数的解, 而实际调度问题中, 往往需要整数解.因此就需要设计分支定界的规则使最终得到的解为整数[13].
在分支的过程中, 若存在多个非整数解, 选择分支的解需满足min{|ys-0.5|}.通过将ys进行分支, 把原问题分成两个子问题(即对应ys=1和ys=0两个节点), 针对这两个子问题需做如下调整.
1) 限制性主问题的初始列, ys=1的分支在产生初始列时不考虑分配给ys的任意时刻, 式(13)中分配给ys的批相应减1, 式(14)右边的N值相应减1;ys=0在产生初始列时不产生与ys一致的列.
2) 求解子问题时, ys=1的分支在新增列时不考虑已经分配给ys的任意时刻; ys=0分支在产生新列时不产生与ys一致的列.由于很难保证不产生与ys一致的列, 因此本文使用列池来存放需要避免的列.当求解子问题得到的列与列池中的列相同时, 则将该列进行局部变异.变异分两种形式:1)对机器上的处理时间进行变异; 2)对批进行变异.对机器上的处理时间进行变异时, 将工件的处理时间往邻近的区域偏移一个时间单位; 对批进行变异时, 即改变工件所分配的批, 同时需要根据式(18)~式(20)调整工件在机器上的处理时间.
3 数值实验为验证列生成算法的有效性, 设计具体算例进行求解.第一阶段的机器数量m=3, 工件数量n=10, 工件层数l=3, 每个工件不同层在各机器的加工时间见表 1.不同层组成的批在第二阶段的加工时间tl, 2=rand(3, 5), l=1, 2, 3, 批的上限值B为3, 工件在第二阶段的等待时间wl=5, l=1, 2, 3.
表 1(Table 1)
 表 1 不同层在各机器上的加工时间Table 1 Processing time of different layer on each machine
| 表 1 不同层在各机器上的加工时间 Table 1 Processing time of different layer on each machine | |||||||||||||||||||
通过MATLAB语言进行编程后, 在英特尔酷睿2.5 GHz处理器上运行, 得到总完成时间变化见图 2.
图 2(Fig. 2)
 | 图 2 求解过程中总完成时间的变化Fig.2 Variation of total completion time during solving process |
当检验数非正时, 得到该算例的LSP问题的最优解, 表明本文设计的列生成算法可以有效求解LSP问题.
用列生成算法对随机产生的实例进行了仿真实验.分别考虑工作站1配置3~6台机器环境下, 对任意工件个数和机器台数的组合, 随机产生10组不同的实例数据, 结果取平均值.将列生成算法得到解和分支定界运行后得到的解分别与启发式给出的初始解做比, 如表 2所示.
表 2(Table 2)
表 2 不同机器及工件规模下的列生成算法数值结果Table 2 Numerical results of column generation algorithm under different sizes of machines and jobs
| 表 2 不同机器及工件规模下的列生成算法数值结果 Table 2 Numerical results of column generation algorithm under different sizes of machines and jobs |
从表 2可以看出, 本文算法对中等规模的问题是有效的, 在可接受的时间范围能进行求解.但随着工件个数的增加, 算法所产生的列和计算时间会急剧增加.列生成算法的列数和计算时间主要受工件个数的影响, 受机器数量的影响不明显.
本文在RHFS调度中考虑了队列约束, 因此对不同的问题分析了队列约束的影响.对机器台数为3台(M3), 工件层数为3层(L3), 工件个数为20, 30, 40(J20/J30/J40)的情况下进行了仿真.将运行的结果与不考虑队列约束情况下得到的结果做对比, 如图 3所示.
图 3(Fig. 3)
 | 图 3 队列约束对RHFS调度的影响Fig.3 Influence of queue constraints on RHFS scheduling |
由图 3可知, 队列约束对RHFS调度具有比较明显的影响, 随着队列时间的增大, 队列约束的影响逐渐减少, 并在一定范围之后, 队列约束对调度不再影响.
对于RHFS调度问题的求解, 大多文献使用遗传算法(GA)或改进的GA对调度问题进行求解.通过将GA和列生成算法(CG)对多个RHFS调度问题进行求解, 从调度目标总完成时间(TC)及算法的运行时间两个维度进行对比, 如表 3所示.
表 3(Table 3)
表 3 不同规模RHFS调度问题下遗传算法和列生成算法求解的对比Table 3 Contrast of genetic algorithm and column generation algorithm in RHFS scheduling problem with different size
| 表 3 不同规模RHFS调度问题下遗传算法和列生成算法求解的对比 Table 3 Contrast of genetic algorithm and column generation algorithm in RHFS scheduling problem with different size | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
从表 3可以发现, 遗传算法可以在小规模问题的求解上得到近优解, 但随着问题规模的增大, 其与最优解之间的差距(gap)也逐渐增大; 同时在求解大规模问题上易于陷入局部收敛, 导致无法得到全局较优的解.列生成算法较GA算法有明显的优势.
4 结语本文研究的RHFS调度问题, 考虑了实际生产中的队列约束, 以及不同处理类型的机器.在使用列生成算法求解问题时, 采用自适应加速策略改进算法, 并建立多重决策的动态规划算法求解子问题, 在分支定界的过程中构造列池并设计变异规则.最后对各种规模的实例进行仿真实验, 验证算法的可行性.实验结果表明, 本文所设计的列生成算法对中等规模的问题是有效的.
参考文献
| [1] | Zhou B, Gao Z, Chen J. Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints[J].Journal of Central South University, 2014, 21(1): 160–166.DOI:10.1007/s11771-014-1927-2 |
| [2] | 周炳海, 石潇铭. 带重入约束的双集束型晶圆制造设备调度算法[J].东北大学学报(自然科学版), 2013, 34(9): 1305–1309. ( Zhou Bing-hai, Shi Xiao-ming. Scheduling algorithm for double-cluster of wafer fabrication system with reentrant constraints[J].Journal of Northeastern University(Natural Science), 2013, 34(9): 1305–1309.DOI:10.3969/j.issn.1005-3026.2013.09.021) |
| [3] | Graves S C, Meal H C, Stefek D, et al. Scheduling of re-entrant flow shops[J].Journal of Operations Management, 1983, 3(4): 197–207.DOI:10.1016/0272-6963(83)90004-9 |
| [4] | Hekmatfar M, Ghomi S M T F, Karimi B. Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan[J].Applied Soft Computing, 2011, 11(8): 4530–4539.DOI:10.1016/j.asoc.2011.08.013 |
| [5] | Dugardin F, Yalaoui F, Amodeo L. New multi-objective method to solve reentrant hybrid flow shop scheduling problem[J].European Journal of Operational Research, 2010, 203(1): 22–31.DOI:10.1016/j.ejor.2009.06.031 |
| [6] | Cho H M, Bae S J, Kim J, et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm[J].Computers & Industrial Engineering, 2011, 61(3): 529–541. |
| [7] | Jeong B, Kim Y D. Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times[J].Computers & Operations Research, 2014, 47(47): 72–80. |
| [8] | Choi H S, Kim H W, Lee D H, et al. Scheduling algorithms for two-stage reentrant hybrid flow shops:minimizing makespan under the maximum allowable due dates[J].International Journal of Advanced Manufacturing Technology, 2009, 42(9/10): 963–973. |
| [9] | Wu K, Zhao N, Gao L, et al. Production control policy for tandem workstations with constant service times and queue time constraints[J].International Journal of Production Research, 2016, 54(21): 6302–6316.DOI:10.1080/00207543.2015.1129468 |
| [10] | Wu K. Classification of queueing models for a workstation with interruptions:a review[J].International Journal of Production Research, 2014, 52(3): 902–917.DOI:10.1080/00207543.2013.843799 |
| [11] | An Y J, Kim Y D, Choi S W. Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times[J].Computers & Operations Research, 2016, 71(1): 127–136. |
| [12] | Nishi T, Izuno T. Column generation heuristics for ship routing and scheduling problems in crude oil transportation with split deliveries[J].Computers & Chemical Engineering, 2014, 60(2): 329–338. |
| [13] | Tas D, Gendreau M, Dellaert N, et al. Vehicle routing with soft time windows and stochastic travel times:a column generation and branch-and-price solution approach[J].European Journal of Operational Research, 2014, 236(3): 789–799.DOI:10.1016/j.ejor.2013.05.024 |
