带有限缓冲区的混合流水车间多目标调度

袁庆欣，董绍华

北京科技大学机械工程学院，北京 100083

考虑工件以批量形式运输、车间中各个工序前后生产节拍不同等因素，在混合流水车间中建立缓冲区是非常必要的. 流水车间中（Flow shop,FS）的缓冲区一般有两种形式，加工工序间共享缓冲区[1]和机器独立配置缓冲区[2]，第一种类型常见于物料搬运较为容易、加工形式单一的串型生产线当中[3]，而对于运输能力有限、车间布局不易更改的混合流水车间，机器独立配置缓冲区更具备研究意义.

求解混合流水车间的调度问题已经被Gupta[4]证明是非确定性多项式（Non-deterministic polynomial, NP）难度问题，目前解决这类问题有适用于低复杂度、小规模问题的精确计算[5−7]、启发式方法[8−9]以及当下被广泛使用的智能搜索算法[10−13]，Smutnicki[14]较早的针对含有容量限制的中间缓冲区的两机排列的混合流水车间，以最小化完工时间为目标，采用了一种基于禁忌搜索的近似算法；Nowicki[15]采用禁忌算法，将其扩展为每个加工工序中可以含有任意数量的机器；Qian等[16]针对有限缓冲区位于连续机器之间的流水车间调度问题，设计一种混合差分进化算法(HDE)，并通过仿真实验验证算法的有效性；Wang与Tang[17]采用一种回溯启发式算法，针对加工阶段间有限等待时间的混合流水车间调度问题，以最小化完工时间为目标进行求解同时验证了算法的有效性.

遗传算法（Genetic algorithm，GA）已经广泛的应用在车间调度问题上[18−20]，本文也拟采用遗传算法进行求解. NSGA-II（Non-dominated sorting genetic algorithm 2，NSGA-II）是由 Deb 等[21]提出，且已经广泛应用在处理多目标混合流水车间调度问题当中[22−24]的智能算法. NSGA-III（Nondominated sorting genetic algorithm 3，NSGA-III）是在NSGA-II基础上提出的[25]，与NSGA-II有着相同的框架，但是在精英选择策略关于同一级非支配个体间的选择机制上，NSGA-II算法采用根据拥挤度大小的方式进行个体选择，NSGA-III则是基于参考点的方式，改进了NSGA-II算法在处理三个及其以上目标时解在非支配层上分布不均匀、易陷入局部最优的缺点.

综上，现有的文献中多数都是假定车间中为无限制缓冲区，或者为工序间共享缓冲区，研究带有限机器独立配置缓冲区混合流水车间调度问题的文献较少，本文将对带有限缓冲区的混合流水车间调度问题进行研究，以最小化完工时间、最小化运载设备运输时间、最小化并行机前置缓冲区空间占用率均衡指数为目标，考虑运载设备运输能力限制、机器不确定性加工时间、缓冲区容积有限等资源限制条件，建立模型，并采用NSGAII与NSGA-III算法进行求解，对比不同算法在求解过程的差异. 最后，将针对实际车间进行实例验证，并对产生的优化结果加以分析.

1 带有限缓冲区的混合流水车间建模

1.1 问题描述

混合流水车间生产加工阶段s=1～S，加工设备k=1～N，每一台加工设备都配置了独立的前置缓冲区和后置缓冲区，受到有限的车间空间和设备生产线布局的影响，除第一道加工工序的前置缓冲区和最后一道加工工序的后置缓冲区视为容量无限大，其他剩下所有的缓冲区均为容量有限的缓冲区，车间中运载设备i=1～Y用于工序间工件运输，每一个加工阶段中都包含着生产精度不同、加工效率不等、工件适用情况存在差异的一定数量的并行机，工件集O按照批次进行划分为A个批次，O={1,2,···,a,···,A−1,A}，工件总数量为J.假设：（1）所有工件的加工顺序一致，均要从第一加工工序开始，完成一个工序的加工任务后，进入下一个加工工序，直到完成最后一个加工工序的加工任务；（2）其中缓冲区的容积可以进行调节，但会受到车间空间和天车运输距离的限制，且加工作业一旦开始，缓冲区容积就不能再更改：（3）所有加工批次均为合理划分，既能满足天车运输能力的要求，同时也符合缓冲区容积要求；（4）不考虑工件的换装时间，且同批次内工件之间无确定先后加工顺序要求.

