張海月，秦永彬，許道云

貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院，貴陽550025

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0433-12

?

求解FFS問題的混合搜索機制粒子群算法*

張海月，秦永彬，許道云+

貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院，貴陽550025

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0433-12

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61262006, 61540050 (國家自然科學(xué)基金); the Major Applied Basic Research Program of Guizhou Province under Grant No. JZ20142001 (貴州省重大應(yīng)用基礎(chǔ)研究項目); the Science and Technology Foundation of Guizhou Province under Grant No. LH20147636 (貴州省科技廳聯(lián)合基金); the Scientific Research Project of Introduce Talents of Guizhou University under Grant No. 201114 (貴州大學(xué)引進(jìn)人才科研項目); the Graduate Student Innovation Fund of Guizhou University under Grant No. 2015013 (貴州大學(xué)研究生創(chuàng)新基金).

Received 2015-10,Accepted 2015-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-12-02, http://www.cnki.net/kcms/detail/11.5602.TP.20151202.1452.004.html

Key words: flexible flow shop; scheduling algorithm; particle swarm; simulated annealing algorithm

摘要：針對柔性流水車間調(diào)度（flexible flow shop scheduling，F(xiàn)FS）問題，提出了一種混合搜索機制粒子群算法（multi-search mechanism particle swarm optimization algorithm，MMPSO），以期獲得柔性流水車間調(diào)度問題的優(yōu)化解。在分析柔性流水車間調(diào)度問題特點的基礎(chǔ)上，設(shè)計了針對該問題的粒子信息編碼方案，提出了瓶頸機器消除算法以提升初始種群的質(zhì)量；同時在個體極值搜索中采用NEH-Greedy搜索算法，在全體極值搜索中采用SADA（simulated snnealing disturb algorithm）搜索算法以擴大搜索范圍，提高可行解質(zhì)量，加快收斂速度，在算法迭代搜索過程中對全體極值進(jìn)行RPA（random perturbation algorithm）操作以避免算法陷入局部最優(yōu)。實驗結(jié)果表明，MMPSO算法能夠以較快的收斂速度獲得柔性流水車間調(diào)度問題的一個較好的優(yōu)化解。

關(guān)鍵詞：柔性流水車間；調(diào)度算法；粒子群；模擬退火算法

1　引言

流水車間調(diào)度問題是由生產(chǎn)制造業(yè)引出的規(guī)劃問題，是確保快速、有效和平穩(wěn)生產(chǎn)的關(guān)鍵。柔性流水車間調(diào)度問題（flexible flow shop scheduling problem）[1-2]是傳統(tǒng)流水車間調(diào)度問題的延伸與推廣，其與傳統(tǒng)流水車間調(diào)度問題的最大區(qū)別是允許工件在一個或多個加工工序中存在并行機，在存在并行機的工序中，工件可任意選擇一臺并行機加工且加工時間不同，其是一種更加一般化的組合優(yōu)化問題。在實際生產(chǎn)過程中，多數(shù)生產(chǎn)場景都具有柔性流水車間的特點，如化工制造、鋼鐵鑄造、紡織制造等。

柔性流水車間調(diào)度問題已被證明是NP-難的[3-4]。針對流水車間調(diào)度問題，許多研究者進(jìn)行了深入的研究，提出了求解此類問題的數(shù)學(xué)規(guī)劃方法、啟發(fā)式算法[5]和智能優(yōu)化算法[6]。其中，數(shù)學(xué)規(guī)劃方法中主要有分支定界法[7]、拉格朗日松弛法[8]、整數(shù)規(guī)劃[9]等，這類方法雖然能給出問題的最優(yōu)解，但只適用于求解小規(guī)模的問題，對于大規(guī)模問題的求解會導(dǎo)致指數(shù)級的時間開銷，無法在實際生產(chǎn)過程中使用。啟發(fā)式算法通過學(xué)習(xí)策略尋求最優(yōu)解，算法運行速度快，能在短時間內(nèi)得到可行解，在研究與實際生產(chǎn)中得到廣泛應(yīng)用，但可行解質(zhì)量與最優(yōu)解的偏離程度是不可預(yù)知的，甚至?xí)a(chǎn)生較大的偏差。而近年來興起的智能優(yōu)化算法[10]在評價機制基礎(chǔ)上通過不斷迭代搜索來獲得最優(yōu)解，此類算法雖不能保證得到最優(yōu)解，但能在可接受的時間范圍內(nèi)得到較好的次優(yōu)解。常用的智能優(yōu)化算法包括粒子群算法[11-12]、遺傳算法[13]、禁忌搜索算法[14]和模擬退火算法[15]等。近年來眾多學(xué)者對智能優(yōu)化算法進(jìn)行了廣泛研究，在系統(tǒng)控制、人工智能、模式識別、生產(chǎn)調(diào)度等領(lǐng)域該算法得到迅速推廣和應(yīng)用。在流水作業(yè)調(diào)度問題研究中，Zandieh等人利用免疫算法[16]增強種群多樣性，優(yōu)化了帶依賴序列裝載時間約束的混合流水車間調(diào)度問題解的質(zhì)量，并給出了該問題的下界；Mastrolilli等人提出了一種能擴大搜索鄰域范圍的禁忌搜索算法[17]，得到了柔性流水車間調(diào)度問題的更好的近似可行解；沈斌等人[18]提出了一種新型的自適應(yīng)遺傳算法，采用初始種群復(fù)合化，適應(yīng)度相同個體的篩選策略以及改進(jìn)自適應(yīng)交叉變異概率等方法優(yōu)化了柔性流水車間調(diào)度問題的求解。但大部分學(xué)者在柔性流水車間調(diào)度問題的研究中，對智能優(yōu)化算法的改進(jìn)都集中在擴大搜索范圍上，并未對同一臺并行機加工工件排序進(jìn)行優(yōu)化，在同一臺機器上工件之間合適的加工順序可使下一階段加工任務(wù)的開始時間得以提前，進(jìn)而提高工作效率，減小工件最大完成時間，優(yōu)化可行解質(zhì)量。

