解決作業車間調度的微粒群退火算法

摘 要:針對微粒群優化算法在求解作業車間調度問題時存在的易早熟、搜索準確度差等缺點，在微粒群優化算法的基礎上引入了模擬退火算法，從而使得算法同時具有全局搜索和跳出局部最優的能力，并且增加了對不可行解的優化，從而提高了算法的搜索效率;同時，在模擬退火算法中引入自適應溫度衰變系數，使得SA算法能根據當前環境自動調整搜索條件，從而避免了微粒群優化算法易早熟的缺點。對經典JSP問題的仿真實驗表明，與其他算法相比，該算法是一種切實可行、有效的方法。

關鍵詞:微粒群優化; 模擬退火; 作業車間調度問題

中圖分類號:TP301.6 文獻標志碼:A

文章編號:1001-3695(2010)03-0856-04

doi:10.3969/j.issn.1001-3695.2010.03.013

Hybrid algorithm of particle swarm optimization and

stimulated annealing for job-shop scheduling

CAI Bin， MAO Fan， FU Li， YANG Shi-hai

(School of Software Engineering， Chongqing University， Chongqing 400044， China)

Abstract:This paper proposed a hybrid algorithm of particle swarm optimization (PSO) and simulated annealing (SA) algorithm， which was used to overcome the deficiency of solving job-shop scheduling problem (JSP)， such as premature convergence and poor search accuracy.By combing PSO with SA algorithm， increased the ability of global search and jumping out of local optimum. And built the optimization of poor solutions to increase the search efficiency. And， by adding the self-adaptive temperature decay coefficient， made the SA algorithm could auto-tune the search criteria according the environment， avoid the deficiency of premature convergence. Comparsion with other results in some of the literatures indicates that this algorithm is a viable and effective approach for the job-shop scheduling problem.

Key words:particle swarm optimization(PSO); simulated annealing(SA); job-shop scheduling problem(JSP)

作業車間調度問題[1](JSP)作為生產制造系統中一個熱門研究領域，一直備受調度領域的重視。其主要目的是在已知資源和工藝約束條件下，確定工件加工的順序和時間。作為一組復雜的組合優化問題，JSP是典型的NP-hard問題[1]，因此，JSP常被用來測試智能算法的性能。這在實際研究和工程領域中具有重要的意義。目前求解JSP的方法主要有分支定界法、啟發式算法、模擬退火算法、禁忌搜索算法、蟻群算法、免疫算法、神經網絡算法以及遺傳算法等。

微粒群優化(PSO)算法[1]作為一類針對連續性函數的優化算法，在JSP上的研究相當少。目前，PSO在JSP上的代表性研究主要有:Sha等人[2]用Giffler-Thompson啟發式算法，并結合禁忌搜索提出的針對最小化最大完工時間的混合PSO算法;Xia等人[3，4]將SA算法嵌入PSO提出的求解JSP和多目標柔性JSP的混合算法;Lian等人[5]將PSO與遺傳算法(GA)相結合提出的求解JSP的混合算法;Tu等人[6]提出的求解傳統JSP的拓撲PSO算法等。

PSO的收斂速度很快，但收斂的精確度卻很低，易陷入局部最優。模擬退火[7](SA)算法是采用一系列連續的搜索策略來進行尋優，能避免搜索陷入局部最優，但其收斂速度很慢，因此用單一的算法很難獲得JSP的全局最優解。對此，許多研究開始致力于PSO混合算法。具有代表性的有: Song等人[8]通過PSO和SA構建的并行式解決方法——HPSOSA算法;Xia等人[3]用SA算法對PSO中的群體最優位置進行局部尋優的HPSO算法;Liu等人[9]提出的基于PSO的改良式基因演算法——PSOMA，以及Li等人[10]提出的求解多目標問題MOPSO算法等。雖然這些算法的有效性都已被證明，但仍存在易產生不可行解、微粒多樣性差等缺點。

本文介紹了一種新的結合了PSO與SA算法的混合微粒群算法——NPSOSA。該算法不僅能有效避免PSO中存在的早熟問題，而且算法的全局收斂性和搜索的準確度也得到了提高。

