离散水波优化算法求解带批处理的混合流水车间批量流调度问题

王文艳， 徐震浩， 顾幸生

（华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237）

随着生产方式的不断改进，一些特殊工艺如钢铁炼制中的热处理操作、半导体芯片的预烧工序等常需要进行批处理[1]。目前，涉及批处理的混合生产方式已成为混合流水车间调度问题的一个重要研究方向，有很多学者针对带批处理的混合流水车间调度问题进行了研究。Qin 等[2]考虑了机器有限等待时间，研究了同时具有批处理机和离散机的两级混合流水车间调度问题。张煜等[3]和Liu 等[4]针对三阶段混合批处理机和非批处理机的混合流水车间问题进行了研究。王君妍等[5]和轩华等[6]在不同约束条件下，研究了中间阶段有多台批处理机、其他阶段为离散机的多阶段混合流水车间调度问题。然而，这些研究成果都是针对单个加工工件，没有考虑工件的批量性。在实际制造过程中，批量生产工件的情况普遍存在，因此，批量流调度的研究对于制造业具有重要的现实意义。

批量流调度是将批量生产的工件划分为多个子批，并以子批为单位进行转移以减少机器闲置时间，提高生产效率。目前已有大量文献对批量流调度问题进行了研究。Zhang 等[7]和Qin 等[8]分别提出了改进候鸟优化算法和两阶段蚁群算法，以解决等量分批的混合流水车间批量流调度问题。Nejati 等[9]研究了带有轮班约束的混合流水车间调度问题，在一致分批下采用GA 算法对工件排序进行优化。Wang 等[10]研究了可变分批下的混合流水车间批量流调度问题，提出了一种混合线性规划模型，确定了工件的划分与排序。就分批方法而言，对等量分批和一致分批的研究相对较多，可变分批因其较灵活、子批的数量和大小具有不确定性使得模型求解难度增加，因此到目前为止相关研究较少。本文将带批处理的混合流水车间问题与批量流调度问题相结合，对带批处理的混合流水车间批量流调度问题进行研究，针对批处理机与离散机不同的加工特点，提出了一种基于批处理机容量与不相关离散机加工能力的可变分批方法，能够减少分批的不确定性，降低搜索空间的维度。

水波优化(Water Wave Optimization, WWO)[11]算法是一种针对连续优化问题的智能算法。受浅水波模型的启发，WWO 算法利用传播、折射和碎浪来实现算法的搜索过程，该算法具有结构简单、参数少、易于实现等特点，可用于调度[12]、经济开发[13]、发电机组检修调度[14]等实际问题。本文在WWO 算法的基础上，提出了一种离散水波优化(DWWO)算法来解决带批处理的混合流水车间批量流调度问题。

1 问题描述

