混沌微粒群算法在離散型生產調度中的應用

陳宇航，劉階萍，秦智晗

（北京交通大學機械與電子控制工程學院，北京100044）

生產調度問題屬于NP-hard問題，是一種很難解決的理論難題。為了有效地解決生產調度問題，研究人員往往需要對復雜的問題進行理論分析，建立數學模型以求解不同的生產調度問題。但通過這類方法很難找到最優解，效果不理想。近年來，人們運用仿生型智能優化算法求解生產調度問題，如遺傳算法、模擬退火算法、蟻群算法、微粒群算法等。

在生產調度領域，因為微粒群算法的概念簡明、依賴的經驗參數較少、收斂速度快、實現方便，所以短期內得到了一定的發展與應用，尤其是在離散型生產調度優化方法研究方面的應用越來越多[1~2]。但是微粒群算法容易陷入局部最優解、后期收斂速度慢，本文基于此對微粒群算法提出改進，在離散型生產調度優化中采用實際項目算例進行驗證[3~4]，在算法運行后期加快了群體的收斂速度，避免了容易陷入局部最優的缺陷，使目標問題的解更加接近最優解，提高了解的質量。

1 數學模型

離散型調度問題，也被稱為非流水車間調度問題[5]，該問題研究n個任務在m臺機器上作業，已知各工序的作業時間和各工件的加工次序，而假設所有工件的工藝順序不完全相同。離散型調度的問題一般有：火箭、飛機、船舶、武器裝備、機械、玩具生產等行業[6]。對于此類問題，通常假定[7~8]：

（1）一個任務在同一時刻只能在一臺機器上加工；（2）每臺機器在同一時刻只能加工一個任務；（3）任務的加工時間在初始時確定，且在整個加工過程中保持不變；（4）任務的加工準備時間和運輸與順序無關，且包含在加工時中；（5）每臺機器上加工各任務的順序不完全一樣；（6）每個任務在所有機器上的加工順序是不完全一樣。

此類問題一般需要滿足以下2個約束條件：

（1）機器約束：每臺機器在同一時刻只能加工一個任務；（2）工藝約束：每道工序必須在它前置的工序加工完畢后再進入下一道加工。

離散型調度問題流程如圖1。將這一類問題的數學模型歸納如下[7]：

圖1 離散型調度問題流程圖

S.T.

cik－pik+M(1－aihk)≥cih，

i=1,2,…, n；h, k=1,2,…, m

cjk－cik+M(1－xijk)≥pik，

i,j=1,2,…, n；k=1,2,…, m

cik≥0, i=1,2,…, n；k=1,2,…, m

生產調度的目標即為產生一個優化的工件調度序列，使得最大流程時間盡可能的小。

2 基于混沌的微粒群算法

微粒群算法，又稱粒子群優化(Particle Swarm Optimization,PSO)，是一種演化計算技術，來源于對一個簡化社會模型的模擬[9]。該算法在圖像處理、模式識別和多目標優化等領域得到廣泛應用。

微粒群算法后期容易陷入局部最優解且收斂速度慢，本文提出了基于混沌的微粒群算法（Chaotic Particle Swarm Optimization,CPSO）來求解復雜的調度離散問題[10]。利用混沌的遍歷性特點進行優化搜索且能避免陷入局部極小，因此，混沌優化搜索方法已成為一種新穎的優化技術[11~12]，將該技術嵌入到微粒群算法，增強其功能。

混沌微粒群算法的優化過程如下[13]：

（1）將所有微粒（種群規模為N）進行初始化，在一定的范圍內隨機設置微粒的初始位置x和速度v，微粒群的進化代數genn。

（2）設定混沌搜索部分的參數。加速常數c1和c2；慣性權重wmin和wmax；混沌變量序列長度m；粒子飛行速度限制設置，該維的速度被限制為該維最大度vmax，即vid∈[-vmin,vmax] 。

（3）在一定的范圍內隨機產生微粒的初始位置和速度，令迭代次數k=1。

（4）根據下式計算慣性權重。

（5）對每個微粒，將它的適應值和它經歷過的最好位置Pbest作比較，如果較好，則將其作為當前的最好位置Pbest；對每個微粒，將它的適應值和全局所經歷最好位置Gbest作比較，如果較好，則將其作為全局的最優解。

為了使得到的結果不要超出所允許的范圍，設定如果vk＜vmin，則vk=vmin；如果vk＞vmax，則vk=vmax；如果xk＜xmin，則xk=xmin；如果xk＞xmax，則xk=xmax。其中vmax和vmin為vk的取值范圍；而xmax和xmin為xk的取值范圍。

（6）在區間（0,1）內任取值rand（0,1），根據公式（1-6）計算Pk，比較rand（0,1）與Pk的大小，如果rand(0,1)≤Pk，則根據以下步驟進行混沌搜索，否則轉到步驟（7）。

采用混沌搜索的概率計算公式：

其中k為迭代的次數。在算法初始，P值較小，整個程序以微粒群算法為主，以很小的概率調用混沌搜索，可以更好地保證搜索的速度。隨著迭代次數的增加，k值增大，即P值越來越趨近于1，算法以更大的概率采取混沌搜索。這主要是因為在算法搜索的初期，微粒群算法搜索速度快，且具有很好的收斂性，采用微粒群算法就可以獲得較好的搜索效果，但是隨著搜索的進行，到進化后期，微粒群搜索收斂性越來越慢，因而采用混沌搜索來彌補這一弱點。因此，在整個搜索尋優的過程中既充分發揮了微粒子群算法簡單易實現、搜索速度快的優點，又在進化后期有效地改進了微粒群算法，使得最后不會收斂到局部最優值。

下面介紹混沌搜索的具體過程：

c.對xld進行混沌搜索：

e.重復b、c、d步驟，直到一定步數內f*保持不變或達到給定的最大搜索步數，結束尋優計算，此時的即為算法得到的最優變量，f*為得到的最優解。

（7）計算適應度，確定全局最優值。

（8）按照速度和位置更新方程(1-1)更新微粒的速度和位置。

（9）如果還沒有達到結束條件（通常為足夠好的適應值或達到一個預設最大代數），令k=k+1則轉步驟（4）。如果達到條件，則輸出全局最優值，程序結束。

混沌微粒群算法流程如圖2。

3 算例分析

3.1 項目背景

圖2 混沌微粒群算法流程圖

某航空發動機公司的精密件加工任務主要由某機械廠車間承擔。試驗車間布置和工件流動場景如圖3。精密件加工屬于典型的離散制造。

圖3 試驗的車間布置和工件流動場景圖

然而，在加工現場每類設備只有一臺，其他設備留作意外情況發生時（比如機器故障、生產任務增加等）使用，以保障整個生產任務的正常進行并完成。

在該車間，精密件整個加工制造流程主要包括生產任務接收、生產準備、工藝執行、產品檢驗和產品交付5個環節。

3.2 編碼方式

工廠的生產任務是根據生產計劃下發的訂單分解后下達到各個車間。本次的研究基于某個項目的具體事例進行分析。其訂單包括5種類型的工件，根據以往的生產經驗，調研并采集數據，將得到每道工序的平均加工時間以及每道工序對應的時間如表1。

表1 項目某訂單作業時間表

