零空閑流水車間問題中啟發(fā)式規(guī)則的研究與改進(jìn)＊

李 杰，李艷武

（重慶三峽學(xué)院電子與信息工程學(xué)院，重慶 404100）

流水車間排列問題（ Permutation Flowshop Scheduling Problem，PFSP）是一個(gè)著名的排列優(yōu)化問題，已經(jīng)被證明是一個(gè)NP 難[1]（非確定性多項(xiàng)式）問題。在PFSP 問題中，n個(gè)工件需要依次在固定順序的m個(gè)機(jī)器上加工，n個(gè)工件加工順序一旦確定，所有的機(jī)器必須按照相同的工件排列順序加工，因此，其目的是根據(jù)給定的優(yōu)化準(zhǔn)則找到作業(yè)的最優(yōu)排列。當(dāng)給定約束條件，要求在每臺機(jī)器上工件處理之間沒有空閑時(shí)間，機(jī)器一旦開啟，就要連續(xù)加工工件，則PFSP問題就進(jìn)一步擴(kuò)展為零空閑流水車間問題（No-idle Permutation Flowshop Scheduling Problem，NIFSP）。在NIFSP 問題中，以最小化最大完工時(shí)間為目標(biāo)的排列尋優(yōu)又被表示為Fm/prmu，no-idle/Cmax。在實(shí)際應(yīng)用中，NIFSP 問題在一些使用昂貴生產(chǎn)機(jī)器的產(chǎn)業(yè)鏈中更為常見，機(jī)器一旦開啟便需要持續(xù)工作，直到完成所有工件。一些產(chǎn)業(yè)的產(chǎn)品特性也需要在加工工件過程中不能中斷機(jī)器，例如傳統(tǒng)行業(yè)中的陶瓷熔塊生產(chǎn)、玻璃纖維加工等。而在技術(shù)不斷發(fā)展的今天，機(jī)器承擔(dān)了越來越多不同的加工作業(yè)，NIFSP 問題不得不成為一個(gè)機(jī)器在生產(chǎn)過程中需要考慮到的重要約束條件。

1982 年，ADIRI 和POHORYLES 首次考慮了最小化總完工時(shí)間的零空閑流水車間調(diào)度問題。同年，VACHAJITPAN 首次考慮了以makespan 為目標(biāo)的NIFSP 問題，采用混合整數(shù)規(guī)劃（Mixed Integer Programming，MIP）進(jìn)行建模，但只能求解較小規(guī)模的算例。WOOLLAM 首次采用幾種啟發(fā)式規(guī)則來求解NIFSP 問題。直到2007 年，RUBéN[2]提出的迭代貪婪算法（Iterative Greedy，IG）被認(rèn)為是解決流水車間問題的有效算法，其中使用的啟發(fā)式規(guī)則就是NEH[3]，2019年SHEN[4]等提出了一種通用變量鄰域搜索算法（GVNS）來解決基于最大化準(zhǔn)則的零空閑流水車間調(diào)度問題，GVNS 的初始解是使用FRB5[5]啟發(fā)式方法生成的。

針對NIFSP 問題，研究了NEH 和FRB5 啟發(fā)式規(guī)則，并提出改進(jìn)的啟發(fā)式規(guī)則FRB5k，通過3 種啟發(fā)式規(guī)則的獨(dú)立對比實(shí)驗(yàn)比較獲得初始解的性能，并將3種啟發(fā)式規(guī)則代入迭代貪婪算法中，比較整體算法在使用不同啟發(fā)式規(guī)則的獲得最終解的性能。

1 NEH 和FRB5 研究與改進(jìn)算法FRB5k

在NIFSP 中，以makespan 為目標(biāo)的Fm/prmu，no-idle/Cmax問題描述如下：假定n個(gè)工件的集合為N={1，2，…，n}，m臺機(jī)器的集合為M={M1，M2，…，Mm}。n個(gè)工件要按照相同的順序在m個(gè)機(jī)器上依次加工，在任意時(shí)刻，每臺機(jī)器最多加工一個(gè)工件，每個(gè)工件最多只能在一臺機(jī)器上加工。對于零空閑約束條件，要求機(jī)器一旦開始加工，就不允許中斷，每臺機(jī)器上的2 個(gè)連續(xù)工件加工之間不允許有空閑時(shí)間。調(diào)度的目標(biāo)是最小化最大完工時(shí)間，即從M1加工第一個(gè)工件到Mm加工完最后一個(gè)工件的時(shí)間。

