張海月，秦永彬，許道云

貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽(yáng)550025

ISSN 1673-9418 CODEN JKYTA8

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

?

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

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

貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽(yáng)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 (國(guó)家自然科學(xué)基金); the Major Applied Basic Research Program of Guizhou Province under Grant No. JZ20142001 (貴州省重大應(yīng)用基礎(chǔ)研究項(xiàng)目); 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)人才科研項(xiàng)目); 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

摘要：針對(duì)柔性流水車間調(diào)度（flexible flow shop scheduling，F(xiàn)FS）問題，提出了一種混合搜索機(jī)制粒子群算法（multi-search mechanism particle swarm optimization algorithm，MMPSO），以期獲得柔性流水車間調(diào)度問題的優(yōu)化解。在分析柔性流水車間調(diào)度問題特點(diǎn)的基礎(chǔ)上，設(shè)計(jì)了針對(duì)該問題的粒子信息編碼方案，提出了瓶頸機(jī)器消除算法以提升初始種群的質(zhì)量；同時(shí)在個(gè)體極值搜索中采用NEH-Greedy搜索算法，在全體極值搜索中采用SADA（simulated snnealing disturb algorithm）搜索算法以擴(kuò)大搜索范圍，提高可行解質(zhì)量，加快收斂速度，在算法迭代搜索過程中對(duì)全體極值進(jìn)行RPA（random perturbation algorithm）操作以避免算法陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，MMPSO算法能夠以較快的收斂速度獲得柔性流水車間調(diào)度問題的一個(gè)較好的優(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ū)別是允許工件在一個(gè)或多個(gè)加工工序中存在并行機(jī)，在存在并行機(jī)的工序中，工件可任意選擇一臺(tái)并行機(jī)加工且加工時(shí)間不同，其是一種更加一般化的組合優(yōu)化問題。在實(shí)際生產(chǎn)過程中，多數(shù)生產(chǎn)場(chǎng)景都具有柔性流水車間的特點(diǎn)，如化工制造、鋼鐵鑄造、紡織制造等。

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

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

2　問題描述

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

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

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

（3）所有機(jī)器均可在時(shí)間0開始加工；

（4）每個(gè)工件的每道工序僅可在一臺(tái)機(jī)器上加工；

（5）每臺(tái)機(jī)器同一時(shí)間只能加工一個(gè)工件；

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

（7）機(jī)器無(wú)故障等特殊情況。

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

3　混合搜索機(jī)制粒子群算法

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

3.1 MMPSO算法編碼方式

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

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

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

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

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

MMPSO算法中每個(gè)粒子表示柔性流水車間調(diào)度方案的一個(gè)可行解，柔性流水車間調(diào)度問題的一個(gè)可行解具有兩個(gè)屬性，機(jī)器選擇和加工順序，因此每個(gè)粒子信息也包含以上兩個(gè)屬性。而標(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（機(jī)器選擇）中xij轉(zhuǎn)換為粒子信息or，其中r=(j-1)×m+i。同理，原調(diào)度信息矩陣XT（加工順序）中xtkl轉(zhuǎn)換為粒子信息otq，其中q=(l-1)×m+k。

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

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

3.2種群初始化

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

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

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

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

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

算法1 BMEA算法

Input：一個(gè)柔性流水車間可行解Sch Output：無(wú)瓶頸機(jī)器可行解Sch

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

3. N←可行調(diào)度Sch各機(jī)器加工工件數(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)；對(duì)于工序i，最壞情況為所有工件都在同一臺(tái)機(jī)器上加工，最多需要對(duì)n-2個(gè)工件的加工機(jī)器信息進(jìn)行修改，時(shí)間復(fù)雜度為O(n)。因此算法BMEA的時(shí)間復(fù)雜度為O(mn)。

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

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

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

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

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

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

3.4 NEH-Greedy搜索算法

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

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

算法2 NEH-Greedy搜索算法

Input：一個(gè)柔性流水車間可行解Sch

Output：一個(gè)柔性流水車間可行解Sch

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

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

3. while ψ≠?

4.φ1←ψ上第一臺(tái)機(jī)器

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

7.α2=′-{α1}

8. Sch1←修改Sch并行機(jī)φ1上工件加工順序?yàn)閧α1,α2}