1 JSP描述

JSP是研究n個工件在m臺機器上加工的過程。每個工件在每臺機器上的加工時間已知，并且每個工件必須按照事先規定的順序完成其在所有機器上的加工，即技術約束條件。

已知條件有:a)工件集pi(i=1，…，n);b)機器集mj(j=1，2，…，m);c)工序OPi，j(i=1，…，m;j=1，…，n)，表示第i臺機器上的j道工序所加工的工件號;d)時間Ti，j，為第i個工件pi的第j道工序所用的時間。且JSP的工件加工必須滿足如下約束條件:a)既定工件加工順序不能改變;b)某時刻某臺機器上最多只能加工一個工件;c)當工件在機器上加工時，只有當前操作完成后，工件才能離開機器;d)在某時刻工件只能在一臺機器上加工。

JSP的求解目標通常是最小化工件最大完工時間，即T=min{max(Ci)}，Ci為工件i(i=1，…，n)的完工時間。

2 NPSOSA

2.1 算法總體描述

微粒群優化算法[11]是基于群體智能的隨機尋優算法，具有全局尋優的特點，但容易陷入局部最優解。模擬退火算法是一種基于Mente Carlo迭代求解策略的隨機尋優算法，具有概率突跳的能力，能有效避免搜索過程陷入局部最優解。

本算法同時繼承了PSO和SA算法的優點，既能在全局范圍內尋找問題最優解，又能避免算法在搜索過程中陷入局部最優解。同時，本文通過采用Giffler-Thompson啟發式算法對微粒進行初始化，使微粒盡可能散落在可行域內，避免了由于PSO算法中微粒的初始位置是隨機產生的，而使得某些微粒散落在問題可行域外，從而降低微粒的使用率，造成資源浪費的情況。

為保持本算法在搜索過程中的分散性，擴大搜索范圍，避免搜索早熟，首先利用SA算法對PSO算法中每個微粒的最佳位置進行局部尋優[12]，然后采用輪盤賭策略從所有微粒的最佳位置中選出一個作為整個種群的最優解。步驟如下:

a)種群尋優(swarm optimizing)。由于PSO算法是通過將微粒的位置引入目標函數來評價當前微粒，在本步驟中，算法首先使用目標函數對種群中所有微粒進行評價，找出每個微粒的最佳位置;然后從所有的最佳位置中找出使得目標函數值最優的微粒，記為種群最優位置;接下來根據PSO的速度和位置更新公式更新微粒，再按如上方法再次查找并更新微粒的最佳位置和群體最佳位置，直到滿足算法終止條件。

b)SA鄰域搜索(SA-neighborhood search)。將微粒的最佳位置作為SA算法的初始值，生成當前微粒最佳位置的一個鄰域解，并計算用此鄰域解代替當前微粒最佳位置的概率。連續進行L次鄰域搜索，然后使用輪盤賭策略從L個鄰域值中選擇一個值代替當前微粒的最佳位置。重復此過程，直到所有微粒都進行了鄰域搜索。

c)最優選擇(optimization choice)。對步驟b)中所有微粒最佳位置使用輪盤賭策略，選出一個最佳位置作為整個種群的最佳位置。算法總體流程如圖1所示。

算法的終止條件為:種群達到最大迭代次數，或群體最佳位置k次保持不變。

2.2 算法相關定義

定義1 違反約束的投影。若對微粒在當前搜索空間上某個維度上的投影進行解碼后，此投影不滿足作業車間調度的約束條件，則稱此投影為當前搜索空間上違反約束的投影。

定義2 不可行解約束違反量函數。用于表示某個微粒中違反約束的投影個數。

定義3 溫度衰減系數。在SA中，溫度的控制通過函數Tk+1=μ×Tk進行。其中μ為溫度衰減系數，其通常為一個常數。

定義4 自適應溫度衰變系數。該系數指可通過對搜索過程優劣的感知來動態地自我調整溫度衰變系數。

本文在罰函數[1]的基礎上，給出自適應溫度衰變系數的計算方法:β=μ+[1-e(fpi-favg)]×N(0，1)2Tk。其中:favg為種群的平均目標函數值;fpi為當前微粒最佳位置的目標函數值;μ為初始溫度衰減系數;Tk為前一次迭代中微粒的溫度。

定義5 微粒最佳位置(pbest)。若當前微粒在當前時刻t的目標函數值優于該微粒在t1(t1

定義6 群體最佳位置(gbest)。所有微粒的pbest中，使目標函數最優的pbest則為群體最佳位置。

定義7 鄰域解。對某個值進行SA鄰域搜索時，在其鄰域范圍內產生新解。計算方法為X=pi+η×γ×N(0，1)。其中:pi為當前微粒的pbest;η為搜索步長;N(0，1)為服從均值為0、方差為1的高斯分布的隨機數;γ為設定的鄰域搜索范圍。

定義8 微粒最優選擇概率。用于表示當前微粒被選為群體最優微粒的概率。計算方法如下:

pc=e-(f(Pi)-f(Pg))/t/∑Nj=1 e-(f(Pj)-f(Pg))/t

其中:N表示整個選擇集中微粒的個數;pi表示微粒i的pbest;pg表示種群的gbest;t為當前溫度。

定義9 假微粒。當微粒在迭代中產生了不可行解時，用于代替此微粒的微粒。生成方式如下:

X=pbest+r×(pbest-xi+vi)×N(0，1)

其中:r表示在0與1之間的隨機分布數;N(0，1)為服從均值為0、方差為1的高斯分布的隨機數;xi表示當前微粒的位置;vi表示微粒當前速度。

定義10 不可行解替換概率。用于表示產生不可行解的微粒被相應的假微粒替換的概率。計算方法為

p=min{1，e-(f(pbest)-f(x))/t}

2.3 算法詳細描述

2.3.1 種群尋優

算法涉及的參數:a)PSO相關參數，種群大小size，算法迭代次數N，微粒加速常數c1和c2;b)SA相關參數，初始溫度衰減系數β，最大溫度衰減系數β1，最小溫度衰變系數β2，SA鄰域搜索次數L。尋優步驟如下:

a)根據Giffler-Thompson啟發式算法對微粒的位置和速度進行初始化;

b)計算種群中每個微粒的目標函數值;

c)更新微粒的pbest和gbest;

d)重復執行下列步驟:

(a)對微粒的pbest進行SA鄰域搜索;

(b)更新各微粒的pbest;

(c)執行最優選擇操作，更新種群gbest;

(d)gbest是否滿足算法終止條件?若是，轉e)，否則轉d);

e)輸出種群最優解。

2.3.2 SA鄰域搜索

在SA算法中，溫度的選取對搜索效率的影響很大，其溫度的控制是通過預先設定溫度，然后再按照溫度衰變函數進行降溫。不能根據算法當前收斂情況來動態調整其局部搜索的深度。本文引入自動調整溫度衰變系數，使得SA能根據當前收斂狀況來動態調整退火算法的溫度衰減速率，使算法能夠自適應改變局部搜索的深度，調整種群多樣性。

退火算法溫度衰減速率的變化，主要是通過對微粒個體的目標函數值與種群的平均目標函數值來感知算法的局部收斂情況，進而根據收斂情況改變衰變速率。當個體目標函數值接近種群平均值時，通過相對的降低溫度衰變系數來適當地提高種群多樣性;否則相反。整個搜索步驟如下:

a)按t0=-fgbest / ln(0.2)計算算法初始溫度t0。 其中fgbest為當前種群最佳微粒的目標值。

b)接收微粒的pbest作為SA的初始解。

c)對下列步驟執行L次:

(a)在pbest鄰域內生成鄰域解。

(b)計算自適應溫度衰變系數β。

(c)由Tk+1=β×Tk計算當前溫度Tk+1。

(d)計算用鄰域解代替pbest的概率。

d)根據(d)得到的概率，使用輪盤賭策略在微粒的L個鄰域解中選擇一個值用于代替當前微粒的pbest。

2.3.3 最優選擇

把種群的pbest及gbest作為一個最優候選集，從中選一個值更新種群的gbest，作為算法最優解。最優選擇步驟如下:

a)用在SA鄰域搜索中得到的pbest及gbest構建一個最優選擇集。

b)計算候選集中微粒的最優選擇概率。

c)根據b)中的最優選擇概率，首先，執行S-1次輪盤賭策略，從候選集中選出S-1個pbest作為最終候選集;其次，執行第S次輪盤賭策略，從最終候選集中選出一個pbest作為種群的gbest。

d)輸出gbest。

2.3.4 目標函數

由于本文研究的是作業車間調度的完工時間Cmax，確定問題的目標函數f(i)=Cmax。

Cmax=maxC(i，j) 1≤i≤m，1≤j≤n

C(1，1)=C(OP11-1，1)+T(p11，1)

C(1，j)=max{C(1，j-1)，C(O(p1j-1)，j，j)}+T(p1j，j)

C(i，1)=C(Opi1-1，1)+T(pi1，1)

C(i，j)=max{C(Opij，j-1)，C(O(pij-1)j，j}+T(pij，j)

2.3.5 不可行解優化

為了對算法在迭代過程中產生的不可行解進行優化，本算法雖然使用Giffler-Thompson啟發式算法初始化微粒位置，但這只能使初始微粒盡可能有效，并不能保證微粒在整個迭代過程中都有效。

本文針對產生不可行解的微粒進行如下優化:

a)針對該微粒生成相應的假微粒。

b)計算不可行解替換概率p。

c)用假微粒以概率p代替原微粒。

2.3.6 算法編碼及解碼

1)編碼 對n×m的JSP，微粒的位置表示為對應于m臺機器的m個子串構成的矩陣，每個子串由n個符號組成，每個符號代表微粒在空間中某個維度上的投影;然后采用基于工件與機器編碼的混合方式，運用ROV規則[1]，將矩陣中的數值轉換為與工件的編號相關的整數。

2)解碼 結合ROV矩陣，工件加工時間矩陣T，工序矩陣OP，采用先后表規則[1]，分析機器上當前等待隊列的狀態，選擇當前等待隊列中最先出現在先后表中的操作，逐步得到最終調度解。

3 仿真實驗結果

為了測試NPSOSA算法的效率和性能，本文以MATLAB 7搭建實驗環境，參數選取如表1所示。將本算法與由Wei等人[9]提出的HPSO算法就JSP的一些經典問題的求解結果進行對比。算法對每個問題獨立執行20次。比較結果如表2所示。表2中涉及的符號描述如下:BKS為該問題目前的最優解;RE(%)為某問題的平均值超過BKS的百分比;Tav為算法尋優所用時間。

通過表2中的比較可看出，NPSOSA算法對所有的實例都能在可接受的時間范圍內找到問題的最優解或近似最優解。在此20個實例中，HPSO算法搜索出了12個最優解，而NPSOSA算法則搜索出了15個最優解。且在沒有得到最優解的實例中，HPSO算法中有2個結果(25%)十分接近最優值，NPSOSA算法中有2個結果(40%)十分接近最優值，表明NPSOSA算法在尋優上比HPSO算法更具優勢。

NPSOSA算法與其他算法的比較如表3所示。

表3 NPSOSA與SB1[13]、SB2[13]、GASA[14]、HGA[15]的比較

問題BKSNPSOSA

移動瓶頸法遺傳算法

SB1SB2GASAHGA

FT06555555555555

FT109309301 015930930930

FT201 1651 1681 2901 1781 1651 165

LA169459451021978945945

LA211 0461 0461 1721 0841 0581 046

LA261 2181 2181 0341 2241 2181 218

LA311 7841 7841 7841 7841 7841 784

LA361 2681 2681 3511 3051 2921 279

通過表3可看出，NPSOSA對表3中的實例均能獲得或是非常接近最優值，且對這些問題的搜索成功率高于移動瓶頸算法中的SB1和SB2算法，與遺傳算法搜索成功率相近。NPSOSA算法成功避免了早熟現象，并提高了算法搜索準確度。

4 結束語

在本文提出的NPSOSA中，PSO進化為SA鄰域搜索提供了一組具有較好質量和分散度的初始解，采用SA機制對這些解進行鄰域搜索，不僅是對PSO搜索的補充，有利于對優良解的局部改良，同時也賦予算法概率突跳的能力，從而解決了微粒多樣性差、易早熟、陷入局部最優解等缺點。同時該算法通過對不可行解的優化，使得算法能充分利用微粒資源，提高了搜索效率。算法通過引入ROV規則，將連續位置轉換為離散的工件排列[9，10]，從而使得PSO適應于解決JSP問題。實驗結果表明，對大多數的實例，本算法均能獲得最優解，且在搜索的準確性上優于文獻[3]中提出的算法。因此，NPSOSA對JSP問題是一種可行、準確度高的算法。由于本算法在搜索過程中考慮了諸如搜索的準確性、早熟、微粒分散性及優化不可行解以提高搜索效率等諸多問題，而導致算法在搜索中耗費的時間過長，這也是本算法今后研究的一個重點。

參考文獻:

[1]王凌，劉波. 微粒群優化與調度算法[M].北京:清華大學出版社，2008.

[2]SHA D Y， HAU C Y. A hybrid particle swarm optimization for job shop scheduling problem[J]. Computers Industrial Engineering， 2006，51(4): 791-808.

[3]XIA Wei-jun， WU Zhi-ming. A hybrid particle swarm optimization approach for the job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology， 2006，29(3-4): 360-366.

[4]XIA Wei-jun， WU Zhi-ming. An effective hybrid optimization opproach for multi-objective flexible job-shop scheduling problems[J]. Computers Industrial Engineering， 2005，48(2): 409-425.

[5]LIAN Zhi-gang， JIAO Bin， GU Xing-sheng. A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan[J].Applied Mathematics Computation， 2006，183(2):1008-1017.

[6]TU Kun， HAO Zhi-feng， CHEN Ming. PSO with improved strategy and topology for job shop scheduling[C]//Proc of LNCS. Berlin:ALLEMAGNE， 2006: 146-155.

[7]KIRKPATRICK S，GELATT C D，VECCHI M P. Optimization by si-mulated annealing[J]. Science， 1983，220(4598): 671-680.

[8]SONG Xiao-yu， CAO Yang， CHANG Chun-guang. A hybrid algorithm of PSO and SA for solving JSP[C]//Proc of the 5th Internatio-nal Conference on Fuzzy Systems and Knowledge Discovery.Washington DC: IEEE Computer Society，2008:111-115.

[9]LIU Bo， WANG Ling， JIN Yi-hui. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Trans on SMC， 2007，37(1):18-27.

[10]LI Bin-bin，WANG Ling， LIU Bo. An effective PSO-based hybrid algorithm for multiobjective permutation flow shop scheduling[J]. IEEE Trans on SMC， 2008，38(4): 818-831.

[11]CLERC M， KENNEDY J. The particle swarm: explosion， stability， and convergence in a multi-dimensional complex space[J]. IEEE Trans on Evolutionary Computation， 2002，6:58-73.

[12]LOURENCO H R. Local optimization and the job-shop scheduling problem[J]. European Journal of Operational Research，1994，83:347-364.

[13]ADAMS J， BALAS E， ZAWACK D. The shifting bottleneck procedure for job shop scheduling[C]//Proc of Management Science.[S.l.]: INFORMS，1988: 391-401.

[14]WANG Ling， ZHENG Da-zhong. An effective hybrid optimization strategy for job-shop scheduling problems[J]. Computers Ope-rations Research， 2001，28(6):585-596.

[15]GONCALVES J F， MENDES J J M， RESENDE M G C. A hybrid genetic algorithm for the job-shop scheduling problem[J]. European Journal of Operational Research， 2005，167(1):77-95.