本文結(jié)合柔性流水車間調(diào)度問題的特點，提出了混合搜索機制粒子群算法（multi-search mechanism particle swarm optimization algorithm，MMPSO），用以求解多階段柔性流水車間調(diào)度問題。基于粒子群算法容易理解，實現(xiàn)方便且搜索能力強的特點，MMPSO算法結(jié)合粒子群算法的思想，首先設(shè)計相應(yīng)的粒子信息編碼方案，根據(jù)平均分配機器原則產(chǎn)生較優(yōu)的初始粒子種群，同時在粒子群全局搜索中增加兩種搜索方法增強粒子搜索能力，優(yōu)化同一臺并行機上工件加工順序，以凹函數(shù)慣性權(quán)重為參數(shù)更新方法加快粒子群收斂速度，算法在執(zhí)行過程中將對全體極值進(jìn)行隨機擾動避免陷入局部最優(yōu)，以幫助粒子跳出局部最優(yōu)。

2　問題描述

柔性流水車間調(diào)度問題可描述為：n個工件{J1,J2,?,Jn}需要在m道工序上加工，所有工件的加工路線相同，在第i道工序中包含Si臺并行機（Si>0?，i∈{1,2,?,m}），所有工件的第i道工序均可在Si中的任意一臺并行機i上加工，所有工件在并行機上加工的時間可以不同。Cij表示工件Ji的工序j的完成時間，Ci表示工件Ji的加工完成時間。該問題假設(shè)如下：

（1）所有工件加工路徑相同，加工順序固定；

（2）各個工件沒有優(yōu)先級限制，即工件間加工順序不受限；

（3）所有機器均可在時間0開始加工；

（4）每個工件的每道工序僅可在一臺機器上加工；

（5）每臺機器同一時間只能加工一個工件；

（6）工件一旦開始加工不能中斷；

（7）機器無故障等特殊情況。

問題的優(yōu)化目標(biāo)是最小化最大完成時間（Makespan），即：

3　混合搜索機制粒子群算法

為了將粒子群算法運用于柔性流水車間調(diào)度問題的求解，首先需要解決的是解的編碼問題。柔性流水車間調(diào)度問題中各個工件需要在所有加工工序上選擇加工機器，常用的編碼方式變得不再適用，因此本文提出了一種矩陣編碼方式用于存儲可行調(diào)度解信息，將粒子信息以行向量的方式存儲在矩陣中。標(biāo)準(zhǔn)的粒子群算法的初始化種群隨機生成，本文在解空間內(nèi)初始化粒子信息，并對某些粒子的初始位置信息進(jìn)行優(yōu)化操作以提高初始種群的質(zhì)量。粒子在每次迭代搜索中根據(jù)自己和群體飛行經(jīng)驗不斷更新位置信息和速度信息，向最優(yōu)位置靠近。本文在保證可行解合法性的前提下，以叉乘方式更新粒子的位置和速度信息。此外，為擴大粒子群搜索范圍，提高算法質(zhì)量，本文提出了NEH-Greedy搜索算法，以一定概率對個體極值進(jìn)行優(yōu)化操作以擴大全體極值的搜索范圍。為避免粒子群算法陷入局部最優(yōu)，對長期處于停滯狀態(tài)的全體極值增加隨機擾動操作，使其跳出停滯狀態(tài)。下面，將詳細(xì)介紹MMPSO算法的各個具體步驟。

3.1 MMPSO算法編碼方式

柔性流水車間調(diào)度問題中每個工件需要指定在每一道加工工序上加工的機器及各并行機上的加工順序，因此該問題的一個可行解具有兩個屬性：機器選擇和加工順序。單一的順序存儲不能滿足柔性流水車間調(diào)度問題可行解的表示，本文采用矩陣編碼方式。假設(shè)有n個工件{J1,J2,?,Jn}待加工，每個工件需要經(jīng)過m道加工工序{S1,S2,?,Sm}，第i道工序有Si臺并行機。那么該問題的一個可行調(diào)度方案如下：

其中，X為機器選擇矩陣，XT為加工順序矩陣。矩陣中，xij?(1≤i≤m,1≤j≤n)表示工件Jj在第i道工序上的加工機器編號。若xij=xik?, j≠k,表示工件Jj在第i道工序所選擇加工機器相同。xtij表示工件Jj在第i道工序加工機器上的順序編號。

