基于雙策略改進混沌粒子群的車間調度優化

高道镠，紀志成，吳定會

（江南大學 物聯網工程學院，江蘇 無錫214122）

0 引 言

近年來，智能優化算法在求解作業車間調度問題 （jobshop scheduling problem，JSP）［1］中被著力研究。遺傳算法、模擬退火、禁忌搜索、神經網絡以及粒子群算法［2］等都在JSP問題中得到應用。PSO 因其快速收斂能力和算法簡易等優點，在求解JSP 問題上應用廣泛，但是標準PSO算法易陷于局部極值，從而無法獲得最優結果，混合算法的研究是粒子群優化的一個重要方向。其中將混沌優化算法和粒子群結合的研究已經不少。文獻 ［3］提出將混沌引入粒子初始化，采用混沌和粒子群的協同優化；文獻 ［4］在粒子群更新時引入小幅混沌擾動，增強其局部尋優能力，擴大尋優范圍；文獻 ［5］引入分段線性混沌映射到粒子群中，替代經典的Logistic映射。這些混沌粒子群算法均是生成一個混沌參數序列，以簡單取代粒子群的某些參數，效果并不理想。

基于文獻 ［6］提出的混沌改進思想，本文在粒子更新運動中引入混沌機制，提出一個混沌因子，使粒子在混沌與穩定中可調節的漸進式靠向最優。受文獻 ［7］啟發，在慣性權重因子的變動中引入經典混沌映射，平衡全局尋優和局部尋優能力，將這種改進混沌粒子群算法應用于JSP問題，驗證其調度性能。

1 Job－shop調度問題

1.1 問題描述

job－shop 問題可以描述為：n 個待加工工件的集合，依次在m 加工機器集合工件Jj，j∈ ｛1，…，n｝在機器Mi，i∈ ｛1，…，m｝上加工對應的工序Oij，其加工時間為tij。調度優化目標是n 個工件在某項指標下的最優調度方案。

為簡化問題描述，須滿足下列假設：

（1）tij時間內，工件Jj只能在機器Mi上生產，并只在同一機器上加工1次。所有機器在整個生產周期內均一直可用。

（2）所有工件的工藝路線均確定。

（3）所有工件享有同一優先級，并且一旦某臺機器進入生產，將不能停止，直到完成該生產，才能開始下一個生產動作。

（4）操作允許等待，即前一工件未加工完，相鄰后一工件允許等待或進入中轉庫存。

1.2 目標函數

建立job－shop調度問題時，調度效果可以由多個性能指標進行衡量，其中最小化最大完工時間 （makespan）被普遍采用，其數學描述為

TMi即為機器Mi的加工完成時間，Cmax即為最大完工時間。

cij，tij≥0分別表示工件Jj在機器Mi上的完工時間和加工時間，式 （2）和式 （3）分別表示待加工工件的工藝路線約束和工件各工序所需設備的約束。L 表示一個足夠大的正數；aihj表示工件Jj在機器Mi與機器Mh之間的加工順序，若機器Mh先加工，則aihj＝1，否則aihj＝0；bijk表示機器Mi上工件Jj與工件Jk的加工順序，若工件Jj先加工，則bijk＝1否則bijk＝0。

2 基于雙策略改進的HCPSO 算法

2.1 PSO 算法

PSO 是由Kennedy等提出的一種群體智能優化算法，近年來被廣泛應用于各類組合優化問題中［8，9］。算法是對鳥群覓食過程中的移動和聚集的模擬，或者說是對群落和個體以及環境之間的交互的模擬。

PSO 中每一個粒子的位置代表優化問題的一個解，速度則代表其運動的方向和速率，粒子位置的好壞由目標函數的適應度值來衡量。