對于n個任務m臺機器流程型生產調度，每個任務都要按照一定順序在m臺機器進行作業，因此，n個任務就有n×m道工序。采用基于工序的染色體編碼方式[7]，用自然數1,2,…, n表示每個任務，相同任務的不同工序均用同一個任務號表示，每個染色體包括n×m個代表工序的基因，從而形成所有任務的工序排列，其中每個任務m次出現在染色體中，每個基因只有上下依賴關系的工序。染色體的任意排列總能產生可行調度。解碼過程是先把染色體轉化為一個有序的工序表，然后根據工序表和生產任務的工藝約束，以最早允許作業時間對各任務逐個進行加工，從而得到調度方案。在編程過程中，設置w=3（程序運行次數），genn=50（最大代數），PS=50（種群規模），e=0.4（PSO算法慣性因子），針對這5種類型的工件，分別采用PSO、CPSO得到不同的生產調度結果。

3.3 CPSO算法結果

基于PSO與CPSO的適應度收斂曲線如圖4。由圖可以看出，在前期，采用CPSO得到的收斂速度與PSO的幾乎相同。但是，在搜索后期采用CPSO收斂速度更快。而且CPSO得到的目標值比PSO得到的結果好，這表明了CPSO彌補了PSO在后期容易陷入局部最優解及收斂速度慢的特點。基于CPSO的精密件加工作業甘特圖如圖5。結果如下：

圖4 基于PSO與CPSO的適應度收斂曲線

minm=48

BestPosition=

機器1：J1→J4→J3→J5→J2；

機器2：J4→J1→J5→J2→J3；

機器3：J1→J3→J5→J4→J2；

機器4：J3→J1→J4→J5→J2；

機器5：J5→J4→J2→J1→J3；

機器6：J3→J1→J5→J2→J4

圖5 基于CPSO的精密件加工作業甘特圖

經過計算得到基于CPSO的精密件加工的機器利用率分別為：M1：56.25%；M2：45.83%；M3：52.08%；M4：39.58%；M5：60.42%：M6：4.17%。用PSO與CPSO得出來的機器利用率對比如圖6，采用CPSO方法得到的機器利用率明顯增高。

4 結束語

對于離散型生產調度組合優化問題，微粒群算法的改進對于目標解的尋找有著較大的幫助。基于混沌微粒群算法搜索速度較快，有助于調度工作效率的提高。在未來的研究中，可以充分利用基于混沌微粒群算法的優勢，將其應用于靜態和動態的生產調度領域，還可以用于流程型生產調度、混合流程型生產調度等領域。

圖6 基于PSO與CPSO的機器利用率對比

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

[2] Lawler,Lenstra,Rinnooy Kan,Sequecing and Scheduling: Algorithms and Conplexity[J] .Operations Research and Management Science,Vol.4.

[3] 高立群，任蘋，李楠. 基于混沌粒子群算法的高速旅客列車優化調度[J] . 東北大學學報，2007（2）.

[4] 吳月秋，紀昌明，王麗萍，李志勝. 基于混沌粒子群算法的水電站水庫優化調度[J] . 人民黃河，2008，30（11）.

[5] 唐宇. 基于微粒群算法的車間調度問題研究[D] . 杭州：浙江工業大學，2007.

[6] 蘇成利，徐志成，王樹青. PSO算法在非線性系統模型參數估計中的應用[J] . 信息與控制，2005，34（1）：123-125.

[7] 顧擎明，宋文忠. 混合遺傳算法在Job-shop調度問題中的應用[J] . 信息與控制，1998，27（5）：369.

[8] ChengR.GenM.A Tutorial Survey of Job Shop Scheduling Problems Using Genetic Algorithms Representation[J] . Computers& Industrial Engineering. 1996, 30(4): 983-989.

[9] 崔志華，曾建潮.微粒群優化算法[M] . 北京：科學出版社，2011.

[10] 曹蘊. 基于混沌搜索與粒子群算法的配電網規劃的研究[D] . 北京：華北電力大學，2008

[11] 石欣. 基于混沌粒子群算法的同步發電機最優調速控制系統[D] . 天津：天津大學，2007.

[12] Lovbjerg,Rasmussen. Hybrid:Partical Swarm Optimizer With Breeding and subpopulation[C] .In:Proc of the third Genetic and Evolution Compution Conference,2001