基于Petri網與GA—PSO算法的FMS優化調度

董立國

摘要：針對柔性制造系統調度難題，提出了一種基于Petri網與改進遺傳-粒子群算法相結合的優化調度方法。利用Petri網對柔性制造系統進行建模，在分析傳統調度算法的基礎上提出了一種改進遺傳-粒子群混合算法對建立的模型進行調度。通過調度驗證表明，該算法能有效地解決多品種、小批量的柔性制造系統仿真時的調度問題。

關鍵詞：柔性制造系統；調度；Petri網；遺傳算法；粒子群算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）03-0046-02

1 概述

柔性制造系統（Flexible Manufacturing System，FMS）的典型特點是系統中時刻存在著異步推進的不同工藝流。在提高系統生產靈活性的同時，也對系統管理提出了很多新的挑戰[1]。在一定的約束條件下，如何統籌安排系統的制造行為，以獲得最優（或近似最優）的系統運行效率，這就是所謂的FMS優化調度問題[2]。針對上述FMS調度編碼和收斂速率問題，本文設計了一種改進的GA-PSO算法求解FMS調度問題。

2 改進的GA-PSO的調度算法

2.1 染色體編碼

因為PSO與GA的操作對象及進化策略并不相同，需拷貝兩份初始染色體編碼以用于后續的進化計算，更新粒子當前的適應度值。GA中染色體的編碼采用整數的雙層編碼[3]。

2.2 適應度函數

本文設計的適應度函數為，其中為所有工序加工時間之和，為進化過程中每次迭代所得的加工完工時間[4]。

2.3 PSO迭代

按照公式（1）、（2）更新粒子的速度、位置，慣性因子執行公式（3）的線性遞減策略，其中，、分別表示w取值上限及下限，通常取值為：，，t表示當前迭代步數。如果新粒子對應的適應度比局部歷史最優可行解或者全局歷史最優可行解更高，那么執行替換[5]。

2.4 GA選擇算子設計

設種群中的個體的總數為N，種群個體其適應度函數值為f（t），則種群中該個體被選中的概率為公式（4）所示。

2.5 GA交叉算子設計

交叉概率用于控制交叉操作發生的頻率，由于交叉概率過大時，種群中個體的更新過快，會使高適應度的個體很快被破壞掉；而當概率過小時，交叉操作發生的頻率過低，使搜索停滯不前，因此本文采用線性遞減的單點交叉策略。線性遞減的方法如公式（5）所示[6]。

2.6 GA變異算子設計

GA變異算子如公式（6）所示同樣采用線性遞減策略。

3 FMS調度實例

為驗證本文算法的有效性和通用性，下面通過具體實例進行驗證，我們利用Matlab2013仿真軟件實現算法。首先對一個簡單FMS系統例子進行調度并與理論最優解進行驗證。

3.1 FJSP調度實例

利用本文算法進行調度都得到了如圖4所示的調度干特圖，將其與實際加工計劃對照，調度出的結果為實際可行解，這說明了本文算法求解FJSP的可行性。

3.2 JSP調度實例

JSP是FJSP的一種，與FJSP主要區別是：JSP的每道工序的加工路徑（加工機器）是確定，而FJSP的加工路徑是未知的。在作業車間調度中，JSP具有重要的代表性。為測試本文算法的有效性和通用性，下面將該算法應用到FT（也稱為MT）和LA兩類基準問題中[7， 8]，其中FT類選取了FT06、FT10兩個不同規模子問題，LA選取了LA01、LA16兩個不同規模子問題進行測試對比。

可見，本文算法對于求解小規模的JSP（FT06和LA01）在保證最優解的前提下有著極高的效率和穩定性。而對大規模系統（FT10和LA16）測試中，LA16問題得到了最優解，盡管FT10問題在這10次仿真沒有收斂最優解，但也得到了較優解，說明本文算在大規模系統調度也具有較強的尋優能力和可行性。

4 結論

本文提出一種改進的基于遺傳算法與粒子群優化算法相結合的調度算法，算法融合了遺傳算法和粒子群算法各自的優點。最后以實例論證了本文算法的可行性和優點。

參考文獻：

[1] 蘇國軍， 汪晉， 田立國. 基于Petri網模型的柔性制造系統優化調度[J]. 系統工程理論與實踐， 2014， 34（10）：2716-2721.

[2] 曹陽. 基于賦時有色Petri網離散制造過程控制系統建模與仿真研究[D]. 長春工業大學， 2015.

[3] 蔣元凱， 韓兵， JiangYuankai，等. 啟發式搜索在時間Petri網的共享資源調度中的應用[J]. 微型電腦應用， 2000， 16（12）：37-39.

[4] 韋志強. FMS生產調度建模、優化與仿真研究[D]. 西安電子科技大學， 2008.

[5] 郭海東. 遺傳算法及其在生產調度中的應用研究[D]，2004.

[6] 馬麗麗. 基于改進粒子群算法的車間作業調度問題研究[D]. 哈爾濱理工大學， 2010.

[7] Thompson H F G. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules[J]. 1963.

[8] Lawrence S. Resource constraint project scheduling： An experimental investigation of heuristic scheduling techniques [J]. 1984.