工件在每臺機器上的加工時間同樣采取矩陣存儲，每道工序i存在Si臺并行機，為方便計算，將機器按照工序依次編號為1,2,?,λ。對任意工序k?(?1≤k≤m)，其并行機Mπ的編號π的取值范圍可控制為：

例1某柔性流水車間調(diào)度問題中包含5個待加工工件，每個工件有4道加工工序，每道工序的并行機數(shù)量分別為2、1、2、3，那么各階段機器編號分別為{1,2}、{3}、{4,5}、{6,7,8}。一個可行的調(diào)度方案如下：

其中，x31=x33=4表示工件J1和工件J3的第三道工序均在機器M4上加工；而由矩陣XT可知，xt31=2，xt33=1，這表明在機器M4上工件J3第一個加工，工件J1第二個加工。

MMPSO算法中每個粒子表示柔性流水車間調(diào)度方案的一個可行解，柔性流水車間調(diào)度問題的一個可行解具有兩個屬性，機器選擇和加工順序，因此每個粒子信息也包含以上兩個屬性。而標(biāo)準(zhǔn)粒子群算法中粒子信息為行向量，以矩陣方式存貯粒子群信息，因此需要將矩陣X和XT分別轉(zhuǎn)換為m×n維行向量O和OT以表示粒子信息：

O=[o1,o2,?,om×n], OT=[ot1,ot2,?,otm×n]

原調(diào)度信息矩陣X（機器選擇）中xij轉(zhuǎn)換為粒子信息or，其中r=(j-1)×m+i。同理，原調(diào)度信息矩陣XT（加工順序）中xtkl轉(zhuǎn)換為粒子信息otq，其中q=(l-1)×m+k。

對于第一道加工工序，即?k=1?，機器編號控制為[1，第一道工序S1并行機數(shù)量]。對于非第一道工序，即k≠1，機器編號控制為[前k-1道工序并行機數(shù)量之和加1，前k道工序并行機數(shù)量之和]。

根據(jù)以上編碼方式，本文求解Makespan只需對m道加工工序中所有待加工的n個工件計算加工開始時間和結(jié)束時間，那么計算Makespan的時間復(fù)雜度為O(mn)。

3.2種群初始化

種群初始化是MMPSO算法的起點，一個可行解包含機器選擇和加工順序這兩個屬性，因此需要同時初始化粒子的以上兩種信息。機器選擇信息需要在由式（2）表示的每道工序可選機器編號范圍內(nèi)隨機產(chǎn)生初始粒子信息，以保證隨機產(chǎn)生的調(diào)度方案的可行性。例如：對于一個調(diào)度方案的機器選擇信息O中or代表工件Jj在第i道工序的加工機器（i=(r-1)mod?m+1，j=?(r-1)/m ? +1），則初始化為：

粒子加工順序OT初始化為值全為1的向量。根據(jù)粒子的機器選擇信息修改加工順序OT。具體方法為：首先將粒子的機器選擇信息O轉(zhuǎn)化為調(diào)度矩陣X=[xij]m×n，然后按以下方法確定OT的值。

（1）xij=xik?，j≠k，i若為第一道加工工序，即i=1，則工件排序按照其加工時間的升序排列；

（2）若不為第一道加工工序，即i≠1，則按照每個工件前一道工序的完成時間升序排列來確定加工順序。

由于隨機產(chǎn)生的調(diào)度方案具有較大的不確定性，在某個粒子的調(diào)度排序中可能出現(xiàn)瓶頸機器（即在同一工序上較多工件都選擇在同一臺機器加工且加工總時間較長，此類機器為瓶頸機器），而其他并行機空閑的狀況，此類情況會影響尋優(yōu)的速度和解的質(zhì)量。為提高尋優(yōu)速度，解決產(chǎn)生瓶頸機器的問題，同時為保證粒子種群的多樣性，在粒子群中以概率popt對粒子的初始位置信息進(jìn)行優(yōu)化操作。本文采用以下瓶頸機器消除算法（bottleneck machine elimination algorithm，BMEA）優(yōu)化粒子初始位置信息。

算法1 BMEA算法

Input：一個柔性流水車間可行解Sch Output：無瓶頸機器可行解Sch

2. CountSame( ) i←計算每臺機器上加工工件數(shù)

3. N←可行調(diào)度Sch各機器加工工件數(shù)

4. w=1←標(biāo)記

5. for k=1,2,?,m

6. while w=1

15. else

16. w=0

17. end

18. end

19. end

20. return Sch

BMEA算法中，需要遍歷每一道工序，其復(fù)雜度為O(m)；對于工序i，最壞情況為所有工件都在同一臺機器上加工，最多需要對n-2個工件的加工機器信息進(jìn)行修改，時間復(fù)雜度為O(n)。因此算法BMEA的時間復(fù)雜度為O(mn)。

3.3粒子位置及速度信息更新

由于柔性流水車間調(diào)度問題的特殊性，粒子位置和速度信息需要合法性檢測，基本粒子群更新方法不再適用，需要對粒子的位置和速度更新公式進(jìn)行改進(jìn)，修改后的粒子速度更新公式為：

