何小妹等：多目标多约束混合流水车间插单重调度问题研究 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 ·