變量塊內部迭代算法求解零空閑流水車間問題

收稿日期：2022-05-16；修回日期：2022-07-06" 基金項目：重慶市三峽庫區地質環境監測與災害預警重點實驗室開放基金資助項目（YB2020C0102）；重慶市教育委員會科學技術研究項目（KJQN202001224）

作者簡介：李杰（1996-），男，安徽馬鞍山人，碩士研究生，主要研究方向為流水車間調度問題、智能優化算法；李艷武（1985-），男（通信作者），湖北天門人，高級工程師，碩導，博士，主要研究方向為流水車間調度問題、智能優化算法、深度學習（andersonliyanwu@sina.com）.

摘 要：

零空閑流水車間問題（NIFSP）是流水車間問題中帶有約束條件的典型NP-hard問題，在大多數現實場景下，零空閑約束是對機器的基本要求。而目前關于NIFSP問題提出的算法對于較大規模算例、綜合性能及參數調整的靈活性較差。為此，以最小化最大完工時間為目標，提出了一種可變內部迭代算法VIIA。在VIIA的初始化階段，使用改進的FRB5產生初始解，提高了FRB5的效率，在保證算法性能的同時極大地縮短了CPU消耗時間。在破壞重建階段，通過增加對移除工件塊數量的內部迭代，從而靈活調整參數值。VIIA增大了鄰域搜索，以適應不同規模的算例。為了驗證VIIA算法的性能，將該算法與在流水車間調度問題中表現優秀的幾種算法進行了比較。實驗結果證明了VIIA在NIFSP問題求解上性能的優越性，并且在最優解的搜索上，性能明顯優于對比算法。

關鍵詞：零空閑流水車間問題；最大完工時間；內部迭代；迭代貪婪算法

