李文超，楊宏兵

LI Wen-chao1, YANG Hong-bing2

(1.江蘇大學 汽車與交通工程學院，鎮(zhèn)江 212013；2.蘇州大學 機電工程學院，蘇州 215021)

0 引言

車間生產調度優(yōu)化不僅是制造自動化領域一項重要研究課題，也是現(xiàn)代企業(yè)管理一項重要內容。對于很多屬于NP難或屬于NP完全的調度問題，至今仍未發(fā)現(xiàn)求解它們的有效算法。

作為作業(yè)調度領域內一個典型模型，Job-shop問題自1976年Job-shop調度問題被證明為NP完全后[1]，關于其解的研究以及相關的延伸問題一直是學術界關注的一個焦點。Job-shop問題早期研究多集中于尋找其最優(yōu)解的精確算法如分枝定界、隱性枚舉等方法[2,3]，這類方法對規(guī)模較小問題（如5×20，或10×10等）效果顯著，但隨著問題規(guī)模增加，該類算法難以實現(xiàn)。自上世紀80代后，隨著計算機技術發(fā)展，研究多轉向于以尋找其近優(yōu)解為目的啟發(fā)式算法。如文獻[4,5]提出構建神經網(wǎng)絡方法來求解Job-shop問題。文獻[6]通過建立多代理結構體系求Job-shop的解。文獻[7]提到利用多點構建思路搜索其解。文獻[8]利用Lagrangian松弛神經網(wǎng)絡求其解。文獻[9]采用禁忌搜索算法和模擬退火方法取得較好效果。這些算法對于規(guī)模較大問題能夠在規(guī)定時間內找到較滿意近優(yōu)解，但也存在一些問題，如有的對參數(shù)取值比較敏感，而有的算法要找到理想的解則耗費時間較長。

作為一種啟發(fā)式隨機搜索算法，禁忌（Tabu Search）算法被普遍用于組合優(yōu)化問題求解。該算法在搜索過程中利用建立的Tabu表，對已經進行的搜索過程做選擇和記錄，為下一步的搜索方向提供參考。在Job-shop研究中，該方法被不同研究者所使用，取得良好效果。除上述文獻[9]外，利用該方法取得顯著效果還有文獻[10,11]。在本文中，對于Job-shop搜索過程中操作對的選擇采取了5種方式，每種方法均有其缺點和優(yōu)點。這些方式在搜索過程中如找不到可行解，則被暫時置入Tabu表，以其他方式代之，繼續(xù)搜索過程，直到得到滿意解或達到規(guī)定時間。

本文組織結構如下：第1節(jié)為問題描述，第2節(jié)針對Job-shop問題介紹算法方案及總體實現(xiàn)步驟。第3節(jié)對所提算法進行數(shù)值仿真實驗。第5節(jié)給出結論及評價。

1 問題描述

Job-shop問題主要是指要處理n個工件在在m臺機器上調度問題，即確定各工件在各臺機器上處理次序，使得某些性能指標達到最優(yōu)，通常以任務最大完工周期(makespan)作為指標。各工件在各機器上處理時，須滿足如下條件：1）每個工件最多經過m臺機器處理，且各工件以不同次序通過各臺機器；2）每臺機器加工各工件次序不同；3）各個工件在每臺機器上加工時間是確定的；4）每個工件通過各臺機器的次序是確定不變的；5）每個工件在同一時間只能在一臺機器上完成；6）每臺機器對各工件只加工一次（即不考慮可重入情況）；7）每臺機器在同一時間內只加工一個工件。

由于Job-shop問題復雜性，其求解方法多種多樣。文獻[12]介紹一種通過有向圖逐步去除析取約束方法來獲取其可行解。本文在其建立有向圖基礎上，通過添加約束（即有向?。┓椒▉砬笕∑淇尚薪?。其過程可通過如下實例[12]加以說明。

表1 4×3Job-shop問題實例

表1給出了一個4×3Job-shop問題（記為E1）初始條件，基于該初始條件，可建立其初始有向圖模型如圖1所示：

圖1 E1初始有向圖模型

由圖1可計算工件j在機器i上操作oij加工指標：

