前幾期的推送已經(jīng)講解了網(wǎng)絡計劃的基本知識、數(shù)學模型和相關(guān)算法，相信大家對網(wǎng)絡計劃已經(jīng)有了充分的了解，這期小編將帶大家一起來讀一篇基于關(guān)鍵路徑的置換流水車間調(diào)度問題的文章。

1.文章信息

題目：An efficient critical path based method for permutation flow shop scheduling problem

作者：Yang Li，Xinyu Li，Liang Gao，Ling Fu，Cuiyu Wang

來源：Journal of Manufacturing Systems

出版信息：Volume 63，April 2022，Pages 344-353

網(wǎng)址：https://doi.org/10.1016/j.jmsy.2022.04.005

2.文章導讀

置換流水車間調(diào)度問題（The permutation flow shop scheduling problem，PFSP）廣泛存在于汽車、船舶、裝備制造、電子信息產(chǎn)品等制造企業(yè)中，是對經(jīng)典的流水車間調(diào)度問題進行簡化后得到的一類子問題。PFSP是一個著名的NP難題，隨著作業(yè)和機器數(shù)量的增加，問題的解空間和求解難度都會迅速增加，要在短時間內(nèi)得到滿意的解決方案非常困難。PFSP問題最初的研究集中在數(shù)學規(guī)劃方法上，如整數(shù)規(guī)劃、分支定界等。隨著問題規(guī)模的增大，數(shù)學規(guī)劃方法的計算效率逐漸降低，在可接受的代價下得到組合優(yōu)化問題可行解的啟發(fā)式方法成為后續(xù)研究的主流。如今，隨著人工智能技術(shù)的興起和計算機技術(shù)的發(fā)展，智能優(yōu)化方法逐漸發(fā)展起來，如禁忌搜索（Tabu Search，TS）、模擬退火（Simulated Annealing，SA）、遺傳算法（Genetic Algorithm，GA）、人工蜂群算法（Ant colony optimization，ACO）等，極大地推動了PFSP的研究，多種元啟發(fā)式方法組合使用的混合算法也成為研究的熱點。然而，對于大規(guī)模PFSP（工件數(shù)≥100），這些元啟發(fā)式算法的求解速度依舊不適用于實際生產(chǎn)，且從計算精度的角度來看，元啟發(fā)式算法的結(jié)果具有隨機性，難以用于指導實際生產(chǎn)。因此，必須找到新的方法來加快算法的計算速度，同時保證解的質(zhì)量。

3.摘要

置換流水車間調(diào)度問題是大規(guī)模定制生產(chǎn)中最重要、最典型的調(diào)度類型之一，也是一個著名的NP難題。然而，已有的算法大多缺乏理論指導，難以達到較好的精度和效率。針對這一問題，本文提出了一種基于關(guān)鍵路徑的快速搜索方法，并給出了PFSP的三個定理及證明。首先，根據(jù)PFSP的特點，定義了關(guān)鍵路徑和關(guān)鍵點的概念，并在此基礎(chǔ)上，提出了一種新的求解PFSP的鄰域搜索方法。在每次鄰域搜索中，只需要計算加工序列中的第一個和最后一個工件以及關(guān)鍵路徑上每臺機器的第一個工件的相鄰工件，無論問題規(guī)模有多大，該方法最多只需搜索（2m+2）次就能找到最優(yōu)鄰域解（m為機器數(shù)）。最后，將新的鄰域搜索方法與改進的模擬退火算法相結(jié)合求解PFSP。為了驗證所提算法的性能，本文在TA測試平臺上與現(xiàn)有算法進行了對比實驗，實驗結(jié)果表明，本文提出的方法取得了明顯的改進，在相同的算法框架下，該方法可以減少平均35.2%的計算時間。

4.主要內(nèi)容

PFSP研究的是n個工件在m臺機器上的流水加工過程，所有工件以相同的順序在每一臺機器上加工完成（加工順序相同但每個加工步驟的工藝可能不同），同時要求每個工件在每臺機器上只加工一次，每臺機器每次最多只能加工一個工件，各工件在各機器上所需的加工時間已知，目標是找到使完成時間最小化的作業(yè)順序。PFSP的解由n個作業(yè)的排列表示，即σ={σ1，σ2，…，σn}，Cσj,m表示工件σj在機器m上的完成時間，tij表示工件i在機器j上的加工時間，完成時間計算如下：

從公式可以看出，每個完工時間的計算都有一定的復雜度，隨著作業(yè)數(shù)量的增加，求解時間將呈指數(shù)增長。因此，對于大型車間來說，如何縮短完工時間的計算時間是必須思考的問題。JSP（單車間調(diào)度問題）中經(jīng)常使用關(guān)鍵路徑來加快搜索過程，它被定義為從第一個作業(yè)的第一步到最后一個作業(yè)的最后一步的最長路徑，關(guān)鍵路徑有一個重要的性質(zhì)，即交換非關(guān)鍵路徑的過程不影響最終的完工時間。以該定義為標準，關(guān)鍵路徑仍然可以在PFSP中找到，如圖1所示的例子中，20個工件在5個機器上流水加工，關(guān)鍵路徑可由紅色箭頭表示，且對PFSP來說，由于在不同的機器上加工工藝的順序均相同，因此所有的工件都在關(guān)鍵路徑上。

本文通過鄰域搜索來獲得最優(yōu)解，并將有效的鄰域搜索定義如下：相鄰工件的加工順序依次交換，如果解的質(zhì)量變好，則保留當前的加工順序并繼續(xù)交換；否則，交換作業(yè)順序，直到解決方案的質(zhì)量無法提高為止，此時，可以獲得局部最優(yōu)解。

為了提高搜索速度、節(jié)約搜索時間，本文還定義了關(guān)鍵塊和關(guān)鍵點的概念，結(jié)合上述20個工件在5個機器上流水加工的例子進行講解。圖2是PFSP的甘特圖，對于圖中工件8和5的交換，求解交換后的最大完工時間需要重新計算，這會花費很長時間。而甘特圖表明，交換相鄰的8和5工件后，整體結(jié)構(gòu)變化并不大，因此整個調(diào)度結(jié)果的變化可以用紅色區(qū)域來表示，本文將這里的紅色區(qū)域定義為關(guān)鍵塊。

另外，將圖1的關(guān)鍵路徑與圖2所示的關(guān)鍵塊結(jié)合起來，關(guān)鍵點被定義為關(guān)鍵路徑和關(guān)鍵塊的交點（如圖中藍色圈起來的部分為關(guān)鍵點）。通過研究和數(shù)學證明，本文給出了關(guān)鍵點的三個性質(zhì)：

定理1.如果交換相鄰作業(yè)后關(guān)鍵點的開始時間增加，解的質(zhì)量一定不會變好；而如果關(guān)鍵點的開始時間減少，則解的質(zhì)量一定不會變差。

定理2.在關(guān)鍵路徑上，如果同一臺機器上有4個或更多的工序相鄰，當任意兩個非外部工序對應的工件交換時，總加工時間不會縮短。

推論3.該鄰域只需要計算加工序列中的第一個和最后一個工件，以及關(guān)鍵路徑上每臺機器的第一個工件的相鄰工件。

結(jié)合甘特圖和定理1、定理2與推論3，在每次鄰域搜索中，只需要計算加工序列中的第一個和最后一個工件以及關(guān)鍵路徑上每臺機器的第一個工件的相鄰工件，無論問題規(guī)模有多大，該方法最多只需搜索（2m+2）次就能找到最優(yōu)鄰域解（m為機器數(shù)）。例如，在圖4中，當前鄰域只需要搜索作業(yè)1和15、5和11、11和7、7和14、6和13、2和3，然后利用定理1對這6組工件進行簡化計算后，便可得到局部最優(yōu)解，從而加快了鄰域搜索的速度。

綜合上述的關(guān)鍵塊、關(guān)鍵點及三條定理，本文給出了鄰域搜索的總體框架，如圖5所示。第一步：輸入初始加工順序，求解關(guān)鍵路徑。第二步：如果遍歷了所有作業(yè)，則輸出局部最優(yōu)解；否則，繼續(xù)執(zhí)行步驟三。第三步：交換下一個相鄰作業(yè)（需要交換的作業(yè)由推論3計算），通過關(guān)鍵點的移動快速判斷解的質(zhì)量變化，如果解的質(zhì)量變好，則更新序列和關(guān)鍵路徑；否則，保持序列和關(guān)鍵路徑不變，返回步驟二。

由于PFSP的鄰域搜索方法在實際應用中需要與元啟發(fā)式算法相結(jié)合，故本文選擇并改進了1983年Kirkpatrick等人提出的基于Metropolis準則的SA算法，得到了基于鄰域搜索的改進SA算法“NS-SA”。改進后的“NS-SA”算法的具體計算框架如圖6所示。

根據(jù)“NS-SA”算法的框架，該算法引入了基于關(guān)鍵路徑的鄰域搜索，可以在更短的時間內(nèi)搜索到更多的解空間，且每次溫度搜索都能保證一定的局部最優(yōu)解，增強了元啟發(fā)式算法的穩(wěn)定性。此外，與SA算法相比，該算法的改進主要集中在以下三個方面：

（1）參數(shù)初始設(shè)置

本文采用自然數(shù)編碼方式，即n個作業(yè)被連續(xù)編號為1-n，初始解由NEH算法生成。由于初始溫度將影響接受劣質(zhì)解的概率，因此為保證初始概率的準確性，本文采用的初始溫度計算公式為T0=(- Δmax)/P0，其中P0是初始接受概率，|Δmax|表示一組隨機解之間的最大適應性差異。

（2）更新新解方式

本文采用基于概率選擇的多規(guī)則鄰域搜索操作來協(xié)作更新新解，采用的鄰域搜索操作包括三種：

①二進制交換：隨機選擇序列中的兩個點，并顛倒它們之間所有作業(yè)的順序；

②三點兌換：隨機選擇序列中的三個點，并交換它們之間的兩個位置；

③兩點兌換：隨機選擇序列中的兩個點，并交換這兩個點的工作。

本文在同一溫度下，對初始序列進行三次獨立的搜索，然后選取最優(yōu)值作為提出的“NS-SA”算法的初始解。

（3）溫度衰減函數(shù)

本文用開普勒型衰變函數(shù)代替了原來的指數(shù)函數(shù)，開普勒型衰減函數(shù)遞減曲線公式如下：

K和k分別表示迭代次數(shù)和總冷卻時間，當溫度衰減到終止溫度時算法程序結(jié)束。

5.結(jié)論

PFSP作為一個經(jīng)典的NP難題，隨著作業(yè)和機器數(shù)量的增加，問題的解空間和求解難度都會迅速增加。本文針對這一問題，定義了PFSP的關(guān)鍵路徑與關(guān)鍵點，并在此基礎(chǔ)上提出了一種基于關(guān)鍵路徑的快速搜索方法。在每次鄰域搜索中，只需要計算加工序列中的第一個和最后一個工件以及關(guān)鍵路徑上每臺機器的第一個工件。無論問題規(guī)模有多大，該方法最多只需搜索（2m+2）次就能找到最優(yōu)鄰域解（m為機器數(shù)）。最后，將新的鄰域搜索方法與改進的模擬退火算法相結(jié)合求解PFSP。

為了驗證所提算法的性能，本文在TA測試平臺上進行實驗。根據(jù)在測試平臺上的測試結(jié)果，“NS-SA”算法得到了38個最優(yōu)解，其中22個達到了已知的上界。特別是在TA116測試平臺中，本文得到的結(jié)果超過了網(wǎng)站上公布的當前最優(yōu)解，這證明本文提出的方法對求解PFSP是有效可靠的，可以大大提高解的質(zhì)量。另外，本文比較了鄰域搜索過程和整個算法所花費的時間，根據(jù)測試結(jié)果，本文提出的改進算法的計算速度平均提高了35.2%，整體計算時間顯著減少。最后，為了驗證算法的魯棒性，本文選取TA61-TA65作為算例，每種情況下測試10次，平均標準差僅為2.4437，證明了算法的魯棒性。

6.貢獻

1、本文根據(jù)PFSP的特點，定義了關(guān)鍵路徑、關(guān)鍵塊和關(guān)鍵點的概念，將車間調(diào)度問題中關(guān)鍵路徑的概念引入到PFSP問題，并通過研究和數(shù)學證明，給出了PFSP的三個定理及相關(guān)證明。

2、本文分析了PFSP的本質(zhì)，并結(jié)合PFSP的三個定理提出了一種基于關(guān)鍵路徑的PFSP鄰域搜索方法。在每次鄰域搜索中，無論問題的規(guī)模有多大，該方法最多只需搜索（2 m+2）次就能找到最優(yōu)鄰域解（m為機器數(shù)），大大減少了計算量，提高了搜索精度。

3、文章將新的鄰域搜索方法與改進的模擬退火算法相結(jié)合，得到了基于鄰域搜索的改進SA算法“NS-SA”，改進的SA算法可以在更短的時間內(nèi)搜索到更多的解空間，增強了元啟發(fā)式算法的穩(wěn)定性。

4、本文提出的鄰域搜索方法還可以與其他元啟發(fā)式算法相結(jié)合，也可以推廣到PFSP的變體，具有廣泛的應用空間。

7.展望

本文提出了一種基于關(guān)鍵路徑的PFSP的鄰域搜索方法，通過對PFSP本質(zhì)的研究找到了相應的規(guī)律定理并將其應用于算法求解中，大大減少了算法的計算量，提高了算法的搜索精度。本文雖然取得了較好的效果，但仍存在一定的局限性：首先，本文提出的算法應用范圍有限，僅適用于置換流水車間調(diào)度問題及其變體，無法進行大規(guī)模推廣。其次，本文提出的算法中，更新新解的鄰域搜索方法只適用于相鄰工件的互換操作，無法解決插入操作，因此在某些特定的應用場景下，該算法可能無法完全滿足需求。

因此，在今后的工作中，可以結(jié)合不同的調(diào)度問題進一步分析其數(shù)學模型，尋找更適合的鄰域搜索方法應用于算法求解。另外還可以考慮在調(diào)度過程中新增任務的動態(tài)事件對調(diào)度方案的影響，進一步改進鄰域搜索方法，為車間調(diào)度問題的解決提供幫助。

作者 | 隋朝陽?王一靜

責編 |?陳夢? ?

審核 | 徐小峰

YUNCHOUSHUO·?

· 知乎｜運籌說 ·

· 簡書｜運籌說 ·

· CSDN | 運籌說 ·