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

董立國(guó)

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

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

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

1 概述

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

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

2.1 染色體編碼

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

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

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

2.3 PSO迭代

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

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

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

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

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

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

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

3 FMS調(diào)度實(shí)例

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

3.1 FJSP調(diào)度實(shí)例

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

3.2 JSP調(diào)度實(shí)例

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 蔣元?jiǎng)P， 韓兵， JiangYuankai，等. 啟發(fā)式搜索在時(shí)間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)粒子群算法的車(chē)間作業(yè)調(diào)度問(wèn)題研究[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.