9. Sch2←修改Sch并行機(jī)φ1上工件加工順序?yàn)閧α2,α1}

10. Sch=min{}

Makespan(Sch1,Sch2,Sch)

11.ψ=ψ-{φ1}

12. end

13. end

14. return Sch

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

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

3.5 SADA搜索算法

粒子群算法中的全體極值為當(dāng)前粒子群最優(yōu)解，為進(jìn)一步擴(kuò)大搜索范圍，提高可行解質(zhì)量，本文采用模擬退火擾動(dòng)算法（simulated annealing disturb algorithm，SADA）?；舅枷胧窃诿枯喌?，隨機(jī)選擇3種擾動(dòng)方案之一產(chǎn)生新解ω′，計(jì)算新解ω′與原始解ω的目標(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: (選擇單點(diǎn)交換擾動(dòng))

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

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

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

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

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

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：（選擇子排序交換擾動(dòng)）

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與擾動(dòng)新解g′的Makespan差

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

23. if rand(1)

24. g=g′

25. end

27. return g

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

SADA算法隨機(jī)選擇單點(diǎn)交換擾動(dòng)、插入擾動(dòng)、子排序交換擾動(dòng)3種策略之一搜索全體極值鄰域，比單一搜索策略較大程度地?cái)U(kuò)大了搜索范圍。

SADA算法的3種擾動(dòng)算法以粒子間排序信息為搜索對(duì)象，NEH-Greedy算法以同一臺(tái)機(jī)器上的工件加工順序?yàn)閮?yōu)化搜索目標(biāo)，兩種算法從不同角度擴(kuò)大粒子群搜索范圍，加快收斂速度。

3.6隨機(jī)擾動(dòng)算法

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

算法4隨機(jī)擾動(dòng)算法

Input：全體極值g

Output：全體極值g

1. if rand(1)≤pRPA

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

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

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)重。在算法初期以個(gè)體極值為主要參考進(jìn)行更新操作，以局部尋優(yōu)為主，使算法較快進(jìn)入局部最優(yōu)；算法后期則以全體極值為參考，以RPA算法幫助粒子跳出局部最優(yōu)，增強(qiáng)全局搜索能力，保證了全局搜索和局部搜索之間的平衡。

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

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

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

4　實(shí)驗(yàn)仿真

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

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

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

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

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

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

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

Table 3　 Average relative deviation of solution computing by algorithms (Group A)表3　算法所得解平均相對(duì)偏差（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算法在初始化階段加入對(duì)初始粒子的優(yōu)化算法BMEA算法，可找到較優(yōu)的可行解，在算法迭代過程中增加NEH-Greedy算法和SADA搜索算法，有效擴(kuò)大了搜索空間，使得算法收斂速度較快，且引入對(duì)當(dāng)前最優(yōu)解的RPA擾動(dòng)，防止算法陷入局部最優(yōu)，最終使得問題可行解質(zhì)量有了進(jìn)一步提高。

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

A組25組不同規(guī)模（機(jī)器總數(shù)×工件數(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。工件在每臺(tái)機(jī)器上的加工時(shí)間為[1,20]上的隨機(jī)整數(shù)，保證工件在各并行機(jī)上的加工時(shí)間不完全相同。

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)束語(yǔ)

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

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é)報(bào), 2009, 27(6): 585-589.

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

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

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

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

[18]沈斌,周瑩君,王家海.基于自適應(yīng)遺傳算法的流水車間作業(yè)調(diào)度[J].計(jì)算機(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)域?yàn)樗惴ㄔO(shè)計(jì)與分析。

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會(huì)員，主要研究領(lǐng)域?yàn)榭捎?jì)算性和計(jì)算復(fù)雜性，智能計(jì)算，可信計(jì)算。

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高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭捎?jì)算性和計(jì)算復(fù)雜性，算法設(shè)計(jì)與分析。

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

中圖分類號(hào)：TP391