啟發(fā)式規(guī)則就是找到一個(gè)工件排列，使得makespan 最小。用π={π（1），π（2），…，π（n）}表示一個(gè)工件排列，即為一個(gè)調(diào)度解，表示工件按π（1）到π（n）的順序依次進(jìn)行加工，令Cmax（π）表示π對應(yīng)的makespan。關(guān)于Cmax（π）的計(jì)算，具體步驟請參照文獻(xiàn)[6]。

1.1 NEH 啟發(fā)式規(guī)則

NEH 啟發(fā)式規(guī)則包含2 個(gè)階段：在第一階段，工件按各自在所有機(jī)器上的處理總時(shí)間進(jìn)行降序排序獲得α={α（1），α（2），…，α（n）}；在第二階段，根據(jù)第一階段的排序，從第二個(gè)工件開始依次插入到π={α（1）}，評估插入的所有可能位置以獲得較優(yōu)makespan，再按照排序?qū)⒌谌齻€(gè)工件插入到已確定好的工件排序中的所有可能位置，計(jì)算makespan，找到最優(yōu)makespan 的位置插入工件，重復(fù)插入操作，直到所有工件都被插入，得到完整的調(diào)度解π。NEH 偽代碼如圖1 所示。

圖1 NEH 和FRB5 偽代碼

1.2 FRB5 啟發(fā)式規(guī)則

FRB5 啟發(fā)式算法獲得初始解，與NEH 不同的是，每插入一個(gè)工件，F(xiàn)RB5 都對插入后序列做一次本地搜索，對插入后的工件排序，再按照順序依次移除一個(gè)工件，將其插入到所有可能位置，找到所有可能位置中makespan 最小的位置插入移除的工件，直到所有的工件都被重新移除插入。FRB5 偽代碼如圖1 所示。

1.3 改進(jìn)的FRB5k 啟發(fā)式規(guī)則

針對FRB5 規(guī)則，每插入一個(gè)工件進(jìn)行一次本地搜索會極大地消耗CPU 計(jì)算時(shí)間，對于零空閑流水車間問題模型，涉及到的工件達(dá)500 個(gè)，雖然獲得的初始解優(yōu)于NEH，但消耗的計(jì)算時(shí)間是NEH 的數(shù)倍。由此，提出的改進(jìn)啟發(fā)式規(guī)則FRB5k。不同于FRB5，采用FRB5k 規(guī)則，當(dāng)插入工件后，整體工件數(shù)達(dá)到k的倍數(shù)后，進(jìn)行一次本地搜索，例如，當(dāng)k=5，即表明當(dāng)序列中工件數(shù)為5，10，15，20…時(shí)才會進(jìn)行一次本地搜索。減少了本地搜索的次數(shù)，為了不降低初始解的質(zhì)量，當(dāng)所有的工件排列完成后再進(jìn)行一次本地搜索。FRB5k 偽代碼如圖2 所示。

圖2 FRB5k 偽代碼

2 實(shí)驗(yàn)環(huán)境與對比實(shí)驗(yàn)方案

2.1 實(shí)驗(yàn)環(huán)境

所有啟發(fā)式規(guī)則的對比實(shí)驗(yàn)都在2021 版本的IDEA 平臺環(huán)境中使用Java 編碼，在具有6 核12 邏輯處理器的Intel（R）Core（TM）i5-10500（CPU 主頻3.10 GHz）上進(jìn)行。并且對于3 種啟發(fā)式規(guī)則的編碼，除了改進(jìn)的階段不同，其余都保持一致。

2.2 對比實(shí)驗(yàn)方案

根據(jù)RUIZ 提出的算例規(guī)模，分別為工件數(shù)N={50，100，150，200，250，300，400，500}，機(jī)器數(shù)M={10，20，30，40，50}，每種規(guī)模包括5 個(gè)算例，一共10×5×5=250 個(gè)算例，算例和目前最優(yōu)解可以從http://soa.iti.es 上獲取。對于每個(gè)參數(shù)組合的解的質(zhì)量評判，采用相對百分比偏差（Relative Percentage Deviation，RPD）來衡量，RPD 計(jì)算公式為：