1）最早開工時間seij：圖中源點B到該操作所在的節(jié)點(i, j)間最大路徑的長度

2）最遲完工時間claij：圖中源點B到終點T間最大路徑長度與該操作所在的節(jié)點(i, j)到終點T間最大路徑的長度之差加上該操作處理時間pij，即：

在同一臺機器i上，工件j可先于工件k加工的先決條件是操作oij的最早完工時間ceij早于操作ojk的最遲開工時間seik，即：

圖2 E1添加約束后有向圖模型

在上述過程中，可互換操作對選取很重要，如果選取不當，則可能導致得不到可行方案或所獲調度方案不理想。本文提出利用Tabu表，在搜索過程中對于不合適選取方法，暫時限定其選取，提高搜索效率。

2 算法實現(xiàn)

2.1 禁忌搜索

作為一種元啟發(fā)式算法，禁忌搜索（TS）被廣泛應用于組合優(yōu)化問題求解。它基本組成要素主要有：初始解、鄰域、動作、喚醒函數(shù)、搜索策略、Tabu表、終止條件等。其基本思路是從初始解開始，在初始解形成的領域內采取既定動作進行搜索，找到該鄰域內最優(yōu)解，并以此最優(yōu)解為新的出發(fā)點，按既有搜索策略繼續(xù)進行搜索。如果在搜索過程中陷入某個鄰域內不能發(fā)現(xiàn)新的最優(yōu)解，則改換搜索策略繼續(xù)搜索，并將原策略放入Tabu表，暫時不用，以避免在搜索過程中陷入循環(huán)。在后續(xù)搜索過程中如果滿足一定條件，則該策略可被喚醒函數(shù)喚醒，可繼續(xù)使用。算法終止與具體條件。

作為一種普適性算法，禁忌算法在解決具體問題應用中若要取得好的效果，則需要結合具體問題進行具體分析，恰當確定算法在所求問題中基本元素和具體參數(shù)。

2.2 算法設置

在本文中，對于JS問題禁忌算法的初始解設置為其初始有向圖模型。動作為按照既定搜索規(guī)則選取可互換操作。鄰域為有向圖模型存在的互換操作對集合。搜索策略功能是選取合適互換操作對，這是算法關鍵。本文給出5種選取方法，算法在搜索過程中可根據(jù)具體情況靈活采用其中一種方法。對于可互換操作oij與ojk，各方法選取標準如下。

1）最小值方法，選取函數(shù)fc1值由下式確定：

2）均值方法，選取函數(shù)fc2如下：

3）乘值方法，選取函數(shù)值fc3如下：

4）均方值方法，選取函數(shù)值fc4如下：

5）均方值方法，選取函數(shù)值fc5如下：

若算法在搜索過程中使用某種選取方法fci找不到更好的解，將該函數(shù)放入Tabu表，暫停使用。直到Tabu表滿，用喚醒函數(shù)將其喚醒重新使用。

2.3 算法總體實現(xiàn)

算法總體思路是從初始解開始，計算初始有向圖中各工序參數(shù)，將存在先后順序操作間約束加在有向圖上，如存在可互換操作，采用2.2中搜索策略選取其中一對，確定先后順序并將其加在有向圖上。對更新后有向圖重復上述步驟，直到滿足終止條件。具體步驟如下：

步驟1：建立JS問題初始有向圖模型G0,并將該模型賦予臨時模型GT,即GT=G0;

步驟2：根據(jù)有向圖GT，若同一機器上任意兩操作間均存在次序約束，轉步驟7，否則轉步驟3。

步驟3：計算圖GT中各操作參數(shù)如最早（遲）開工和（完工）時間，兩操作對間時間間隔。若存在均小于0，轉步驟6。否則，轉步驟4。

步驟4：對存在先后次序操作對，將其次序約束添加到有向圖GT上，形成新有向圖GT’。令GT=GT’，判斷GT’中是否存在可互換操作對，若有轉步驟5；否則，轉步驟2。

步驟5：根據(jù)2.2中選取方法，選取函數(shù)值fci最小操做對，若，則按操作oij先于oik將約束添加到有向圖GT上，形成新有向圖GC，令GT=GC，轉步驟2。

步驟6：判斷Tabu表是否飽和，若飽和，彈出其第一個元素，并將步驟5中最近使用選取函數(shù)置入Tabu表，令GT=GC，轉步驟5。

步驟7：得到可行調度，終止程序。

3 仿真計算

本文從兩方面設計了數(shù)值仿真實驗：首先從求解精度測試所提算法（記為TSCG）性能，然后從求解效率方面對所提算法進行測試。在測試過程中，與文獻[10]所提算法i-TSAB進行對比。算法中Tabu表長度為3。算法程序用Matlab7.0編寫實現(xiàn)，仿真在PC上進行，參數(shù)為CPUCeleron M(1.6GHz), 內存504M。

圖3給出算法TSCG與i-TSAB（記為SEJS）在求解精度方面對比。橫標Ti表示不同規(guī)模算例,分別為(m×n)15×30、15×50、20×30、20×50、20×100；圖中橫標為各算例標號，縱坐標為算法相對精度，表示如下：

式（8）中H可取TSCG或i-TSAB，LB所求問題下界，所用算例和LB值可參見文獻[10]。

圖3 算法TSCG與i-TSAB求解精度比較

圖4為兩種算法求解效率比較。雖然兩種算法在求解過程中所耗費時間與問題規(guī)?；旧隙汲删€性關系，但由圖3可知算法TSCG的坡度明顯低于算法i-TSAB的坡度。結合圖3可以看出本文所提算法在求解精度方面在問題規(guī)模較小時不如i-TSAB，但在問題規(guī)模較大時兩者相近。同時在求解時間存在明顯優(yōu)勢。綜合考慮精度和效率，算法TSCG優(yōu)于算法i-TSAB。

圖4 兩種算法求解效率比較

4 結束語

本文針對Job-shop問題，在析取有向圖模型基礎上，提出一種通過逐步添加析取約束的禁忌搜索算法。算法在搜索過程中能夠通過不同策略選取可互換操作對。數(shù)值仿真結果說明算法TSCG在求解精度面和效率方面存在綜合優(yōu)勢，比較適合工程方面應用。

[1]Garey M R,Johnson D S,and Sethi R.The complexity of flow-shop and job-shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.

[2]M.Florian,P.Trepant,G.McMahon.An implicit enumerationalgorithm for the machine sequencing problem[J].Management Science,1971,17(7):782-792.

[3]H.H.Greenberg.A branch and bound solution to the general scheduling problem[J].Operations Research,1968,16(3):353-361.

[4]張長水,閻平凡.解Job-shop問題的神經網(wǎng)絡方法[J].自動化學報,1995,21(6):706-712.

[5]楊圣祥,汪定偉.神經網(wǎng)絡和啟發(fā)式算法混合策略解Jobshop調度問題[J].系統(tǒng)工程學報,1999,14(2):140-145.

[6]張宇,孫憲鵬.基于多代理結構的Job-shop動態(tài)優(yōu)化調度策略研究[J].制造業(yè)自動化,2001,23(3):22-25.

[7]J.C.Beck.Solution-guided multi-point constructive search for job shop scheduling[J].Journal of Artificial Intelligence Research,2007,29(1):49-77.

[8]Luh P.B.,Zhao xing,Wang Yajun,etc.Lagrangian relaxation neural networks for Job shop scheduling[J].IEEETRANSA CTION Son Robotics and Automation,2000,16(1): 78-88.

[9]C.Y.Zhang,P.Li,Y.Rao,etc.A very fast TS/SA algorithm for the job-shop scheduling problem[J].Computers and Operations Research,2008,25(1):282-294.

[10]E.Nowicki,C.Smutnicki.An advanced tabu search algorithm for the job shop problem[J].Journal of Scheduling,2005,8:145-159.

[11]E.Nowicki,C.Smutnicki.A fast taboo search algorithm for the job shop problem[J].Management Science,1996,42:797-813.

[12]Pinedo M.Scheduling:Theory,algorithm,and system[M].Beijing:China Machine Press,2005.