零空闲流水车间问题中启发式规则的研究与改进＊

李 杰，李艳武

（重庆三峡学院电子与信息工程学院，重庆 404100）

流水车间排列问题（ Permutation Flowshop Scheduling Problem，PFSP）是一个著名的排列优化问题，已经被证明是一个NP 难[1]（非确定性多项式）问题。在PFSP 问题中，n个工件需要依次在固定顺序的m个机器上加工，n个工件加工顺序一旦确定，所有的机器必须按照相同的工件排列顺序加工，因此，其目的是根据给定的优化准则找到作业的最优排列。当给定约束条件，要求在每台机器上工件处理之间没有空闲时间，机器一旦开启，就要连续加工工件，则PFSP问题就进一步扩展为零空闲流水车间问题（No-idle Permutation Flowshop Scheduling Problem，NIFSP）。在NIFSP 问题中，以最小化最大完工时间为目标的排列寻优又被表示为Fm/prmu，no-idle/Cmax。在实际应用中，NIFSP 问题在一些使用昂贵生产机器的产业链中更为常见，机器一旦开启便需要持续工作，直到完成所有工件。一些产业的产品特性也需要在加工工件过程中不能中断机器，例如传统行业中的陶瓷熔块生产、玻璃纤维加工等。而在技术不断发展的今天，机器承担了越来越多不同的加工作业，NIFSP 问题不得不成为一个机器在生产过程中需要考虑到的重要约束条件。

1982 年，ADIRI 和POHORYLES 首次考虑了最小化总完工时间的零空闲流水车间调度问题。同年，VACHAJITPAN 首次考虑了以makespan 为目标的NIFSP 问题，采用混合整数规划（Mixed Integer Programming，MIP）进行建模，但只能求解较小规模的算例。WOOLLAM 首次采用几种启发式规则来求解NIFSP 问题。直到2007 年，RUBÉN[2]提出的迭代贪婪算法（Iterative Greedy，IG）被认为是解决流水车间问题的有效算法，其中使用的启发式规则就是NEH[3]，2019年SHEN[4]等提出了一种通用变量邻域搜索算法（GVNS）来解决基于最大化准则的零空闲流水车间调度问题，GVNS 的初始解是使用FRB5[5]启发式方法生成的。

针对NIFSP 问题，研究了NEH 和FRB5 启发式规则，并提出改进的启发式规则FRB5k，通过3 种启发式规则的独立对比实验比较获得初始解的性能，并将3种启发式规则代入迭代贪婪算法中，比较整体算法在使用不同启发式规则的获得最终解的性能。

1 NEH 和FRB5 研究与改进算法FRB5k

在NIFSP 中，以makespan 为目标的Fm/prmu，no-idle/Cmax问题描述如下：假定n个工件的集合为N={1，2，…，n}，m台机器的集合为M={M1，M2，…，Mm}。n个工件要按照相同的顺序在m个机器上依次加工，在任意时刻，每台机器最多加工一个工件，每个工件最多只能在一台机器上加工。对于零空闲约束条件，要求机器一旦开始加工，就不允许中断，每台机器上的2 个连续工件加工之间不允许有空闲时间。调度的目标是最小化最大完工时间，即从M1加工第一个工件到Mm加工完最后一个工件的时间。

启发式规则就是找到一个工件排列，使得makespan 最小。用π={π（1），π（2），…，π（n）}表示一个工件排列，即为一个调度解，表示工件按π（1）到π（n）的顺序依次进行加工，令Cmax（π）表示π对应的makespan。关于Cmax（π）的计算，具体步骤请参照文献[6]。

1.1 NEH 启发式规则

NEH 启发式规则包含2 个阶段：在第一阶段，工件按各自在所有机器上的处理总时间进行降序排序获得α={α（1），α（2），…，α（n）}；在第二阶段，根据第一阶段的排序，从第二个工件开始依次插入到π={α（1）}，评估插入的所有可能位置以获得较优makespan，再按照排序将第三个工件插入到已确定好的工件排序中的所有可能位置，计算makespan，找到最优makespan 的位置插入工件，重复插入操作，直到所有工件都被插入，得到完整的调度解π。NEH 伪代码如图1 所示。

图1 NEH 和FRB5 伪代码

1.2 FRB5 启发式规则

FRB5 启发式算法获得初始解，与NEH 不同的是，每插入一个工件，FRB5 都对插入后序列做一次本地搜索，对插入后的工件排序，再按照顺序依次移除一个工件，将其插入到所有可能位置，找到所有可能位置中makespan 最小的位置插入移除的工件，直到所有的工件都被重新移除插入。FRB5 伪代码如图1 所示。

1.3 改进的FRB5k 启发式规则

针对FRB5 规则，每插入一个工件进行一次本地搜索会极大地消耗CPU 计算时间，对于零空闲流水车间问题模型，涉及到的工件达500 个，虽然获得的初始解优于NEH，但消耗的计算时间是NEH 的数倍。由此，提出的改进启发式规则FRB5k。不同于FRB5，采用FRB5k 规则，当插入工件后，整体工件数达到k的倍数后，进行一次本地搜索，例如，当k=5，即表明当序列中工件数为5，10，15，20…时才会进行一次本地搜索。减少了本地搜索的次数，为了不降低初始解的质量，当所有的工件排列完成后再进行一次本地搜索。FRB5k 伪代码如图2 所示。

图2 FRB5k 伪代码

2 实验环境与对比实验方案

2.1 实验环境

所有启发式规则的对比实验都在2021 版本的IDEA 平台环境中使用Java 编码，在具有6 核12 逻辑处理器的Intel（R）Core（TM）i5-10500（CPU 主频3.10 GHz）上进行。并且对于3 种启发式规则的编码，除了改进的阶段不同，其余都保持一致。

