基于Petri網(wǎng)與GA—PSO算法的FMS優(yōu)化調(diào)度

董立國

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

關(guān)鍵詞：柔性制造系統(tǒng)；調(diào)度；Petri網(wǎng)；遺傳算法；粒子群算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）03-0046-02

1 概述

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

2 改進(jìn)的GA-PSO的調(diào)度算法

2.1 染色體編碼

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

2.2 適應(yīng)度函數(shù)

本文設(shè)計的適應(yīng)度函數(shù)為，其中為所有工序加工時間之和，為進(jìn)化過程中每次迭代所得的加工完工時間[4]。

2.3 PSO迭代

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

2.4 GA選擇算子設(shè)計

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

2.5 GA交叉算子設(shè)計

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

2.6 GA變異算子設(shè)計

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

3 FMS調(diào)度實例

為驗證本文算法的有效性和通用性，下面通過具體實例進(jìn)行驗證，我們利用Matlab2013仿真軟件實現(xiàn)算法。首先對一個簡單FMS系統(tǒng)例子進(jìn)行調(diào)度并與理論最優(yōu)解進(jìn)行驗證。

3.1 FJSP調(diào)度實例

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

3.2 JSP調(diào)度實例

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

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

4 結(jié)論

本文提出一種改進(jìn)的基于遺傳算法與粒子群優(yōu)化算法相結(jié)合的調(diào)度算法，算法融合了遺傳算法和粒子群算法各自的優(yōu)點(diǎn)。最后以實例論證了本文算法的可行性和優(yōu)點(diǎn)。

參考文獻(xiàn)：

[1] 蘇國軍， 汪晉， 田立國. 基于Petri網(wǎng)模型的柔性制造系統(tǒng)優(yōu)化調(diào)度[J]. 系統(tǒng)工程理論與實踐， 2014， 34（10）：2716-2721.

[2] 曹陽. 基于賦時有色Petri網(wǎng)離散制造過程控制系統(tǒng)建模與仿真研究[D]. 長春工業(yè)大學(xué)， 2015.

[3] 蔣元凱， 韓兵， JiangYuankai，等. 啟發(fā)式搜索在時間Petri網(wǎng)的共享資源調(diào)度中的應(yīng)用[J]. 微型電腦應(yīng)用， 2000， 16（12）：37-39.

[4] 韋志強(qiáng). FMS生產(chǎn)調(diào)度建模、優(yōu)化與仿真研究[D]. 西安電子科技大學(xué)， 2008.

[5] 郭海東. 遺傳算法及其在生產(chǎn)調(diào)度中的應(yīng)用研究[D]，2004.

[6] 馬麗麗. 基于改進(jìn)粒子群算法的車間作業(yè)調(diào)度問題研究[D]. 哈爾濱理工大學(xué)， 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.