多目标多约束混合流水车间插单重调度问题研究

工程科学学报.第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 non￾dominance 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 期

何小妹等：多目标多约束混合流水车间插单重调度问题研究 1455· 各指标的计算公式可参见文献16]，本文不再进行 表2紧急订单插单信息表 说明. Table 2 Information of the rush order insertion case 实验1：NSGA-IⅡ算法和NSGA-II算法求解双 初始订单(2018/04/188：00) 紧急订单(2018/04/1811：00) 目标初始订单调度模型效果对比. 零件类型 加工数量 零件类型 加工数量 以该企业的一组实际插单案例（信息见表2） 1 16 1 32 作为实验对象，分别用NSGA-Ⅱ算法和NSGA- 3 72 2 0 l算法对模型进行求解.两种算法所得的Pareto 0 3 0 最优解集如图3(a)和图3(b)所示，其中，NSGA- 60 64 Ⅱ算法可得到25个最优解，即25种最优调度方 0 5 0 案，而NSGA-I算法仅得I5种最优调度方案，就 6 0 6 0 解的个数来说，NSGA-I算法更优.对两种算法的 7 0 7 100 MID,SNS和POD三种评价指标值进行计算，结果 90 8 80 如表3所示 600 600 (a) (b) 580 580 560 560 540 540 520 520 500 500 480 480 460 460 + 44 500550 600650700750800850 900 4900550600650700750800850900 订单完工时间/min 订单完T时间/min 国3两种算法所得初始订单优化调度的Pareto最优解集.(a)NSGA-Ⅱ算法：(b)NSGA-IⅢ算法 Fig.3 Pareto optimal solutions of the initial order:(a)NSGA-II algorithm;(b)NSGA-III algorithm 表3NSGA和NSGA-Ⅲ算法对初始订单调度的评价指标对 图4(b)所示，其中，NSGA-II和NSGA-II算法各得 比表 到10种和21种最优调度方案，NSGA-II算法更 Table3 Comparison of three indications obtained by NSGA-II 优.两种算法的MID,SNS和POD三种评价指标 and NSGA-III that applied to solve initial order scheduling problem 值如表4所示 算法 MID SNS POD 由表4可得，NSGA-II算法的MID,SNS和 NSGA-IⅡ 912.89 24790.13 0.63 POD的值都要优于NSGA-II算法，即NSGA-I算 NSGA-Ⅲ 1239.21 24976.66 0.37 法在算法的收敛性、解的多样性与解的支配占比 由表3可得，NSGA-II算法的MID值和POD 三方面的表现均要比NSGA-Ⅱ算法好，因此，在解 值均要优于NSGA-II算法，即NSGA-Ⅱ算法的收 决三目标优化问题时，NSGA-II算法的效果比 敛性与解的支配占比更好，虽然NSGA-I算法的 NSGA-II算法的效果好 实验3：企业实际紧急订单插单调度结果与优 SNS值较优，但是二者的值相差不大，即解的多样 化后紧急订单插单调度结果对比. 性相近，因此，在求解双目标优化问题时，总的来 随机选取该企业实际生产中的10组紧急订单 说，NSGA-Ⅱ算法的性能要优于NSGA-II算法. 插单案例，依次用NSGA-IⅡ算法对双目标初始订 实验2：NSGA-Ⅱ算法和NSGA-II算法求解三 单调度模型进行求解，用NSGA-II算法对三目标 目标插单调度模型效果对比 插单调度模型进行求解，可得企业实际初始订单 以实验1的案例作为实验对象，分别用NSGA-IⅡ 调度与NSGA-Ⅱ算法优化后初始订单调度结果的 算法和NSGA-II算法对插单调度模型进行求解. 双目标对比如图5所示，企业实际插单调度与 两种算法所得的Pareto最优解集分别如图4(a)和 NSGA-Ⅲ算法优化后插单调度结果的三目标对比

