作業車間調度問題的典型智能優化算法
2023-03-31 來源：?智造苑
JSP作為NP-難問題，基于數學模型的方法只能求解小規模問題，調度規則求解速度快但效果一般。因此現在的研究大多采用遺傳算法等智能優化算法求解JSP問題以期望在合理時間內獲得滿意解。局部搜索是智能優化算法取得高質量解的關鍵，而鄰域結構作為局部搜索的核心極大影響算法的性能。
「 1. 智能優化算法在作業車間調度中的應用 」
局部搜索算法能很好地克服了智能優化算法易陷入局部最優的缺點。因此，越來越多的研究人員將局部搜索算法引入其他算法框架求解JSP問題。Zhang等[1]將模擬退火算法和禁忌搜索算法相結合求解JSP問題。Peng等[2]將禁忌搜索算法引入路徑重連算法框架求解JSP問題。路徑重連算法增加了種群的多樣性，將種群中的個體分散到解空間各處，更有利于個體執行禁忌搜索操作。Gonçalves和Resende[3]將禁忌搜索算法引入遺傳算法框架求解JSP問題。遺傳算法和禁忌搜索算法的結合很好地平衡了混合算法的全局搜索和局部搜索能力。將局部搜索算法與其他算法組合，能有效擴大算法的搜索空間，增強算法的全局搜索能力。因此，運用混合算法求解JSP問題逐漸成為了研究的熱點。
局部搜索算法能很好地克服了智能優化算法易陷入局部最優的缺點。因此，越來越多的研究人員將局部搜索算法引入其他算法框架求解JSP問題。Zhang等[1]將模擬退火算法和禁忌搜索算法相結合求解JSP問題。Peng等[2]將禁忌搜索算法引入路徑重連算法框架求解JSP問題。路徑重連算法增加了種群的多樣性，將種群中的個體分散到解空間各處，更有利于個體執行禁忌搜索操作。Gonçalves和Resende[3]將禁忌搜索算法引入遺傳算法框架求解JSP問題。遺傳算法和禁忌搜索算法的結合很好地平衡了混合算法的全局搜索和局部搜索能力。將局部搜索算法與其他算法組合，能有效擴大算法的搜索空間，增強算法的全局搜索能力。因此，運用混合算法求解JSP問題逐漸成為了研究的熱點。
「 2. 鄰域結構在作業車間調度中的應用 」
鄰域結構是否合理對局部搜索算法的效果有著直接的影響。在調度問題中，一般鄰域結構的移動都是通過對關鍵路徑上的工序產生小的擾動產生，只有如此才有可能縮短當前解的最大完工時間。
最著名的鄰域結構是基于關鍵塊的N5[4]、N6[5]和N7[6]鄰域結構。N5鄰域結構的設計如下：①若是第一個關鍵塊，則交換塊尾的兩道工序；②若是最后一個關鍵塊，則交換塊首的兩道工序；③若既不是第一個關鍵塊，也不是最后一個關鍵塊，則交換塊首的兩道工序和塊尾的兩道工序。圖1是N5鄰域結構的示意圖。N6鄰域結構是N5鄰域結構擴展，進一步考慮了將關鍵塊內部的工序移動到關鍵塊的塊首和塊尾，但由于在作業車間調度問題中存在有不可行解的情況，因此需要在滿足一定的約束條件的基礎上，才能將內部工序移動到塊首或塊尾進行加工。圖2是N6鄰域結構的示意圖。N7鄰域結構在N6鄰域結構的基礎上，增加了將關鍵塊塊首和塊尾的工序移動到關鍵塊內部，同樣，為了避免不可行解的出現，N7也需要滿足與N6相同的約束條件。圖3是N7鄰域結構的示意圖。
圖1 N5鄰域結構
圖2 N6鄰域結構
圖3 N7鄰域結構
N6和N7中的約束條件能夠確保移動后產生的結果為可行解的充分條件，但仍然存在大量移動后的結果為可行解，但并不滿足N6和N7中的約束條件，即這些約束條件為保證可行解的充分非必要條件。為了探究保證產生可行解的充分必要條件，首先要了解由可行解產生不可行解的充分必要條件，然后就可以反推出產生可行解的充分必要條件。
「 3. 基于遺傳算法求解作業車間調度問題[8] 」
遺傳算法基于自然界的進化規律而得到，由種群、選擇、交叉和變異算子等部分組成，需要建立從染色體基因到個體外部特征的映射，即完成相應的編解碼工作，編解碼方式對算法性能有著重要影響。遺傳算法的特性使其非常適合求解組合優化問題，在JSP的研究中應用廣泛。
1）編碼與解碼
編碼就是解的遺傳基因表示，它是遺傳算法實施優化過程中遇到的首要問題，是為了實現交叉、變異等類似于生物界的遺傳操作，也是應用成功與否的關鍵之一。編碼過程必須考慮染色體的合法性、可行性和有效性，以及對問題解空間表達的完全性，直接影響算法求解速度、計算精度等性能。良好的編碼方式有利于在后續遺傳操作中產生可行解，提高執行效率；否則，經過遺傳操作會產生不可行解，需要一定的修補措施，這樣就降低了執行效率。
本文采用Gen等[7]提出的基于工序的編碼方式進行編碼，染色體的長度等于所有工件的工序之和。每一個基因用工件號直接編碼，工件號出現的順序表示該工件工序間的先后加工順序，即對染色體從左到右進行編譯，對于第j次出現的工件號，表示該工件i的第j道工序，并且工件號的出現次數等于該工件的工序總數。如此編碼柔性很高，可滿足調度規模變化、工件工序數不定等各種復雜情況，而且任意置換染色體中的順序后總能得到可行調度。假設染色體的編碼是[2, 2, 1, 1, 2]，則其中第一個2表示工序O21，第二個2表示工序O22，以此類推，轉換成各工序的加工順序為O21→O22→O11→O12→O23。
舉例說明[8]，表1為一個3×3的JSP問題，假設它的一個染色體為[2 1 1 3 1 2 3 3 2]，其中1表示工件J1，2和3意義相同。染色體中的3個1依次表示工件J1的3道工序，分別為工序1、工序2和工序3；此染色體對應的機器分配為[3 1 2 2 3 1 3 1 2]，對應的加工時間為[2 3 2 2 3 3 2 3 4]。圖4表示該染色體解碼成為對應機器和加工時間的方式[8]。按一般解碼方式，依次從左到右將染色體上的工序都安排完為止，可生成的染色體對應的半活動調度方案，圖5顯示該染色體一般方式解碼后所得半活動調度解[8]，其中，機器1上的工件加工順序為1-2-3，機器2上為1-3-2，機器3上為2-1-3，最大完工時間Makespan = 13。
表1 一個3×3的JSP問題
圖4 解碼方式
圖5 半活動解碼圖6活動解碼
按一般解碼方式只能得到半活動調度，而不是活動調度。本文介紹一種插入式貪婪解碼算法[8]，能保證染色體經過解碼后生成活動調度。插入式貪婪解碼算法描述如下：首先將染色體看作工序的有序序列，根據工序在該序列上的順序進行解碼，序列上第1道工序首先安排加工，然后取序列上第2道工序，將其插入到對應機器上最佳可行的加工時刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。按插入式貪婪解碼算法，該染色體解碼后可生成圖6所示的活動調度解[8]。其中，機器1上的工件加工順序為1-2-3，機器2為3-1-2，機器3為2-3-1，最大完工時間Makespan減少為10。然后，可以獲得該活動調度對應的染色體[2 1 3 1 2 2 3 1 3]。
2）交叉算子
交叉的目的是利用父代個體經過一定操作組合后產生新個體，在盡量降低有效模式被破壞的概率基礎上對解空間進行高效搜索。交叉操作是主要的遺傳操作，遺傳算法的性能在很大程度上依賴于所使用的交叉操作，它決定了算法的全局搜索能力。在設計交叉操作是必須滿足可行性、特征的有效繼承性、完全性和信息非冗余性等指標。特征的有效繼承性保證父代中的優良信息能夠保留到子代；信息非冗余性保證子代中不會產生過多無用信息，這兩個特征在交叉操作設計中是兩個重要指標。遺傳算法中常用的交叉操作有單點交叉（SPX），多點交叉（MPX），均勻交叉（UX），基于工件順序的交叉（JOX）和基于工件優先順序的交叉（POX）等。本文采用的POX交叉操作，其具體的流程如下[8]：
步驟1 隨機劃分工件集{1, 2, 3, …, n}為兩個非空的子集J1和J2。
步驟2 復制Parent1包含在J1的工件到Children1，Parent2包含在J1的工件到Children2，保留它們的位置。
步驟3 復制Parent2包含在J2的工件到Children1，Parent1包含在J2的工件到Children2，保留它們的順序。
圖7說明了兩個4個工件和3臺機器調度問題的染色體交叉過程。兩父代Parent1、Parent2交叉生成Children1染色體基因為[3 2 2 1 2 3 1 4 4 1 4 3 ]，Children2染色體基因為[4 1 3 4 2 2 1 1 2 4 3 3]?？梢钥闯鼋涍^POX交叉，Children1染色體保留了Parent1中工件{2, 3}和Parent2中工件{1, 4}的次序，Children2染色體保留了Parent2中工件{2, 3}和Parent1中工件{1, 4}的次序，使子代可能繼承父代優良特征。
圖7 POX交叉算子[8]
3）變異算子
在傳統遺傳算法中，變異是為了保持群體的多樣性，它是由染色體較小的擾動產生。傳統調度問題的遺傳算法變異算子包括交換變異、插入變異和逆轉變異。本文采用一種基于領域搜索的變異算子，如圖8所示[8]，它具有通過局部范圍內搜索來改善子代的性能，具體步驟如下：
步驟1 設i= 0。
步驟2 判斷i≤ popsize× pm是否成立（popsize是種群規模，pm是變異概率），是轉到步驟3，否則轉步驟6。
步驟3 取變異染色體上λ個不同的基因，生成其排序的所有領域。
步驟4 評價所有領域的調度適應值，取其中的最佳個體。
步驟5 i= i+ 1，轉至步驟2。
步驟6 結束。
圖8 變異算子[8]
4）遺傳算法流程
在傳統遺傳算法中，交叉產生的子代總是被接受，即使它們適應度遠低于父代的適應度，這可能造成優良解被丟失或破壞，而導致傳統遺傳算法易于早熟和收斂于較差解。本文設計一種改進子代產生模式的遺傳算法，兩父代交叉n次生成2n個后代，為了使子代更好地繼承父代的優良特征，在從父代優的一個和所有2n個后代中選擇最優一個的染色體作為下一代（兩染色體適應度不同），這樣既能將最優染色體保留到下一代，又能保證子代的多樣性。這與人類繁殖類似，可使父代的優良特性更好地傳遞到下一代。求解JSP問題遺傳算法的具體步驟如下：
步驟1 初始化隨機產生P個染色體個體，P為種群規模。
步驟2 計算個體適應度，評價個體適應度值。
步驟3 判斷是否達到終止條件，若滿足則輸出最優解，結束算法；否則轉步驟4。
步驟4 按賭輪選擇策略選取下一代種群。
步驟5a 按交叉概率Pc，對兩父代個體交叉n次，從最優父代和所有后代中選擇最優兩染色體作為下一代。
步驟5b 按變異概率Pm選擇個體，進行變異操作生成新個體。
步驟6 生成的新一代的種群，返回到步驟3。
5）實驗結果與分析
本文用著名的Fisher和Thompson（FT）基準實例[9]對提出的改進遺傳算法進行測試。具體遺傳算法試驗運行參數如下：種群規模P= 500，交叉概率Pc= 0.8，變異概率Pm= 0.01。實驗結果見表7.5。
對于較簡單FT6×6實例，遺傳算法可以迅速收斂到下界，而對于難度較大的FT10×10也能在較短時間內收斂到下界。從表2可以看出對于FT基準實例[8]，本文采用的遺傳算法能取得較好的結果。
表2 FT基準實例測試結果[8]
遺傳算法有著很強的并行性和全局尋優能力，但也有收斂速度慢、局部尋優能力較差等缺點，而禁忌搜索算法等一些啟發式搜索算法則具有較強的局部搜索能力。結合不同算法的尋優思想對遺傳算法進行改進，如在遺傳框架內加入禁忌搜索操作可以提高算法的運行效率和求解質量。
「 4. 基于遺傳與禁忌搜索混合算法求解作業車間調度問題[8] 」
1）交叉和變異操作
交叉和變異是遺傳算法進化過程中的關鍵操作，它們決定著遺傳算法全局搜索的能力。
2）禁忌搜索算法設計
禁忌搜索算法已經被有效地用于求解多種車間調度問題。該算法的特點是采用禁忌表來避免個體陷入局部最優。如果某一個體被禁忌表所禁止，那么它就不能被選為新解進入下一代。禁忌搜索算法包含以下幾種元素：鄰域結構、移動屬性、禁忌表、特赦準則和終止條件。本文所采用的鄰域結構是N7鄰域結構。移動屬性指工序間的移動操作。禁忌表用來禁止重復的移動操作。特赦準則是指當新解的Makespan比當前最優解更小時，即使新解的移動操作被禁止，仍然接受。終止條件是指當新解的Makespan達到了下界或算法到達了給定的迭代次數，則算法終止。禁忌搜索算法的流程如下：
步驟1 隨機產生一個候選解x0，并設置當前最優解xb←x0。
步驟2 設置禁忌表T為Ø。
步驟3 基于N7鄰域結構產生x0的多個鄰域解，并選擇Makespan最小且沒有被禁忌，或滿足特赦準則的解為x’。
步驟4 如果x’優于xb，設置xb← x’；同時設置x0← x’。
步驟5 更新禁忌表T。
步驟6 判斷是否達到終止條件，若滿足則輸出最優解xb，結束算法；否則轉步驟3。
3）混合算法的框架設計
遺傳與禁忌搜索混合算法將“適者生存”的進化準則融入多起點禁忌搜索算法中，由遺傳算法和對初始化及進化過程中產生的個體進行優化的強化禁忌搜索算法組成。從總體上分析，遺傳算法用于執行全局探索，而強化禁忌搜索算法用于對有希望的區域進行集中搜索（局部探索）。由于遺傳算法和禁忌搜索算法具有互補的特性，混合算法能夠超越這兩種算法單獨使用。求解JSP問題的遺傳與禁忌搜索混合算法流程如下：
步驟1 種群初始化并設代數i=1。
步驟2 對種群適應度值進行評估。
步驟3 判斷是否滿足終止條件？滿足則跳轉至步驟6；否則跳轉至步驟4。
步驟4 更新種群：首先使用遺傳算子（選擇、交叉和變異）更新種群；然后對種群中每個個體使用禁忌搜索操作提高解的質量。
步驟5 設i=i+1，并返回步驟2。
步驟6 輸出最優個體。
4）實驗結果與分析
在混合算法中，遺傳算法種群規模P、交叉概率Pc、變異概率Pm、進化代數和禁忌搜索算法參數等由大量試驗測試確定，以保證算法在解的質量和計算速度之間平衡。
本文從經典的FT[9]、LA[10]和ABZ[11]基準集中選取15個困難案例對遺傳與禁忌搜索混合算法進行測試?；旌纤惴ǖ倪\行參數設置如下：種群規模P= 10，交叉概率Pc= 0.8，變異概率Pm=0.1，禁忌列表長度L= 10，未改進迭代次數ImproveIter = 100 × n（n為工件數）。標準測試每個實例連續運行10次，以計算實例平均適應度和平均運行時間。實驗結果見表3。
1）交叉和變異操作
交叉和變異是遺傳算法進化過程中的關鍵操作，它們決定著遺傳算法全局搜索的能力。
2）禁忌搜索算法設計
禁忌搜索算法已經被有效地用于求解多種車間調度問題。該算法的特點是采用禁忌表來避免個體陷入局部最優。如果某一個體被禁忌表所禁止，那么它就不能被選為新解進入下一代。禁忌搜索算法包含以下幾種元素：鄰域結構、移動屬性、禁忌表、特赦準則和終止條件。本文所采用的鄰域結構是N7鄰域結構。移動屬性指工序間的移動操作。禁忌表用來禁止重復的移動操作。特赦準則是指當新解的Makespan比當前最優解更小時，即使新解的移動操作被禁止，仍然接受。終止條件是指當新解的Makespan達到了下界或算法到達了給定的迭代次數，則算法終止。禁忌搜索算法的流程如下：
步驟1 隨機產生一個候選解x0，并設置當前最優解xb←x0。
步驟2 設置禁忌表T為Ø。
步驟3 基于N7鄰域結構產生x0的多個鄰域解，并選擇Makespan最小且沒有被禁忌，或滿足特赦準則的解為x’。
步驟4 如果x’優于xb，設置xb← x’；同時設置x0← x’。
步驟5 更新禁忌表T。
步驟6 判斷是否達到終止條件，若滿足則輸出最優解xb，結束算法；否則轉步驟3。
3）混合算法的框架設計
遺傳與禁忌搜索混合算法將“適者生存”的進化準則融入多起點禁忌搜索算法中，由遺傳算法和對初始化及進化過程中產生的個體進行優化的強化禁忌搜索算法組成。從總體上分析，遺傳算法用于執行全局探索，而強化禁忌搜索算法用于對有希望的區域進行集中搜索（局部探索）。由于遺傳算法和禁忌搜索算法具有互補的特性，混合算法能夠超越這兩種算法單獨使用。求解JSP問題的遺傳與禁忌搜索混合算法流程如下：
步驟1 種群初始化并設代數i=1。
步驟2 對種群適應度值進行評估。
步驟3 判斷是否滿足終止條件？滿足則跳轉至步驟6；否則跳轉至步驟4。
步驟4 更新種群：首先使用遺傳算子（選擇、交叉和變異）更新種群；然后對種群中每個個體使用禁忌搜索操作提高解的質量。
步驟5 設i=i+1，并返回步驟2。
步驟6 輸出最優個體。
4）實驗結果與分析
在混合算法中，遺傳算法種群規模P、交叉概率Pc、變異概率Pm、進化代數和禁忌搜索算法參數等由大量試驗測試確定，以保證算法在解的質量和計算速度之間平衡。
本文從經典的FT[9]、LA[10]和ABZ[11]基準集中選取15個困難案例對遺傳與禁忌搜索混合算法進行測試?；旌纤惴ǖ倪\行參數設置如下：種群規模P= 10，交叉概率Pc= 0.8，變異概率Pm=0.1，禁忌列表長度L= 10，未改進迭代次數ImproveIter = 100 × n（n為工件數）。標準測試每個實例連續運行10次，以計算實例平均適應度和平均運行時間。實驗結果見表3。
表3 FT、LA和ABZ基準實例測試結果[8]
由表3可以看出，在最優解已知的13個實例中，混合算法獲得了11個實例的最優解。實驗結果驗證了混合算法能有效地求解JSP問題。此外，10次運行獲得的平均值與最優解的差距很小，反映了混合算法的魯棒性極強。對于這15個困難的實例，混合算法都能在很短的時間內獲得最優（或近似最優）解，顯示了混合算法的高效性。
參考文獻
[1]ZHANG C Y, LI P G, RAO Y Q, et al. A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research, 2008, 35(1): 282-294.
[2]PENG B, LÜ Z, CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research, 2015, 53: 154-164.
[3]GONÇALVES J F, RESENDE M G C. An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling. International Transactions in Operational Research, 2014, 21(2): 215-246.
[4]NOWICKI E, SMUTNICKI C. A fast taboo search algorithm for the job shop problem. Management science, 1996, 42(6): 797-813.
[5]BALAS E, VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling. Management science, 1998, 44(2): 262-275.
[6]ZHANG C Y, LI P G, GUAN Z L, et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 2007, 34(11): 3229-3242.
[7]GEN M, TSUJIMURA Y, KUBOTA E. Solving job-shop scheduling problems by genetic algorithm // Proceedings of IEEE International Conference on Systems, Man and Cybernetics. IEEE, 1994, 2: 1577-1582.
[8]張超勇.基于自然啟發式算法的作業車間調度問題理論與應用研究[D].武漢：華中科技大學. 2006.
[9]FISHER H. Probabilistic learning combinations of local job-shop scheduling rules. Industrial scheduling, 1963: 225-251.
[10]LAWRENCE S. Resouce constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, 1984.
[11]ADAMS J, BALAS E, ZAWACK D. The shifting bottleneck procedure for job shop scheduling. Management science, 1988, 34(3): 391-401.
引自：《智能調度》（作者：李新宇, 張利平, 牟健慧）
相關新聞
版權聲明
1、凡本網注明“來源：中國輕工業網” 的作品，版權均屬于中國輕工業網，未經本網授權，任何單位及個人不得轉載、摘編或以其它方式使用。已經本網授權使用作品的，應在授權范圍內使用，并注明“來源：中國輕工業網”。違反上述聲明者，本網將追究其相關法律責任。
2、凡本網注明 “來源：XXX（非中國輕工業網）” 的作品，均轉載自其它媒體，轉載目的在于信息之傳播，并不代表本網贊同其觀點和對其真實性負責。
3、如因作品內容、版權和其它問題需要同本網聯系的，請于轉載之日起30日內進行。
4、免責聲明：本站信息及數據均為非營利用途，轉載文章版權歸信息來源網站或原作者所有。