其中，vti+1和vti分別表示粒子i在t+1和t時刻的速度信息；ω為慣性權(quán)重；pi是粒子i當(dāng)前個體極值；g為當(dāng)前粒子群全體極值；c1,c2∈{ } 0,1；?為叉乘操作，若差乘操作對象為零矩陣則取消該項。ω采用遞減凹函數(shù)策略更新。算法初期，粒子需要較大的自我認(rèn)知，而后期則需要較大的社會認(rèn)知，才不會使算法陷入局部最優(yōu)，加快收斂速度。因此，算法以概率ω選取c1=1，c2=0，否則選取c1=0，c2=1。以ω為比重計算交換列數(shù)r(1≤r≤n)，隨機產(chǎn)生r個交換列，列交換后產(chǎn)生兩個新的調(diào)度方案，更新較優(yōu)調(diào)度為粒子新時刻速度信息。

相應(yīng)修改后的粒子位置信息更新公式為：

例2圖1中，規(guī)模為3×5的個體a1和a2信息，計算a1?a2。算法產(chǎn)生隨機交叉點r=2，即分別交換第1~2列和第3~5列的位置信息，交叉操作后所得新個體信息為b1和b2。其中b1為a1的1~2列信息與a2的3~5列信息的連接；b2為a1的3~5列信息與a2的1~2列信息的連接。分別計算b1和b2的最大完成時間，取最大完成時間最小排序為a1?a2的運算結(jié)果。

Fig.1　 An example of article information updates圖1　粒子信息更新舉例

3.4 NEH-Greedy搜索算法

基本NEH算法是求解置換流水車間調(diào)度問題的效率較高的啟發(fā)式算法，其賦予加工時間越長的加工優(yōu)先權(quán)，由此優(yōu)先權(quán)取得初始排列，通過插入方法構(gòu)造一個調(diào)度。貪心算法是近似算法中常用的簡單方法，該算法對問題求解時，總是做出當(dāng)前最優(yōu)解選擇，可稱局部最優(yōu)解選擇。

在柔性流水車間調(diào)度問題中，每個工件在每道加工工序的并行機上加工時間不同，很難對工件進(jìn)行總時間排序和分別插入操作，因此將在同一機器上工件加工順序視為傳統(tǒng)流水車間調(diào)度問題中的某一加工階段，采用NEH算法得到較好的局部排序。同時結(jié)合貪心算法獲取當(dāng)前最優(yōu)的特點，本文提出NEH-Greedy搜索算法，優(yōu)化粒子個體極值。算法中，對于一個可行解，首先計算需要加工多個工件的機器集合ψ，取集合ψ中的第一臺機器φ1，按待加工工件加工時間升序排列，將排序后的工件前后平均分成兩組α1和α2，構(gòu)成兩種子排序{α1,α2}和{α2,α1}，產(chǎn)生兩個新可行解；評價新可行解與原可行解，保存較優(yōu)排序為當(dāng)前最優(yōu)解；若ψ≠?，對于ψ中下一臺機器重復(fù)以上操作，否則算法結(jié)束，輸出優(yōu)化解。具體算法描述如下。

算法2 NEH-Greedy搜索算法

Input：一個柔性流水車間可行解Sch

Output：一個柔性流水車間可行解Sch

1. for k=1,2,?,m

2.ψ←加工工件數(shù)量大于1的機器集合

3. while ψ≠?

4.φ1←ψ上第一臺機器

6.α1←′上前round(num(′)/2)項

7.α2=′-{α1}

8. Sch1←修改Sch并行機φ1上工件加工順序為{α1,α2}

9. Sch2←修改Sch并行機φ1上工件加工順序為{α2,α1}

10. Sch=min{}

Makespan(Sch1,Sch2,Sch)

11.ψ=ψ-{φ1}

12. end

13. end

14. return Sch

以概率ppb對粒子群所有粒子執(zhí)行NEH-Greedy搜索算法，增加粒子搜索空間，提高可行解質(zhì)量。NEH-Greedy算法中對工件加工的所有m道工序循環(huán)操作，循環(huán)中對于工序i，判斷所有并行機狀態(tài)，產(chǎn)生新可行解，比較新可行解與原可行解，計算Makespan的復(fù)雜度為O(mn)，因此該算法的時間復(fù)雜度為O(nm2)。

在柔性流水車間調(diào)度問題中，同一臺機器上工件順序?qū)⒂绊懴乱浑A段工件的開始時間，從而影響問題的最大完成時間，而在目前對柔性流水車間調(diào)度問題的研究中幾乎沒有對同一臺機器上工件順序進(jìn)行調(diào)優(yōu)的算法，因此本文引入NEH-Greedy算法從新的優(yōu)化角度擴大搜索范圍。

3.5 SADA搜索算法

粒子群算法中的全體極值為當(dāng)前粒子群最優(yōu)解，為進(jìn)一步擴大搜索范圍，提高可行解質(zhì)量，本文采用模擬退火擾動算法（simulated annealing disturb algorithm，SADA）?；舅枷胧窃诿枯喌校S機選擇3種擾動方案之一產(chǎn)生新解ω′，計算新解ω′與原始解ω的目標(biāo)值差值ΔE=Cω-Cω′，以概率min{1,exp(-ΔE/T)}更新新解，更新退火溫度T=。TotalIte為MMPSO算法總迭代次數(shù)，ite為當(dāng)前迭代次數(shù)。SADA搜索算法如下。

