離散改進PSO求解模糊柔性作業車間多目標調度

辛 悅,顧 德

(江南大學物聯網工程學院，江蘇 無錫 214122)

0 引言

制造業是當今社會的支柱。隨著“工業4.0”時代的到來以及國家相關政策的實施，智能制造受到了廣泛關注[1]。作為智能制造生產過程的關鍵環節，車間需要在有限的設備生產性能約束下，合理決策工件、工序以及加工設備，使所得的生產調度方案能夠實現一個或者多個目標。因此，調度方案的合理性對智能制造的效率有著巨大的影響。車間調度是智能制造的研究熱點之一。

柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)是車間調度問題的進一步拓展。其在車間調度問題的基礎上考慮了同一工件工序所用設備的彈性選擇。對于FJSP的研究，國內外取得了很多進展：Yuan等[2]提出了一種新的模因算法，并將一種新的局部搜索算法引入到適應的非支配排序遺傳算法(non-dominated sorting genetic alogrithm,NSGA-II)中，以求解FJSP；Tianhua等[3]提出了一種基于雙種群的離散貓群優化算法，以得到車間的最優調度方案；Pezzella等[4]提出了一種集成了不同初始種群生成策略、個體選擇策略和新個體復制策略的遺傳算法，以尋求最優調度方案；Xia等[5]將粒子群算法與模擬退火算法混合，有效求解大規模多目標調度問題；徐華等[6]利用呈指數遞減的慣性權重策略改進蝙蝠算法，求解調度最優解。

雖然以上方法很好地求解了FJSP，但僅考慮了確定的生產參數。在實際情況下，設備的損耗、電費的漲幅等外界因素使得工序加工時間、生產成本等生產參數并不是一個確定值。對于此問題，將FJSP中加工時間、加工成本等不確定參數用三角模糊數來代替，利用三角模糊函數對車間調度優化的問題進行數學建模并設計相關問題的目標函數，所得到的調度結果更具魯棒性。使用離散改進的粒子群優化(particle swarm optimization,PSO)算法對調度方案進行尋優，保留了調度算法的多樣性，避免后期迭代過程陷入局部最優。同時，通過計算機仿真結果對比，反映改進算法的優越之處。

1 問題模型

1.1 問題描述以及約束

FJSP可以敘述為：車間有m臺加工設備、n個工件，各工件有多道工序，每道工序有多臺可選設備，工序的加工順序固定，每臺設備的性能不同。調度的目的是確定各個加工設備安放的工件及其工序，使得整個生產系統的加工時間、加工成本這兩個目標最小化。其具體約束如下。

①每道工序開始處理后不允許暫停。

②一臺設備在某一時刻只可處理一個工件。

③在t=0時，所有工件都可以被可選設備集中的機器加工。

④同一工件按照設定工序加工，不同工件優先級相同。

根據符號定義，本文的目標函數可表示為：

(1)

(2)

式中：minNcost為最小加工總成本；minNperiod為最小完工時間。

為便于分析，對建模涉及的變量進行定義，如表1所示。

表1 變量定義Tab.1 Variable definition

1.2 三角模糊數運算

③比較運算。

2 基本粒子群算法

粒子群算法模擬了鳥類群體的覓食特性[7]，是全世界群體算法研究者的研究熱點。其主要遵循以下兩個尋優規則。

①根據個體自身搜尋經驗進行搜索。

②根據社會最優個體搜尋經驗進行搜索。

其主要的速度和位置更新操作如式(3)與式(4)所示。

(3)

(4)

3 離散改進PSO

3.1 編碼方式

FJSP包括兩個子問題，分別為工序排序問題(operations sequencing，OS)與機器選擇問題(machines selection，MS)。對于一個調度方案的編碼示例如圖1所示。

圖1 編碼示例Fig.1 Example of code

圖1中：OS部分的首個1表示工件1的首道工序O11；MS部分的首個1表示O11的可選加工設備集的第一個設備。使用工序對應可選設備集的順序編號，而不是原始的機器編號，可以保證后續引入交叉、變異操作后產生的解仍是可行解。

假設其加工設備集為{M1，M2}，則該數字表示M1；假設所有工件工序集合為{M1，M2}，則編碼意義如圖2所示。使用OS與MS分離的編碼方式，能有效解決調度任務在計算機中的存儲方式，便于算法運算。

圖2 編碼意義Fig.2 Meaning of code

3.2 重構公式

由于傳統PSO算法是連續算法，在迭代后期存在多樣性喪失的問題，無法處理FJSP之類的復雜組合優化問題。因此，本文根據廣義粒子群思想[8]，設計新算法框架，重構了PSO的公式，使得算法具有解決離散問題的能力。在粒子群的位置與速度更新操作中引入遺傳算法的交叉、變異操作，其改進公式如式(5)與式(6)所示。

(5)

(6)

則由式(6)可知，變異概率不會大于0.25。新設計的算法框架以遺傳算法交叉變異操作的離散操作算子替換原有公式的加乘運算，可有效利用遺傳算法能夠保留多樣性的特點、確保算法迭代后期的多樣性、提升算法的尋優性能。