中圖分類號：TP278"" 文獻標志碼：A""" 文章編號：1001-3695（2022）12-021-3667-06

doi："" 10.19734/j.issn.1001-3695.2022.05.0234

Variable-block internal iteration algorithm for solving no-idle

permutation flowshop scheduling problem

Li Jie， Li Yanwu

（College of Electronic amp; Information Engineering， Chongqing Three Gorges University， Chongqing 404100， China）

Abstract：

The no-idle flowshop problem （NIFSP） is a typical NP-hard problem with constraints in the flowshop problem. In most real-world scenarios， the no-idle constraint is the basic requirement for the machine. However， the current proposed algorithms on the NIFSP problem have poor flexibility in comprehensive performance and parameter adjustment， for large-scale instances. To this end， this paper proposed an variable block internal iteration algorithm named VIIA with the goal of minimizing the maximum makespan. In the initialization phase of VIIA， it used the improved FRB5 produced the initial solutions， which improved the efficiency of FRB5， and greatly reduced the CPU consumption time while ensuring the algorithm performance. In the destruction reconstruction phase， it increased the internal iteration of the number of removed variable blocks， thus flexibly adjusted the parameter values. VIIA increased the neighborhood search to adapted to different size of instances. In order to verify the performance of VIIA， the algorithm was compared with several algorithms that perform well in the flowshop scheduling problem. The experimental results demonstrate the superiority of VIIA in solving the NIFSP problem， and the performance of VIIA is obviously better than that of the comparison algorithms in the search of the optimal solution.

Key words：no-idle permutation flowshop scheduling problem; makespan criterion; internal iteration; iterated greedy algorithm

0 引言

流水車間排列問題（permutation flowshop scheduling problem，PFSP）是一個著名的排列優化問題，已經被證明是一個NP難（非確定性多項式）問題［1］。在PFSP中，n個工件需要依次在固定順序的m個機器上加工，n個工件加工順序一旦確定，所有的機器必須按照相同的工件排列順序加工，因此，其目的是根據給定的優化準則找到作業的最優排列。當給定約束條件，要求在每臺機器上工件處理之間沒有空閑時間，機器一旦開啟，就要連續加工工件，則PFSP就進一步擴展為零空閑流水車間問題。在NIFSP中，以最小化最大完工時間為目標的排列尋優又被表示為Fm/prmu，no-idle/Cmax。

實際應用中，NIFSP在一些使用昂貴生產機器的產業鏈中更為常見，機器一旦開啟便需要持續工作直到完成所有工件。一些產業的產品特性也需要工件在加工過程中不能中斷機器，例如傳統行業中的陶瓷熔塊生產、玻璃纖維加工等。而在技術不斷發展的今天，機器承擔了越來越多不同的加工作業，NIFSP不得不成為一個機器在生產過程中需要考慮到的重要約束條件。

1982年，文獻［2］首次考慮了最小化總完工時間的零空閑流水車間調度問題。同年，Vachajitpan［3］首次考慮了以makespan為目標的NIFSP，采用混合整數規劃（mixed integer programming，MIP）進行建模，但只能求解較小規模的算例。Woollam［4］首次采用幾種啟發式規則來求解NIFSP。直到2007年，Ruiz等人［5］提出的迭代貪婪算法（iterative greedy，IG）被認為是解決流水車間問題的有效算法。之后，許多文章都在IG算法框架的基礎上提出變體，并將其應用在不同約束條件的流水車間問題中。2008年針對NIFSP，文獻［6，7］分別提出了一種離散粒子群算法（HDPSO）和一種離散差分進化算法（DDEls）。這兩篇文章提出了一種加速方法，將評估鄰域插入的時間復雜度從O（mn3）降到O（mn2）。2009年，Ruiz等人［8］對于求解NIFSP中的Fm/prmu，no-idle/Cmax問題的各種算法進行了比較，并指出文獻［5］提出的IGLS算法用于該問題性能優于其他算法（包括HDPSO與DDEls）。2012年，文獻［9］針對該問題提出了一種混合離散微分進化算法（HDDE），并提出一種新的加速方法評估插入領域，將時間復雜度從O（mn3）降到O（mn2），并通過實驗表明，HDDE性能優于IGLS。2013年，Tasgetiren等人［10］利用差分進化算法來優化可變迭代貪婪算法的參數，提出了一種被稱為vIG_DE的算法來求解 NIFSP，并在 Ruzi基準測試集上進行了測試。結果表明，vIG_DE與HDDE、HDPSO算法相比性能有所提高。同年，文獻［11］又提出一種一般變量鄰域搜索的方法求解該問題（GVNS），GVNS是一種元啟發式算法，其中內循環操作一個可變的鄰域下降（variable neighbor decline，VND）算法，而外循環對當前的解執行一些擾動，并在外循環中使用一個簡單的插入和交換移動，而在VND中使用迭代貪婪（IG）和迭代局部搜索（iterate local search，ILS）算法作為鄰域結構，并且與vIG_DE進行了對比實驗，結果表明，其性能優于vIG_DE算法。2014年，Pan等人［12］在混合零空閑流水車間問題中使用Rad等人提出的FRB4k啟發式規則產生初始解，并在破壞重建階段借鑒了其思想提出了稱為eDC的破壞重建操作，在第七組完全零空閑流水車間問題中也取得了良好的效果。2015年，Shen等人［13］利用雙種群EDA方法求解了零空閑流水車間調度的總延遲問題。2017年，Shao等人［14］基于節點和邊緣直方圖的模因算法解決零空閑流水車間的總留時間問題。2017年，Ying等人［15］將IG算法應用于分布式的零空閑流水車間問題中。VBIH是2019年文獻［16］提出用于解決PFSP的，其塊結構的破壞重建階段為鄰域探索擴大了可能性，但還未曾應用在NIFSP中。同年，Shen等人［17］提出了一種新的通用變量鄰域搜索算法來解決基于最大化準則的零空閑流水車間調度問題，與文獻［11］不同，新的GVNS的初始解是使用FRB5啟發式方法生成的，在可變鄰域下降過程的內環中，使用了兩種有效的算法，即變體迭代貪婪算法和變量塊插入啟發式（VBIH）算法，但只與原始IG算法進行了比較，并沒有和VBIH算法比較。2020年，文獻［18］提出新的IG算法用于求解總延遲標準的零空閑流水車間問題，在性能上有所提升。國內對于流水車間調度問題的研究也很廣泛。2021年，劉麗娜等人［19］改進了麻雀搜索算法求解作業車間調度問題。這種與傳統進化類算法的結合同樣在求解NIFSP中取得了不錯的效果。2022年，羅浩嘉等人［20］改進了布谷鳥算法求解雙資源約束柔性車間調度問題，同年，尹瑞雪等人［21］改進了果蠅算法求解零空閑流水車間調度問題，都取得了不錯的效果。

針對NIFSP中的Fm/prmu，no-idle/Cmax問題，提出算法VIIA獲得更優解，將其與在同樣問題中表現良好的VBIH、GVNS算法以及在PFSP中性能良好的IG_RS和IG_ALL算法進行實驗比較。

1 零空閑流水車間調度問題闡述

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

Cmax（π;A，B）=maxk=1，2，…，n［∑kj=1aπ（j）+∑nj=kbπ（j）］（1）

啟發式規則就是找到一個工件排列，使得makespan最小。用π=（π（1），π（2），…，π（n））表示一個工件排列，即為一個調度解，表示工件按π（1）到π（n）的順序依次進行加工，令Cmax（π）表示π對應的makespan。關于Cmax（π）的計算，本文參照文獻［9］，用Cmax（π；A，B）表示具有兩臺機器A和B的F2/prmu/Cmax問題的調度解π對應的makespan，用aj和bj分別表示工件j在機器A和B上的加工時間。Cmax（π；A，B）是圖1所示的網格圖中關鍵路徑的長度，計算如式（1）所示。

為了簡化網格圖，假定π=（1，2，…，n），對應的網格圖如圖2所示。首先計算n個工件在第1、2臺機器上關鍵路徑下的最小完工時間，假設關鍵路徑為P11，P21，P22，…，P2n（Pij表示第i個工件在第j個機器上的加工時間），可得出Cmax（π；1，2）=P11+P21+P22+…+P2n。再計算n個工件在第2、3臺機器上關鍵路徑下的最小完工時間，假設關鍵路徑為P21，P22，…，P2n，P3n，Cmax（π；2，3）=P21+P22+…+P2n+P3n，當求解n個工件在前三個機器上的最小完工時間，假設工件在三臺機器上的關鍵路徑為P11，P21，P22，…，P2n，P3n，則最小完工時間為Cmax（π）=P11+P21+P22+…+P2n+P3n，只需將Cmax（π；1，2），Cmax（π；2，3）求和，再減去工件在中間一臺機器上的重復時間，即圖2中的-P21，-P22，…，-P2n。可見，Cmax（π）的計算可以通過多次Cmax（π；A，B）的計算實現。于是對于任意的π，Cmax（π）計算如式（2）所示。

Cmax（π）=∑m－1i=1Cmax（π;Mi，Mi+1）－∑m－1i=2 ∑nj=1pij（2）

其中：Cmax（π;Mi，Mi+1）表示具有兩臺機器Mi和Mi+1的F2/prmu/Cmax問題的調度解π對應的makespan。通過關鍵路徑方法（critical path methoh，CPM），Cmax（π）可以在O（mn）時間內計算得到，用Ⅱ表示所有工件排列的集合，則以makespan為目標的Fm/prmu，no-idle/Cmax問題即在Ⅱ中找到一個調度解π*，使得式（3）成立。

Cmax（π*）≤Cmax（π）" π∈N（3）

除了對makespan的求解，鄧冠龍等人通過利用CPM對于插入鄰域的評估也提出了新的加速方法，將時間復雜度從O（mn3）降到O（mn2）。假設s=π（i）是已經調度在π =（π（1），π（2），…，π（n））中的索引為i的工件，ω =（ω（1），ω（2），…，ω（n-1））是將s從π中刪除之后得到的子序列。用ω（s，h）表示將工件s插入到ω的第h（h≠i）個位置得到的排列，并用πsbinsert表示ω（s，h*），其中h*為最小化ω（s，h）的makespan（出現僵局則h*取值為較大的數）。

采用CPM來計算所有的ω（s，h）。首先，不失一般性，考慮Cmax（π；A，B）。用TA（π（j））和TB（π（j））來表示CPM的前向通道上工件π（j）在機器A和B上的最早完工時間；用LB（π（j））和LA（π（j））表示CPM的后向通道上工件在機器B和A上的最早完工時間。顯然，Cmax（π；A，B）=TB（π（n））=LA（π（1））。這些最早完工時間可由式（4）～（8）迭代計算得到。

TA（π（j））=TA（π（j－1））+aπ（j）（4）

TB（π（j））=max［TA（π（j）），TB（π（j－1））］+bπ（j） j=1，2，…，n（5）

LB（π（j））=LB（π（j+1））+bπ（j）（6）

LA（π（j））=max［LB（π（j）），LA（π（j+1））］+aπ（j）j=n，n－1，…，1（7）

TA（π（0））=TB（π（0））=LA（π（n+1））=LB（π（n+1））=0（8）

因此，所有的TA（π（j））、TB（π（j））、LB（π（j））、LA（π（j））都可以在Ο（card（π））=Ο（n）時間內計算得到。對給定的ω，TA（ω（j））、TB（ω（j））、LB（ω（j））、LA（ω（j））可在Ο（n）時間內由式（9）計算得到。

Cmax（ω（s，h）;A，B）=max［TA（ω（h－1））+

as+LA（ω（h）），TB（ω（h－1））+bs+（9）

LB（ω（h）），TA（ω（h－1））+as+bs+LB（ω（h））］

對于給定的工件排列π，它的插入鄰域包含（n-1）兩個解，如果不使用加速方法，全部評價需要時間O（mn3）。通過利用CPM，評價這個鄰域僅需O（mn2）時間的加速方法，具體詳細的步驟可參考文獻［9］。

2 VIIA算法

由于零空閑約束下的流水車間問題更加復雜，針對該問題設計的算例規模也更大，工件數和機器數達到了500×50，原始IG算法的破壞重建尋優階段對鄰域的搜索力度較小，每次只移除固定數量的工件，為了避免陷入局部最優，提出的VIIA算法依據IG算法框架［5］，在破壞重建階段通過擴大對鄰域的搜索，產生較大變化的新調度解，增大對最優解的搜索范圍。依據文獻［16］，在VIIA中引入塊插入的方式，擴大了對新調度解的尋優，并創新性地提出工件塊變量的內部迭代，將IG算法中的破壞移除工件和工件塊插入相結合，使每次移除的工件塊數量隨著調度解的優化以及不同算例規模進行靈活選擇。

2.1 調度解初始化階段

VIIA啟發式算法可概括為調度解初始化階段、破壞重建階段、鄰域搜索階段和接受準則四個階段。在初始化階段，對比的算法IG_RS［5］是使用NEH［22］產生初始解，VBIH［16］和對比算法IG_ALL［23］一樣，都是通過FRB5［24］啟發式算法獲得初始解。NEH啟發式規則包含兩個階段，在第一階段，工件按各自在所有機器上的處理總時間Pj進行降序排序獲得α={α（1），α（2），…，α（n）}。根據第一階段的排序，從第二個工件開始依次插入到π={α（1）}，評估插入的所有可能位置以獲得較優makespan，重復插入操作，直到所有工件都被插入，得到完整的調度解π。FRB5與NEH不同的是每插入一個工件，都對插入后序列進行一次本地搜索。

值得注意的是FRB5作為初始階段，雖然得到的調度解質量高于NEH，但消耗的CPU時間是NEH的數倍。在提出的VIIA算法中，對FRB5規則進行改進，記做IFRB5作為調度解的初始化階段。IFRB5啟發式規則不同于NEH和FRB5規則的是在第二階段，每當已排列工件數為5的倍數后才進行一次本地搜索，本地搜索是將已排列好的序列依次移除一個工件，并在剩余序列的所有可能位置中找到最優位置重新插入。NEH、FRB5以及改進的IFRB5偽代碼將在算法1中詳細闡述。

算法1 NEH和FRB5以及IFRB5偽代碼

輸入：n個工件子m個機器上的加工時間矩陣Pij。

輸出：工件初始調度解π。

a） 計算每個工件j在所有機器上的總時間Pj。

b） 按照Pj降序排列得到α={α（1），α（2），…，α（n）}。初始序列為π={α（1）}。

c） 按照α的順序將下一個工件插入到π中的所有可能位置，并計算最大完工時間，找到最優位置插入。

d） 對序列π進行本地搜索，依次移除π中工件，重新插入到最優位置。 //FRB5進行該步驟，NEH、IFRB5跳過該步驟

e） 每當對序列π中工件數為5的倍數進行一次本地搜索時，依次移除π中工件，重新插入到最優位置。

//IFRB5進行該步驟，FRB5、NEH跳過該步驟

f） 轉到步驟c），直到所有工件被插入，獲得完整調度解π。

g） 將完整調度解進行一次本地搜索。

//IFRB5進行該步驟，FRB5、NEH跳過該步驟

h） 輸出初始調度解π。

2.2 破壞重建階段

在破壞重建階段，對于增加了約束條件的零空閑流水車間調度問題，需要擴大對鄰域的搜索，避免算法陷入局部最優，這就需要更加多元且針對算例規模的方法對調度解進行破壞重建。用于對比的其他算法對于不同規模的算例每次迭代只移除固定數量的工件，對于NIFSP，可能會陷入局部最優。針對這一點，VIIA在破壞重建階段對于重新插入工件的數量d設置增加了內部迭代的方法靈活選擇，并且工件塊數量值d大小的選擇會根據調度解的makespan值在內部迭代增加。這樣保證了在規模較大的算例中，對調度解的破壞較大，避免陷入局部最優。除了內部迭代，在外部迭代中引入工件塊插入的方法，設置塊規模為b，將內部選擇的工件以塊方式重新插入。即外部迭代決定工件塊的規模大小，內部迭代決定工件塊的數量。這種內外部迭代的方法可隨著算例規模以及調度解目標值的改變對調度解進行適應性的破壞重建。

為了清晰地表述VIIA的工件塊變量內部迭代機制，流程如圖3所示。VIIA內外部迭代步驟如下：IFRB5產生初始解π，進入主循環；外部迭代循環中，在一個工件塊大小為b=bmin值下，內部循環將調度解π移除d=dmin個工件塊，存入Πb，剩余部分工件序列πp進行本地搜索，再將移除的d個工件塊依次重新插入到部分解的最優位置，得到新的完整解；再經過RIS鄰域搜索，得到本次迭代的新解；通過模擬退火接受準則，若新解得到改善，保持該d值，繼續下一次內部迭代，否則，d增加1，直到d=dmax。當一個b值下的d到達dmax而新解沒有改善時，外部迭代的b值加1，d從dmin重新開始進入內部迭代。與上述對比算法一樣，CPM加速法被應用其中。

算法2 VIIA偽代碼

輸入：參考序列πref；加工時間矩陣Pij。

輸出：算法尋找到的最優調度解πbest。

a） π=IFRB5（Pij）;πbest=π。

b） 進入主循環，工件塊規模b=bmin=1。

c） 進入內部迭代，移除工件塊數量d=dmin=1。

d） π′=π; 在π′中移除d個工件塊，儲存在工件塊集合Πb中，并獲得剩余部分序列πp。 //破壞階段

e） πp= local search（πp）。 //對部分序列進行本地搜索

f） 將集合Πb中的工件塊依次重新插入到πp的最優位置中，獲得完整調度解π1。 //重建階段

g） π2=RIS（π1，πref）。" //將π1再進行RIS鄰域搜索

h） if Cmax（π2）lt;Cmax（π），π=π2，if Cmax（π）lt;Cmax（πbest），πbest=π;

else if （random≤（exp{-（Cmax（π2）-Cmax（π））/Temperature}））， d=d+1，π=π2。

//模擬退火接受準則，依據隨機概率接受差解，避免陷入局部最優

i） if d ≤dmax; 轉到步驟d）;else b=b+1。/*移除的工件塊會因為沒有獲得更優解依次增加數量直到達到dmax，并結束此次內部迭代*/

j） if b ≤bmax;轉到步驟c）; else 輸出πbest。/*在新的工件塊規模b下進入新的內部迭代進行破壞重建階段，當達到bmax后，結束主循環，輸出算法找到的最優解πbest*/

2.3 鄰域搜索和接受準則

獲得的完整解使用參考序列插入鄰域［25］（referenced insertion scheme，RIS）的方法進行鄰域搜索，與IG算法中的鄰域搜索不同的是IG鄰域搜索是隨機移除工件，RIS是根據目前已找到的最優解序列順序πref依次移除工件π（k），偽代碼將在算法3中詳細闡述，具體細節見文獻［25］。

算法3 RIS鄰域搜索偽代碼

輸入：相應算例的已知最優解作為參考序列πref以及完整序列π。

輸出：優化后的調度解π。

a） count=1，i=1。//用于進入循環和依次迭代

b） 在π中找到工件π（k）=πref（i），并移除得到部分序列;將工件π（k）重新插入到部分序列的最優位置，獲得新的完整序列π′。

c） if Cmax（π′）lt;Cmax（π），π=π′，count=1;else count=count+1。

d） i=mod（i+1，n）。 //確保依次按照πref中的工件順序移除

e） if （countlt;n），轉到步驟b）;else 輸出優化后的調度解π。

經過鄰域搜索后的完整解使用類似模擬退火的接受準則判定新解是否被接受進入到下一輪的迭代，該規則是根據式（10）［26］計算的。

Temperature=T·∑mi=1 ∑nj=1pijn·m·10（10）

其中：T是一個需要調整的參數，是否接受新解的概率根據文獻［27］的e-（f（π′）-f（π））/Temperature公式給定。求解NIFSP中Fm/prmu，no-idle/Cmax問題的GVNS［17］即是在內循環（VND）中靈活選擇IG_ALL［23］和VBIH［16］算法，當其中一個算法獲得的新解根據以上接收準則沒有改善時，在內部下一次迭代時則選擇另一個算法，具體算法框架及內部迭代算法的參數設置見文獻［16］。

3 VIIA參數調優

VIIA算法涉及到需要調整的參數包括移除工件塊上限dmax，工件塊規模上限bmax，模擬退火溫度T。工件塊數量上限本文設計了五個級別dmax∈{2，3，4，5，6}，工件塊規模設計了四個級別bmax∈{2，3，4，5}，溫度T分為五個級別T∈{0.4，0.5，0.6，0.7，0.8}，一共有5×4×5=100種組合。

根據Ruiz提出的算例規模分別為工件數為N={50，100，150，200，250，300，400，500}，機器數M={10，20，30，40，50}，每種規模包括五個算例，一共10×5×5=250個算例，算例和目前最優解可以從http：//soa.iti.es上獲取。

參數調優過程中，將100種參數組合在50個規模的第二個算例上重復實驗五次，即一共實驗100×50×5=25 000次，算法在每個算例的計算終止標準是CPU時間StopTime=n·m·t/2 ms，n、m分別表示該算例規模下的工件數和機器數。這樣就保證了不同規模的算例都有相對合理的計算時間，不會導致小規模算例計算時間溢出得到優解，大規模算例計算時間不足得到的解較差。該階段，設置t=10。所有算法都在2021版本的MATLAB平臺環境中編碼，在具有6核12邏輯處理器的Intel CoreTM i5-10500（CPU主頻3.10 GHz）上進行實驗。對于每個參數組合的性能評判，采用平均相對百分比偏差（average relative percentage deviation，ARPD）來衡量，RPD計算公式為

RPD=Mh-MbestMbest×100（11）

其中：Mh是算法得到的算例makespan值；Mbest是目前找到的最優makespan值。

本文對參數實驗的結果進行了多方差分析（analysis of variance，ANOVA），由于100組參數組合數據較多，對于以每個參數為變量的實驗數據，另外兩個參數變量組合的具體實驗數據取ARPD作為該參數下的對比數據，三個參數的調優實驗數據如表1～3所示。

為了更清晰地進行對比，各個參數的ARPD的95%置信區間如圖4所示。

根據三個參數的ARPD區間圖，本文設置的參數值為dmax=3，bmax=2，T=0.7，（bmin=dmin=1）。而其他四個對比算法的參數值都由原文獻給定，IG_RS參數設置為d=4，T=0.4。IG_ALL為d=2，T=0.7。VBIH為bmin=bmax=2，T=0.5。GVNS中的內部IG_ALL算法參數為d=5，T=0.5，內部VBIH為bmin=1，bmax=5，T=0.5。

4 對比實驗設計與結果分析

VIIA算法調優后，將其與幾種在車間流水問題中表現優秀的算法進行實驗比較，包括了2007年Ruiz提出的原始IG算法IG_RS［5］，Dubois-Lacoste 2017年提出的IG_ALL［23］以及在2019年Shen等人在求解NIFSP時提出的內循環使用了IG_ALL［23］和VBIH［16］的GVNS［17］以及VBIH算法。為了驗證IFRB5優化初始解和在破壞重建階段增加內部工件塊數量可變迭代擴展鄰域搜索兩方面改進策略的實際影響效果，增加了兩組單一改進的對比組，分別記為VBIH_IFRB5（在使用FRB5的VBIH框架中使用IFRB5替代FRB5產生初始解）以及IG_IIS（在使用NEH規則的IG框架中改進破壞重建階段增加內外部迭代的鄰域搜索策略），所使用的實驗算例是基于Ruiz提出的針對NIFSP的250個算例。

每種算法都在250個算例上重復運行五次，并且CPU停止時間StopTime=n·m·t/2 ms中的參數t分別取值為20、40、60。一共要進行7×250×5×3=26 250次計算。所有實驗都在具有6核12邏輯處理器的Intel CoreTM i5-10500（CPU主頻3.10 GHz）上進行。同樣使用ARPD來評判算法的性能。對每種算法找到的各個算例的最優解同樣求解了其RPD值，表4是七種算法在三種時間下的ARPD。

表4中min表示算法在重復五次實驗中得到的最優解與當前最優解計算所得的RPD值，avg表示五次實驗結果與當前最優解計算得到的RPD的平均值。從表中三個時間下的ARPD可知，IG_ALL和VBIH在NIFSP中效果差異不大，但優于IG_RS，GVNS如文獻中的對比實驗描述相同，優于IG_RS。此次對比，也得出其性能優于所使用的兩個內部函數IG_ALL和VBIH。兩個單一改進對照組分別是VBIH_IFRB5的min_RPD的平均值為0.16，ARPD的平均值為0.32，IG_IIS的min_RPD的平均值為0.14，ARPD的平均值為0.3，說明初始解的優化和破壞重建階段領域擴展兩個方向的改進相比較原始VBIH以及IG都取得了不錯的效果。VIIA的min_RPD的平均值為0.09，ARPD的平均值為0.23，從數據可知提出算法VIIA的性能是優于其他六種算法的。為了表現七種算法對算例最優解的搜索性能，各個算法的ARPD和min_RPD趨勢如圖5所示。

由趨勢圖可知，VIIA獲取的解與當前最優解的平均相對百分比誤差在不同時間下的趨勢優于其他對比算法，在獲取最優解的性能方面，VIIA也顯著優于其他對比算法。

圖6是三個時間t下整體的95%置信區間的ARPD，也說明了VIIA的改進是具有統計學意義的，在Ruiz提出的針對NIFSP的250個算例上進行了大量對比實驗，并與http：//soa.iti.es獲得的最著名的解決方案進行了對比，VIIA算法改進了91個算例的當前最優解。大量實驗數據驗證了在求解零空閑流水車間中以makespan為目標的Fm/prmu，no-idle/Cmax問題時，VIIA的性能優于以上算法，并且搜索最優解的能力也更加突出。

5 結束語

對于大多數現實場景下機器運行中零空閑的約束，在NIFSP模型中，提出的VIIA對于工件加工順序以及加工流程安排的尋優降低了工件加工的最大完工時間。通過仿真實驗，在250個針對性的算例中，對最優解的搜索性能明顯優于其他對比算法。兩組單一改進的對照組算法也說明了在破壞重建階段提出的內外迭代結構能擴大對鄰域的搜索，提升了算法的尋優性能。在工廠模型多樣化的今天，對機器的約束條件也越來越多，針對性的建模算例規模也越來越大。VIIA內外迭代的靈活性以及對算例規模適應性的優勢更加顯著。未來將會在不同約束條件下的流水車間調度問題中應用VIIA算法，對于不同規模算例，研究調整變量參數的取值，并驗證其綜合性能。另外，對于機器智能化的今天，研究趨勢向機器學習，深度學習方向擴展，傳統算法框架中嵌入智能學習策略進行鄰域尋優也是未來研究方向之一。

參考文獻：

［1］Garey M R，Johnson D S，Sethi R. The complexity of flowshop and job shop scheduling［J］. Mathematics of Operations Research，1976，1（2）： 117-129.

［2］Adiri I，Pohoryles D. Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times［J］. Naval Research Logistics，1982，29（3）： 495-504.

［3］Vachajitpan P. Job sequencing with continuous machine operation［J］. Computers and Industrial Engineering，1982，6（3）： 255-259.

［4］Woollam C R. Flowshop with no idle machine time allowed［J］. Computers and Industrial Engineering，1986，10（1）： 69-76.

［5］Ruiz R，Styutzle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem［J］. European Journal of Operational Research，2005，177（3）： 2033-2049.

［6］Pan Q K，Wang Ling. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm［J］. The International Journal of Advanced Manufacturing Technology，2008，39（7-8）： 796-807.

［7］Pan Quanke，Wang Ling，Qian Bin. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems［J］. Computers and Operations Research，2008，36（8）： 2498-2511.

［8］Ruiz R，Vallada E，Fernández-Martínez C. Scheduling in flowshops with no-idle machines［M］// Chakraborty U K. Computational intel-ligence in flow shop and job shop scheduling. Berlin： Springer，2009： 21-51.

［9］Deng Guanlong，Gu Xingsheng. A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion［J］. Computers and Operations Research，2011，39（9）： 2152-2160.

［10］Tasgetiren M F，Pan Quanke，Suganthan P N，et al. A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem［J］. Computers and Operations Research，2013，40（7）： 1729-1743.

［11］Tasgetiren M F，Buyukdagli O，Pan Quanke，et al. A general variable neighborhood search algorithm for the no-idle permutation flowshop scheduling problem［J］. Swarm，Evolutionary，and Memetic Computing，2013，8297： 24-34.

［12］Pan Quanke，Ruiz R. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem［J］. Omega，2014，44： 41-50.

［13］Shen Jingnan，Wang Ling，Wang Shengyao. A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion［J］. Knowledge-Based Systems，2015，74： 167-175.

［14］Shao Weishi，Pi Dechang，Shao Zhongshi. Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion［J］. Applied Soft Computing，2017，54： 164-182.

［15］Ying K C，Lin S W，Cheng C Y，et al. Iterated reference greedy algorithm for solving distributed no-idle permu tation flowshop scheduling problems［J］. Computers and Industrial Engineering，2017，110： 413-423.

［16］Kizilay D，Tasgetiren M F，Pan Quanke，et al. A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion［J］. Algorithms，2019，12（5）： 100.

［17］Shen Liangshan，Tasgetiren M F，ztop H，et al. A general variable neighborhood search for the noidle flowshop scheduling problem with makespan criterion［C］// Proc of IEEE Symposium Series on Computational Intelligence. Piscataway，NJ： IEEE Press，2019： 1684-1691.

［18］Riahi V，Chiong R，Zhang Yuli. A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion［J］. Computers and Operations Research，2020，117： 104839.

［19］劉麗娜，南新元，石躍飛. 改進麻雀搜索算法求解作業車間調度問題［J］. 計算機應用研究，2021，38（12）： 3634-3639. （Liu Lina，Nan Xinyuan，Shi Yuefei. Improved sparrow search algorithm for solving job-shop scheduling problem［J］. Application Research of Computers，2021，38（12）： 3634-3639.）

［20］羅浩嘉，潘大志. 改進布谷鳥算法求解雙資源約束柔性車間調度問題［J］.計算機應用研究，2022，39（8）： 2295-2300. （Luo Haojia，Pan Dazhi. Improved cuckoo algorithm for flexible job shop schedu-ling with dual resource constraints ［J］. Application Research of Computers，2022，39（8）： 2295-2300.）

［21］尹瑞雪，馮旭青，吳拓，等.改進果蠅算法求解零空閑流水車間調度問題［J］. 組合機床與自動化加工技術，2022（2）： 142-145，150. （Yin Ruixue，Feng Xuqing，Wu Tuo，et al. Improved fruit fly algorithm for solving no-idle flow shop scheduling problem［J］. Modular Machine Tool amp; Automatic Manufacturing Technique，2022（2）： 142-145，150.）

［22］Nawaz M，Emory Enscore E，Ham I. A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem［J］. Omega，1983，11（1）： 91-95.

［23］Dubois-Lacoste J，Pagnozzi F，Stützle T. An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem［J］. Computers and Operations Research，2017，81： 160-166.

［24］Rad S F，Ruiz R，Boroojerdian N. New high performing heuristics for minimizing makespan in permutation flowshops［J］. Omega，2009，37（2）： 331-345.

［25］Pan Quanke，Tasgetiren M F，Liang Y C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem［J］. Computers and Industrial Engineering，2008，55（4）： 795-816.

［26］Osman I H，Potts C N. Simulated annealing for permutation flow-shop scheduling［J］. Omega，1989，17（6）： 551-558.

［27］Metropolis N，Rosenbluth A W，Rosenbluth M N，et al. Equation of state calculations by fast computing machines，AECU-2435［R/OL］. （1953-03-06）. https：//doi.org/10.2172/4390578.