假設，維度為D 的搜索空間里，PSO 隨機獲取由Num個粒子組成的群體，其中Xi＝ （xi1，xi2，…，xiD）的意義為編號為i的粒子的位置，Vi＝ （vi1，vi2，…，viD）意義為該粒子的速度。粒子朝著本身和群體兩個最好的位置運動，pbesti＝ （pbesti1，pbesti2，…，pbestiD）為編號為i的粒子本身的最好值，稱為個體最優；gbest＝ （gbest1，gbest2，…，gbestD）則是整個粒子群體尋到的最好值，為全局最優。其迭代公式及相關參數意義請參見文獻 ［9］。

2.2 HCPSO 算法

混沌優化算法的基礎思想是，提出一個混沌變量，將其從混沌空間映射到解空間，以實現搜索方法在全局漸進性收斂。PSO 算法具有收斂速度快的特點，混沌機制則具有全局遍歷性，混沌粒子群算法有助于在提高搜索精度和獲取全局最優值，克服PSO 算法易陷入局部極值的缺點。

文章提出的HCPSO 算法，將混沌機制引入到粒子更新運動過程中，又將混沌引入慣性權重的變化過程，前者可以使算法在混沌和穩定中交替運動，漸進性靠向全局最優值；后者能夠平衡算法在整體和局部上的搜索。

2.2.1 在粒子更新運動中引入混沌

混沌算法采用文獻 ［6］中給出的混沌系統，迭代方式如下

在基于粒子群算法的優化問題中，提高其跳出局部極值的能力的改進尤為重要，上文所述，混沌機制在這一點上具備優越性。在大多數研究中，兩者的結合，多在于不同的混沌映射方式產生的混沌變量和局值點的簡單交換。改進算法將混沌機制引入到粒子的更新運動過程中，并提出一個混沌因子，對算法混沌程度進行調節。算法模型為

式 （5）和標準粒子群算法標準更新公式一致；式 （6）為混沌因子的序列生成方式；式 （7）表示混沌因子rid對混沌變量cid的混沌程度進行調節；式 （8）為將混沌引入后的位置更新公式，其中Ψd為搜索測度，Ki表示為搜索空間向負方向移動的比例。以上公式中，t均為迭代數，d 為維度下標。

式 （6）中提出的混沌因子rid對混沌變量cid的調節，可以控制算法的混沌程度，影響位置的更新方式：

當cid→1時，式 （8）即為

可以從式 （9）看出，位置更新主要遵從混沌發揮的作用。

當cid→0時，式 （8）變體為

式 （10）和標準粒子群算法中的速度更新公式一致，可見，此時算法遵從粒子群的更新方式。

可以看出，引入混沌變量的位置更新公式，可以有效調節HCPSO 算法的混沌程度。在混沌變量初始值cid＝0.999，隨著迭代進行，cid趨向于0，混沌程度減弱。這種趨勢有助于在引入混沌，使算法跳出局部極值后，漸進的重新側重粒子群的更新方式，加速收斂。

上述混沌粒子群位置更新方式，在算法開始，要求快速尋優時不是最好的方式，此時應當充分發揮PSO 算法的快速收斂優點，只有在算法被判定陷入局部極值時，改進算法才應當被引入以跳出局部極值。

為判定算法是否陷入局部極值，文章引入兩個參數mov和sta，前者表示粒子較上一次位置的移動距離，后者表示粒子較其個體歷史最優位置的距離。即

N 為總的迭代次數，當t＜0.95 N 時，算法處于全局尋優階段，采取下述策略，著力于跳出局部極值：

mov＜10－6且sta＜10－6：即算法陷入局部極值，此時，令cid＝0.999，引入上述式 （8）的更新方式；

sta≥10－6：即算法處于不穩定狀態，此時，令xid（t）＝pbestid（t），采用PSO 更新的公式，加速收斂。

t≥0.95 N 時，算法進入尾聲，不再著力于跳出局部極值，轉而采用PSO 更新方式，加速運行到迭代結束。2.2.2 在慣性權重因子中引入混沌

應用上述改進方法后，算法在全局漸進式收斂，加強了克服局部最優的能力。進一步，為平衡全局和局部尋優能力，引入混沌機制到慣性權重因子w 中，在初始化時，即生成一個混沌參數序列。此處使用經典的混沌動力學模型Logistic映射，其表達式為

其中，yi是 （0，1）之間的隨機數。

慣性權重因子的混沌序列生成公式為

并映射到 （wmin，wmax）區間，即慣性權重因子的上下限內

2.2.3 算法步驟

算法的求解步驟如下：

步驟1 初始化參數：粒子個數Num、總迭代數N、終止條件、適應度函數，以及慣性權重的范圍：（wmin，wmax）；學習因子c1、c2；搜索測度Ψd，搜索移動比例Ki；rid序列等。

步驟2 隨機生成初始種群，根據式 （14）、式 （15）生成w 的混沌時間序列。為每個粒子賦值個體最優解pbestid，取最好的個體最優，賦值全局最優解gbestd。

步驟3 迭代開始，根據當前迭代數t、參數mov和sta衡量算法所處階段、穩定與否，以選擇根據標準粒子群更新公式或者式 （5）至式 （8），進行粒子位置更新，并將個體最優和最好的個體最優分別賦值給個體最優解和全局最優解。

步驟4 若算法達到最大迭代次數或者適應值在一定迭代次數內不再變化，則算法終止，否則重復步驟3。

算法步驟如圖1所示。

圖1 算法步驟

3 JSP調度優化仿真研究

3.1 粒子編碼

粒子編碼，是求解JSP 的第一個問題。文章采用基于操作的編碼方式，確定了加工工件數和每個工件的工藝路線后，隨機給出一個編碼序列，序列中每個工件出現的次數等同于其工藝路線中確定的工序數。以一個3×3的調度問題為例，即有3個工件，每個工件有3 道工序。設該問題的隨機粒子編碼為 （3 1 1 2 2 3 1 2 3），則編碼中出現的數字代表相應工件，同一個工件在整個序列中出現的前后順序，代表其工序順序

不同工件的每道工序的生產機臺和生產時間，均由工藝數據表事先確定。如表1所示，上述3×3問題的機器序列為（1 3 2 2 1 3 1 3 2），加工時間序列為（3 3 2 3 2 2 1 1 1）。

3.2 仿真環境及仿真參數設置

仿真在Matlab2013a下進行，運行于intel core i5處理環境。仿真設計了常規混沌粒子群算法 （CPSO）［9］、標準粒子群算法 （PSO）、改進慣性權重的粒子群算法 （WPSO），以及本文提出的HCPSO 算法的對比仿真實驗。

表1 3×3問題的工藝數據

仿真參數設置：初始粒子Num＝20、迭代總次數N＝500、 （wmin，wmax）＝ （0.4，0.9）、c1＝c2＝1.4962，Ψd＝10.45，Ki＝0.5，cid（0）＝0.999。

使用文獻 ［2］中提及的JSP benchmark 問題FT06、FT10、LA21、LA26基準測試，對算法進行檢驗。其中，FT06問題的機器矩陣和時間矩陣如下：

由前文編碼規則可知：以第一行為例，工件1 的機器加工序列為 （3 1 2 4 6 5），一一對應加工時間序列為 （1 3 6 7 3 6），……，依次。已知該問題最優解為55min。

3.3 仿真結果

使用HCPSO 求解FT06問題可以得到在最大完工時間最小化目標下的最佳調度方案，其粒子排序為 （3，3，1，2，1，4，6，2，6，3，4，2，1，5，1，4，3，6，2，1，5，4，6，5，2，3，3，4，5，6，5，2，4，5，6，1）。調度結果如圖2所示。

圖2 FT06最優解時的調度甘特圖

仿真對上述WPSO、CPSO、PSO以及本文提出的HCPSO算法進行仿真對比。圖3為運行50次FT06問題仿真，可以看出，HCPSO 算法較其它3種算法，尋優能力更強，50次運行的平均值也更接近FT06問題理論最優值。

圖3 算法收斂性對比

表2 算法在其它問題上的仿真對比數值

4 結束語