算法3 SADA搜索算法

Input：全體極值g，模擬退火溫度T

Output：全體極值g

1. i=randi(3)

2. switch (i)

3. Case 1: (選擇單點交換擾動)

4. k=randi(m)←隨機選擇一道加工工序

5. J1=rand(Ji|i=1,2,?,n)

6. J2=rand(Ji|i=1,2,?,n)?←J1≠J2

7. g′←交換g中工件J1、J2在工序k的加工機器

8. Case 2：(選擇插入擾動)

9. J1=rand(Ji|i=1,2,?,n)

10. J2=rand(Ji|i=1,2,?,n)←J1≠J2

11. if J1

12. g′←將g中工件J2信息插入到J1之前（即第j列數(shù)據(jù)插入到第i列前）

13. else

14. g′←將g中工件J1信息插入到J2之前

15. end

16. Case 3：（選擇子排序交換擾動）

17. J1=rand() Ji|i=1,2,?,n

18. J2=rand(Ji|i=1,2,?,n)?←J1≠J2

19. g′←交換g中工件J1和J2的調(diào)度信息（即交換調(diào)度信息矩陣中第j列和第i列數(shù)據(jù)）

20. end

21.ΔE=Cg-Cg′←原始解g與擾動新解g′的Makespan差

22. p=min{1,exp(-ΔE/T)}

23. if rand(1)

24. g=g′

25. end

27. return g

SADA搜索算法中，單點交換擾動與子排序交換擾動均為交換操作，時間復(fù)雜度為常數(shù)級，即O(1)；選擇插入擾動中，插入操作的復(fù)雜度為O(n)，因此該算法復(fù)雜度為O(n)。

SADA算法隨機選擇單點交換擾動、插入擾動、子排序交換擾動3種策略之一搜索全體極值鄰域，比單一搜索策略較大程度地擴大了搜索范圍。

SADA算法的3種擾動算法以粒子間排序信息為搜索對象，NEH-Greedy算法以同一臺機器上的工件加工順序為優(yōu)化搜索目標(biāo)，兩種算法從不同角度擴大粒子群搜索范圍，加快收斂速度。

3.6隨機擾動算法

若最優(yōu)粒子在一定迭代次數(shù)內(nèi)未更新，表明粒子可能陷入局部最優(yōu)，則對最優(yōu)粒子以概率pRPA進(jìn)行隨機擾動操作，避免局部最優(yōu)，改變粒子停滯狀態(tài)。隨機擾動算法（random perturbation algorithm，RPA）如下。

算法4隨機擾動算法

Input：全體極值g

Output：全體極值g

1. if rand(1)≤pRPA

2. Jα=rand(Ji|i=1,2,?,n)

3.在并行機編號限定范圍內(nèi)對工件Jα每道工序加工機器（即調(diào)度矩陣第α列數(shù)據(jù)）進(jìn)行隨機重置

4. end

5. return g

3.7更新慣性權(quán)重

慣性權(quán)重更新公式如下：

其中，ωstart為慣性權(quán)重初始值；ωend為算法達(dá)到最大迭代次數(shù)的慣性權(quán)重取值；TotalIte為種群迭代次數(shù)；ite為當(dāng)前迭代次數(shù)。

本文以遞減凹函數(shù)ω作為種群更新的慣性權(quán)重。在算法初期以個體極值為主要參考進(jìn)行更新操作，以局部尋優(yōu)為主，使算法較快進(jìn)入局部最優(yōu)；算法后期則以全體極值為參考，以RPA算法幫助粒子跳出局部最優(yōu)，增強全局搜索能力，保證了全局搜索和局部搜索之間的平衡。

基于以上思想及算法，MMPSO算法流程如圖2所示。

Fig.2　 Flow chart of MMPSO圖2　 MMPSO算法流程圖

經(jīng)以上分析，MMPSO算法的時間復(fù)雜度為O(TotalIte×nm2)。

4　實驗仿真

為驗證本文MMPSO算法的正確性與有效性，將MMPSO算法與FCFS算法、貪心算法[5]、改進(jìn)的遺傳算法[6]和最優(yōu)子種群遺傳算法[13]進(jìn)行仿真實驗和比較。各個算法在Matlab 2014a上編程實現(xiàn)，算法運行在CPU為Intel?CoreTMi5-3470 3.20 GHz，內(nèi)存為8 GB 的PC上。經(jīng)過實驗，MMPSO算法中慣性權(quán)重取值為ωstart=0.94，ωend=0.4，模擬退火初始溫度T=0.64，其他參數(shù)設(shè)置為種群規(guī)模PS=30，迭代次數(shù)TotalIte=50。

由于目前針對柔性流水車間調(diào)度問題沒有標(biāo)準(zhǔn)的測試實例集，本文采用隨機策略產(chǎn)生測試實例集。實例中工件加工時間為{1,2,?,20}上的隨機數(shù)。例如：根據(jù)隨機策略產(chǎn)生問題規(guī)模（總并行機數(shù)×工件數(shù)）為10×20的一個柔性流水車間調(diào)度問題實例的數(shù)據(jù)如表1所示。