带批处理的混合流水车间批量流调度问题可以描述为：n种工件进行m道工序的加工，每道工序k上有xk(xk≥1) 台不相关并行机，每台机器的加工批量有限。其中，第a( 1

1.1 参数符号

1.2 决策变量

其中：ls和le分别为工件i在工序k的子批l中最先到达工件和最后到达工件在工序k−1 中的子批号；RSikl为子批l中在转折点之前到达的工件数；Po 为到达即可加工的剩余工件所属子批在工序k−1 的序号，即子批l中在转折点到达的工件在工序k−1 的子批序号。

（6）一般工序k上机器加工完工件i的空闲时刻：

（7）批处理工序的批处理子批批量：

（10）若当前子批是批处理机的第一个加工子批，则批处理机在准备操作之后即可工作，否则需等待批处理机完成前一子批的加工。

2 离散水波优化算法设计

WWO 算法结构简单、参数较少，目前只用于解决连续问题。本文将WWO 算法进行离散化处理并进行了改进，使其能更好地解决混合流水车间环境下的批量流调度问题。

2.1 编码 / 解码方案

以工件在第一道工序的加工顺序为编码方案，如有6 种工件，编码后产生个体 π =[2, 5, 3, 6, 4, 1] ：在此个体中，数字代表各工件的序号，数字的排序为各工件在第一道工序上的加工顺序。为了获得切实有效的调度方案，解码时需要解决两个问题：一是各工件在后续工序的加工顺序；二是工件在每道工序的机器选择。对于工件在后续工序的加工顺序，本文根据先入先出(First In First Out，FIFO)规则，设计了两种策略：

（1）子批优先，根据每种工件的第一个子批在工序k的完工时间决定工件在工序k+1 的加工顺序；

（2）工件优先，考虑工件最后一个子批在工序k的完工时间，若工件在工序k上优先完工，则安排此工件在工序k+1 上优先加工。

针对工件在每道工序上机器的选择问题，设计了如下两种策略：

(1) 机器最短完工策略 m in(EPikh) 。若工件i在工序k上选择第h台机器上加工，则机器h的完工时间为

Ⅱ. 子批优先+机器加工均衡。采用机器加工均衡策略选择机器，其他过程与方案Ⅰ类似。

Ⅲ. 工件优先+机器最短完工。在后续工序，工件加工顺序按照各工件在上一工序的最后一个子批的加工结束时间升序排列生成，其他过程与方案Ⅰ类似。

Ⅳ. 工件优先+机器加工均衡。采用机器加工均衡策略选择机器，其他过程与方案Ⅰ类似。

2.2 操作算子的改进

3 数据仿真与分析

目前针对考虑了批处理机容量和不相关离散机加工能力的混合流水车间批量流调度问题的研究成果较少，且没有标准算例可供参考比较，因此根据参考文献中的设置，设计了如下数据集：各工件批量随机分布在[10,30] 中；一般工序阶段的机器数在[1,3]中随机产生，机器最大加工能力和加工时间分别分布在[5,15]和[4,16]中，可分离准备时间分布在[1,4]中；批处理工序随机分布在[2,m]中；批处理阶段，批处理机的加工容量和加工时间分别在[10,30]和[10,99]中随机产生，批处理机的准备时间分布在[6,15] 中。此数据集由50 种工件和15 道工序构成，由于考虑了工件分批且工序存在不相关并行机，对于带批处理的混合流水车间批量流调度来说，数据集的规模较大且相对复杂。本文中的所有程序在Windows 10 系统、Intel Corei7 处理器、内存为8 GB 的PC 上使用MATLAB R2019a 软件编写并运行。

3.1 参数调节

为了使算法能在较优的状态下运行，需要对参数进行合理设置[18]。设置种群规模为30，波长上界λmax=L/3 ，波长下界 λmin=λmax/2[19]。因算法的迭代次数M、波高上限hmax、碎浪操作中循环次数上限P和折射操作中折射长度len也会影响算法的运行结果，为了保证算法具有最佳的运行状态，采用正交实验法对上述4 个参数进行设置。在兼顾算法性能和运行时间的情况下，本文设置为M=150 ，hmax=3 ，P=15 ，len=L/5 。图1 为参数水平影响趋势图，其中AVG 为算法运行10 次时makespan 的平均值。

图1 参数水平影响趋势图Fig. 1 Trend graphs of influence of parameters

3.2 解码方案对模型的影响

为了评估不同的解码方案的性能，对2. 1 节的4 种解码方案进行对比。每种方案都在不同规模的算例上测试10 次，结果如表1 所示，较优值用黑体显示。

表1 不同解码方案对比结果Table 1 Comparison results of different decoding schemes

通过方案Ⅰ与方案Ⅱ、方案Ⅲ与方案Ⅳ的两两对比，可以观察出针对大部分算例，方案Ⅱ的AVG比方案Ⅰ的值小。同样地，方案IV 的AVG 也优于方案Ⅲ。因此，对于工件排序问题，工件优先策略比子批优先策略更适用于本文研究的问题，这是因为工件优先策略能够减小因先到达工件不足一个子批时等待的时间。另外，通过方案Ⅰ与方案Ⅲ、方案Ⅱ与方案Ⅳ的两两对比，可以观察出针对大部分算例，方案Ⅰ与方案Ⅱ的结果分别优于其他两种方案。因此，对于机器选择问题，机器最短完工策略优于机器加工均衡策略，由于机器最短完工策略综合考虑机器空闲时间和子批在机器上的加工时间，相比于机器加工均衡策略只考虑机器加工总时间均衡，更能选择到合适的机器使子批在各道工序上尽快完工。综上所述，在基于批处理机容量和离散机加工能力的可变分批下，方案Ⅱ的性能优于其他3 种方案。因此，本文采用方案Ⅱ较为适合。

3.3 动态连续加工对模型的影响

为测试动态连续加工策略的有效性，将其与不带动态连续加工策略的调度方案进行了比较。表2示出了两种策略下针对不同规模算例运行10 次的AVG 对比结果，黑体为较优值。

从表2 中可以看出，针对不同规模的算例，带动态连续加工策略的方案均能取得更优的目标值。以6×4 规模为例，带动态连续加工策略获得的加工序列为 π1=[1,5,2,3,4,6] ，AVG 为1 122；不带动态连续加工策略获得的加工序列为 π2=[5,6,1,4,3,2] ，AVG为1 220。用两种策略分别对 π1进行调度，对应的甘特图如图2 所示，子批用白色方框表示，机器准备时间用黑色方框表示。在一般工序中，方框上的数字表示子批所属工件，方框中的数字表示子批批量；在批处理工序中，由于子批包含不同种类的工件，因此方框中的数字表示为工件-批量。白色方框下的数字表示子批的开始加工时间。

表2 两种策略下的实验结果对比Table 2 Comparison of experimental results under two strategies

从图2 可以看出，采用动态连续加工策略进行调度得到的目标值更优。因为采用带动态连续加工策略时, 在保证子批加工连续的情况下，子批中先到达的工件可以提前加工，减少了后续机器的等待时间，提高了生产效率。以图2(a)和(b)为例，对于工序3 上工件1 第2 个子批的加工，由于批处理子批1 中包含11 个工件1，因此当批处理子批1 完成批处理到达工序3 时，批处理子批1 中工件1 的其中9 个工件作为其在工序3 上第1 个子批，另外2 个工件1 将放入第2 个子批。采用带动态连续加工策略时，在工序3 上工件1 的第2 个子批连续加工的情况下，先到达的这2 个工件可提前加工，因此此子批比不带动态连续加工策略时的开始加工时间早了16 个单位时间，由此可以验证动态连续加工策略的有效性。

图2 加工序列为 π1 时两种策略下的甘特图Fig. 2 Gantt charts under two strategies when the processing sequence is π1

3.4 算法性能比较与分析

为了验证DWWO 算法的有效性，选取不同规模的算例，并与果蝇优化算法(FOA)[20]、变邻域改进遗传算法(IGA_VNS)[16]、基本水波优化算法(WWO)[11]、候鸟优化算法(MMBO)[21]进行了对比。所有算法都具有相同的编程语言和实验环境且终止条件都为迭代150 次。离散水波优化算法的参数设置如3.1 节所述，其他算法的参数根据其文献确定。所有算法都运行10 次，实验结果见表3。表中各项性能指标的最优值用黑体显示。算法性能采用相对百分比偏差平均值(MRPD)、相对百分比偏差标准差 (SDRPD)、相对百分比偏差最优值(BRPD)进行评估。计算公式如下：

其中：ck表示算法第k次运算的结果(k=1,2,···,s)；c∗为所有算法得到的最优值。

从表3 中可以看出，对于较小规模的算例，5 种算法的结果相差不大，说明对于小规模算例，这5 种算法都能取得最优值且性能较稳定；但随着规模的增加，DWWO 算法的优势逐渐体现出来，针对工件数为15、20、35 和50，工序数为10 和15 的8 个较大规模的算例，DWWO 算法在其中8 个算例都获得了最小的MRPD 和BRPD 值，且在其中5 个算例上获得了最小的SDRPD 值，说明DWWO 算法在求解较大规模问题时，寻优性能和稳定性相对优于其他对比算法。对于所有规模的问题，WWO 算法只在其中10 个较小规模的算例中取得了最小的BRPD 值，而DWWO 算法在24 个算例中都取得了最小的BRPD 值，说明DWWO 算法的搜索质量相比于WWO 算法有了极大的改善。

表3 DWWO，FOA，MMBO，WWO，IGA_V 算法对比结果Table 3 Comparison results of DWWO, FOA, MMBO, WWO and IGA_V

图3 示出了5 种算法针对4 种不同规模实例的收敛曲线。在求解不同规模的问题时，DWWO 算法在第1 代都具有较好的解，主要是由于DWWO 算法采用了NEH 方法对种群进行初始化，从而提高了初始解的质量；DWWO 算法的收敛曲线在迭代前期会发生较大幅度的下降，之后会表现出逐步下降的趋势。主要是因为算法在寻优过程中采用块最优插入及多邻域搜索提高了操作算子的性能，增强了算法的局部搜索能力，使算法能够快速跳出局部最优；在每代中不断替换当前代的最差解，提升了DWWO 算法解的整体质量从而加快了收敛速度，提高了全局搜索能力。但是在求解 50 ×15 的算例时，DWWO 算法的收敛速度却较慢，从图3(d) 也可以看出，DWWO 算法的收敛曲线在100 代左右下降趋势才有所减缓。

图3 各算法求解不同规模问题的迭代曲线Fig. 3 Iterative curves of each algorithm for solving problems of different scales

相对于其他算法，DWWO 算法具有更好的解决带批处理的混合流水车间批量流调度问题的能力，其稳定性和收敛能力均较优，且由于DWWO 算法对操作算子进行了改进并提出了一种替换差解操作，因此具有较优的局部和全局搜索能力。

4 结 论

本文在考虑机器可分离准备时间的情况下，以最大完工时间最小化为优化目标，研究了带批处理的混合流水车间批量流调度问题：

（1）结合实际生产中批处理机与离散机混合加工的特点，首次提出了一种可变分批方法将两种机器的加工方式相结合对工件进行分批。

（2）针对可变分批下工件在不同工序批量不同这一特点，提出了一种动态连续加工策略，能够减小工件的等待时间，提高生产效率。

（3）提出了一种离散水波优化算法，采用基于工件在第一道工序上加工顺序的编码方案，并设计了4 种解码方案确定后续工序工件的加工顺序及机器的选择；采用启发式算法提高种群初始解质量；利用块最优插入、交叉操作、多邻域搜索分别对基本操作进行了改进，并加入替换差解操作以协调算法的局部和全局搜索的能力，提高了算法的收敛速度。

（4）采用实验设计方法生成随机算例，并对算法参数进行标定，测试了本文算法的性能。实验结果验证了DWWO 算法求解带批处理的混合流水车间批量流调度问题的可行性和有效性。