劉勝輝　李小陽(yáng)　張淑麗

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

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

DOI：10.15938/j.jhust.2016.06.010

中圖分類(lèi)號(hào)：TP301

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-2683（2016）06-0050-05

0.引言

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

1.問(wèn)題描述

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

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

2）加工順序矩陣J_M是已知的，也就是說(shuō)加工每個(gè)工件各個(gè)工序的加工，必須在指定的機(jī)器上；

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

2.算法設(shè)計(jì)

2.1鄰域設(shè)計(jì)

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

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

移動(dòng)的定義每個(gè)關(guān)鍵塊在Nowicki和Smutnicki的定義的基礎(chǔ)上，有以下幾點(diǎn)有所不同：

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

2）若關(guān)鍵塊B是關(guān)鍵路徑上的尾塊，則要交換關(guān)鍵塊B的前兩個(gè)工序和α₁和α₁

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

這些移動(dòng)構(gòu)成了移動(dòng)集合p（s），令g（s，p）來(lái)表示通過(guò)對(duì)s運(yùn)用一次移動(dòng)而獲得的一個(gè)可行解，那么s的鄰域N（s）={g（s，p）：p∈p（s）}.之所以這樣定義鄰域的原因是，每個(gè)關(guān)鍵塊只增加了兩個(gè)移動(dòng)，并沒(méi)有極大的增加計(jì)算量。

2.2禁忌表

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

2.3逆排時(shí)技術(shù)

給定一個(gè)排時(shí)問(wèn)題實(shí)例E和它的開(kāi)工順序，把工件的開(kāi)工順序和加工順序倒過(guò)來(lái)得到另外一個(gè)可行解，例如給定的加工順序（o（1），o（2）…，o（n）），計(jì)算得到倒轉(zhuǎn)后的實(shí)例得到的加工順序?yàn)椋╫（n）….，o（2），o（1），計(jì)算倒轉(zhuǎn)后的每項(xiàng)工作的開(kāi)始時(shí)間和最大完工時(shí)間。

舉個(gè)例子，給定加工時(shí)間矩陣T_ij和加工順序矩陣R_ij其中：

3.實(shí)例驗(yàn)證

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

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

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

4.結(jié)論

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