以表1為實例，對FCFS算法、貪心算法、改進(jìn)的遺傳算法、最優(yōu)子種群遺傳算法和MMPSO算法分別進(jìn)行兩項實驗：算法所得可行解質(zhì)量及算法收斂速度。

Table 1　 An instance of flexible flow shop scheduling problem表1　一個柔性流水車間調(diào)度問題實例

運用以上5種算法對表1所示的實例分別獨立運行15次，各算法目標(biāo)值如表2所示。

由表2可知，F(xiàn)CFS算法和貪心算法中不存在解的更新機制，因此實驗所得目標(biāo)函數(shù)值沒有變化，可行解質(zhì)量有待提高；而改進(jìn)的遺傳算法、最優(yōu)子種群遺傳算法能不斷更新解的質(zhì)量，但在多次測試中所得可行解并不唯一，可行解質(zhì)量比FCFS算法和貪心算法有所提高；本文提出的MMPSO算法在15次實驗中12次取得較優(yōu)解Makespan=49，說明本文算法有效提高了可行解質(zhì)量。

針對表1所示的實例，對比混合粒子群算法、最優(yōu)子種群遺傳算法和改進(jìn)的遺傳算法收斂速度，結(jié)果如圖3所示。

Table 3　 Average relative deviation of solution computing by algorithms (Group A)表3　算法所得解平均相對偏差（A組）

Fig.3　 Objective function values change graph圖3　算法目標(biāo)函數(shù)值變化曲線圖

由圖3可知，MMPSO算法在種群初始階段便能得到優(yōu)于最優(yōu)子種群算法和改進(jìn)的遺傳算法的可行解，且隨著迭代次數(shù)增加收斂速度最快，最早得到優(yōu)化解，優(yōu)化解質(zhì)量最高。而最優(yōu)子種群遺傳算法和改進(jìn)的遺傳算法收斂速度較慢，且最優(yōu)解質(zhì)量差于MMPSO算法。這是由于MMPSO算法在初始化階段加入對初始粒子的優(yōu)化算法BMEA算法，可找到較優(yōu)的可行解，在算法迭代過程中增加NEH-Greedy算法和SADA搜索算法，有效擴大了搜索空間，使得算法收斂速度較快，且引入對當(dāng)前最優(yōu)解的RPA擾動，防止算法陷入局部最優(yōu)，最終使得問題可行解質(zhì)量有了進(jìn)一步提高。

單一實例測試具有偶然性，且本研究領(lǐng)域目前沒有統(tǒng)一的測試實例集，因此為驗證本文算法的適用性，采用隨機策略產(chǎn)生測試實例集。測試實例集分為A、B兩組不同參數(shù)實例。

A組25組不同規(guī)模（機器總數(shù)×工件數(shù)）實例，問題規(guī)模分別為4×6、5×5、5×10、5×20、5×30、5×50、10×10、10×20、10×30、10×50、10×100、10×200、15×5、15×10、15×15、15×20、15×30、15×50、20×200、20×500、10×5、20×20、100×20、200×20、500×20。工件在每臺機器上的加工時間為[1,20]上的隨機整數(shù)，保證工件在各并行機上的加工時間不完全相同。

B組測試實例問題規(guī)模為10×20。10組不同工件加工時間分別在[1,10]、[1,20]、[1,30]、[1,40]、[1, 50]、[1,60]、[1,70]、[1,80]、[1,90]、[1,100]上隨機產(chǎn)生。

對于每一組實例分別運行FCFS算法、貪心算法、改進(jìn)的遺傳算法、最優(yōu)子種群遺傳算法、MMPSO算法各15次，計算相對偏差及運行時間以評價算法質(zhì)量。平均相對偏差計算公式為：

式中，Li為算法i（i∈S）的輸出結(jié)果，S={FCFS算法，貪心算法，改進(jìn)的遺傳算法，最優(yōu)子種群遺傳算法，MMPSO算法}；L*=min(Li)。比較各算法平均相對偏差如表3、表4所示，運行時間如表5、表6所示。

Table 4　 Average relative deviation of solution computing by algorithms (Group B)表4　算法所得解平均相對偏差（B組）

Table 5　 Running time of algorithms (Group A)表5　算法運行時間（A組）　s

Table 6　 Running time of algorithms (Group B)表6　算法運行時間（B組）　s

由表3可知，對于以上5種對比算法的平均相對偏差而言，在不同問題規(guī)模下，實例中工件順序具有隨機性，且FCFS算法較大依賴于待加工工件的初始順序，因此隨著問題規(guī)模的變化FCFS算法的相對偏差表現(xiàn)較差，個別實例測試中表現(xiàn)較好，優(yōu)化效果波動明顯；貪心算法相對偏差最大，優(yōu)化效果最差；改進(jìn)的遺傳算法與最優(yōu)子種群遺傳算法有近似的優(yōu)化性能，相對偏差表現(xiàn)相近，區(qū)別不明顯，但明顯優(yōu)于FCFS算法和貪心算法；MMPSO算法相對偏差最小，在不同規(guī)模的測試實例下均能得到較好的可行解，具有較好的有效性。為了更清晰地比較和評價各算法的優(yōu)劣，給出了A組測試實例集的平均相對偏差對比圖，如圖4所示。

Fig.4　 Average relative deviation comparison (Group A)圖4　平均相對偏差對比圖（A組）