式（1）中：Mh為啟發(fā)式規(guī)則得到的算例makespan 值；Mbest為已知目前找到的最優(yōu)makespan 值。

實(shí)驗(yàn)一：3 種啟發(fā)式規(guī)則的獨(dú)立實(shí)驗(yàn)設(shè)計(jì)如下，250個(gè)算例分別在3 種啟發(fā)式規(guī)則下重復(fù)計(jì)算5 次，記錄計(jì)算每個(gè)算例得到初始解的時(shí)間。由于FRB5k 啟發(fā)式算法中的k是個(gè)變量，分別取k=5，10（分別記IG_FRB5k_5、IG_FRB5k_10）。每個(gè)算例的5 個(gè)結(jié)果和已知最優(yōu)結(jié)果計(jì)算RPD，再求平均，得到每個(gè)算例的平均相對百分比偏差A(yù)RPD，再通過多方差（ANOVA）分析比較3 種啟發(fā)式規(guī)則獨(dú)立實(shí)驗(yàn)的性能。

實(shí)驗(yàn)二：為了比較3 種啟發(fā)式規(guī)則在完整尋優(yōu)框架中的性能，使用經(jīng)典有效的迭代貪婪算法框架（IG算法），在IG 算法的初始化階段分別使用NEH（記為IG_NEH）、FRB5（記為IG_FRB5）、FRB5k（k的具體取值根據(jù)實(shí)驗(yàn)一的獨(dú)立實(shí)驗(yàn)結(jié)果選取最優(yōu)值）。250 個(gè)算例同樣在使用了不同初始解獲得方案的IG 框架算法中分別計(jì)算5 次，因?yàn)椴煌膯l(fā)式規(guī)則消耗的CPU 時(shí)間不同，為了驗(yàn)證出消耗的時(shí)間對整體算法框架性能的影響，整體IG 算法框架對每個(gè)組合算例的計(jì)算時(shí)間是固定的，計(jì)算終止標(biāo)準(zhǔn)是CPU 時(shí)間為n·m·t/2（ms），n、m分別表示該算例規(guī)模下的工件數(shù)和機(jī)器數(shù)，設(shè)置t=20。這樣就保證了不同規(guī)模的算例都有相對合理的計(jì)算時(shí)間，不會導(dǎo)致小規(guī)模算例計(jì)算時(shí)間溢出得到優(yōu)解，大規(guī)模算例計(jì)算時(shí)間不足得到的解較差。由于不同啟發(fā)式方案的IG 算法對每個(gè)算例的整體計(jì)算時(shí)間相同，所以在初始解獲得階段的啟發(fā)式規(guī)則如果消耗時(shí)間過多，則會影響IG 算法迭代的時(shí)間，則會影響最終解的質(zhì)量。得到的最終解同樣和已知最優(yōu)解對比計(jì)算得到ARPD，再通過ANOVA 分析比較3 種啟發(fā)式規(guī)則在IG 算法中的性能。

通過以上2 個(gè)實(shí)驗(yàn)，能夠從不同維度驗(yàn)證3 種啟發(fā)式規(guī)則的性能，重復(fù)5 次的計(jì)算也消除了尋優(yōu)過程中的偶然性，多方差分析也能更加直觀地比較出3 種規(guī)則的性能差異。

3 實(shí)驗(yàn)結(jié)果分析

3.1 獨(dú)立實(shí)驗(yàn)結(jié)果分析

運(yùn)用3 種啟發(fā)式規(guī)則分別重復(fù)計(jì)算250 個(gè)算例5次，計(jì)算得到的解與當(dāng)前最優(yōu)解得到5 次的相對百分比偏差（RPD）并記錄算法完成250 個(gè)算例的時(shí)間。實(shí)驗(yàn)數(shù)據(jù)對比表現(xiàn)如圖3 所示，橫坐標(biāo)表示3 種啟發(fā)式在250 個(gè)算例上平均完成每個(gè)算例的CPU 時(shí)間，縱坐標(biāo)表示3 種啟發(fā)式所得解的平均相對百分比偏差（ARPD）。