2.2 对比实验方案

根据RUIZ 提出的算例规模，分别为工件数N={50，100，150，200，250，300，400，500}，机器数M={10，20，30，40，50}，每种规模包括5 个算例，一共10×5×5=250 个算例，算例和目前最优解可以从http://soa.iti.es 上获取。对于每个参数组合的解的质量评判，采用相对百分比偏差（Relative Percentage Deviation，RPD）来衡量，RPD 计算公式为：

式（1）中：Mh为启发式规则得到的算例makespan 值；Mbest为已知目前找到的最优makespan 值。

实验一：3 种启发式规则的独立实验设计如下，250个算例分别在3 种启发式规则下重复计算5 次，记录计算每个算例得到初始解的时间。由于FRB5k 启发式算法中的k是个变量，分别取k=5，10（分别记IG_FRB5k_5、IG_FRB5k_10）。每个算例的5 个结果和已知最优结果计算RPD，再求平均，得到每个算例的平均相对百分比偏差ARPD，再通过多方差（ANOVA）分析比较3 种启发式规则独立实验的性能。

实验二：为了比较3 种启发式规则在完整寻优框架中的性能，使用经典有效的迭代贪婪算法框架（IG算法），在IG 算法的初始化阶段分别使用NEH（记为IG_NEH）、FRB5（记为IG_FRB5）、FRB5k（k的具体取值根据实验一的独立实验结果选取最优值）。250 个算例同样在使用了不同初始解获得方案的IG 框架算法中分别计算5 次，因为不同的启发式规则消耗的CPU 时间不同，为了验证出消耗的时间对整体算法框架性能的影响，整体IG 算法框架对每个组合算例的计算时间是固定的，计算终止标准是CPU 时间为n·m·t/2（ms），n、m分别表示该算例规模下的工件数和机器数，设置t=20。这样就保证了不同规模的算例都有相对合理的计算时间，不会导致小规模算例计算时间溢出得到优解，大规模算例计算时间不足得到的解较差。由于不同启发式方案的IG 算法对每个算例的整体计算时间相同，所以在初始解获得阶段的启发式规则如果消耗时间过多，则会影响IG 算法迭代的时间，则会影响最终解的质量。得到的最终解同样和已知最优解对比计算得到ARPD，再通过ANOVA 分析比较3 种启发式规则在IG 算法中的性能。

通过以上2 个实验，能够从不同维度验证3 种启发式规则的性能，重复5 次的计算也消除了寻优过程中的偶然性，多方差分析也能更加直观地比较出3 种规则的性能差异。

3 实验结果分析

3.1 独立实验结果分析

运用3 种启发式规则分别重复计算250 个算例5次，计算得到的解与当前最优解得到5 次的相对百分比偏差（RPD）并记录算法完成250 个算例的时间。实验数据对比表现如图3 所示，横坐标表示3 种启发式在250 个算例上平均完成每个算例的CPU 时间，纵坐标表示3 种启发式所得解的平均相对百分比偏差（ARPD）。

图3 启发式规则独立实验结果

NEH 获得初始解消耗的时间最少，为0.115 s，但初始解的ARPD 最大，为5.56%，说明与一致最优解相差较大。FRB5 获得的初始解的ARPD 最小，为2.03%，但是从消耗的CPU 时间5.33 s 可知，远高于NEH。可以看出FRB5k 相比较FRB5 和NEH，FRB5k_10 的ARPD 为2.27%，FRB5k_5 的ARPD 为2.15%，略大于FRB5，但是消耗的CPU 时间比FRB5少了数倍，性能和CPU 消耗时间更均衡。所以在实验二的IG 算法框架中，选择FRB5k_5 作为IG 的初始化阶段，记为IG_FRB5k_5。

3.2 嵌入IG 算法实验结果分析

使用不同初始化方案的IG 算法实验结果如图4 所示，从图中数据可知，在95%的置信区间下，改进的FRB5k 启发式规则在IG 算法中的性能优于NEH 和FRB5。

图4 嵌入IG 算法实验结果95%置信区间的APRD

为了比较3 种启发式在IG 算法中对最优解的搜寻性能，通过ANOVA 分析了IG 利用不同启发式所找到的最优解，并计算了最优结果的min_RPD。具体的实验结果数据如表1 所示。

表1 嵌入IG 算法实验结果

从表1 中数据可知，IG_FRB5k_5 搜寻到的最优解与已知最优解的偏差百分比为0.41%，优于IG_NEH的0.45%以及IG_FRB5 的0.44%。

从3 种不同启发式规则的独立实验和嵌入IG 算法框架的整体实验都得出，提出的改进启发式规则FRB5k 能获得更优的初始解，达到了性能和CPU 时间消耗的平衡。同时在整体实验中改进了经典IG 算法的性能，提高了IG 算法对流水车间问题的寻优能力。

4 总结

对于大多数现实场景下机器运行中零空闲的约束，在NIFSP 问题模型中，提出的改进的FRB5k 启发式规则对于工件加工顺序以及加工流程安排的寻优降低了工件加工的最大完工时间。通过独立实验，在250 个针对性的算例中，对最优解的搜索性能明显优于NEH，并且改进的初始阶段启发式规则FRB5k 对于初始解的优化和CPU 消耗时间之间的平衡性明显优于FRB5 规则。在将3 种规则嵌入到IG 框架中的对比实验结果中也能发现，FRB5k 对算法整体性能的提升优于其他2种启发式规则，提升了算法的寻优性能。在工厂模型多样化的今天，对机器的约束条件也越来越多，针对性的建模算例规模也越来越大。FRB5k 的综合性能以及k值可变的灵活性的优势更加显著。