零空闲流水车间问题中启发式规则的研究与改进_李杰.pdf

Science and Technology&Innovation科技与创新2023 年 第 04 期13文章编号：2095-6835（2023）04-0013-03零空闲流水车间问题中启发式规则的研究与改进李 杰，李艳武（重庆三峡学院电子与信息工程学院，重庆 404100）摘要：在流水车间问题中，通过启发式规则获得初始解的优劣是影响整体算法性能的重要因素。但目前被广泛使用的有效启发式规则（如 NEH、FRB5 等）都不能在获得初始解的质量和消耗 CPU 时间上取得平衡，在对这 2 种启发式规则研究后，改进了获得初始解时的邻域搜索，使改进的启发式规则在获得较好初始解的同时减少了 CPU 消耗时间，嵌入到迭代贪婪算法后提升了整体算法的性能。关键词：零空闲流水车间；启发式规则；邻域搜索；迭代贪婪算法中图分类号：TP297文献标志码：ADOI：10.15913/ki.kjycx.2023.04.004流 水 车 间 排 列 问 题（Permutation FlowshopScheduling Problem，PFSP）是一个著名的排列优化问题，已经被证明是一个 NP 难1（非确定性多项式）问题。在 PFSP 问题中，n 个工件需要依次在固定顺序的m 个机器上加工，n 个工件加工顺序一旦确定，所有的机器必须按照相同的工件排列顺序加工，因此，其目的是根据给定的优化准则找到作业的最优排列。当给定约束条件，要求在每台机器上工件处理之间没有空闲时间，机器一旦开启，就要连续加工工件，则 PFSP问题就进一步扩展为零空闲流水车间问题（No-idlePermutation Flowshop Scheduling Problem，NIFSP）。在NIFSP 问题中，以最小化最大完工时间为目标的排列寻优又被表示为 Fm/prmu，no-idle/Cmax。在实际应用中，NIFSP 问题在一些使用昂贵生产机器的产业链中更为常见，机器一旦开启便需要持续工作，直到完成所有工件。一些产业的产品特性也需要在加工工件过程中不能中断机器，例如传统行业中的陶瓷熔块生产、玻璃纤维加工等。而在技术不断发展的今天，机器承担了越来越多不同的加工作业，NIFSP 问题不得不成为一个机器在生产过程中需要考虑到的重要约束条件。1982 年，ADIRI 和 POHORYLES 首次考虑了最小化总完工时间的零空闲流水车间调度问题。同年，VACHAJITPAN 首次考虑了以 makespan 为目标的NIFSP 问题，采用混合整数规划（Mixed IntegerProgramming，MIP）进行建模，但只能求解较小规模的算例。WOOLLAM 首次采用几种启发式规则来求解NIFSP 问题。直到 2007 年，RUBN2提出的迭代贪婪算法（Iterative Greedy，IG）被认为是解决流水车间问题的有效算法，其中使用的启发式规则就是 NEH3，2019年 SHEN4等提出了一种通用变量邻域搜索算法（GVNS）来解决基于最大化准则的零空闲流水车间调度问题，GVNS 的初始解是使用 FRB55启发式方法生成的。针对 NIFSP 问题，研究了 NEH 和 FRB5 启发式规则，并提出改进的启发式规则 FRB5k，通过 3 种启发式规则的独立对比实验比较获得初始解的性能，并将 3种启发式规则代入迭代贪婪算法中，比较整体算法在使用不同启发式规则的获得最终解的性能。1NEH 和 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。基金项目重庆市教育委员会科学技术研究项目（编号：KJQN202001224）科技与创新Science and Technology&Innovation142023 年 第 04 期1.1NEH 启发式规则NEH 启发式规则包含 2 个阶段：在第一阶段，工件按各自在所有机器上的处理总时间进行降序排序获得=（1），（2），（n）；在第二阶段，根据第一阶段的排序，从第二个工件开始依次插入到=（1），评估插入的所有可能位置以获得较优makespan，再按照排序将第三个工件插入到已确定好的工件排序中的所有可能位置，计算 makespan，找到最优 makespan 的位置插入工件，重复插入操作，直到所有工件都被插入，得到完整的调度解。NEH 伪代码如图 1 所示。图 1NEH 和 FRB5 伪代码1.2FRB5 启发式规则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 所示。图 2FRB5k 伪代码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 个算例，一共 1055=250 个算例，算例和目前最优解可以从http:/soa.iti.es 上获取。对于每个参数组合的解的质量评判，采用相对百分比偏差（Relative PercentageDeviation，RPD）来衡量，RPD 计算公式为：%100bestbesthRPD-=MMMM（1）式（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 时间为 nmt/2（ms），n、m 分别表示该算例规模下的工件数和机器数，设置 t=20。这样就保证了不同规模的算例都有相对合理的计算时间，不会导致小规模算例计算时间溢出得到优解，大规模算例计算时间不足得到的解较差。由于不同启发式方案的 IG 算法对每个算例的整体计算时间相同，所以在初始解获得阶段的启发式规则如果消耗时间过多，则会影响 IG 算法迭代的时间，则会Science and Technology&Innovation科技与创新2023 年 第 04 期15影响最终解的质量。得到的最终解同样和已知最优解对比计算得到 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。为了比较3种启发式在IG算法中对最优解的搜寻性能，通过 ANOVA 分析了 IG 利用不同启发式所找到的最优解，并计算了最优结果的 min_RPD。具体的实验结果数据如表 1 所示。图 4嵌入 IG 算法实验结果 95%置信区间的 APRD表 1嵌入 IG 算法实验结果算法IG_NEHIG_FRB5IG_FRB5k_5ARPD/（%）0.720.65061min_RPD/（%）0.450.440.41从表 1 中数据可知，IG_FRB5k_5 搜寻到的最优解与已知最优解的偏差百分比为 0.41%，优于 IG_NEH的 0.45%以及 IG_FRB5 的 0.44%。从3种不同启发式规则的独立实验和嵌入IG算法框架的整体实验都得出，提出的改进启发式规则FRB5k 能获得更优的初始解，达到了性能和 CPU 时间消耗的平衡。同时在整体实验中改进了经典 IG 算法的性能，提高了 IG 算法对流水车间问题的寻优能力