本文采用加入擁擠測度的快速NSGA-II[9]對粒子個體評價。更新個體歷史最優位置的方式為：若粒子當前位置可以支配個體歷史最優位置，則將其作為個體歷史最優位置。而對于全局歷史最優位置的更新方式為：若在所有粒子個體中，存在一個粒子位置能支配全局歷史最優位置，則更新為該粒子的位置。

粒子更新過程偽代碼如下：

01 初始化N個粒子位置xg，最大迭代次數G，粒子速度vg

02 Forg=1 toG

03 Fori=1 toN

04 Ifr

06 End If

07 Ifr

09 End If

10 Ifr

12 End For

14 End For

3.3 OX交叉操作

本文f2交叉操作采用的是順序交叉方式，如圖3所示。圖3中，淺灰色子代編碼來自父代1，深灰色子代編碼來自父代2。首先，從父代1編碼中選取相臨的一段編碼放入子代，其順序與位置與父代1相同。然后，在父代2中找出剩余缺少的基因，并按照原來的順序填入子代編碼空位處。

圖3 順序交叉方式Fig.3 The way of order crossover

3.4 精英保留策略

為保護粒子的多樣性，使用帶外部記憶庫的精英保留策略，如圖4所示。

圖4 精英保留策略Fig.4 Elite retention strategy

粒子位置更新后形成新種群，并對個體進行評價。每一次對新種群評價排序后，都需要對外部記憶庫進行更新，將非支配等級最高的新精英個體與記憶庫中的精英個體進行比較。若當前個體被記憶庫中的某個體支配，則丟棄該解；若記憶庫中的某個體被新精英個體支配，則將被支配個體剔除并將新個體存入記憶庫。若記憶庫的個體與新精英個體不存在支配與被支配關系，則直接將新的精英個體放入記憶庫中。使用帶外部記憶庫的精英保留策略，使得算法能夠充分利用迭代優化過程中的信息并將其用于指導子代的產生，以提高算法的尋優性與收斂性。

3.5 算法步驟

結合離散化改進和精英保留策略，整體的算法步驟如下。

①初始化個體位置和速度，全局最優及個體最優。

②利用變異操作隨機探索個體位置。

③利用交叉操作獲取個體最優位置信息，以更新個體位置。

④利用交叉操作獲取全局最優位置信息，更新個體位置。

⑤更新粒子群中個體的位置與速度。

⑥對粒子個體進行快速非支配排序，更新全局最優、個體最優及外部記憶庫。

⑦確認是否已達到最大迭代次數；若達到，則停止運算并輸出最優解；若未達到，則返回步驟⑦。

4 試驗仿真及結果分析

為驗證本文算法的有效性，進行試驗測試。測試環境為：Win7 x64 專業版系統，8 GB DDR3內存，I7-4900MQ處理器，編程語言為MATLAB 2016a，試驗數據參考文獻[10]。采用C測度來對比算法之間的性能優越性，測度函數如式(7)所示。

(7)

式中：a、b分別為算法A、B產生的Pareto解；Count為解集的個數。

若C(A,B)>C(B,A)，則算法A優于算法B。為便于比較，采用三角模糊數的準則一來使得模糊數近似于定值，以此構造近似Pareto前沿。

對比算法為文獻[10]的自適應離散多目標花授粉算法(adaptive discrete multi-objective flower pollination algorithm,ADMOFPA)以及文獻[11]的多目標粒子群優化(multi-objective particle swarm optimization,MOPSO)算法。本文算法仿真參數為w=0.4，c1、c2設置為1.5，對比算法按照原文設置參數，每個算法的種群規模為50，迭代次數為200。繪制迭代結束時三種算法的近似Pareto前沿，如圖5所示。

圖5 近似Pareto前沿示意圖Fig.5 Approximate Pareto front

由圖5可以看出，本文算法的近似Pareto前沿在ADMOFPA和MOPSO算法的左下方，因此更逼近最優解。由于粒子群初始值設置欠妥，導致Pareto解集存在少量劣解，但這不影響近似最優解的產生。三種算法的C測度結果如表4所示，可知本文所得Pareto解支配其余算法的比例遠大于被支配的比例。

根據NSGA-II的擁擠測度對各算法所得的Pareto前沿進行排序，排在首位的解即該算法的最優解。

表4 算法對比Tab.4 Comparison of methods

本文算法最優解調度方式如圖6所示。

圖6 最優解調度方式Fig.6 Sispatching mode of optimal solution

圖6中，下三角表示開始加工，上三角表示結束加工，編碼意義為工件標號與工序標號。本文算法、MOPSO、ADMOFPA所得最大完工時間與生產成本的最優解值分別為(115,3 398),(116,3 425),(173,3 172)。由三組最優解可知,本文所得最優解支配MOPSO的解，相比ADMOFPA的最優解，近似成本雖然有略微的劣勢但在完工時間上卻有絕對的優勢。因此，本文算法更優。

5 結論

本文針對多目標模糊柔性作業車間調度問題，提出了一種離散改進PSO算法。該算法使用遺傳算法的交叉、變異算子重構了PSO的位置與速度更新公式，并針對多目標使用帶外部記憶庫的精英保留策略。最后，通過對比多種算法的車間實例仿真結果，驗證了改進算法的合理性。今后，可將算法用于實際的生產中，以提高算法的適用性。