李 俊,劉志雄,張 煜,賀晶晶

(1.武漢科技大學汽車與交通工程學院，湖北 武漢，430081；2. 武漢理工大學物流工程學院，湖北 武漢，430063)

柔性作業(yè)車間調度優(yōu)化的改進模擬退火算法

李 俊1,劉志雄1,張 煜2,賀晶晶1

(1.武漢科技大學汽車與交通工程學院，湖北 武漢，430081；2. 武漢理工大學物流工程學院，湖北 武漢，430063)

針對柔性作業(yè)車間調度問題，提出一種改進模擬退火算法來進行求解。該算法引入粒子群算法中的基于位置取整和基于輪盤賭兩種個體編碼方法，并采用3種不同的局部搜索方法來構造個體的鄰域結構。算例計算表明，改進模擬退火算法在求解柔性作業(yè)車間調度問題時，比粒子群算法、混合粒子群算法以及模擬退火算法具有更好的求解性能，其中采用輪盤賭編碼時，算法的求解性能要優(yōu)于采用位置取整時的求解性能，且基于互換的局部搜索方法要優(yōu)于其他兩種局部搜索方法，能更有效地改善算法的求解性能。

柔性作業(yè)車間調度;job shop;模擬退火算法;輪盤賭;局部搜索

柔性作業(yè)車間調度問題(Flexible Job-shop Scheduling Problem，F(xiàn)JSP)與其他生產調度問題相比更為復雜，也更加貼近實際的生產情況。在傳統(tǒng)的作業(yè)車間調度問題(Job-shop Scheduling Problem，JSP)中，每個工件的每道工序只能在指定的機器上進行加工，而FJSP中每個工件的每道工序均可選擇多臺機器來進行加工，并且在不同機器上的加工時間也不同。但由于FJSP減少了對加工設備的約束，擴大了可行解的搜索范圍，所以問題的求解也更加復雜。

針對FJSP的復雜性，目前常用的求解方法有遺傳算法(GA)、模擬退火算法(SA)、演化算法(EA)、禁忌搜索(TS)、粒子群算法(PSO)等智能優(yōu)化算法，其中模擬退火算法由于穩(wěn)定性較好，得到了廣泛的應用。Laarhoven等[1]于1992年最早將模擬退火算法應用于求解車間作業(yè)(Job Shop)調度問題。Jamili等[2]將模擬退火算法與仿電磁學算法雜交來求解周期作業(yè)車間調度問題；Zhang等[3]提出了一種基于塊屬性的模擬退火算法來求解考慮總權重拖期的Job Shop問題；Dai[4]等使用一種改進的遺傳-模擬退火算法來對柔性作業(yè)車間進行能源有效性調度優(yōu)化，對作業(yè)車間的能源消耗和環(huán)境影響等因素進行了考慮；Elmi等[5]針對考慮工作單元間物料流動和可重入的作業(yè)車間調度問題，運用模擬退火算法進行了求解，為了提高算法的搜索效率，提出了基于塊概念的鄰域結構；Zhang等[6]基于一種新的免疫機制提出了一種求解作業(yè)車間調度問題的混合模擬退火算法，對其總權重拖期進行了優(yōu)化；Jolai等[7]針對無等待的兩階段柔性作業(yè)車間調度問題提出了一種雙目標的模擬退火算法，該算法混合了田口法以及多目標決策方法；Shahsavari-Pour等[8]將遺傳算法與模擬退火算法混合提出了一種新的混合亞啟發(fā)式算法，來求解多目標柔性作業(yè)車間調度問題；梁旭等[9]提出了一種求解車間調度問題的新遺傳退火混合策略，將遺傳算法與模擬退火算法相結合；藍萌等[10]提出了一種混合鄰域搜索算法來求解多目標柔性作業(yè)車間調度問題，該算法融合了模擬退火算法、遺傳算法以及免疫機制。綜上可見，在求解作業(yè)車間調度問題，尤其是柔性作業(yè)車間調度問題時，大多數(shù)學者都將模擬退火算法作為一種局部搜索方法來對其他算法進行改進。但模擬退火算法在參數(shù)設置不當時容易陷入局部最優(yōu)。為此，本文考慮以模擬退火算法作為主體，加入其他的局部搜索策略來改善算法跳出局部最優(yōu)的能力，對其進行改進，并通過對幾個不同規(guī)模的FJSP算例進行試驗計算，以驗證改進模擬退火算法求解FJSP的有效性。