在機器數(shù)與工件數(shù)的數(shù)量差距較大時，F(xiàn)CFS算法與貪心算法的平均相對偏差增大，算法表現(xiàn)不穩(wěn)定；而智能優(yōu)化算法此類情況下表現(xiàn)優(yōu)秀，其中MMPSO算法表現(xiàn)最佳，平均相對偏差最小，說明MMPSO算法能較好解決不同規(guī)模比例的柔性流水車間調(diào)度問題。

表4中，工件加工時間的隨機取值范圍變化，貪心算法在少數(shù)實例下能得到較好的解，相對偏差較小，但大多數(shù)情況平均相對偏差較大，且優(yōu)化效果不穩(wěn)定；FCFS算法平均相對偏差表現(xiàn)一般，但在加工時間有較大差值時，優(yōu)化效果出現(xiàn)較大偏差；改進(jìn)的遺傳算法與最優(yōu)子種群遺傳算法在加工時間[0,20]區(qū)間內(nèi)表現(xiàn)最好，相對偏差最小，在所有實例集測試中波動幅度不大；MMPSO算法平均相對偏差最小且?guī)缀鯖]有較大波動，同樣能較好地解決不同加工時間范圍內(nèi)的柔性流水車間調(diào)度問題，優(yōu)于其他算法。B組測試實例集的平均相對偏差對比圖如圖5所示。

Fig.5　 Average relative deviation comparison (Group B)圖5　平均相對偏差對比圖（B組）

對比各算法的時間效率，如表5、表6所示，雖然FCFS算法和貪心算法速度較快，但優(yōu)化效果差，給實際應(yīng)用帶來較大的損失；而基于群體的智能優(yōu)化算法雖然時間消耗較大，但在可接受的時間范圍內(nèi)得到較好的可行解，在實際應(yīng)用過程中能大大降低生產(chǎn)成本，提高利潤。比較改進(jìn)的遺傳算法、最優(yōu)子種群遺傳算法和MMPSO算法均屬于智能優(yōu)化算法，其中MMPSO算法運行時間最短，且對比表4、表5，MMPSO算法相對偏差最小，可行解最優(yōu)。

綜上所述，本文MMPSO算法對于柔性流水車間調(diào)度問題的求解是非常有效的，而且MMPSO算法性能明顯優(yōu)于參與比較的其他算法。

5　結(jié)束語

針對柔性流水車間調(diào)度問題的特點，分析現(xiàn)有粒子群算法和模擬退火算法的優(yōu)勢及不足，本文提出了MMPSO算法。以粒子群算法為基礎(chǔ)，MMPSO算法初期在解空間內(nèi)隨機產(chǎn)生粒子群信息，通過BMEA算法對隨機選擇的初始粒子進(jìn)行優(yōu)化操作，在保證種群多樣性的基礎(chǔ)上避免瓶頸機器出現(xiàn)，提高了初始種群質(zhì)量。隨后按照合法性更新策略更新粒子信息。在算法迭代過程中，為擴大粒子搜索范圍，本文提出了兩種搜索算法：（1）在結(jié)合NEH算法和貪心算法基礎(chǔ)上提出NEH-Greedy搜索算法，對粒子群個體極值執(zhí)行NEH-Greedy算法操作，提高可行解質(zhì)量，擴大算法搜索范圍；（2）對粒子全體極值執(zhí)行SADA搜索算法，進(jìn)一步擴大粒子搜索范圍。同時加入RPA擾動操作，使處于靜止?fàn)顟B(tài)的全體極值跳出局部最優(yōu)狀態(tài)。仿真實驗證明了MMPSO算法具有較強的有效性和適用性。

References:

[1] Hong Wang. Flexible flow shop scheduling optimum heuristics and artificial intelligence solutions[J]. Expert Systems, 2005, 22(2): 78-85.

[2] Jungwattanakit J, Reodecha M, Chaovalitwongse P, et al. Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria[J]. International Journal of Advanced Manufacturing Technology, 2008, 37(3/4): 354-370.

[3] Hoogeveen J A, Lenstra J K, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research, 1996, 89(1): 172-175.

[4] Linn R. Hybrid flow shop scheduling: a survey[J]. Computers & Industrial Engineering, 1999, 37(1/2): 57-61.

[5] Li Xiaofeng, Zhao Hai, Du Hongjun, et al. Greedy algorithm solution of flexible flow shop scheduling problem[J]. Jilin University Journal, 2009, 27(6): 585-589.

[6] Wang Xudong, Dai Qingyun. Scheduling for flexible flowshop problem based on an improved genetic algorithm[C]// Proceedings of the 2014 IEEE International Conference on Consumer Electronics-China. Piscataway, USA: IEEE, 2014: 1-3.

[7] Song Ye, Yang Genke. Real time scheduling using branchbound algorithm and artificial neural network[J]. ComputerSimulation, 2008, 25(12): 321-324.

[8] Xuan Hua, Tang Lixin. Lagrangian relaxation algorithm for real-time hybrid flowshop scheduling with no-wait in process[J]. Control and Decision, 2006, 21(4): 376-380.

[9] Sun Ying, Chi Hong, Jia Chuanliang. Nonlinear mixed-integer programming model for emergency resource dispatching with multi-path[J]. Operations Research and Management Science, 2007, 16(5): 5-8.