從上述仿真可以看出，提出的雙策略改進HCPSO 算法，性能較一般調度算法，有較大提升，為解決調度問題提供了一種新的方法。

HCPSO 算法將混沌機制引入到粒子位置更新運動和慣性權重變化中，以混沌因子調節混沌程度，以距歷史優值距離判斷使用混沌更新還是標準更新，兼顧收斂速度和跳出局優的能力，并使用其對JSP進行調度研究，取得較好調度效果。下一步，將從更廣泛的調度問題上去研究算法適用性。

［1］MAO Fan，FU Li，CAI Bin.Particle swarm genetic annealing algorithm for job－shop scheduling ［J］.Computer Engineering and Applications，2011，47 （5）：227－231 （in Chinese）. ［毛帆，傅鸝，蔡斌.求解作業車間調度問題的微粒群遺傳退火算法 ［J］.計算機工程與應用，2011，47 （5）：227－231.］

［2］WANG Ling，LIU Bo.Particle swarm optimization and scheduling algorithms ［M］.Beijing：Qsinghua University Press，2008 （in Chinese）. ［王凌，劉波.微粒群優化與調度算法［M］.北京：清華大學出版社，2008.］

［3］LI Peng，CHE A’da.Chaos particle swarm optimization approach to robotic cells scheduling ［J］.Industrial Engineering Journal，2013 （6）：90－95 （in Chinese）.［李鵬，車阿大.自動化生產單元調度的混沌粒子群算法 ［J］.工業工程，2013（6）：90－95.］

［4］CHEN Junlan，YE Chunming.Chaos particle swarm optimization on flexible－resource constrained multi－project scheduling research ［J］.Application Research of Computers，2014，30（1）：66－69 （in Chinese）.［陳君蘭，葉春明.柔性資源受限多項目調度的混沌粒子群算法研究 ［J］.計算機應用研究，2014，30 （1）：66－69.］

［5］XIANG T，LIAO XF， WONG K.An improved particle swarm optimization algorithm combined with piecewise linear chaotic map ［J］.Applied Mathematics and Computation，2007，190 （2）：1637－1645.

［6］XU Xiaobo，ZHENG Kangfeng，LI Dan，et al.New chaosparticle swarm optimization algorithm ［J］.Journal on Communications，2012，31 （1）：24－30 （in Chinese）. ［胥小波，鄭康鋒，李丹，等.新的混沌粒子群優化算法 ［J］.通信學報，2012，31 （1）：24－30.］

［7］KUANG Fangjun，XU Weihong，ZHANG Siyang.Parameter optimization and application of SVM with mixtures kernels based on improved chaotic particle swarm optimization ［J］.Application Research of Computers，2014，31 （3）：671－674（in Chinese）.［匡芳君，徐蔚鴻，張思揚.基于改進混沌粒子群的混合核SVM 參數優化及應用 ［J］.計算機應用研究，2014，31 （3）：671－674.］

［8］WANG Fei.Study on vehicle scheduling problem with time windows based on improved particle swarm optimization ［J］.Computer Engineering and Applications，2014，50 （6）：226－229 （in Chinese）.［王飛.帶時間窗車輛調度問題的改進粒子群算法 ［J］.計算機工程與應用，2014，50 （6）：226－229.］

［9］ZHOU Rong，YE Chunming，XIE Yang，et al.Research of multi－objective and multi－mode project scheduling problem based on chaos particle swam optimization ［J］.Computer Science，2013，40 （4）：259－262 （in Chinese）.［周蓉，葉春明，謝陽，等.基于混沌粒子群算法的多目標多執行模式項目調度問題研究 ［J］.計算機科學，2013，40 （4）：259－262.］

［10］ZHANG Fei，GENG Hongqin.Optimization of job－shop scheduling problem based on chaos particle swarm optimization algorithm ［J］.Journal of Shandong University （Engineering Science），2013，43 （3）：19－22 （in Chinese）.［張飛，耿紅琴.基于混沌粒子群算法的車間作業調度優化 ［J］.山東大學學報 （工學版），2013，43 （3）：19－22.］