求解車間調度問題的雙禁忌表禁忌搜索算法

劉勝輝　李小陽　張淑麗

摘要：針對車間調度問題的特點，為解決傳統禁忌搜索算法容易陷入局部最優解的問題，提出一種求解車間調度問題改進的禁忌搜索算法一雙禁忌表禁忌搜索算法，該算法通過建立雙禁忌表避免在搜索最優解時出現循環的現象，通過該算法與TSAB算法進行比較可知，該算法具有較強的尋優能力。

關鍵詞：車間調度；啟發式算法；禁忌搜索；禁忌表；鄰域

DOI：10.15938/j.jhust.2016.06.010

中圖分類號：TP301

文獻標志碼：A

文章編號：1007-2683（2016）06-0050-05

0.引言

車間調度JSP（J0b Shop scheduling）問題是一種NP-hard問題，由于其本身問題比較復雜，加之要解決的問題規模比較大，有些問題不能求出一組最優解，只能求出次優解，或者近似最優解，啟發式方法較適合求解這類問題，禁忌搜索算法是一種有效的求得全局最優解的啟發式算法，其優點是有靈活記憶的功能，當搜索陷入局部最優解時能夠跳出；其缺點是對初始解的依賴較強，一個好的初始解往往能夠得出一個比較好的結果，當產生某一個最優解時，常常因為這個最優解產生循環，而此時我們要跳出循環，本文提出一種新的禁忌搜索算法一雙禁忌表禁忌搜索算法，用以解決在產生最優解的同時容易出現循環的問題。

1.問題描述

JSP問題實際上是安排n個工件在m臺機器上加工使工件的加工時間最短，而且每一個工件都有若干道工序，每道工序有指定的加工順序，固定機器上工件的工序有各自的加工時問.每一個工件都是獨立的，也就是說一個工件在某一時刻只能被一臺機器加工，并且某一時刻每臺機器只能加工一個一個工件，加工期間不允許被中斷，每個工件不能在同一臺機器上加工多次，最終的目標是使工件完工時間最小。更具體的，問題可以形式化描述成一種JSP調度模型，工件集：J={1，2，…，n}；機器集：M={1，2，…，m}；加工時間矩陣用T表示，機器j上工件i的加工時間用T表示；機器的加工順序矩陣J_M，加工工件i第j個操作的機器編號用jm（i，j）表示，j_m（i，·）表示要工件i所有操作按優先級順序加工的各機器號的排列；工件排列矩陣M_i，其中M_i（i，j）表示在機器i上加工的第，j個操作的工件號，M_i（i，·）表示在加工機器i上依次加工的各工件號的排列；工件i在機器，j上的完工時間C（i，j）

1）工件的加工時間矩陣T為常數矩陣，也就是說每個工件的各個操作加工時間T_tj是已知的，并且均為常數；

2）加工順序矩陣J_M是已知的，也就是說加工每個工件各個工序的加工，必須在指定的機器上；

3）同一臺機器上每個工件只能加工一次，也就是說同一臺機器上不允許出現循環加工某個工件的現象；

2.算法設計

2.1鄰域設計

本算法基于禁忌搜索算法，并采用兩個禁忌表.由于當鄰域規模比較大時，只試走一步，在規定的時間內，很容易陷入局部最優解，要采取一種策略使搜素的范圍更廣一些，并且所用的時間并不是很大.那么在規定一個可行解的情況下，對每兩個連續的移動用禁忌搜索得到一個可行解，然后從這些可行解當中選一個最好的解，當作下一次迭代過程的起點，重復以上過程直到不能得到更好的調度解則停止，更具體的描述如下：

JSP問題的完工時間取決于關鍵路徑長短，在一個可行調度解中如果工序之間的時間間隔為0，最長的路徑被稱為關鍵路徑，我們的工作就是如何減少關鍵路徑的長度.如圖1中關鍵路徑為（1，1）（2，1）（1，3）（1，4）（2，2）（3，2）（1，6），圖1中調度為單一關鍵路徑，當然可能出現多個關鍵路徑.在關鍵路徑上，有塊的定義，在圖1中有3個塊分別是B1.B2.B3。

移動的定義每個關鍵塊在Nowicki和Smutnicki的定義的基礎上，有以下幾點有所不同：

1）若關鍵塊B是關鍵路徑上第一個關鍵快，那么要交換的是關鍵塊B上的最后兩個工序61和62；

2）若關鍵塊B是關鍵路徑上的尾塊，則要交換關鍵塊B的前兩個工序和α₁和α₁

3）另外的關鍵塊B，交換前兩道工序α₁和α₁和最后兩道工序b₁和b₁，具體的操作如圖1所示.

這些移動構成了移動集合p（s），令g（s，p）來表示通過對s運用一次移動而獲得的一個可行解，那么s的鄰域N（s）={g（s，p）：p∈p（s）}.之所以這樣定義鄰域的原因是，每個關鍵塊只增加了兩個移動，并沒有極大的增加計算量。

2.2禁忌表

在傳統的Ts算法中，禁忌表T所記錄的是移動.也就是說在滿足定義的鄰域前提下，從一個可行解到下一個可行解的移動是交換工序i和j，那么有序對（i，j）被記錄在禁忌表T中，它的意思是在接下來的一次移動中，不能再進行工序i和j的交換，禁忌表并不能把每一個可行解都保存，鑒于此設置一個禁忌表長度，禁忌表長度是指接下來的迭代不能再回到禁忌元素的最大步數，每一個新的移動都會被加到禁忌表最后的位置，隨之最前面的移動被刪除，但這就會形成一個問題，當某個移動被刪除的時候，此移動還可能在某次迭代時被使用，因為此時該移動已經不在禁忌表中了，為了解決這一問題，采用雙禁忌表的策略，兩個禁忌表分別為SHORT-T和LONG-T（如圖2所示），其中T₁，T₁…T_i，…T_n=（（α₁，α₂），（α₃，α₄））…（（α_i，α_i），α_m，α_n））表示移動，SHORT-T用來存放當前搜索到并且需要禁忌的解（移動），當滿足迭代次數的迭代之后，并不是將所有禁忌的解直接釋放，而是將普通的解從SHORT-T中釋放，而通過移動產生最優解的移動則放入LONG-T中.LONG-T存儲的是歷史最優解，在LONG-T更新時，若當前解，與LONG-T中的解相同時，則說明出現了循環，可以允許出現一定的循環，但是循環達到一定次數的話，就要重新產生初始解而跳出循環.這么做的原因是，當通過迭代產生循環時，最容易產生循環的是產生最優解的移動而導致的循環，而且在最優解上產生的循環是不能容忍的，特別要強調的一點，SHORT-T存放的是移動，LONG-T存放的是歷史最優解。

2.3逆排時技術

給定一個排時問題實例E和它的開工順序，把工件的開工順序和加工順序倒過來得到另外一個可行解，例如給定的加工順序（o（1），o（2）…，o（n）），計算得到倒轉后的實例得到的加工順序為（o（n）….，o（2），o（1），計算倒轉后的每項工作的開始時間和最大完工時間。

舉個例子，給定加工時間矩陣T_ij和加工順序矩陣R_ij其中：

3.實例驗證

算法在linux環境下使用c語言進行實驗，實驗環境為，CPU i3處理器，內存lG.Benchmark算例是國際上通用的算例，能夠反映一個算法的優劣，對于35個Benchmark問題，將本文算法與TSAB算法進行比較計算得到makespan。

在合理的時間內，應用本算法有23個相同，并且是最優解，說明本算法對于大部分的算例能夠計算出最優解是可行的，有10個優于TSAB算法得到的解更接近最優解，有兩個與TSAB算法相比得到的解較差，從總體來說大部分的解都優于或者與TSAB算法的解相同，只有兩個解稍差，說明本算法有一定的優越性，結果不同的算例為FTl0，LAl6，LA22，LA24，LA25，LA27，LA29，LA36-LA40，其中與TSAB算法對比makespan表不同的實例如表1所示。

衡量車間調度問題算法的優劣的標準一般有兩個，分別是計算機時間和得到的最優解，本算法在計算時間上和TSAB算法基本相同，但是在尋優能力上比TSAB算法更強，由表1可畫出如圖6的折線圖，從圖6中可直觀看出本算法更接近最優解，表明本算法有一定的尋優能力，并且可有效提高解的質量。

4.結論

本文通過從JSP問題的搜索鄰域人手，提出了一種新的禁忌表的搜索算法，減少了算法在達到歷史最優解的時候產生的循環，從而提高了禁忌搜索算法的優化效果，通過對benchmarks實例進行測試，驗證了本文提出的設計算法有一定的尋優能力.當出現在作業車間調度中臨時加入一些工件工序的情況是下一步研究的內容，同時在數據量非常大的情況下，如何提高效率是研究的另一個方向。