圖3 啟發(fā)式規(guī)則獨(dú)立實(shí)驗(yàn)結(jié)果

NEH 獲得初始解消耗的時(shí)間最少，為0.115 s，但初始解的ARPD 最大，為5.56%，說明與一致最優(yōu)解相差較大。FRB5 獲得的初始解的ARPD 最小，為2.03%，但是從消耗的CPU 時(shí)間5.33 s 可知，遠(yuǎn)高于NEH。可以看出FRB5k 相比較FRB5 和NEH，F(xiàn)RB5k_10 的ARPD 為2.27%，F(xiàn)RB5k_5 的ARPD 為2.15%，略大于FRB5，但是消耗的CPU 時(shí)間比FRB5少了數(shù)倍，性能和CPU 消耗時(shí)間更均衡。所以在實(shí)驗(yàn)二的IG 算法框架中，選擇FRB5k_5 作為IG 的初始化階段，記為IG_FRB5k_5。

3.2 嵌入IG 算法實(shí)驗(yàn)結(jié)果分析

使用不同初始化方案的IG 算法實(shí)驗(yàn)結(jié)果如圖4 所示，從圖中數(shù)據(jù)可知，在95%的置信區(qū)間下，改進(jìn)的FRB5k 啟發(fā)式規(guī)則在IG 算法中的性能優(yōu)于NEH 和FRB5。

圖4 嵌入IG 算法實(shí)驗(yàn)結(jié)果95%置信區(qū)間的APRD

為了比較3 種啟發(fā)式在IG 算法中對最優(yōu)解的搜尋性能，通過ANOVA 分析了IG 利用不同啟發(fā)式所找到的最優(yōu)解，并計(jì)算了最優(yōu)結(jié)果的min_RPD。具體的實(shí)驗(yàn)結(jié)果數(shù)據(jù)如表1 所示。

表1 嵌入IG 算法實(shí)驗(yàn)結(jié)果

從表1 中數(shù)據(jù)可知，IG_FRB5k_5 搜尋到的最優(yōu)解與已知最優(yōu)解的偏差百分比為0.41%，優(yōu)于IG_NEH的0.45%以及IG_FRB5 的0.44%。

從3 種不同啟發(fā)式規(guī)則的獨(dú)立實(shí)驗(yàn)和嵌入IG 算法框架的整體實(shí)驗(yàn)都得出，提出的改進(jìn)啟發(fā)式規(guī)則FRB5k 能獲得更優(yōu)的初始解，達(dá)到了性能和CPU 時(shí)間消耗的平衡。同時(shí)在整體實(shí)驗(yàn)中改進(jìn)了經(jīng)典IG 算法的性能，提高了IG 算法對流水車間問題的尋優(yōu)能力。

4 總結(jié)

對于大多數(shù)現(xiàn)實(shí)場景下機(jī)器運(yùn)行中零空閑的約束，在NIFSP 問題模型中，提出的改進(jìn)的FRB5k 啟發(fā)式規(guī)則對于工件加工順序以及加工流程安排的尋優(yōu)降低了工件加工的最大完工時(shí)間。通過獨(dú)立實(shí)驗(yàn)，在250 個(gè)針對性的算例中，對最優(yōu)解的搜索性能明顯優(yōu)于NEH，并且改進(jìn)的初始階段啟發(fā)式規(guī)則FRB5k 對于初始解的優(yōu)化和CPU 消耗時(shí)間之間的平衡性明顯優(yōu)于FRB5 規(guī)則。在將3 種規(guī)則嵌入到IG 框架中的對比實(shí)驗(yàn)結(jié)果中也能發(fā)現(xiàn)，F(xiàn)RB5k 對算法整體性能的提升優(yōu)于其他2種啟發(fā)式規(guī)則，提升了算法的尋優(yōu)性能。在工廠模型多樣化的今天，對機(jī)器的約束條件也越來越多，針對性的建模算例規(guī)模也越來越大。FRB5k 的綜合性能以及k值可變的靈活性的優(yōu)勢更加顯著。