各指标的计算公式可参见文献 [16]，本文不再进行 说明. 实验 1：NSGA-II 算法和 NSGA-III 算法求解双 目标初始订单调度模型效果对比. 以该企业的一组实际插单案例（信息见表 2） 作为实验对象 ，分别 用 NSGA-II 算 法 和 NSGA￾III 算法对模型进行求解. 两种算法所得的 Pareto 最优解集如图 3（a）和图 3（b）所示，其中，NSGA￾II 算法可得到 25 个最优解，即 25 种最优调度方 案，而 NSGA-III 算法仅得 15 种最优调度方案，就 解的个数来说，NSGA-II 算法更优. 对两种算法的 MID，SNS 和 POD 三种评价指标值进行计算，结果 如表 3 所示. 由表 3 可得，NSGA-II 算法的 MID 值和 POD 值均要优于 NSGA-III 算法，即 NSGA-II 算法的收 敛性与解的支配占比更好，虽然 NSGA-III 算法的 SNS 值较优，但是二者的值相差不大，即解的多样 性相近，因此，在求解双目标优化问题时，总的来 说，NSGA-II 算法的性能要优于 NSGA-III 算法. 实验 2：NSGA-II 算法和 NSGA-III 算法求解三 目标插单调度模型效果对比. 以实验 1 的案例作为实验对象，分别用 NSGA-II 算法和 NSGA-III 算法对插单调度模型进行求解. 两种算法所得的 Pareto 最优解集分别如图 4（a）和 图 4（b）所示，其中，NSGA-II 和 NSGA-III 算法各得 到 10 种和 21 种最优调度方案，NSGA-III 算法更 优. 两种算法的 MID，SNS 和 POD 三种评价指标 值如表 4 所示. 由 表 4 可得 ， NSGA-III 算 法 的 MID， SNS 和 POD 的值都要优于 NSGA-II 算法，即 NSGA-III 算 法在算法的收敛性、解的多样性与解的支配占比 三方面的表现均要比 NSGA-II 算法好，因此，在解 决三目标优化问题时 ， NSGA-III 算法的效果 比 NSGA-II 算法的效果好. 实验 3：企业实际紧急订单插单调度结果与优 化后紧急订单插单调度结果对比. 随机选取该企业实际生产中的 10 组紧急订单 插单案例，依次用 NSGA-II 算法对双目标初始订 单调度模型进行求解，用 NSGA-III 算法对三目标 插单调度模型进行求解，可得企业实际初始订单 调度与 NSGA-II 算法优化后初始订单调度结果的 双目标对比如图 5 所示 ，企业实际插单调度与 NSGA-III 算法优化后插单调度结果的三目标对比 表 2 紧急订单插单信息表 Table 2 Information of the rush order insertion case 初始订单（2018/04/18 8:00） 紧急订单（2018/04/18 11:00） 零件类型 加工数量 零件类型 加工数量 1 16 1 32 2 72 2 0 3 0 3 0 4 60 4 64 5 0 5 0 6 30 6 0 7 0 7 100 8 90 8 80 表 3 NSGA-II 和 NSGA-III 算法对初始订单调度的评价指标对 比表 Table 3 Comparison of three indications obtained by NSGA-II and NSGA-III that applied to solve initial order scheduling problem 算法 MID SNS POD NSGA-II 912.89 24790.13 0.63 NSGA-III 1239.21 24976.66 0.37 600 580 560 540 520 500 500 550 600 650 700 750 800 850 900 480 460 440 总运输时间/min 订单完工时间/min (a) 600 580 560 540 520 500 500 550 600 650 700 750 800 850 900 480 460 440 总运输时间/min 订单完工时间/min (b) 图 3 两种算法所得初始订单优化调度的 Pareto 最优解集. （a）NSGA-II 算法; （b）NSGA-III 算法 Fig.3 Pareto optimal solutions of the initial order: (a) NSGA-II algorithm; (b) NSGA-III algorithm 何小妹等： 多目标多约束混合流水车间插单重调度问题研究 · 1455 ·

