东北大学学报:自然科学版  2018, Vol. 39 Issue (9): 1315-1320  
0

引用本文 [复制中英文]

周炳海, 王科. 带队列约束的RHFS列生成调度算法[J]. 东北大学学报:自然科学版, 2018, 39(9): 1315-1320.
[复制中文]
ZHOU Bing-hai, WANG Ke. Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints[J]. Journal of Northeastern University Nature Science, 2018, 39(9): 1315-1320. DOI: 10.12068/j.issn.1005-3026.2018.09.020.
[复制英文]

基金项目

国家自然科学基金资助项目(71471135)

作者简介

周炳海(1965-), 男, 浙江浦江人, 同济大学教授, 博士生导师。

文章历史

收稿日期:2017-05-18
带队列约束的RHFS列生成调度算法
周炳海, 王科    
同济大学 机械与能源工程学院, 上海 201804
摘要:为有效提升多重入车间的生产效率, 考虑实际生产中队列约束, 提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述, 以最小化工件总完成时间为优化目标, 建立数学规划模型.针对该调度模型提出列生成算法, 设计带多重决策的动态规划方法来求解工件级子问题, 为更快收敛, 主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中, 构造列池并设计局部变异.最后, 对各种不同问题规模进行了数值实验, 结果表明所提出的调度算法是有效可行的.
关键词队列    可重入    列生成    动态规划    分支定界    
Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints
ZHOU Bing-hai, WANG Ke    
School 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: queue    reentrant    column generation    dynamic programming    branch-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为工件il层在工作站2上开始加工的时间; Cl, i, 1为工件il层在工作站1上的完成时间; Cl, i, 2为工件il层在工作站2上的完成时间; Co表示批o的完成时间; wl为工件l层等待时间的阈值; Zi, i′, l为工件i及工件i′l层在工作站2上的同一批中加工; xl, i, j, k为工件il层在机器j的可行排序的第k个位置加工; tl, 2为工件的l层在工作站2的加工时间; tl, i, 1为工件il层在工作站1上的加工时间; φj, l, i表示工件il层在机器j上加工; B为批容量的上限值.

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

图 1 考虑队列约束的RHFS问题 Fig.1 Problem of RHFS with queue constraints

工件每一层都有专用的加工机器, 工件在专用机器上加工的时间为普通机器上加工的时间的μ倍, 如式(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为满足调度需要的总时间长度; 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)

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

构造列时需将可行调度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 < 0, 则说明主问题还未达到最优解.通常需将RCs值最小的列添加到RLMP中.本文对列生成算法进行改进, 采用自适应加速策略.

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

当调度s被接收作为主问题的列, Rs为1, 否则为0;Rands为调度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上加工的批相对应, 即Xl={o|boli=1}, l=1, 2, …, L.

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

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

其中To={t|Co-tl, 2-wlt < Co-tl, 2+1}.

建立递归方程如下:

其中:X′l-1={o′|bo′(l-1)i=1且Co′ < Co}; fil(Xl, o)表示工件il层采用策略o达到状态为Xl-1的最优值.

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

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

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 Processing time of different layer on each machine

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

图 2 求解过程中总完成时间的变化 Fig.2 Variation of total completion time during solving process

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

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

表 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 队列约束对RHFS调度的影响 Fig.3 Influence of queue constraints on RHFS scheduling

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

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

表 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