1.2 模型建立

相关参数设计如表1.

表1 参数及变量设计Table 1 Design of the parameters and decision variables

车间资源约束条件如下：

上述模型中，式（1）～（3）为机器能力、运载设备运输能力约束，具体为一台机器一次只能加工一个工件，一台运载设备一次也只能运输一个批次的工件；式（4）～（5）为缓冲区容积限制；式（6）、式（11）分别为加工时间约束和运输时间约束；式（7）～（10）和式（12）～（13）为车间工艺约束；式（14）为加工时间、起运时间均大于零.

目标函数如下：

考虑车间工作效率和车间内相关运营成本，将最小化完工时间和最小化运载设备运输时间作为本文研究的两个目标，建立两目标带有限缓冲区的混合流水车间调度模型，记为模型1，如式（15）和式（16）所示.

由于缓冲区容积有限，在一些未考虑工件占用缓冲区空间均衡的排产方案中，会导致部分缓冲区出现“拥堵”的现象，即缓冲区空间被工件占满，导致上一工序加工完的工件无法进入到下一工序，而停留在上一工序的缓冲区和机器中，增加了等待时间. 本文中以缓冲区占用率来衡量加工过程中各缓冲区占用情况，以并行机前置缓冲区占用率均衡作为第3个目标，建立3目标带有限缓冲区的混合流水车间调度模型，记为模型2，并行机前置缓冲区占用率均衡指数如式（19）所示，Ps,k为机器缓冲区占用率，为第s工序并行机中的各个机器的平均占用率.

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]是机器码部分，工件码与机器码为一一对应关系，既包含全部加工阶段与全部工件编号的工件码同时也有对应机器码的染色体为一个完整的调度方案.

图1 编码示意图（a）与交叉示意图（b）Fig.1 Coding diagram (a) and cross diagram (b)

2.2 交叉与变异

采用基于工序编码的交叉算子 (Precedence operation crossover，POX)所生成的新基因，保留了父代中工件分配到机器的机器码部分，可以保证满足新产生的子代符合生产工艺的约束，同时满足本文中对工序间关联性的要求. 具体操作如图1中示例所示， p 1、 p 2是随机选择的两个父代个体，在工件码部分随机生成交叉点，并首先在该部分进行交叉，保留两个父代个体中保持关联性的相关基因，随后机器码部分对应工件码相关部分的交叉方式进行交叉，对其中不符合工艺要求的基因调整方式为，在满足工艺要求的基因组合中随机选择，保证种群的多样性，最终生成子代c.

多点变异是遗传算法中常见的变异方式，本文中基因变异主要针对机器码部分，根据变异率随机选取个体进行变异，为保证个体的多样性，变异过程为全随机变异方式.

3 实例验证

本文以某船用管类生产企业为研究对象，对其生产加工车间进行考虑缓冲区容积有限的混合流水车间多目标优化调度的相关研究. 其车间生产布局图如图2所示，车间被分为2跨4区，其中共有6个加工工序，工件在各个加工工序间通过天车进行运输，每道工序都包含数量不等，加工精度、工作效率、工件适用情况不同的并行机，每台机器都配置了独立的前置后置缓冲区，该车间可以认为是一个带有限缓冲区的混合流水车间. 车间生产工件信息如表2所示.

图2 生产车间布局图Fig.2 Production workshop layout

表2 工件编号以及对应各阶段机器适用状况统计表Table 2 Workpiece number and statistics of applicable conditions of themachine at each stage

现拟设计3个实验，（1）以该车间为研究基础，分别采用NSGA-II与NSGA-III处理多目标车间调度问题，验证算法的有效性，探究2个算法处理3目标优化问题时的区别；（2）通过改变缓冲区的容积，比较不同缓冲区容积时，模型2中3个目标值的变化；（3）采用NSGA-III处理模型1，统计3个指标值并与模型2的3个目标值进行对比分析. 所处理订单为企业实际订单，订单中将工件划分为6个批次，批次1到批次6在各个阶段的机器适用情况分别对应表2中工件编号，每个批次的批量都是8.

实验一：分别采用NSGA-II与NSGA-III解决3目标带有限缓冲区的混合流水车间调度模型，共2组实验，每组实验进行10次，2个算法均设置为初始种群数量为500，交叉率为0.8，变异率为0.2，算法迭代10次即完成10次交叉变异之后达到终止条件.

图3为优化的结果，通过结果可知，在处理3目标问题时，NSGA-III的收敛性要明显好于NSGA-II，图4中为分别统计10次NSGA-II与NSGA-III算法处理该模型时一级个体（最优解）的个数，通过对比可知在处理3目标带有限缓冲区的混合流水车间调度模型时，NSGA-III的一级个体更多，也说明收敛效果更好.

图3 NSGA-II（a）与 NSGA-III（b）优化结果图Fig.3 NSGA-II (a) and NSGA-III (b) optimization results

图4 NSGA-II与NSGA-III一级个体数量对比图Fig.4 Comparison of the number of NSGA-II and NSGA-III individuals

实验二：为更贴近车间实际情况，除第一阶段机器的前置缓冲区和最后一阶段的后置缓冲区，其余各个机器的前置后置缓冲区容积均相等且统一变化，以缓冲区可容纳工件数量作为描述缓冲区容积的指标，缓冲区可调整的最小容量为订单中单个批次最大工件数，当前订单中为8，逐步增加缓冲区容量至50，对比不同缓冲区容积下，3个目标值的变化，如图5所示.

图5 优化3目标有限缓冲区的混合流水车间调度模型三指标统计结果Fig.5 Three statistical results of hybrid flow shop scheduling model with optimized three-object limited buffer zone

通过该实验结果可知，缓冲区的容积逐渐变大，工序间独立性增强，运输时间与缓冲区占用率均衡指数明显下降，其中缓冲区容积增大至14后，运输时间变化开始趋于稳定，不再有明显的下降，缓冲区占用率均衡指数在缓冲区容积增大至10后，下降速度放缓，增大至20后再次放缓，但整体上仍继续下降，完工时间则基本保持不变.

实验结果分析如下. 缓冲区容积较小则加工过程中发生“拥堵”的概率会增大，从而会延长工件在天车上的滞留时间，致使运输时间增多；在同一缓冲区中，缓冲区中相同工件数量时，缓冲区容积大的缓冲区空间占用率低，使得缓冲区均衡指数下降，同时随着缓冲区容积增大，工序间独立性增强，可选择加工方案增多，其中可使缓冲区占用率更均衡的方案数量也会增加，以上两点都是导致缓冲区占用率均衡指数下降的原因；完工时间不受缓冲区容积影响.

实验三：使用NSGA-III处理模型1，统计3个指标值情况，与实验二中统计模型2的3个目标值情况对比，探究模型1与模型2在不同缓冲区容积下3个指标值的区别，如图6所示.

图6 模型 1 与模型 2 对比. （a）完工时间；（b）运输时间；（c）缓冲区均衡指数Fig.6 Comparison of model 1 and model 2: (a) completion time; (b) transportation time; (c) buffer equilibrium index

通过实验结果可知，模型1与模型2完工时间基本相同，且随着缓冲区容积改变，完工时间基本无变化，在缓冲区容积较小时，模型1的运输时间要小于模型2的运输时间，但缓冲区均衡指数较高，说明在生产过程中出现了缓冲区空间占用率不均衡和机器负载不均衡的情况，缓冲区容积增大后，两模型的运输时间指标与缓冲区占用率均衡指数分别趋于相等.

4 结论

（1）同时采用NSGA-II与NSGA-III两个算法对3目标调度模型进行优化，得出在处理3个目标的问题时，NSGA-III在收敛性和生成一级个体数量上要好于NSGA-II的结论.

（2）求解3目标带有限缓冲区的混合流水车间调度模型，不断增加缓冲区容积，得出缓冲区容积越大，完工时间基本不变，运输时间越短和缓冲区占用率更均衡的结论.

（3）若不考虑缓冲区占用率均衡，在缓冲区容积较小时模型1可以得到与模型2相比更小的运输时间，但会导致缓冲区占用率均衡性较差，缓冲区容积增大后，模型1的缓冲区占用率均衡性逐渐得到改善，则得出在缓冲区容积较小时，考虑缓冲区占用率均衡更具备研究意义.