1494 工程科学学报.第43卷第11期 (7)~(10)和式(12)~（13)为车间工艺约束；式 Ns (14)为加工时间、起运时间均大于零. (Ps k-P 目标函数如下： f=min (19) 考虑车间工作效率和车间内相关运营成本， 将最小化完工时间和最小化运载设备运输时间作 为本文研究的两个目标，建立两目标带有限缓冲 2带有限缓冲区的混合流水车间调度问题 区的混合流水车间调度模型，记为模型1，如式 (15)和式(16)所示 针对所建立的调度模型，分别采用NSGA-Ⅱ， NSGA-I算法对模型进行求解，算法框架与两算 i=min(max级l (15) 法不同的个体选择方式详见文献[25).本文中由于 =m22i.w-ra） 各机器配置了容积有限的缓冲区，增加了工序与工 (16) 序之间的关联性，初始种群的生成方式为随机生 i=l a=1 由于缓冲区容积有限，在一些未考虑工件占 成，终止准则为达到预定的终止时间，适应度为个体 用缓冲区空间均衡的排产方案中，会导致部分缓 的目标值，基因编码、交叉变异的具体设计如下， 2.1基因编码 冲区出现“拥堵”的现象，即缓冲区空间被工件占 满，导致上一工序加工完的工件无法进入到下一 本文中建立的模型涉及工件排序和并行机选 工序，而停留在上一工序的缓冲区和机器中，增加 择两部分，在编码方式上采用了双层编码的方式， 了等待时间.本文中以缓冲区占用率来衡量加工 第1层为工件码，按照工艺顺序划分为多个加工 阶段，每个基因位中的数字代表工件的批次编号； 过程中各缓冲区占用情况，以并行机前置缓冲区 占用率均衡作为第3个目标，建立3目标带有限缓 第2层为机器码，对应第一层中的工件所选择的 机器，每个基因位中的数字代表该批次工件在该 冲区的混合流水车间调度模型，记为模型2，并行 阶段可选机器集中所选择的机器索引号，若2个 机前置缓冲区占用率均衡指数如式(19)所示， 不同批次的工件在某阶段选择同一台机器，则以 Pk为机器缓冲区占用率，P,为第s工序并行机中 工件码中出现的先后顺序确定排产顺序，同时基 的各个机器的平均占用率 因的编码顺序满足工序间关联性的要求.例：如 图1所示[2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1,1,2,2,1,2， 3,2,1,2,3,2,1,2,3,3,1,1,2]为一个3加工阶段6批次 .Vs.k (17) 工件模型的其中1条染色体，[2,1,3,5,4,6,3,2,4,5,1,6,4， 6,3,5,2,1]是工件码部分，[1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1， 1,2]是机器码部分，工件码与机器码为一一对应关系. P:= 既包含全部加工阶段与全部工件编号的工件码同时 18) 也有对应机器码的染色体为一个完整的调度方案 (a) (b) Workcode Machine code Workcode 2 13 5 4 63 2 4 5 16 653024064523D30233010210 214351611325164221331221①1T1① Machine After POX crossover code 022023202320 c 420356132564002331T02 Genes adjust to meet production process requirements 图1编码示意图(a)与交叉示意图(b) Fig.1 Coding diagram (a)and cross diagram(b) 2.2交叉与变异 父代中工件分配到机器的机器码部分，可以保证 采用基于工序编码的交叉算子(Precedence 满足新产生的子代符合生产工艺的约束，同时满 operation crossover,,POX)所生成的新基因，保留了 足本文中对工序间关联性的要求.具体操作如图1（7）～（10）和式（12）～（13）为车间工艺约束；式 （14）为加工时间、起运时间均大于零. 目标函数如下： 考虑车间工作效率和车间内相关运营成本， 将最小化完工时间和最小化运载设备运输时间作 为本文研究的两个目标，建立两目标带有限缓冲 区的混合流水车间调度模型，记为模型 1，如式 （15）和式（16）所示. f1 = min{maxt C s,k, j } （15） f2 = min∑ Y i=1 ∑ A a=1 (T l i,s→(s+1), j −T l s,k,B, j ) （16） Ps,k Ps 由于缓冲区容积有限，在一些未考虑工件占 用缓冲区空间均衡的排产方案中，会导致部分缓 冲区出现“拥堵”的现象，即缓冲区空间被工件占 满，导致上一工序加工完的工件无法进入到下一 工序，而停留在上一工序的缓冲区和机器中，增加 了等待时间. 本文中以缓冲区占用率来衡量加工 过程中各缓冲区占用情况，以并行机前置缓冲区 占用率均衡作为第 3 个目标，建立 3 目标带有限缓 冲区的混合流水车间调度模型，记为模型 2，并行 机前置缓冲区占用率均衡指数如式（ 19）所示 ， 为机器缓冲区占用率， 为第 s 工序并行机中 的各个机器的平均占用率. Ps,k = w ∑ J j=1 Xj,s,k,F,t C F s,k ,∀s, k （17） Ps = ∑ Ns k=1 Ps,k Ns ,∀s （18） f3 = min    ∑ S s=1 ∑ Ns k=1 (Ps,k − Ps) 2 Ns −1    （19） 2    带有限缓冲区的混合流水车间调度问题 针对所建立的调度模型，分别采用 NSGA-II， NSGA-III 算法对模型进行求解，算法框架与两算 法不同的个体选择方式详见文献 [25]. 本文中由于 各机器配置了容积有限的缓冲区，增加了工序与工 序之间的关联性，初始种群的生成方式为随机生 成，终止准则为达到预定的终止时间，适应度为个体 的目标值，基因编码、交叉变异的具体设计如下. 2.1    基因编码 本文中建立的模型涉及工件排序和并行机选 择两部分，在编码方式上采用了双层编码的方式， 第 1 层为工件码，按照工艺顺序划分为多个加工 阶段，每个基因位中的数字代表工件的批次编号； 第 2 层为机器码，对应第一层中的工件所选择的 机器，每个基因位中的数字代表该批次工件在该 阶段可选机器集中所选择的机器索引号，若 2 个 不同批次的工件在某阶段选择同一台机器，则以 工件码中出现的先后顺序确定排产顺序，同时基 因的编码顺序满足工序间关联性的要求. 例：如 图 1 所 示 [2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1,1,2,2,1,2, 3,2,1,2,3,2,1,2,3,3,1,1,2] 为一个 3 加工阶段 6 批次 工件模型的其中 1 条染色体，[2,1,3,5,4,6,3,2,4,5,1,6,4, 6,3,5,2,1] 是工件码部分，[1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1, 1,2] 是机器码部分，工件码与机器码为一一对应关系， 既包含全部加工阶段与全部工件编号的工件码同时 也有对应机器码的染色体为一个完整的调度方案. Workcode 2 1 3 5 4 6 3 2 4 5 1 6 6 5 3 1 2 4 1 6 4 5 2 3 1 3 1 2 3 3 1 1 1 2 1 1 2 1 4 3 5 6 1 3 2 5 6 4 2 2 1 3 3 2 2 1 1 1 1 1 4 p1 p2 c 2 1 3 5 6 1 3 2 5 6 4 1 3 1 2 3 3 1 1 1 2 1 1 1 2 2 1 2 3 2 1 2 3 2 1 Machine code Workcode (a) (b) Machine code After POX crossover Genes adjust to meet production process requirements 图 1 编码示意图（a）与交叉示意图（b） Fig.1 Coding diagram (a) and cross diagram (b) 2.2    交叉与变异 采用基于工序编码的交叉算子 (Precedence operation crossover，POX) 所生成的新基因，保留了 父代中工件分配到机器的机器码部分，可以保证 满足新产生的子代符合生产工艺的约束，同时满 足本文中对工序间关联性的要求. 具体操作如图 1 · 1494 · 工程科学学报，第 43 卷，第 11 期