.1456 工程科学学报.第41卷，第11期 自 (a) 0 (b) 10 8、 8 6 6 4 2 2 1300 13o 1200° 1400 1200 1200 1400 总运输时间min 1100 ,1100 订单完工时间/min 1000 1000 1200 1000600 800 900600 800 订单完工时间min 图4两种算法所得插单后所有工件调度的Pareto最优解集.(a)NSGAⅡ算法；(b)NSGA-III算法 Fig.4 Pareto optimal solutions of all unfinished jobs:(a)NSGA-II algorithm;(b)NSGA-III algorithm 表4NSGA-Ⅱ和NSGA-Ⅲ算法对紧急订单插单重调度问题的 化率为0.36和0.26，均接近三分之一；由图6(a)、 评价指标对比表 图6(b)和图6(c)可得，十组插单案例中，NSGA- Table 4 Comparison of three indications obtained by NSGA-II I算法优化后的插单调度的总完工时间、总运输 and NSGA-III that applied to solve ROIRP 时间和总机器偏差均要优于企业实际的调度结 算法 MID SNS POD 果，平均优化率为0.37,0.43和0.44，均高于三分之一 NSGA-II 1474.68 24904.33 0.32 NSGA-III 上述三组实验中，实验1和实验2表明，在解 548.24 25036.51 0.68 决双目标优化问题时，NSGA-Ⅱ算法的效果要优 如图6所示 于NSGA-II算法，而在解决三目标优化问题时， 由图5(a)和图5(b)可得，在十组案例中， NSGA-II算法的效果更好，验证了本文所提求解 NSGA-Ⅱ算法优化后的初始订单总完工时间与总 方法的科学性；实验3则验证了本文所建模型与 运输时间均要短于企业实际的完成时间，平均优 所提求解方法的实用性和有效性，相对于企业的 ■实际调度■NSGA-I算法优化调度 ■实际调度■NSGA-I算法优化调度 (a) (b) 766 三 103 2 6 7 9 0 3 5 6 7 8 910 初始订单调度案例 初始订单调度案例 图5企业实际调度和NSGA-I算法优化调度结果的双目标对比图.()初始订单，总完工时间；(b)总运输时间 Fig.5 Compare of two objectives obtained by the actual and the optimal initial order scheduling:(a)total completion time;(b)transportation time ■实际调度NSGA-I算法优化调度 ■实际调度■NSGAⅡ算法优化调度 ■实际调度NSGA-I算法优化调度 (a) (b) (c) 6 紧急订单插单案例 紧急订单插单案例 紧急订单插单案例 图6企业实际调度和NSGA-Ⅲl算法优化调度结果的三目标对比图.()插单后总完工时间：(b)总运输时间：(c)总机器偏差 Fig.6 Compare of three objectives obtained by the actual and the optimal rush order insertion rescheduling:(a)total completion time;(b)total transportation time;(c)total machine deviation

如图 6 所示. 由 图 5（ a） 和 图 5（ b） 可得 ，在十组案例中 ， NSGA-II 算法优化后的初始订单总完工时间与总 运输时间均要短于企业实际的完成时间，平均优 化率为 0.36 和 0.26，均接近三分之一；由图 6（a）、 图 6（b）和图 6（c）可得，十组插单案例中，NSGA￾III 算法优化后的插单调度的总完工时间、总运输 时间和总机器偏差均要优于企业实际的调度结 果，平均优化率为 0.37,0.43 和 0.44，均高于三分之一. 上述三组实验中，实验 1 和实验 2 表明，在解 决双目标优化问题时，NSGA-II 算法的效果要优 于 NSGA-III 算法，而在解决三目标优化问题时， NSGA-III 算法的效果更好，验证了本文所提求解 方法的科学性；实验 3 则验证了本文所建模型与 所提求解方法的实用性和有效性，相对于企业的 表 4 NSGA-II 和 NSGA-III 算法对紧急订单插单重调度问题的 评价指标对比表 Table 4 Comparison of three indications obtained by NSGA-II and NSGA-III that applied to solve ROIRP 算法 MID SNS POD NSGA-II 1474.68 24904.33 0.32 NSGA-III 548.24 25036.51 0.68 12 10 8 6 4 2 1300 1200 1100 1000 600 800 1000 1200 1400 0 总机器偏差 总运输时间/min 订单完工时间/min (a) 10 8 6 4 2 1300 1200 1000 1100 900 600 800 1000 1200 1400 0 总机器偏差 总运输时间/min 订单完工时间/min (b) 图 4 两种算法所得插单后所有工件调度的 Pareto 最优解集. （a）NSGA-II 算法; （b）NSGA-III 算法 Fig.4 Pareto optimal solutions of all unfinished jobs: (a) NSGA-II algorithm; (b) NSGA-III algorithm (a) 初始订单调度案例 NSGA-II算法优化调度 1 2 15.421.17 27.58 47.23 30.11 62.62 23.22 31.14 32.05 55.62 31.42 52.34 15.74 28.44 9.45 12.82 8.88 14.81 14.1 18.99 3 4 5 6 7 8 9 10 实际调度 订单完工时间/h (b) 初始订单调度案例 NSGA-II算法优化调度 1 2 10.0112.28 9.2 12.75 10.25 18.16 9.36 11.72 15.58 22.96 17.92 22.35 8.1 12.26 3.6 4.2 4.13 5.3 6.14 8.73 3 4 5 6 7 8 9 10 实际调度 总运输时间/h 图 5 企业实际调度和 NSGA-II 算法优化调度结果的双目标对比图. （a）初始订单总完工时间; （b）总运输时间 Fig.5 Compare of two objectives obtained by the actual and the optimal initial order scheduling: (a) total completion time; (b) transportation time (a) 紧急订单插单案例 1 2 26.77 52.49 41.56 71.66 59.26 95.58 40.82 51.67 53.17 75.95 48.91 69.87 47.16 62.88 15.77 31.54 16.55 24.7 22.57 50.18 3 4 5 6 7 8 9 10 订单完工时间/h (b) 紧急订单插单案例 1 2 10.6 19.43 12.75 25.95 12.32 32.65 11 29.89 19.27 28.19 14.03 19.53 8.9 21.66 9.18 13.46 7.77 10.13 10.52 15.32 3 4 5 6 7 8 9 10 总运输时间/h (c) 紧急订单插单案例 NSGA-III算法优化调度 1 2 7 17 13 22 15 31 10 11 6 14 12 23 14 19 7 12 8 12 5 18 3 4 5 6 7 8 9 10 实际调度 NSGA-III算法优化调度 实际调度 NSGA-III算法优化调度 实际调度 总机器偏差 图 6 企业实际调度和 NSGA-III 算法优化调度结果的三目标对比图. （a）插单后总完工时间; （b）总运输时间; （c）总机器偏差 Fig.6 Compare of three objectives obtained by the actual and the optimal rush order insertion rescheduling: (a) total completion time; (b) total transportation time; (c) total machine deviation · 1456 · 工程科学学报，第 41 卷，第 11 期

何小妹等：多目标多约束混合流水车间插单重调度问题研究 1457 实际调度结果，优化率接近三分之一，效果较为显著 systems:a framework of strategies,policies,and methods.J Scheduling,2003,6(1):39 4结论 [7]Wu S D,Storer R H,Pei C C.One-machine rescheduling (1)对紧急订单插单重调度问题，先以最小化 heuristics with efficiency and stability as criteria.Compur Operations Res,1993,20(1):1 订单完工时间和最小化总运输时间为双目标建立 [8]CuiZ,Gu XS.A discrete group search optimizer for hybrid flow- 初始订单调度模型，再增加最小化总机器偏差值 shop scheduling problem with random breakdown.Math Probl 作为稳定性指标建立三目标优化模型，并依次用 Emg,2014,24:621393 NSGA-IⅡ算法、结合重排插单方式和基于事件驱 [9]Wang K.Choi S H.A decomposition-based approach to flexible 动的重调度方式的NSGA-Ⅲ算法对其进行求解. flow shop scheduling under machine breakdown.Int/Prod Res (2)通过MID,SNS和POD三个指标对比了 2012,50(1):215 NSGA-IⅡ算法和NSGA-III算法的性能，得出NSGA-II [10]Gao K Z,Suganthan P N,Pan Q K,et al.Artificial bee colony 算法更适用于解决双目标优化问题，而NSGA-I algorithm for scheduling and rescheduling fuzzy flexible job 算法对三目标优化问题表现更好的结论 shop problem with new job insertion.Knowledge-Based Syst, 2016,109:1 (3)将所提的模型与求解方法应用于某实际 [11]Chiu Y F,Shih CJ.Rescheduling strategies for integrating rush 船用管类零件生产企业的紧急订单插单案例中， orders with preventive maintenance in a two-machine flow shop. 所得到的结果较企业实际数据优化近三分之一， nt J Prod Res,2012,50(20):5783 验证了模型和算法的实用性和有效性 [12]Wang D J,Liu F,Wang J J,et al.Integrated rescheduling and preventive maintenance for arrival of new jobs through 参考文献 evolutionary multi-objective optimization.Sofi Comput,2016, [1]Gupta J N D.Two-stage,hybrid flowshop scheduling problem.J 20(4):1635 Operational Res Soc,1988,39(4):359 [13]Pei H Y,Jiang Z H,Hu J W,et al.Integrating rescheduling with [2]Meng T.Pan Q K.Li J Q.et al.An improved migrating birds preventive maintenance in the flow-shop problem under rush optimization for an integrated lot-streaming flow shop scheduling order.Ind Eng Manage,2017,22(1):50 problem.Swarm Evolutionary Comput,2018,38:64 (裴海燕，蒋祖华，胡家文，等.插单扰动下流水线生产与维护的 [3]Rossi A.Flexible job shop scheduling with sequence-dependent 重调度优化.工业工程与管理，2017,22(1)：50) setup and transportation times by ant colony with reinforced [14]Deb K,Jain H.An evolutionary many-objective optimization pheromone relationships.Int Prod Economics,2014,153:253 algorithm using reference-point-based non-dominated sorting [4]Yue L.Guan Z L.Zhang L.et al.Multi-objective lotsizing and approach,Part I:solving problems with box constraints.IEEE scheduling with material constraints in flexible parallel lines using Trans Evolutionary Compul,2014,18(4):577 a Pareto based guided artificial bee colony algorithm.CompuInd [15]Qi X T,Bard J F,Yu G.Disruption management for machine Emg,2019,128:659 scheduling:the case of SPT schedules.Int J Prod Economics, [5]Qin H B,Fan P F,Tang H T.et al.An effective hybrid discrete 2006,103(1):166 grey wolf optimizer for the casting production scheduling problem [16]Govindan K,Jafarian A,Khodaverdi R,et al.Two-echelon with multi-objective and multi-constraint.Comput Ind Eng,2019, multiple-vehicle location-routing problem with time windows for 128:458 optimization of sustainable supply chain network of perishable [6]Vieira G E,Herrmann J W,Lin E.Rescheduling manufacturing food.Int J Prod Economics,2014,152:9

实际调度结果，优化率接近三分之一，效果较为显著. 4    结论 （1）对紧急订单插单重调度问题，先以最小化 订单完工时间和最小化总运输时间为双目标建立 初始订单调度模型，再增加最小化总机器偏差值 作为稳定性指标建立三目标优化模型，并依次用 NSGA-II 算法、结合重排插单方式和基于事件驱 动的重调度方式的 NSGA-III 算法对其进行求解. （ 2）通过 MID， SNS 和 POD 三个指标对比了 NSGA-II 算法和NSGA-III 算法的性能，得出NSGA-II 算法更适用于解决双目标优化问题，而 NSGA-III 算法对三目标优化问题表现更好的结论. （3）将所提的模型与求解方法应用于某实际 船用管类零件生产企业的紧急订单插单案例中， 所得到的结果较企业实际数据优化近三分之一， 验证了模型和算法的实用性和有效性. 参    考    文    献 Gupta J N D. Two-stage, hybrid flowshop scheduling problem. J Operational Res Soc, 1988, 39（4）: 359 [1] Meng T, Pan Q K, Li J Q, et al. An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem. Swarm Evolutionary Comput, 2018, 38: 64 [2] Rossi A. Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. Int J Prod Economics, 2014, 153: 253 [3] Yue L, Guan Z L, Zhang L, et al. Multi-objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm. Comput Ind Eng, 2019, 128: 659 [4] Qin H B, Fan P F, Tang H T, et al. An effective hybrid discrete grey wolf optimizer for the casting production scheduling problem with multi-objective and multi-constraint. Comput Ind Eng, 2019, 128: 458 [5] [6] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. J Scheduling, 2003, 6（1）: 39 Wu S D, Storer R H, Pei C C. One-machine rescheduling heuristics with efficiency and stability as criteria. Comput Operations Res, 1993, 20（1）: 1 [7] Cui Z, Gu X S. A discrete group search optimizer for hybrid flow￾shop scheduling problem with random breakdown. Math Probl Eng, 2014, 24: 621393 [8] Wang K, Choi S H. A decomposition-based approach to flexible flow shop scheduling under machine breakdown. Int J Prod Res, 2012, 50（1）: 215 [9] Gao K Z, Suganthan P N, Pan Q K, et al. Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowledge-Based Syst, 2016, 109: 1 [10] Chiu Y F, Shih C J. Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop. Int J Prod Res, 2012, 50（20）: 5783 [11] Wang D J, Liu F, Wang J J, et al. Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization. Soft Comput, 2016, 20（4）: 1635 [12] Pei H Y, Jiang Z H, Hu J W, et al. Integrating rescheduling with preventive maintenance in the flow-shop problem under rush order. Ind Eng Manage, 2017, 22（1）: 50 （裴海燕, 蒋祖华, 胡家文, 等. 插单扰动下流水线生产与维护的 重调度优化. 工业工程与管理, 2017, 22（1）：50 ） [13] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, Part I: solving problems with box constraints. IEEE Trans Evolutionary Comput, 2014, 18（4）: 577 [14] Qi X T, Bard J F, Yu G. Disruption management for machine scheduling: the case of SPT schedules. Int J Prod Economics, 2006, 103（1）: 166 [15] Govindan K, Jafarian A, Khodaverdi R, et al. Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. Int J Prod Economics, 2014, 152: 9 [16] 何小妹等： 多目标多约束混合流水车间插单重调度问题研究 · 1457 ·