零空閑流水車間問題中啟發式規則的研究與改進＊

李 杰，李艷武

（重慶三峽學院電子與信息工程學院，重慶 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值可變的靈活性的優勢更加顯著。