[10] Liu Bo, Wang Ling, Jin Yihui. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2007, 27(1): 18-27.

[11] Akhshabi M, Tavakkoli-Moghaddam R, Rahnamay-Roodposhti F. A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time[J]. International Journal of Advanced Manufacturing Technology, 2014, 70(5): 1181-1188.

[12] Zhang Changsheng, Sun Jigui, Zhu Xingjun, et al. An improved particle swarm optimization algorithm for flow shop scheduling problem[J]. Information Processing Letters, 2008, 108(4): 204-209.

[13] Wang Jinpeng, Zhu Hongjun, Zhou Jun. Optimal sub-population genetic algorithm for flexible flow shop scheduling problem[J]. Application Research of Computers, 2012, 29 (2): 442-444.

[14] Hertz A. Finding a feasible course schedule using tabu search[J]. Discrete Applied Math, 1992, 35(3): 255-270.

[15] van Laarhoven P J M, Aarts E H L, Lenstra J K. Job shop scheduling by simulated annealing[J]. Operation Research, 1992, 40(1): 113-125.

[16] Zandieh M, Fatemi Ghomi S M T, Moattar Husseini S M. An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2006, 180(1): 111-127.

[17] Mastrolilli M, Gambaroella L M. Effective neighborhood functions for the flexible job shop problem[J]. Journal of Scheduling, 2000, 3(1): 3-20.

[18] Shen Bin, Zhou Yingjun, Wang Jiahai. Flow job shop scheduling based on self-adaptive genetic algorithm[J]. Computer Engineering, 2010, 36(14): 201-203.

附中文參考文獻(xiàn)：

[5]李曉峰,趙海,杜洪軍,等.柔性流水作業(yè)排序問題的貪心算法求解[J].吉林大學(xué)學(xué)報, 2009, 27(6): 585-589.

[7]宋曄,楊根科.基于分支定界和神經(jīng)網(wǎng)絡(luò)的實時調(diào)度策略[J].計算機仿真, 2008, 25(12): 321-324.

[8]軒華,唐立新.實時無等待HFS調(diào)度的一種拉格朗日松弛算法[J].控制與決策, 2006, 21(4): 376-380.

[9]孫穎,池宏,賈傳亮.多路徑下應(yīng)急資源調(diào)度的非線性混合整數(shù)規(guī)劃模型[J].運籌與管理, 2007, 16(5): 5-8.

[13]王金鵬,朱洪俊,周俊.最優(yōu)子種群遺傳算法求解柔性流水車間調(diào)度問題[J].計算機應(yīng)用研究, 2012, 29(2): 442-444.

[18]沈斌,周瑩君,王家海.基于自適應(yīng)遺傳算法的流水車間作業(yè)調(diào)度[J].計算機工程, 2010, 36(14): 201-203.

ZHANG Haiyue was born 1990. She is an M.S. candidate at Guizhou university. Her research interest is algorithms design and analysis.張海月（1990—），女，河北唐山人，貴州大學(xué)碩士研究生，主要研究領(lǐng)域為算法設(shè)計與分析。

QIN Yongbin was born in 1980. He is an associate professor and M.S. supervisor at Guizhou university, and the member of CCF. His research interests include computability and computational complexity, intelligent computing and trusted computing.秦永彬（1980—），男，山東人，貴州大學(xué)副教授、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為可計算性和計算復(fù)雜性，智能計算，可信計算。

XU Daoyun was born in 1959. He is a professor and Ph.D. supervisor at Guizhou University, and the senior member of CCF. His research interests include computability and computational complexity, algorithms design and analysis.許道云（1959—），男，貴州安順人，貴州大學(xué)教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域為可計算性和計算復(fù)雜性，算法設(shè)計與分析。

Multi-Search Mechanism Particle Swarm Optimization Algorithm for Solving FFS Problem?

ZHANG Haiyue, QIN Yongbin, XU Daoyun+
College of Computer Science and Technology, Guizhou University, Guiyang 550025, China
+ Corresponding author: E-mail: dyxu@gzu.edu.cn

ZHANG Haiyue, QIN Yongbin, XU Daoyun. Multi-search mechanism particle swarm optimization algorithm for solving FFS problem. Journal of Frontiers of Computer Science and Technology, 2016, 10(3)：433-444.

Abstract:For the flexible flow shop scheduling (FFS) problem, this paper proposes a multi-search mechanism particle swarm optimization algorithm (MMPSO) in order to obtain a better optimal solution. Based on the analysis of the characteristics of flexible flow shop scheduling problem, this paper designs a particle information encoding scheme for the problem, then proposes the bottleneck machine elimination algorithm to improve the quality of initial population, while using NEH-Greedy search algorithm in the individual extremum search and SADA (simulated annealing disturb algorithm) search algorithm in all extremum search, which are both used to widen the search scope, improve the quality of feasible solutions and speed up the convergence process, in the iterative search RPA (random perturbation algorithm) operations are used to avoid plunging local optimum for all extremum. The experimental results show that the proposed algorithm can obtain a good optimal solution of this flexible flow shop scheduling problem by a faster convergence rate.

doi:10.3778/j.issn.1673-9418.1511041

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP391