求解車間調(diào)度問題的雙禁忌表禁忌搜索算法

劉勝輝　李小陽　張淑麗

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

關鍵詞：車間調(diào)度；啟發(fā)式算法；禁忌搜索；禁忌表；鄰域

DOI：10.15938/j.jhust.2016.06.010

中圖分類號：TP301

文獻標志碼：A

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

0.引言

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

1.問題描述

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

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

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

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

2.算法設計

2.1鄰域設計

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

JSP問題的完工時間取決于關鍵路徑長短，在一個可行調(diào)度解中如果工序之間的時間間隔為0，最長的路徑被稱為關鍵路徑，我們的工作就是如何減少關鍵路徑的長度.如圖1中關鍵路徑為（1，1）（2，1）（1，3）（1，4）（2，2）（3，2）（1，6），圖1中調(diào)度為單一關鍵路徑，當然可能出現(xiàn)多個關鍵路徑.在關鍵路徑上，有塊的定義，在圖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禁忌表

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

2.3逆排時技術

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

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

3.實例驗證

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

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

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

4.結論

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