1 柔性作業(yè)車間調度問題

柔性作業(yè)車間調度問題的優(yōu)化目標可以描述為最小化最大完工時間MakeSpan。假設有n個工件，m臺機器，工件i有Ji道工序。在某一確定的加工序列中，Sijk、Tijk、Cijk分別為工件i的第j(j∈Ji)道工序在機器k上的開始加工時間、加工過程時間、加工完成時間，而Tegk、Cegk則分別為機器k的上一加工任務的加工過程時間和加工完成時間，Cendk為機器k上加工的最后一道工序的加工完成時間，CTk為機器k上所有工件的加工完成時間，CTend為所有工件的加工完成時間。則最大作業(yè)完工時間最小的目標函數(shù)為：

Min{CTend}=max{CTk}

(1)

約束條件為：

Sijk+Tijk=Cijk

(2)

Sijk=max{S(i-1)(j-1)k+

T(i-1)(j-1)k,Ci(j-1)(k-1)}

(3)

Cegk-Cijk≥Tegk

(4)

CTk=Cendk

(5)

CTend=max{CTk}

(6)

2 求解FJSP的改進模擬退火算法

改進的模擬退火算法(ModifiedSimulatedAnnealing，MSA)是將粒子群算法(PSO)中粒子編碼方法引入到模擬退火算法中來，采用基于位置取整和基于輪盤賭[11]兩種不同的編碼方法，并利用3種不同的局部搜索方法來構造個體的鄰域結構。

2.1 個體編碼方法

在柔性作業(yè)車間調度問題中，需要確定每個工件的加工路徑，將粒子群算法中的兩種粒子編碼方法(基于位置取整和基于輪盤賭的方法)引入到模擬退火算法中，以此來進行工序加工機器的選擇，進而確定工件的加工路徑。

(1)基于位置取整的個體編碼。

基于位置取整的編碼方法需要限定個體位置在正數(shù)范圍內，然后對其進行取整操作，通過映射對應的機器號得到每道工序所對應的加工機器，從而得到每個工件的加工路徑，最后根據(jù)工件的有序加工序列和加工路徑來生成調度方案。

(2)基于輪盤賭的個體編碼。

由于柔性作業(yè)車間調度問題存在部分柔性的情況，即工序并不能在所有機器上進行加工，因此采用基于位置取整的編碼方法進行個體編碼時，取整后的個體位置對應的機器號可能并不在該工序的備選機器范圍內，此時需要對該工序的個體位置進行重新生成，這樣就會增加算法的計算時間。因此考慮一種基于輪盤賭的編碼方法，該方法采用輪盤賭概率選擇來進行機器選擇，每次生成的個體位置一定會有唯一的一臺備選機器與之一一對應，因此在求解部分柔性作業(yè)車間調度問題時能明顯比基于粒子位置取整的編碼方法更加節(jié)省時間，加快算法的搜索效率。

基于輪盤賭的編碼方法限定個體位置在(0,1)區(qū)間內隨機生成，得到每道工序選擇機器的輪盤賭概率，然后看其概率落在哪臺機器的概率區(qū)間內，就選擇哪臺機器來進行加工。從而得到每個工件的加工路徑，最后根據(jù)工件的有序加工序列和加工路徑來生成調度方案。

2.2 局部搜索方法

模擬退火算法要求較高的初始溫度、較慢的降溫速率、較低的終止溫度以及各溫度下足夠多的抽樣次數(shù)，同時，如果在參數(shù)選取不恰當時，算法容易陷入某個局部最優(yōu)值。為了使算法在合適的參數(shù)設置下能夠順利地找到最優(yōu)的調度解，且能相應地降低算法的運行時間，改進模擬算法中考慮加入局部搜索的算法。

(1)基于互換的局部搜索方法?；诨Q的局部搜索方法按以下步驟來實現(xiàn)：①針對當前解隨機選擇個體編碼中的兩個不同位置p、q(p

(2)基于逆序的局部搜索方法?；谀嫘虻木植克阉鞣椒ò匆韵虏襟E來實現(xiàn)：①針對當前解隨機選擇個體編碼中的兩個不同位置p、q(p

(3)基于插入的局部搜索方法。基于插入的局部搜索方法按以下步驟來實現(xiàn)：①針對當前解隨機選擇個體編碼中的兩個不同位置p、q(p

以上各種局部搜索方法均設置一定的次數(shù)進行重復操作。

2.3 改進模擬退火算法的實現(xiàn)

在設定的性能指標為最小化最大完工時間時，求解FJSP的改進模擬退火算法可以按以下步驟來實現(xiàn)：

(1)控制參數(shù)的初始化。設置初始溫度T0、降溫速率Q、結束溫度Te以及每個溫度下的迭代次數(shù)(即Metropolis鏈長)L。

(2)初始解S1的編碼。采用粒子群算法中的編碼方法對初始解進行個體編碼。

(3)當前解S1的局部搜索。設置一定的局部搜索次數(shù)對當前解S1的鄰域進行搜索，找到新的解S2。

(4)Metropolis準則判斷。設最大完工時間計算函數(shù)為f(S)，則當前解的最大完工時間為f(S1)，新解的最大完工時間為f(S2)，時間差為df=f(S2)-f(S1)，若df<0，則接受S2作為新的當前解，即S1=S2。否則計算新解S2的接受概率exp(-df/T)，其中T為當前迭代溫度，若exp(-df/T)>rand(rand表示(0,1)之間的隨機數(shù))，也接受S2作為新的當前解，即S1=S2。否則保留當前解S1。

(5)降溫迭代。利用降溫速率Q對當前溫度T進行降溫，降溫方法為T=Q×T。

(6)迭代終止。當前溫度小于結束溫度，即T

3 算例分析

3.1 算例計算

選用經典FJSP算例Hurink算例中的car1～car8問題[12]來進行計算。這8個算例的規(guī)模分別為car1(11×5)(11×5為算例規(guī)模，表示有11個工件，5臺加工機器，其他算例類似)、car2(13×4)、car3(12×5)、car4(14×4)、car5(10×6)、car6(8×9)、car7(7×7)、car8(8×8)。

對于改進模擬退火算法(MSA)，分別采用基于位置取整和基于輪盤賭的編碼方法，其參數(shù)設定為初始溫度T0=1000、降溫速率Q=0.98、結束溫度Te=0.001，每個溫度下的迭代次數(shù)L=300，基于互換操作的局部搜索次數(shù)為3次。對于car1～car8問題，連續(xù)優(yōu)化20次，將改進模擬退火算法(MSA)的求解結果分別與SA、采用慣性權重線性遞減的基本粒子群算法(PSO)和混合粒子群算法(HPSO)的求解結果進行比較分析。其中，SA的參數(shù)設置與MSA的參數(shù)設置保持一致。PSO和HPSO均采用基于輪盤賭的編碼方法，且HPSO為加入了基于互換操作的局部搜索方法的粒子群算法。其中，考慮到FJSP算例的復雜性，為了算法能獲得更好的求解性能，將PSO的參數(shù)設置為種群數(shù)量為20，最大迭代次數(shù)為1000次，將HPSO的互換次數(shù)設置為3次。

采用Matlab對上述問題進行編程求解，以優(yōu)化最大作業(yè)完工時間為目標，找出各方法在求解不同問題時得到的最優(yōu)解、最差解以及平均解，結果如圖1所示，其中適應值表示設定的優(yōu)化目標，即最大作業(yè)完工時間。

從圖1中可以看出，在8個car類FJSP算例的計算中，MSA無論是最優(yōu)解、最差解還是平均解都要優(yōu)于PSO、HPSO以及SA的相應值，而且基于輪盤賭編碼的MSA比基于位置取整的MSA具有更好的求解性能。

圖1 不同算法解的比較

Fig.1 Comparison of solutions by different algorithms

3.2 MSA算法控制參數(shù)設置分析

對于MSA算法，一般設置初始溫度T0=1000，而Te、Q以及L的設置則比較靈活。在T0確定了以后，這3個參數(shù)的設置直接與算法的求解性能相關。以下以car1問題為例，以優(yōu)化最大作業(yè)完工時間為目標，采用基于輪盤賭編碼的MSA算法，對Te、Q及L的參數(shù)選擇進行分析。

(1)Te的設置。設置T0=1000、Q=0.98、L=300，互換操作次數(shù)為3次，連續(xù)優(yōu)化20次，Te分別設置為0.0001、0.001、0.01和0.1來進行試驗計算，結果如表1所示。從表1中可以看出，Te的值并不是越小越好，當Te=0.001時，雖然求解時間比前兩者要長，但算法有更好的尋優(yōu)性能和穩(wěn)定性能，且求解時間也在可接受的范圍之內。因此Te的值選擇0.001較佳。

(2)Q的設置。設置T0=1000、Te=0.001、L=300，互換操作次數(shù)為3次，連續(xù)優(yōu)化20次，Q分別設置0.90、0.93、0.95和0.98來進行試驗計算，結果如表2所示。從表2中可以看出，當Q=0.9、0.93、0.95時，雖然算法的耗時明顯少于Q=0.98時，但其求解結果卻要差的多，因而設置Q=0.98更為合理。

(3)L的設置。設置為T0=1000、Te=0.001、Q=0.98，互換操作次數(shù)為3次，連續(xù)優(yōu)化20次，L分別設置為100、200、300和400來進行試驗計算，結果如表3所示。從表3的結果可以看出，在

表3 不同Metropolis鏈長時的計算結果

Table 3 Calculation results at different lengths of Metropolis

可接受的求解耗時范圍內，當L=300時，算法取得了更好的求解結果。

綜上所述，MSA算法的控制參數(shù)設置為T0=1000、Q=0.98、Te=0.001、L=300較為合理。

3.3 局部搜索方法的比較

采用不同的局部搜索方法會使MSA算法得到不同的求解結果。對于上述car1～car8問題，運用基于輪盤賭編碼的MSA算法，分別采用3種不同的局部搜索方法來進行求解。其參數(shù)設置均為T0=1000、Q=0.98、Te=0.001、L=300，局部搜索次數(shù)為3次，連續(xù)優(yōu)化20次，找出不同局部搜索方法下的最優(yōu)解、最差解以及平均解，結果如圖2所示。從圖2中可以看出，在采用3種不同局部搜索方法的MSA算法中，基于互換的局部搜索方法有更好的求解性能，尤其是在算例規(guī)模更大的時候，比如car6問題。同時，基于互換的局部搜索方法在編程實現(xiàn)時代碼更加簡單，具有更快的求解速度。

圖2 不同局部搜索策略下算法解的比較

Fig.2 Comparison of solutions by the algorithm under different local searches

3.4 局部搜索次數(shù)的確定

在局部搜索過程中，局部搜索次數(shù)的設置是一個很重要的參數(shù)。局部搜索次數(shù)過少，則搜索的效果不明顯，無法體現(xiàn)局部搜索的作用，而次數(shù)過多則會加大MSA算法的搜索空間，影響算法的求解效率。為此，需要確定一個合適的局部搜索次數(shù)，既能保證MSA算法的有效性，又能保證MSA算法的求解效率。

針對規(guī)模較大的car6問題，參數(shù)設置為T0=1000、Q=0.98、Te=0.001，L=300，連續(xù)優(yōu)化20次，分別設置局部搜索次數(shù)為1～10次來進行試驗計算，結果如表4所示。從表4中可以看出，算法的求解結果并不完全是隨著互換操作次數(shù)的增加而變得更好，但求解時間卻隨著互換操作次數(shù)的增加而變得越來越長。設置合理的互換操作次數(shù)不僅可以獲得更好的求解結果，而且可以縮小算法的搜索空間，節(jié)約算法的求解時間，加快算法的求解效率。從表5可以看出，無論是最優(yōu)值、最差值還是平均值，從提高算法的尋優(yōu)性能和穩(wěn)定性能角度出發(fā)，互換操作次數(shù)設置為3次最為合理。

4 結語

本文在研究了柔性作業(yè)車間調度問題的基礎上，將PSO算法中基于位置取整和基于輪盤賭兩種不同的編碼方法引入到模擬退火算法中來，并采用了3種不同的局部搜索方法，提出一種改進模擬退火算法(MSA)來求解柔性作業(yè)車間調度問題。然后通過對幾個不同規(guī)模的FJSP算例的試驗計算，分析了不同局部搜索方法的有效性，確定了合理的參數(shù)，說明了基于輪盤賭編碼的MSA算法在求解FJSP問題時具有更好的求解性能，且采用基于互換的局部搜索方法能有效改善算法的求解性能。

[1] Laarhoven P J M，Aarts E，Lenstra J K．Job shop scheduling by simulated annealing[J]．Operations Research，1992，40(1)：113-125．

[2] Jamili A，Shafia M A，Tavakkoli-Moghaddam R．A hybridization of simulated annealing and electromagnetism-like mechanism for a periodic job shop scheduling problem[J]．Expert Systems with Applications，2011，38：5895-5901．

[3] Zhang R，Wu C．A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]．Computers & Operations Research，2011，38：854-867．

[4] Dai M，Tang D B，Giret A，et al．Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J]．Robotics and Computer-Integrated Manufacturing，2013，29：418-429．

[5] Elmi A，Solimanpur M，Topaloglu S，et al．A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts[J]．Computers & Industrial Engineering，2011，61：171-178．

[6] Zhang R，Wu C．A hybrid immune simulated annealing algorithm for the job shop scheduling problem[J]．Applied Soft Computing，2010，10：79-89．

[7] Jolai F，Asefi H，Rabiee M，et al． Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]．Scientia Iranica E，2013，20(3)：861-872．

[8] Shahsavari-Pour N，Ghasemishabankareh B．A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling[J]．Journal of Manufacturing Systems，2013，32：771-780．

[9] 梁旭，黃明，常征．求解車間調度問題的一種新遺傳退火混合策略[J]．計算機集成制造系統(tǒng)，2005，11(6)：851-854．

[10]藍萌，徐汀榮，黃斐．使用混合鄰域搜索算法求解多目標柔性JSP問題[J]．計算機工程與設計，2011，32(1)，293-296．

[11]劉志雄，楊光祥．基于輪盤賭概率分配編碼方法的并行機調度優(yōu)化[C]//Proceedings of the 29th Chinese Control Conference，Beijing，2010：1775-1780．

[12]Monaldo Mastrolilli．Flexible job shop problem[DB/OL]．http: //people.idsia.ch/～monaldo /fjsp.html.

[責任編輯 鄭淑芳]

Modified simulated annealing algorithm for flexible job-shop scheduling problem

LiJun1,LiuZhixiong1,ZhangYu2,HeJingjing1

(1. College of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan 430081, China; 2. College of Logistics Engineering, Wuhan University of Technology, Wuhan 430063, China)

A modified simulated annealing algorithm was put forward to resolve the flexible job-shop scheduling problem, which used two kinds of individual encoding method respectively based on particle position rounding and roulette probability assignment in particle swarm algorithm.Three different local search methods were employed to constitute the neighborhood structure. The computational results show that the modified simulated annealing algorithm is more effective than particle swarm algorithm, hybrid particle swarm algorithm and simulated annealing algorithm in resolving the flexible job-shop scheduling problem. Compared with the position rounding encoding method, the roulette-probability-assignment-based encoding method can render the algorithm more effective, and the local search method based on crossing-over operation is better than the other two search methods in improving the solving performance of the algorithm.

flexible job-shop scheduling problem; job shop;simulated annealing algorithm; roulette selection; local search

2014-09-05

國家自然科學基金資助項目(70801047,71372202)；中央高?；究蒲袑ｍ椈鹳Y助項目(2013-IV-057).

李 俊(1989-)，男，武漢科技大學碩士生.E-mail:286485135@qq.com

劉志雄(1975-)，男，武漢科技大學教授，博士.E-mail:lzx_brad@126.com

TP18

A

1674-3644(2015)02-0111-06