工程科学学报.第41卷.第11期：1450-1457.2019年11月 Chinese Journal of Engineering,Vol.41,No.11:1450-1457,November 2019 D0L:10.13374/.issn2095-9389.2018.11.27.002,http://journals.ustb.edu.cn 多日标多约束混合流水车间插单重调度问题研究 何小妹四，董绍华 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:18813127630@163.com 摘要研究了多目标多阶段混合流水车间的紧急订单插单重调度问题，综合考虑工件批量、刀具换装时间、运输能力等约 束.先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型，再针对紧急订单插单干扰，增加最 小化总加工机器偏差值目标，建立三目标重调度优化模型，并分别用NSGAⅡ算法与融合基于事件驱动的重调度策略和重排 插单策略的NSGAⅢI算法对两个模型进行求解，最后，以某实际船用管类零件生产企业为案例，先对NSGA-Ⅱ算法和 NSGA-ⅢI算法的性能进行评估，得到NSGA-Ⅱ算法更适用于解决双目标优化问题而NSGAⅢI算法在解决三目标优化问题时 表现更优的结论，再将所建模型与所提算法应用于该企业的十组插单案例中，所得优化率接近三分之一，验证了实用性和有 效性 关键词混合流水车间：紧急订单插单重调度：多目标：多约束：NSGAⅢ算法 分类号U673.2 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint HE Xiao-me,DONG Shao-hua School of Mechanical Engineering.University of Science and Technology Beijing.Beijing 100083,China Corresponding author,E-mail:18813127630@163.com ABSTRACT To study the multi-objective rush order insertion rescheduling problem under hybrid flow shop with multiple stages and multiple machines,the constraints,such as job lots,sequence-dependent set-up times,and round-trip transportation times,were simultaneously considered.A static optimal scheduling model of initial orders was first established to minimize the maximum order completion time and minimize the total transportation time.The non-dominated sorting genetic algorithm (NSGA)-II algorithm was applied to solve a two-objective optimal problem.Then,for the rush order insertion disturbance factor,the objective to minimize the total machine deviation between the initial scheduling and rescheduling plans was added as a stability index to establish an optimal rush order rescheduling model.The NSGA-III algorithm based on the event-driven rescheduling strategy and order rearrangement strategy was applied to solve a three-objective optimal problem.Finally,a realistic ship pipe parts manufacturing enterprise is regarded as a study case.Two sets of experiments are carried out to explain the motivation of the selected method.The performances of the NSGA-II and NSGA-III algorithms are evaluated by three metrics,including the mean ideal distance,spread of non-dominated solution,and percentage of domination.The results show that the NSGA-II algorithm is more suitable for solving two-objective optimal problem, whereas NSGA-III algorithm performs better in solving three-objective optimal problems.Then,the proposed model and method were applied to 10 rush order insertion cases of the enterprise.All the three objectives were improved according to the compared results obtained by the actual and optimal scheduling.The optimal rate is close to one third,which verifies the feasibility of the proposed model 收稿日期：2018-11-27 基金项目：国家自然科学基金资助项目(71301008)
多目标多约束混合流水车间插单重调度问题研究 何小妹苣，董绍华 北京科技大学机械工程学院，北京 100083 苣通信作者，E-mail：18813127630@163.com 摘 要 研究了多目标多阶段混合流水车间的紧急订单插单重调度问题，综合考虑工件批量、刀具换装时间、运输能力等约 束. 先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型，再针对紧急订单插单干扰，增加最 小化总加工机器偏差值目标，建立三目标重调度优化模型，并分别用 NSGA-II 算法与融合基于事件驱动的重调度策略和重排 插单策略的 NSGA-III 算法对两个模型进行求解. 最后，以某实际船用管类零件生产企业为案例，先对 NSGA-II 算法和 NSGA-III 算法的性能进行评估，得到 NSGA-II 算法更适用于解决双目标优化问题而 NSGA-III 算法在解决三目标优化问题时 表现更优的结论，再将所建模型与所提算法应用于该企业的十组插单案例中，所得优化率接近三分之一，验证了实用性和有 效性. 关键词 混合流水车间；紧急订单插单重调度；多目标；多约束；NSGA-III 算法 分类号 U673.2 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint HE Xiao-mei苣 ，DONG Shao-hua School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E-mail: 18813127630@163.com ABSTRACT To study the multi-objective rush order insertion rescheduling problem under hybrid flow shop with multiple stages and multiple machines, the constraints, such as job lots, sequence-dependent set-up times, and round-trip transportation times, were simultaneously considered. A static optimal scheduling model of initial orders was first established to minimize the maximum order completion time and minimize the total transportation time. The non-dominated sorting genetic algorithm (NSGA)-II algorithm was applied to solve a two-objective optimal problem. Then, for the rush order insertion disturbance factor, the objective to minimize the total machine deviation between the initial scheduling and rescheduling plans was added as a stability index to establish an optimal rush order rescheduling model. The NSGA-III algorithm based on the event-driven rescheduling strategy and order rearrangement strategy was applied to solve a three-objective optimal problem. Finally, a realistic ship pipe parts manufacturing enterprise is regarded as a study case. Two sets of experiments are carried out to explain the motivation of the selected method. The performances of the NSGA-II and NSGA-III algorithms are evaluated by three metrics, including the mean ideal distance, spread of non-dominated solution, and percentage of domination. The results show that the NSGA-II algorithm is more suitable for solving two-objective optimal problem, whereas NSGA-III algorithm performs better in solving three-objective optimal problems. Then, the proposed model and method were applied to 10 rush order insertion cases of the enterprise. All the three objectives were improved according to the compared results obtained by the actual and optimal scheduling. The optimal rate is close to one third, which verifies the feasibility of the proposed model 收稿日期: 2018−11−27 基金项目: 国家自然科学基金资助项目 (71301008) 工程科学学报，第 41 卷，第 11 期：1450−1457，2019 年 11 月 Chinese Journal of Engineering, Vol. 41, No. 11: 1450−1457, November 2019 DOI：10.13374/j.issn2095-9389.2018.11.27.002; http://journals.ustb.edu.cn
何小妹等：多目标多约束混合流水车间插单重调度问题研究 1451· and the effectiveness of the proposed method.The proposed model and method may assist other enterprises that apply make-to-order production mode to reduce the impact of rush order insertion and realize a win-win mechanism between enterprises and customers KEY WORDS hybrid flow shop;rush order insertion rescheduling;multi-objective;multi-constraint;NSGA-IlI algorithm 混合流水车间(hybrid flow shop,HFs)调度问 constraint and longest common sequence crossing GA, 题广泛存在于流程工业和制造业中，Gupta已经 IPC-LCSC GA)对多阶段流水车间下的ROIRP进 证明了两阶段中一个阶段有两台加工机器的 行研究. HFS调度问题是非确定性多项式(non-deterministic 综上，已有的对ROIRP的研究文献中，场景大 polynomial,.NP)难度问题.而紧急订单又是面向订 多限定在流水线或单机设备，以HFS为研究原型 单生产型企业普遍存在的问题，它在为企业带来 的甚少，且大多目标单一，运输时间、刀具换装时 额外利润的同时，也对企业的生产系统稳定性造 间等约束均被忽略，与实际生产情况存在较大差 成破坏，对企业的快速应变能力来说，是一个巨大 异，因此本文对多约束HFS下的多目标ROIRP进 的挑战.因此，对HFS下的紧急订单插单重调度问 行研究，综合考虑工件批量、刀具换装时间和运输 (rush order insertion rescheduling problem,ROIRP) 能力约束.，建立紧急订单插单重调度模型，依次用 的研究十分必要且意义重大. NSGA-IⅡ算法和NSGA-III算法对其进行求解，并 实际生产车间往往存在多种生产约束，如提 将某实际船用管类零件生产企业作为实验对象， 高生产效率的分批生产，Meng等]采用改进鸟群 验证了所建模型与所提方法的实用性与有效性 迁移优化算法对批量流调度问题进行求解.刀具 1紧急订单插单重调度问题建模 换装时间大多存在于多产品混合生产的车间中， Rossil)对某制造系统的刀具换装时间约束进行研 1.1模型描述及假设 究，Yue等则同时考虑带批量与刀具换装时间约 本文所研究的问题可描述为：某混合流水车 束的多并行机调度问题.此外，在流程工业和制造 间的生产阶段集为Stage={l,2,…,…,sh,加工设 业中，运输时间往往不可忽视，如Qin等便研究 备集为M={1,2,…,m,…,Mal,运送设备集为 了带交货期时间窗和机器运输时间约束的铸造业 V={1,2,…,y,…,Vl.任一阶段j均包含m;台异构 生产调度问题，除了客观存在的生产约束外，由于 并行机和v台搬运设备，M为阶段j的加工机器 生产系统的不确定性，车间调度还面临着许多动 集.初始订单0={O1,02,…,0,…,0n}包含n种工 态干扰，如机器故障、新工件到达、紧急订单插单 件，工件O的批次集为X={1,2,…,x,…,h,用 等，重调度是应对千扰最重要的举措，Vieira等 Ox表示工件0的第x批工件，O,表示工件Ox在 对其做出了综述，认为重调度可由事件或周期驱 阶段j加工，即工序Ox,M,表示工件O,x在阶段 动.动态干扰因素会造成生产系统的混乱，因此 j的可选加工机器集，MSM.在1=0时刻，综合 Wu等☑提出新旧调度计划中各工件的开始加工 考虑客户满意度和企业资源消耗量，以最小化订 时间偏差和加工次序偏差两种指标来评价重调度 单完工时间和最小化总运输时间为双目标，对初 方案的稳定性.在对重调度问题干扰因素的研究 始订单进行优化调度；在t=T时刻，包含n种工件 文献中，以机器故障和新工件到达因素居多，如 的紧急订单0={O1',O2',…,Om'1到达并需插入到 Cui和Gu提出一种离散群搜索优化算法对机器 当前系统中进行合并生产，增加插单前后调度方 故障下的混合流水车间重调度问题进行求解，而 案中的总加工机器偏差值作为生产稳定性指标， Wang和Choi例则采用基于聚类分解结合最短加 生成插单后所有线上未完成工件的调度计划 工时间规则的方法对该问题进行求解，Gao等o 基于所研究的问题，本文做出如下假设： 采用人工蜂群算法解决了新工件随机到达的作业 (1)各类工件按照最优批量进行分批生产：(2)不 车间重调度问题.已有的文献对ROIRP研究甚 同批次工件的工序之间没有先后约束；(3)同批 少，其中，Chiu和Shih叮研究了两台设备组成的流 工件的加工不能中断：(4)各阶段缓冲区容量无 水线下的ROIRP,Wang等a考虑的则是单设备系 限大 统下的ROIRP,Pei等1用带初始种群约束与最长 1.2模型建立 公共序列交叉算子的遗传算法(initial population 为便于建模，设置模型参数如下所示：
and the effectiveness of the proposed method. The proposed model and method may assist other enterprises that apply make-to-order production mode to reduce the impact of rush order insertion and realize a win-win mechanism between enterprises and customers. KEY WORDS hybrid flow shop；rush order insertion rescheduling；multi-objective；multi-constraint；NSGA-III algorithm 混合流水车间（hybrid flow shop, HFS）调度问 题广泛存在于流程工业和制造业中，Gupta[1] 已经 证明了两阶段中一个阶段有两台加工机器 的 HFS 调度问题是非确定性多项式（non-deterministic polynomial, NP）难度问题. 而紧急订单又是面向订 单生产型企业普遍存在的问题，它在为企业带来 额外利润的同时，也对企业的生产系统稳定性造 成破坏，对企业的快速应变能力来说，是一个巨大 的挑战. 因此，对 HFS 下的紧急订单插单重调度问 题（rush order insertion rescheduling problem, ROIRP） 的研究十分必要且意义重大. 实际生产车间往往存在多种生产约束，如提 高生产效率的分批生产，Meng 等[2] 采用改进鸟群 迁移优化算法对批量流调度问题进行求解. 刀具 换装时间大多存在于多产品混合生产的车间中， Rossi[3] 对某制造系统的刀具换装时间约束进行研 究，Yue 等[4] 则同时考虑带批量与刀具换装时间约 束的多并行机调度问题. 此外，在流程工业和制造 业中，运输时间往往不可忽视，如 Qin 等[5] 便研究 了带交货期时间窗和机器运输时间约束的铸造业 生产调度问题. 除了客观存在的生产约束外，由于 生产系统的不确定性，车间调度还面临着许多动 态干扰，如机器故障、新工件到达、紧急订单插单 等，重调度是应对干扰最重要的举措，Vieira 等[6] 对其做出了综述，认为重调度可由事件或周期驱 动. 动态干扰因素会造成生产系统的混乱，因此 Wu 等[7] 提出新旧调度计划中各工件的开始加工 时间偏差和加工次序偏差两种指标来评价重调度 方案的稳定性. 在对重调度问题干扰因素的研究 文献中，以机器故障和新工件到达因素居多，如 Cui 和 Gu[8] 提出一种离散群搜索优化算法对机器 故障下的混合流水车间重调度问题进行求解，而 Wang 和 Choi[9] 则采用基于聚类分解结合最短加 工时间规则的方法对该问题进行求解，Gao 等[10] 采用人工蜂群算法解决了新工件随机到达的作业 车间重调度问题. 已有的文献对 ROIRP 研究甚 少，其中，Chiu 和 Shih[11] 研究了两台设备组成的流 水线下的 ROIRP，Wang 等[12] 考虑的则是单设备系 统下的 ROIRP，Pei 等[13] 用带初始种群约束与最长 公共序列交叉算子的遗传算法（ initial population constraint and longest common sequence crossing GA， IPC-LCSC GA）对多阶段流水车间下的 ROIRP 进 行研究. 综上，已有的对 ROIRP 的研究文献中，场景大 多限定在流水线或单机设备，以 HFS 为研究原型 的甚少，且大多目标单一，运输时间、刀具换装时 间等约束均被忽略，与实际生产情况存在较大差 异，因此本文对多约束 HFS 下的多目标 ROIRP 进 行研究，综合考虑工件批量、刀具换装时间和运输 能力约束，建立紧急订单插单重调度模型，依次用 NSGA-II 算法和 NSGA-III 算法对其进行求解，并 将某实际船用管类零件生产企业作为实验对象， 验证了所建模型与所提方法的实用性与有效性. 1 紧急订单插单重调度问题建模 1.1 模型描述及假设 Stage = {1,2,··· , j,··· ,s} M= {1,2,··· ,m,··· , Mall} V= {1,2,··· , v,··· ,Vall} mj vj Mj O= {O1,O2,··· ,Oi ,··· ,On} Oi Xi= {1,2,··· , x,··· , xi} Oi,x Oi Oi j ,x Oi,x Oi j ,x Mi j Oi,x Mi j ⊆ Mj t = 0 t = T n ′ O ′= {O1 ′ ,O2 ′ ,··· ,On ′ ′ } 本文所研究的问题可描述为：某混合流水车 间的生产阶段集为 ，加工设 备 集 为 ， 运 送 设 备 集 为 . 任一阶段 j 均包含 台异构 并行机和 台搬运设备， 为阶段 j 的加工机器 集. 初始订单 包含 n 种工 件 ， 工 件 的 批 次 集 为 ， 用 表示工件 的第 x 批工件， 表示工件 在 阶段 j 加工，即工序 ， 表示工件 在阶段 j 的可选加工机器集， . 在 时刻，综合 考虑客户满意度和企业资源消耗量，以最小化订 单完工时间和最小化总运输时间为双目标，对初 始订单进行优化调度；在 时刻，包含 种工件 的紧急订单 到达并需插入到 当前系统中进行合并生产，增加插单前后调度方 案中的总加工机器偏差值作为生产稳定性指标， 生成插单后所有线上未完成工件的调度计划. 基于所研究的问题 ，本文做出如下假设 ： （1）各类工件按照最优批量进行分批生产；（2）不 同批次工件的工序之间没有先后约束；（3）同批 工件的加工不能中断；（4）各阶段缓冲区容量无 限大. 1.2 模型建立 为便于建模，设置模型参数如下所示： 何小妹等： 多目标多约束混合流水车间插单重调度问题研究 · 1451 ·
1452 工程科学学报，第41卷，第11期 Pijm: 单个工件O,在阶段的机器m上的加工时间： Pijm. 整批工件O:x在阶段的机器m上的加工时间： Sijmx: 工序O在机器m上的开始加工时间： Fijm.i 工序O在机器m上的完工时间： Setijmx 工序O在机器m上的刀具换装时间： Setm: 机器m的刀具换装时间： MTm 机器m1与2间的运输时间，m∈Mj,∈M1: STijj+Dxv: 运送设备将整批工件O:,从阶段运到阶段()+1)的开始运输时间： FTij+D)xv: 运送设备将整批工件O:x从阶段运到阶段()+1)的运输完成时间： J0ab→0rjm: 0-1决策变量，若为1，则在阶段的机器m上，工件Oab为工件O:x的上一批加工工件： KO.j-Oi.jj+Iw 0-1决策变量，若为1，则运送设备v在阶段与阶段+1)间，工件O为工件0的上一批运送工件： Xijm.xi 0-1决策变量，若为1，则整批工件0.在阶段的机器m上加工： TiRj+D).tv: 0-1决策变量，若为1，则工序0由运输设备从阶段运到阶段(+1)： Yajmb-ijm. 0-l决策变量，若为1，则Jo一0m为1，且0ab与0ix为不同种类工件，即a≠i。 本文所研究的ROIRP包括对插单前静态初始 FTijj+D).t.v STij(j+D).xy+MT(m2,m),When Xijmz 订单优化调度和插单后所有未完成工件的优化调 Xi+lm=1,Tixj+Dy=1.Ko-0uty=1. 度两个子问题，因此模型也包括两个部分.先对静态 Hi,ixeX,m2∈Mij,m∈MU+,v∈V (10) 初始订单调度子问题进行建模，目标函数如下所示： min fi max(Fiim.x (1) 2Ti=ueiSTwieTh minh=月之芝1l× i,i,v,x∈X: ie1j=1=1=1 (2) (11) (FTijG+D.xv-STij+Dx) 约束函数为： 立7nw=小（2Y i,ix∈X ∑SumO)=sumo)Yi (3) Pimx=Pim×Sum(0ix)i,方 之xm=lie5a,Fuh me。 (4) x∈{L,2,…,Xh,m∈M (13) Setijm.x=Yajm.b-ijm.xX Setm,When Xijm.x,Xajm.b =1, Yi,a,j,x∈X,b∈Xa,m∈Mij and Maj EXm-小rel,2,Xij (5) (14) Fimx=SetimPimx,whenXimx1.(6) Pim,Pimx≥0，x∈(1,2，…，Xh。m∈M,i,j（15) Vi,j,xE Xi,mE Mij Sim.x≥0，x∈(l,2,…,Xh,meM,ij（16) Si(j+D)m.x=max(Fa(j+D)m.b.FTixj+D).v),when Xi(j+I)m, Xa(j+lym.b.Tijj+D)-x.v.JOab-Oix.(j+D)m=1, 式(3)中，Sum(O)为工件O,的总数量，Sum(O.x) Vi,a,j.xEXi,bE Xa,mE Mij,vEV 为整批工件O.x的数量：对于式(9)和式(10)，运送 (7) 设备v依次运输工件O。,f和O.x,O,r被运到阶段 FTij(j+D).ty+Seti(j+D)m.t+Pi(j+D)ma<Fi(j+D)m.x when Xi(j+D)m.x Tij(j+D).xy =1 j+1)的机器m上进行加工，O.x从阶段j的机器 (8) i,x∈X,m∈MU+,v∈V m2被运到阶段(j+1)的机器m上进行加工. 再对紧急订单插单调度子问题进行建模.由 STijj+D).v=FTejj+D).f.v+MT(m1,m2).When Xijm2. Xi(j+D)mxXc(j+D)m.f=1,Tij(j+D).x.v,Tejj+D).f.v=1, 于紧急订单插单调度模型的前两个目标和所有生 Ko-Out=1.Vi.e,j.x feX 产约束与静态初始订单调度模型相同，只需将求 m∈Mtl),m2eM,m∈M+I,v∈V 解对象变更为紧急订单所有工件和初始订单所有 (9) 未完成工件的合集，因此不再进行展示.该模型的
本文所研究的 ROIRP 包括对插单前静态初始 订单优化调度和插单后所有未完成工件的优化调 度两个子问题，因此模型也包括两个部分. 先对静态 初始订单调度子问题进行建模，目标函数如下所示： min f1 = max{Fi jm,x} （1） min f2 = ∑n i=1 S ∑−1 j=1 ∑ Xi x=1 ∑ Vall v=1 Ti j(j+1) ,x,v × (FTi j(j+1) ,x,v −STi j(j+1) ,x,v ) （2） 约束函数为： ∑ Xi x=1 Sum(Oi,x ) = Sum(Oi) ∀i （3） Pi jm,x =Pi jm ×Sum(Oi,x ) ∀i, j, x ∈ {1,2,··· ,Xi}, m ∈ Mi j （4） Seti jm,x =Ya jm,b−i jm,x ×Setm,when Xi jm,x,Xa jm,b = 1, ∀i,a, j, x ∈ Xi , b ∈ Xa, m ∈ Mi j and Ma j （5） Fi jm,x =Seti jm,x +S i jm,x + Pi jm,x, when Xi jm,x = 1, ∀i, j, x ∈ Xi , m ∈ Mi j （6） S i(j+1)m,x =max{Fa(j+1)m,b,FTi j(j+1),x,v},when Xi(j+1)m,x, Xa(j+1)m,b,Ti j(j+1),x,v, JOa,b→Oi,x,(j+1),m = 1, ∀i,a, j, x ∈ Xi , b ∈ Xa, m ∈ Mi j, v ∈ V （7） FTi j(j+1),x,v +Seti(j+1)m,x + Pi(j+1)m,x ⩽ Fi(j+1)m,x, when Xi(j+1)m,x,Ti j(j+1),x,v = 1 ∀i, j, x ∈ Xi , m ∈ Mi(j+1), v ∈ V （8） STi j(j+1),x,v = FTe j(j+1), f,v +MT(m1,m2),when Xi jm2,x, Xi(j+1)m,x ,Xe(j+1)m1, f = 1, Ti j(j+1),x,v,Te j(j+1), f,v=1, KOe, f →Oi,x , j(j+1),v = 1,∀i, e, j, x ∈ Xi , f ∈ Xe, m1 ∈ Me(j+1), m2 ∈ Mi j, m ∈ Mi(j+1), v ∈ V （9） FTi j(j+1),x,v = STi j(j+1),x,v +MT(m2,m),when Xi jm2,x, Xi(j+1)m,x = 1, Ti j(j+1),x,v = 1,KOe, f →Oi,x , j(j+1),v = 1, ∀i, j, x ∈ Xi , m2 ∈ Mi j,m ∈ Mi(j+1), v ∈ V （10） ∑n i=1 ∑ Xi x=1 Ti j(j+1),x,v = 1,t ∈ [STi j(j+1),x,v,FTi j(j+1),x,v], ∀i, j, v,x ∈ Xi （11） ∑ V v=1 Ti j(j+1),x,v = 1, t ∈ [STi j(j+1),x,v,FTi j(j+1),x,v], ∀i, j, x ∈ Xi （12） ∑n i=1 ∑ Xi x=1 Xi jm,x = 1, t ∈ [S i jm,x,Fi jm,x], m ∈ Mj , ∀ j （13） ∑ m∈Mj Xi jm,x = 1, t ∈ [S i jm,x,Fi jm,x], x ∈ {1,2,··· ,Xi}, ∀i, j （14） Pi jm,Pi jm,x ⩾ 0, x ∈ {1,2,··· ,Xi}, m ∈ Mi j , ∀i, j （15） S i jm,x ⩾ 0, x ∈ {1,2,··· ,Xi}, m ∈ Mi j , ∀i, j （16） Sum(Oi) Oi Sum(Oi,x ) Oi,x Oe, f Oi,x Oe, f (j+1) m1 Oi,x m2 (j+1) 式（3）中， 为工件 的总数量， 为整批工件 的数量；对于式（9）和式（10），运送 设备 v 依次运输工件 和 ， 被运到阶段 的机器 上进行加工， 从阶段 j 的机器 被运到阶段 的机器 m 上进行加工. 再对紧急订单插单调度子问题进行建模. 由 于紧急订单插单调度模型的前两个目标和所有生 产约束与静态初始订单调度模型相同，只需将求 解对象变更为紧急订单所有工件和初始订单所有 未完成工件的合集，因此不再进行展示. 该模型的 Pi jm： 单个工件 Oi在阶段j的机器m上的加工时间； Pi jm,x： 整批工件 Oi,x在阶段j的机器m上的加工时间； S i jm,x： Oi j 工序 ,x在机器m上的开始加工时间； Fi jm,x： Oi j 工序 ,x在机器m上的完工时间； Seti jm,x： Oi j 工序 ,x在机器m上的刀具换装时间； Setm： 机器m的刀具换装时间； MTm1,m2 ： m1 m2 m1 ∈ Mj ,m2 ∈ M( j+1 机器 与 间的运输时间， )； STi j(j+1),x,v： Oi,x 运送设备v将整批工件 从阶段j运到阶段 (j+1) 的开始运输时间； FTi j(j+1),x,v： Oi,x 运送设备v将整批工件 从阶段j运到阶段 (j+1) 的运输完成时间； JOa,b→Oi,x , jm： 0-1决策变量，若为1，则在阶段 Oa,b Oi,x j的机器m上，工件 为工件 的上一批加工工件； KOe, f →Oi,x , j(j+1),v ： 0-1决策变量，若为1，则运送设备v在阶段 (j+1) Oe, f Oi,x j与阶段 间，工件 为工件 的上一批运送工件； Xi jm,x： 0-1决策变量，若为1，则整批工件 Oi,x在阶段j的机器m上加工； Ti j(j+1),x,v： Oi j ,x 0-1决策变量，若为1，则工序 由运输设备v从阶段j运到阶段 (j+1)； Ya jm,b−i jm,x： JOa,b→Oi,x 0-1决策变量，若为1，则 , jm 为1，且 Oa,b与 Oi,x为不同种类工件，，即a , i。 · 1452 · 工程科学学报，第 41 卷，第 11 期
何小妹等：多目标多约束混合流水车间插单重调度问题研究 1453 第三个优化目标为最小化总机器偏差值，其函数 行求解.此外，由于重排插单方式既能提高生产资 如下所示： 源利用率，又能维护生产系统的稳定性，因此本 文选用重排插单方式对紧急订单进行插单操作， min f3= mintmaxtm(17) 再结合基于事件驱动的重调度方式，将紧急订单 n≤N≤n+m' 到达作为重调度的驱动事件，以紧急订单到达时 刻作为重调度的起始点 其中，mold和mncw依次为初始调度方案和重调度方 NSGA-IⅡ算法与NSGA-I算法框架相同，不 案中工件O在阶段j的加工机器编号 同之处在于精英选择策略中对最后被选层个体的 上述ROIRP模型中，式(1)、式(2)和式(17) 选择机制上，NSGA-Ⅱ算法采用拥挤度距离选择个 为目标函数；式(3)和式(4)为分批加工时间约束； 体，而NSGA-I算法则是基于参考点对个体进行 式(5)为刀具转换时间约束：式(6)和式(7)为加工 选择，实施流程可参见文献[14].本文采用种群随 时间约束：式(8)为混合流水车间工序先后约束； 机初始化方式，终止准则为达到预定停止时间，编 式(9)和式(10)为考虑往返运输的运送设备运输 码与解码、交叉和变异两大部分的设计如下所示： 时间约束：式(11)和式(12)为运输能力约束，即同 (1)基于工件、机器的双层编码与解码， 批工件同一时刻只能由一台运输工具进行运输， 为同时描述工件的加工顺序与加工机器两种 同一台运输工具同一时刻只能运输同一批工件； 信息，本文采用双层编码结构，第一层为工件码， 式(13)和式(14)为机器能力约束，即同一批工件 工件号出现的次数表示其工序数：第二层为机器 同一时刻只能被一台机器加工，同一台机器同一 码，每一个机器码为该工件可选加工机器集的索 时刻只能加工同一批工件；式(15)表示所有工序 引号.每一个双层编码对应一个调度方案，表示各 的加工时间为正数，式(16)表示所有工件在0时 工件各道工序所选择的加工机器.如图1(a)所示， 刻均可被加工 若某条染色体编码为[2,2,1,3,1,2,3,3,1,1,1,2， 2紧急订单插单重调度问题求解 2,2,1,2,2,31,则其工件码为[2,2,1,3,1,2,3,3， 1],机器码为[1,1,2,2,2,1,2,2,3引，假设各工序加 NSGA-IⅡ算法是解决多目标优化问题的经典 工的均为第一批次工件，则工件码表示工序 的算法之一，但Deb和Jain!指出，NSGA-Ⅱ算法 {021.1,022,1,011,1,031.1,012,1,0231,0321,033,1,013.1, 在解决双目标优化问题时表现较好，但在解决三 根据各工序的可选加工机器集（见图1(a)可确定 个及以上目标优化问题时，其所得解在非支配层 该机器码所对应的加工机器编号依次为1,4,2,2， 上分布不均，容易导致算法陷入局部最优，收敛性 5,7,6,9,9} 与多样性不好，因此Deb和Jain在NSGA-lI算法 (2)基于POX的交叉和基于启发式规则的变 的基础上，提出了种群分布性表现更为良好的 异操作 NSGA-算法，以解决Many-objective问题.依据 由于优先操作交叉(precedence operation Deb和Jain的研究成果，本文针对所建立的双目标 crossover,.POX)方式产生的子代都是可行的，不会 初始订单优化调度模型与三目标插单优化调度模 违背生产工艺约束，因此本文采用POX方式对工 型分别选用NSGA-Ⅱ算法和NSGA-II算法对其进 件码和机器码进行交叉.图1(b)给出了POX交叉 O2LO21O1OO210O210O 父代染色体1 223233112221223 工件码221312331 机器码112221223 代染色体22323322222B 各工序可 4喝M4MM码MMM 选加工机MM场MM 器集 M.MMM 父代染色体2 2212333 213311122 工件码 机器码 包 (b) 图1双层编码与解码()和个体交叉(b)示意图 Fig.1 Double encoding and decoding mechanism(a)and example of crossover operator(b)
第三个优化目标为最小化总机器偏差值，其函数 如下所示： min f3 = ∑ N i=1 ∑s j=1 ∑ Xi x=1 min{max{|mold−mnew|,0},1}, n ⩽ N ⩽ n+n ′ （17） mold mnew Oi,x 其中， 和 依次为初始调度方案和重调度方 案中工件 在阶段 j 的加工机器编号. 上述 ROIRP 模型中，式（1）、式（2）和式（17） 为目标函数；式（3）和式（4）为分批加工时间约束； 式（5）为刀具转换时间约束；式（6）和式（7）为加工 时间约束；式（8）为混合流水车间工序先后约束； 式（9）和式（10）为考虑往返运输的运送设备运输 时间约束；式（11）和式（12）为运输能力约束，即同 批工件同一时刻只能由一台运输工具进行运输， 同一台运输工具同一时刻只能运输同一批工件； 式（13）和式（14）为机器能力约束，即同一批工件 同一时刻只能被一台机器加工，同一台机器同一 时刻只能加工同一批工件；式（15）表示所有工序 的加工时间为正数，式（16）表示所有工件在 0 时 刻均可被加工. 2 紧急订单插单重调度问题求解 NSGA-II 算法是解决多目标优化问题的经典 的算法之一，但 Deb 和 Jain[14] 指出，NSGA-II 算法 在解决双目标优化问题时表现较好，但在解决三 个及以上目标优化问题时，其所得解在非支配层 上分布不均，容易导致算法陷入局部最优，收敛性 与多样性不好，因此 Deb 和 Jain 在 NSGA-II 算法 的基础上 ，提出了种群分布性表现更为良好的 NSGA-III 算法，以解决 Many-objective 问题. 依据 Deb 和 Jain 的研究成果，本文针对所建立的双目标 初始订单优化调度模型与三目标插单优化调度模 型分别选用 NSGA-II 算法和 NSGA-III 算法对其进 行求解. 此外，由于重排插单方式既能提高生产资 源利用率，又能维护生产系统的稳定性[15] ，因此本 文选用重排插单方式对紧急订单进行插单操作， 再结合基于事件驱动的重调度方式，将紧急订单 到达作为重调度的驱动事件，以紧急订单到达时 刻作为重调度的起始点. NSGA-II 算法与 NSGA-III 算法框架相同，不 同之处在于精英选择策略中对最后被选层个体的 选择机制上，NSGA-II 算法采用拥挤度距离选择个 体，而 NSGA-III 算法则是基于参考点对个体进行 选择，实施流程可参见文献 [14]. 本文采用种群随 机初始化方式，终止准则为达到预定停止时间，编 码与解码、交叉和变异两大部分的设计如下所示： （1）基于工件、机器的双层编码与解码. {O21,1,O22,1,O11,1,O31,1, O12,1, O23,1,O32,1,O33,1,O13,1} 为同时描述工件的加工顺序与加工机器两种 信息，本文采用双层编码结构，第一层为工件码， 工件号出现的次数表示其工序数；第二层为机器 码，每一个机器码为该工件可选加工机器集的索 引号. 每一个双层编码对应一个调度方案，表示各 工件各道工序所选择的加工机器. 如图 1（a）所示， 若某条染色体编码为 [ 2, 2, 1, 3, 1, 2, 3, 3, 1, 1, 1, 2, 2, 2, 1, 2, 2, 3]，则其工件码为 [ 2, 2, 1, 3, 1, 2, 3, 3, 1]，机器码为 [1, 1, 2, 2, 2, 1, 2, 2, 3]，假设各工序加 工的均为第一批次工件 ，则工件码表示工序 ， 根据各工序的可选加工机器集（见图 1（a））可确定 该机器码所对应的加工机器编号依次为{1, 4, 2, 2, 5, 7, 6, 9, 9}. （2）基于 POX 的交叉和基于启发式规则的变 异操作. 由 于 优 先 操 作 交 叉 （ precedence operation crossover, POX）方式产生的子代都是可行的，不会 违背生产工艺约束，因此本文采用 POX 方式对工 件码和机器码进行交叉. 图 1（b）给出了 POX 交叉 工件码 2 机器码 各工序可 选加工机 器集 2 1 3 1 2 3 3 1 父代染色体1 2 2 1 3 1 2 3 3 1 子代染色体 2 2 1 3 1 2 3 3 1 父代染色体2 1 工件码 机器码 2 2 1 2 3 (a) (b) 3 1 3 O21,1O22,1O11,1O31,1O12,1O23,1O32,1O33,1O13,1 M1 M3 M1 M5 M6 M1 M2 M3 M1 M2 M3 M4 M5 M6 M7 M8 M4 M6 M8 M9 M7 M8 M9 1 1 2 2 2 1 2 2 3 1 1 2 2 2 1 2 2 3 1 3 2 2 2 1 2 2 3 2 1 3 3 1 1 1 2 2 图 1 双层编码与解码（a）和个体交叉（b）示意图 Fig.1 Double encoding and decoding mechanism (a) and example of crossover operator (b) 何小妹等： 多目标多约束混合流水车间插单重调度问题研究 · 1453 ·
·1454 工程科学学报，第41卷，第11期 的一个例子.先对工件码进行交叉，设初始工件集 对象对多约束HFS下的多目标ROIRP进行研究 为O={1,2,3,随机分成两组子工件集Oe={1,3引和 该企业的生产车间可被抽象为HFS,车间布局如 0={2,其中0来自父代染色体1,0来自父代染色 图2所示，机器名括号内数值为机器加工时间，机 体2，则子代染色体由父代染色体1的0工件集和 器间连线上数值为机器间运输时间，单位均为分 父代染色体2的O工件集两部分组成.完成工件码 钟.车间共生产8类零件，各零件的最优生产批量 交叉后，相应的机器码也进行同样的交叉操作. 和工艺路线如表1表示，弯管工序所有加工机器 变异操作主要针对机器码，随机选取多个变 均存在30min的刀具换装时间 异点，由于每条染色体都具有三个适应度值（初始 为了验证本文所建模型与求解方法的实用性 订单调度为两个)一总完工时间、总运输时间 和有效性，本节设置三组实验.实验前，为两种算 和总机器偏差值，因此各变异点均有三个变异方 法设置相同的参数—种群数量为500，交叉概率 向，若该条染色体中效果最差的适应度值为总完 为0.8，变异概率为0.2，停止准则为t=500s.用 工时间，则将机器号变异为该工件在该阶段加工 Matlab20l2进行编程，算法的运行环境为Inter(R) 时间最短的机器，同理，若总运输时间效果最差， Core(TM)i5-7300U CPU 2.60 GHz 2.71 GHz, 则变异为与上阶段机器运输时间最短的机器，若 8G运行内存，Window764位操作系统，每组实验 总机器偏差值效果最差，则变异为与初始调度方 各进行l0次.算法的性能通过Govindan等t提 案相同的加工机器号，该变异方式能够加速收敛 出的三种指标进行评估一衡量算法收敛性的平 速度，提高算法的运行效率 均理想距离(mean ideal distance,MID)、衡量解的 3实例验证 多样性的非支配解的标准偏差(spread of non- dominance solution,.SNS)和衡量算法支配其它算法 本文以某实际船用管类零件生产企业为实验 解的能力的支配占比(percent of domination,.POD) 区域1 天车1 天车3 天车5 天车7 天车9区域3 切制1(2) 弯管6(10) *弯管710】 点焊16(15) 全焊18(30) 打磨20(2.25) 2(2) 弯管14(0) 切3(1.5) 弯管86 弯管96]K好 泵压22 弯管106)丝 切制41.5) 弯管11(2) 点焊17(15) 全焊1930の+打磨21(2.25) 弯管12(2) 28 弯管13(2) 切脚501.5) 弯管15(0) 区域2 天车2 车4 天车6 天车8 厌车1四区域4 图2生产车间布局图 Fig.2 Layout of the shop 表1 零件最优生产批量和工艺路线表 Table 1 Optimal lot sizing and routing of each job 零件类型 最优生产批量 切割 弯管 点焊 全焊 打磨 泵压 16 [1,2] [14] [16,17刀 [18.19] [20,21] [22 2 40 [34, [15] [16,17刀 [18.19 [20,21 [22] 3 16 1,2] [6,刀 [16,17 [18.19 [20,21] [22 64 [3.4,5 8 [16,17刀 [18,19月 [20,21] [22] 32 [3,4, [9 [16,17 18,19y [20,21] [22 6 ￥ [3,4,5] [10 [16,17刀 18,19y [20,21] [2] 1 50 [3.4,5习 [11,12] [16,17刀 18,19y [20,21] [22] 8 100 34,5] [13] [16,17刀 [18.19] [20,21] [22
O= {1,2,3} Oe= {1,3} Of= {2} Oe Of Oe Of 的一个例子. 先对工件码进行交叉，设初始工件集 为 ，随机分成两组子工件集 和 ，其中 来自父代染色体 1， 来自父代染色 体 2，则子代染色体由父代染色体 1 的 工件集和 父代染色体 2 的 工件集两部分组成. 完成工件码 交叉后，相应的机器码也进行同样的交叉操作. 变异操作主要针对机器码，随机选取多个变 异点，由于每条染色体都具有三个适应度值（初始 订单调度为两个）−总完工时间、总运输时间 和总机器偏差值，因此各变异点均有三个变异方 向，若该条染色体中效果最差的适应度值为总完 工时间，则将机器号变异为该工件在该阶段加工 时间最短的机器，同理，若总运输时间效果最差， 则变异为与上阶段机器运输时间最短的机器，若 总机器偏差值效果最差，则变异为与初始调度方 案相同的加工机器号，该变异方式能够加速收敛 速度，提高算法的运行效率. 3 实例验证 本文以某实际船用管类零件生产企业为实验 对象对多约束 HFS 下的多目标 ROIRP 进行研究. 该企业的生产车间可被抽象为 HFS，车间布局如 图 2 所示，机器名括号内数值为机器加工时间，机 器间连线上数值为机器间运输时间，单位均为分 钟. 车间共生产 8 类零件，各零件的最优生产批量 和工艺路线如表 1 表示，弯管工序所有加工机器 均存在 30 min 的刀具换装时间. t = 500 为了验证本文所建模型与求解方法的实用性 和有效性，本节设置三组实验. 实验前，为两种算 法设置相同的参数−种群数量为 500，交叉概率 为 0.8，变异概率为 0.2，停止准则为 s. 用 Matlab2012 进行编程，算法的运行环境为 Inter(R) Core(TM)i5-7300U CPU @ 2.60 GHz 2.71 GHz， 8G 运行内存，Window7 64 位操作系统，每组实验 各进行 10 次. 算法的性能通过 Govindan 等[16] 提 出的三种指标进行评估−衡量算法收敛性的平 均理想距离（mean ideal distance, MID）、衡量解的 多样性的非支配解的标准偏差 （ spread of nondominance solution, SNS）和衡量算法支配其它算法 解的能力的支配占比（percent of domination, POD）. 表 1 零件最优生产批量和工艺路线表 Table 1 Optimal lot sizing and routing of each job 零件类型 最优生产批量 切割 弯管 点焊 全焊 打磨 泵压 1 16 [1, 2] [14] [16, 17] [18, 19] [20, 21] [22] 2 40 [3, 4, 5] [15] [16, 17] [18, 19] [20, 21] [22] 3 16 [1, 2] [6, 7] [16, 17] [18, 19] [20, 21] [22] 4 64 [3, 4, 5] [8] [16, 17] [18, 19] [20, 21] [22] 5 32 [3, 4, 5] [9] [16, 17] [18, 19] [20, 21] [22] 6 32 [3, 4, 5] [10] [16, 17] [18, 19] [20, 21] [22] 7 50 [3, 4, 5] [11, 12] [16, 17] [18, 19] [20, 21] [22] 8 100 [3, 4, 5] [13] [16, 17] [18, 19] [20, 21] [22] 切割1(2) 切割2(2) 切割3(1.5) 切割4(1.5) 切割5(1.5) 区域2 区域1 区域4 区域3 弯管6(10) 4 21 弯管7(10) 8 26 弯管14(0) 14 9 13 14 0 17 26 弯管8(6) 弯管9(6) 弯管10(6) 弯管11(2) 弯管12(2) 弯管13(2) 弯管15(0) 20 21 16 28 3 5 3 16 4 14 18 7 4 9 点焊16(15) 7 天车3 天车4 天车5 天车6 天车1 天车2 天车7 天车8 天车9 天车10 全焊18(30) 4 打磨20(2.25) 点焊17(15) 全焊19(30) 打磨21(2.25) 泵压22 9 19 19 9 11 8 10 4 2 19 15 7 13 17 8 20 6 0 0 23 20 24 22 28 26 0 图 2 生产车间布局图 Fig.2 Layout of the shop · 1454 · 工程科学学报，第 41 卷，第 11 期