宋存利

大連交通大學(xué)，遼寧大連 116028

求解柔性作業(yè)調(diào)度問題的協(xié)同進(jìn)化粒子群算法

宋存利

大連交通大學(xué)，遼寧大連 116028

1 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）是JSP調(diào)度問題的擴(kuò)展。在JSP中一個(gè)作業(yè)包含多個(gè)工序，每道工序僅在一臺(tái)加工設(shè)備上加工，而FJSP中，每個(gè)工序可有多臺(tái)性能不一的加工設(shè)備，放松了對(duì)加工設(shè)備的約束，擴(kuò)大了解的搜索范圍，相比JSP更接近加工實(shí)際也更加復(fù)雜。對(duì)FJSP問題進(jìn)行研究的文獻(xiàn)很多，其中Bruker和Schlie[1]是最早對(duì)FJSP問題進(jìn)行研究的人，他們提出了求解2工件的FJSP的多項(xiàng)式算法。之后很多學(xué)者都陸續(xù)對(duì)之進(jìn)行了研究，如Chen等[2]、楊曉梅等[3]、張超勇等[4]、劉冬梅等[5]、李鐵克等[6]這些作者提出了求解該問題的遺傳算法，在這些算法中，他們有的將工件排序和設(shè)備分配作為兩個(gè)變量求解，有些用一個(gè)統(tǒng)一的方法求解，然后對(duì)相應(yīng)的遺傳算子進(jìn)行改進(jìn)，以便優(yōu)化算法性能；Brandimarte 等[7]則是用禁忌搜索算法求解該問題；Fattahi等[8]提出了四種將禁忌搜索算法與模擬退火算法相混合的策略來解決該問題；Mastrololli等[9]則將禁忌搜索算法和鄰域函數(shù)混合來求解該問題；劉曉冰等[10]提出了免疫克隆選擇算法求解柔性生產(chǎn)調(diào)度問題；Liu等[11]針對(duì)柔性調(diào)度問題提出了一種多粒子群求解多目標(biāo)的算法求解該問題，該算法中，不同種群以不同的目標(biāo)求解，同時(shí)各種群間通過信息的傳遞來求得一個(gè)滿足多目標(biāo)的綜合優(yōu)化解。Zribi等[12]提出了求解柔性調(diào)度問題的Z.K.K方法，該方法的特點(diǎn)是將柔性Job-shop調(diào)度問題分解為設(shè)備分配和工序排序兩個(gè)子問題，首先用分枝定界和禁忌搜索算法結(jié)合一種下界評(píng)估方法來求出設(shè)備分配方案的較優(yōu)解，然后根據(jù)此設(shè)備分配方案利用一種遺傳算法來對(duì)工序排序?qū)ふ易顑?yōu)解。Ho等[13]提出了求解柔性Job-shop調(diào)度問題的文化進(jìn)化遺傳算法GENACE，該算法的CDR算法利用不同的優(yōu)先級(jí)規(guī)則來初始化遺傳算法的種群，然后利用文化遺傳算法來求解。彭傳勇等[14]提出了廣義的粒子群算法求解作業(yè)車間調(diào)度問題，在此算法的啟發(fā)下，本文提出求解柔性作業(yè)車間調(diào)度問題的粒子群算法。

總之對(duì)柔性調(diào)度問題的研究文獻(xiàn)較多，但利用粒子群算法對(duì)此問題的求解卻相對(duì)較少，在此基礎(chǔ)上，本文在研究柔性作業(yè)車間調(diào)度問題特點(diǎn)的基礎(chǔ)上，提出了解決該問題的協(xié)同進(jìn)化的粒子群優(yōu)化算法CPSO，該算法對(duì)設(shè)備分配碼和工件編碼分別采用不相同的編碼方法。對(duì)設(shè)備分配碼采用整數(shù)編碼方法，提出了修訂的粒子更新公式來對(duì)設(shè)備編碼進(jìn)行更新操作，以保證設(shè)備編碼在運(yùn)動(dòng)過程的合法性。對(duì)工件序列采用基于操作的隨機(jī)鍵編碼方式編碼。同時(shí)考慮到設(shè)備分配與工件排序之間的強(qiáng)耦合性，傳統(tǒng)的粒子群求解模式有可能在粒子運(yùn)動(dòng)過程中破壞gbest的優(yōu)化模式，因此將設(shè)備選擇和工件調(diào)度分別作為兩個(gè)尋優(yōu)變量，分別利用PSO算法進(jìn)行尋優(yōu)，并根據(jù)兩個(gè)變量的內(nèi)容進(jìn)行互相評(píng)價(jià)，最終獲得一個(gè)將設(shè)備選擇和工件調(diào)度相結(jié)合的最優(yōu)的調(diào)度結(jié)果。最后實(shí)驗(yàn)表明該算法對(duì)FJSP問題的有效性。

2 柔性作業(yè)車間調(diào)度問題描述

柔性Job-shop調(diào)度問題可描述為：n個(gè)工件在m臺(tái)設(shè)備上加工。n個(gè)工件的編號(hào)用Ji來表示（其中i=1，2，…，n），每個(gè)工件Ji包含Oi道工序，用Oij表示工件Ji的第j道工序(1≤j≤Oi)。m臺(tái)設(shè)備的編號(hào)用Mk來表示（其中k=1，2，…，m），對(duì)每道工序Oij都至少有1臺(tái)設(shè)備可完成它的加工。定義P為設(shè)備分配矩陣，當(dāng)Pijk=1時(shí)，表示工件Ji的第j道工序在設(shè)備Mk上加工，否則Pijk=0。定義Tijk為加工時(shí)間矩陣，當(dāng)設(shè)備Mk不能加工此工序時(shí)，則定義Tijk=∞，矩陣S代表工件的開工時(shí)間矩陣，其中Sij為工件Ji的第j道工序的開工時(shí)間，矩陣C代表工件的完工時(shí)間矩陣，其中Cij為工件Ji的第j道工序的完工時(shí)間。當(dāng)每臺(tái)設(shè)備都可加工所有工序時(shí)，則問題為全柔性車間作業(yè)調(diào)度問題（Τotal-Flexible Job-shop Scheduling Problem，Τ-FJSP），當(dāng)每道工序的加工設(shè)備是m臺(tái)設(shè)備的部分設(shè)備時(shí)，則此問題為部分柔性車間作業(yè)調(diào)度問題（Partial-Flexible Job-shop Scheduling Problem，P-FJSP），本文設(shè)定調(diào)度的目標(biāo)是求最小化最大完工時(shí)間makespan，其表達(dá)如公式（1）所示。

公式（2）～（6）表示問題的約束條件，其中公式（2）表示一個(gè)工序的完工時(shí)間等于其開工時(shí)間加上其在某一具體加工設(shè)備上的加工時(shí)間之和，這表明工序在加工過程中設(shè)備不會(huì)故障、不被其他工序搶占，直到在該設(shè)備加工完成才可離開。公式（3）說明每道工序都必須等其前驅(qū)工序加工完成才能開始加工；公式（4）和公式（5）說明對(duì)應(yīng)每個(gè)工序，只能將它分配到一臺(tái)可加工設(shè)備上去。公式（6）說明必須為所有的工序分配加工設(shè)備。

3 算法描述

3.1 編碼及解碼算法

（2）工序排序編碼

粒子群算法求解FJSP的第一個(gè)問題是用一種合適的粒子碼來表示合法的調(diào)度結(jié)果。在FJSP問題中，由于每道工序的加工設(shè)備不唯一，因此相比JSP它的編碼工作涉及到兩方面，一個(gè)是加工設(shè)備分配問題，另一個(gè)是安排工序的加工順序問題。由于兩個(gè)工作的性質(zhì)不同，因此一個(gè)FJSP的調(diào)度編碼應(yīng)由兩部分編碼組成，第一部分對(duì)應(yīng)設(shè)備分配的編碼，第二部分對(duì)應(yīng)工序排序的編碼。

（1）設(shè)備分配編碼方案

首先對(duì)m臺(tái)加工設(shè)備依次從1開始編號(hào)，每臺(tái)設(shè)備對(duì)應(yīng)唯一的編號(hào)。對(duì)工序進(jìn)行編號(hào)，根據(jù)問題描述，總共有待加工工序總數(shù)為道工序的加工任務(wù)，用一個(gè)長度為S的向量來表示粒子位置，工件i將在向量中出現(xiàn)Oi次，第一次出現(xiàn)代表第i個(gè)工件的第一道工序，第二次出現(xiàn)代表第i個(gè)工件的第二道工序，以此類推。這樣做保證了粒子更新操作將產(chǎn)生滿足工藝約束的編碼方案，不需額外的調(diào)整。

3.2 粒子更新公式定義

在PSO算法中，每個(gè)粒子被映射成問題空間的一個(gè)可行解。在D維的搜索空間中，每個(gè)粒子都具有自己D維的位置和速度。在飛行過程中，每個(gè)粒子通過自身和同伴的飛行經(jīng)驗(yàn)不斷調(diào)整自己的飛行速度，從而達(dá)到飛向好的搜索空間的目的。這里用Xi=(xi，1，xi，2，…，xi，d)表示粒子的位置，用Vi=(νi，1，νi，2，…，νi，d)表示粒子速度，用Pi= (pi，1，pi，2，…，pi，d)表示粒子自身的最佳位置，用Pg=(pg1，pg2,…，pgd)表示群體的最佳位置，用MPg=(mpg1，mpg2，…，mpgd)表示所有群體的目前最佳位置。則工序編碼部分的粒子編碼，采用的粒子更新公式如式（7）所示。

設(shè)備分配碼這部分的粒子碼用整數(shù)來編碼，每個(gè)數(shù)據(jù)代表設(shè)備的編號(hào)，針對(duì)設(shè)備分配碼部分設(shè)計(jì)了粒子更新公式如式（8）所示。

具體對(duì)公式（8）的解釋是w代表粒子Xi的變異概率，即對(duì)于粒子Xi每維上的元素值，隨機(jī)生成一個(gè)隨機(jī)數(shù)ρ，若ρ〈w，則修改對(duì)應(yīng)維上的設(shè)備號(hào)，讓其為另一個(gè)能加工該工序的合法設(shè)備號(hào)。否則不變。參數(shù)c1和c2為交叉率，其中c1+c2≤0.7。具體的交叉操作步驟為：

步驟1首先設(shè)置集合set={1，2，…，D}，set1=set2=Φ （Φ代表空集）。

步驟2從集合set中隨機(jī)選擇c1×D個(gè)元素，每選擇一個(gè)元素，則將它放入集合set1，并從集合set中去掉。

步驟3再次從集合set中選擇c2×D個(gè)元素，每選擇一個(gè)元素，則將它放入集合set2，并從集合set中去掉。

步驟4以set中的元素為下標(biāo)，將粒子xi，d(t)中對(duì)應(yīng)位置的元素值賦值給xi，d(t+1)的對(duì)應(yīng)位置；以set1中的元素為下標(biāo)，將粒子pi，d(t)中對(duì)應(yīng)位置的元素值賦值給xi，d(t+1)的對(duì)應(yīng)位置；以set1中的元素為下標(biāo)，將粒子pgd(t)中對(duì)應(yīng)位置的元素值賦值給xi，d(t+1)的對(duì)應(yīng)位置，則操作結(jié)束。

3.3 協(xié)同進(jìn)化模型

協(xié)同進(jìn)化的一般思想是多個(gè)種群共同進(jìn)化，或者是一個(gè)種群分為多個(gè)部分，各種群在各自獨(dú)立進(jìn)化的同時(shí)相互間共享和不斷進(jìn)行信息交換。各種群不僅利用從外界獲得的各種信息來指導(dǎo)自身的搜索，同時(shí)還把搜索得到的經(jīng)驗(yàn)與其他種群分享，從而使整個(gè)系統(tǒng)協(xié)同進(jìn)化，直至獲得最優(yōu)解。本文的協(xié)同進(jìn)化粒子群算法框架如圖1所示，其中M代表設(shè)備分配編碼，P代表工件排序碼。

圖1 協(xié)同進(jìn)化粒子群優(yōu)化算法模型

在該協(xié)同進(jìn)化模型中，粒子種群有兩種類型，一種是由s個(gè)M={Mj|j=1，2，…，s}粒子構(gòu)成的設(shè)備分配群，用Mswarm表示，該種群中每個(gè)粒子對(duì)應(yīng)一個(gè)設(shè)備分配方案，且該種群只有一個(gè)群體，用于對(duì)設(shè)備分配方案進(jìn)行求解。另一種是含有s個(gè)子種群的工件排序群Pswarmj，其中j= 1，2，…，s，每個(gè)Pswarmj又包含k個(gè)粒子，每個(gè)粒子Pj，i(i=1，2，…，k)表示一個(gè)工件排序碼，該類種群用于對(duì)工件排序方案進(jìn)行進(jìn)化。設(shè)備分配粒子Mj與工件排序種群Pswarmj一一對(duì)應(yīng)，相互結(jié)合進(jìn)行評(píng)價(jià)。具體的CPSO算法進(jìn)化過程描述為Pswarmj中的每個(gè)粒子與Mj表示的設(shè)備分配方案相結(jié)合進(jìn)行最小化最大完工時(shí)間的計(jì)算，并利用PSO算法連續(xù)進(jìn)化POP1代獲得一個(gè)新的種群Pswarmj。對(duì)于設(shè)備分配種群Mswarm中的每個(gè)粒子Mj的評(píng)價(jià)，則利用與其對(duì)應(yīng)的工件排序種群Pswarmj中的目前存在的最優(yōu)工件排序粒子對(duì)其進(jìn)行評(píng)價(jià)，然后對(duì)Mswarm進(jìn)化一代，從而獲得新的Mswarm種群，即一組新的設(shè)備分配方案。在一次協(xié)同進(jìn)化結(jié)束后，對(duì)Pswarmj種群的每個(gè)粒子再利用新的設(shè)備分配方案進(jìn)行評(píng)價(jià)，以此類推，直到滿足協(xié)同進(jìn)化算法終止條件。本文中用最大協(xié)同進(jìn)化代數(shù)POP2來確定。最后輸出所有Pswarm種群中最好的工序分配方案和Mswarm中的最好設(shè)備分配方案?？傊疚闹械膮f(xié)同進(jìn)化算法是同時(shí)利用設(shè)備種群和工件分配種群的同時(shí)進(jìn)化來獲取最優(yōu)解。協(xié)同進(jìn)化PSO算法的流程圖如圖2所示。

圖2 協(xié)同進(jìn)化PSO算法流程圖

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

首先對(duì)完全柔性調(diào)度問題Kacem進(jìn)行測(cè)試，其中的CPSO算法參數(shù)設(shè)置如下：由于全柔性調(diào)度問題可選方案較多，所以對(duì)Mswarm種群規(guī)模設(shè)計(jì)較大s=15。對(duì)部分柔性調(diào)度問題Brandimarte問題，Mswarm種群規(guī)模設(shè)計(jì)較小一些s=10。其他方面兩問題可采用一致。每個(gè)Pswarm子種群的規(guī)模采用k=20，Mswarm種群進(jìn)化最大代數(shù)pop1= 30，每個(gè)Pswarm子種群進(jìn)化最大代數(shù)pop2=40。對(duì)Pswarm種群，其慣性因子w=1，加速因子c1=c2=1.5，c3=1.5，每個(gè)粒子的矢量值區(qū)間為-4～4，速度的矢量值區(qū)間為-2～2。對(duì)Mswarm種群，其慣性因子w=0.05，c1=c2=0.25。所有的工件序列碼采用隨機(jī)生產(chǎn)方式，設(shè)備分配碼隨機(jī)生成40%，最短設(shè)備優(yōu)先選擇生成一個(gè)，剩余粒子采用70%的設(shè)備選擇最短設(shè)備加工算法生成。

每個(gè)算例均運(yùn)行10次，下面給出算法的統(tǒng)計(jì)結(jié)果。其中表中指標(biāo)表示如公式（9）和公式（10）：

其中Cmax為各個(gè)算法取得的最優(yōu)值，Cavg為各個(gè)算法運(yùn)行10次取得結(jié)果的平均值。

表1中給出的是關(guān)于Kacem問題的調(diào)度統(tǒng)計(jì)結(jié)果，從結(jié)果看CPSO和GENACE算法取得的最優(yōu)結(jié)果均相同，求出了問題的目前最優(yōu)解。從ARE的統(tǒng)計(jì)結(jié)果可看出CPSO算法誤差較小。表2給出了關(guān)于Brandimarte問題的運(yùn)行結(jié)果，其中LB指問題的下界值，UB指問題的上界值。將算法CPSO的統(tǒng)計(jì)結(jié)果與目前比較好的算法Z.K.K[12]的運(yùn)行結(jié)果和Chen[2]等的運(yùn)行結(jié)果進(jìn)行比較。統(tǒng)計(jì)結(jié)果表明CPSO算法相對(duì)于Z.K.K算法，有8個(gè)結(jié)果都要好于Z.K.K，對(duì)問題MK03和MK08的優(yōu)化結(jié)果和Z.K.K相同。將CPSO算法和Chen的算法相比，5個(gè)問題的結(jié)果優(yōu)于Chen的結(jié)果，3個(gè)問題的結(jié)果和Chen的結(jié)果相同，2個(gè)問題的結(jié)果稍差于Chen的結(jié)果。通過以上實(shí)驗(yàn)說明了協(xié)同進(jìn)化算法在求解FJSP問題上具有明顯的優(yōu)越性。

表1 各種算法對(duì)Kacem問題的調(diào)度結(jié)果

表2 各種算法對(duì)Brandimarte問題的求解結(jié)果

5 結(jié)論

本文在研究柔性作業(yè)車間調(diào)度問題特點(diǎn)的基礎(chǔ)上，提出了解決該問題的協(xié)同進(jìn)化粒子群優(yōu)化算法CPSO，該算法對(duì)設(shè)備分配碼和工件序列碼分別采用不相同的編碼方法。對(duì)設(shè)備分配碼采用整數(shù)編碼方法，提出了修訂的粒子更新公式來對(duì)設(shè)備編碼進(jìn)行更新操作，以保證設(shè)備編碼在運(yùn)動(dòng)過程的合法性。對(duì)工件序列采用基于操作的隨機(jī)鍵編碼方式編碼，該部分粒子的更新采用標(biāo)準(zhǔn)粒子更新公式。同時(shí)考慮到設(shè)備分配與工件排序之間的強(qiáng)耦合性，傳統(tǒng)的粒子群求解模式有可能在粒子運(yùn)動(dòng)過程中破壞gbest的優(yōu)化模式，同時(shí)將設(shè)備選擇和工件調(diào)度分別作為兩個(gè)尋優(yōu)變量，分別利用PSO算法進(jìn)行自適應(yīng)尋優(yōu)，并根據(jù)兩個(gè)變量的內(nèi)容進(jìn)行互相評(píng)價(jià)，最終獲得一個(gè)將設(shè)備選擇和工件調(diào)度相結(jié)合的最優(yōu)的調(diào)度結(jié)果。通過實(shí)驗(yàn)驗(yàn)證了算法的有效性，但不足之處是算法運(yùn)行時(shí)間較長，今后需在提高算法運(yùn)行效率方面繼續(xù)研究。

[1]Bruker P，Schlie R.Job shop scheduling with multipurpose machines[J].Computing，1990，45：369-375.

[2]Chen H，Ihlow J，Lehmann C.A genetic algorithm for flexiblejob-shopscheduling[C]//ΤheProceedingsofthe1999 IEEE International Conference on Robotics&Automation，Detroit，1999：1120-1125.

[3]楊曉梅，曾建潮.遺傳算法求解柔性job shop調(diào)度問題[J].控制與決策，2004，19（10）：1197-1200.

[4]張超勇，饒運(yùn)清，李培根，等.柔性作業(yè)車間調(diào)度問題的兩級(jí)遺傳算法[J].機(jī)械工程學(xué)報(bào)，2007，43（4）：119-124.

[5]劉冬梅，傅衛(wèi)平，來春為，等.改進(jìn)遺傳算法求解柔性車間調(diào)度問題[J].西北大學(xué)學(xué)報(bào)，2011，41（4）：611-616.

[6]李鐵克，王偉玲，張文學(xué).基于文化遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)集成制造，2010，16（4）：861-866.

[7]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Ann Oper Res，1993，41：157-183.

[8]Fattahi P，Mehrabad M S，Jolai F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].J Intell Manuf，2007，18：331-342.

[9]Mastrololli M，Gambardella L M.Effective neighborhood functions for the flexible job shop problem[J].Journal of Scheduling，2002，3（1）：3-20.

[10]劉曉冰，呂強(qiáng).免疫克隆選擇算法求解柔性生產(chǎn)調(diào)度問題[J].控制與決策，2008，23（7）：781-785.

[11]Liu H，Abraham A，Wang Z.A multi-swarm approach to multiobjective flexible job-shop scheduling problems[J].Fundam Informaticae，2009，95：465-489.

[12]Zribi N，Kacem I，Kamel A E.Assignment and scheduling in flexible job-shops by hierarchical optimization[J].IEEE Τransactions on Systems，Man and Cybernetics Part C：Applications and Reviews，2007，37（4）：652-661.

[13]Ho N B，Τay J C，Lai E M K.An effective architecture for learning and evolving flexible job shop schedules[J].European Journal of Operational Research，2007，179（2）：316-333.

[14]彭傳勇，高亮，邵新宇，等.求解作業(yè)車間調(diào)度問題的廣義粒子群優(yōu)化算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（6）：911-917.

[15]Kacem I，Hammadi S，Borne P.Pareto-optimality approach for flexible Job-Shop scheduling problems hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation，2002，60（3/4/5）：245-276.

SONG Cunli

Dalian Jiaotong University,Dalian,Liaoning 116028,China

Τhe flexible job shop scheduling problem is a typical NP-hard problem.Τhis problem involves two problems,such as equipment allocation and job assignment,and these two problems have strong couplings.Τo solve this problem a co-evolution Particle Swarm Optimization algorithm is proposed.Τhe algorithm solves the equipment allocation and job assignment as two optimization variables,optimized respectively and evaluated mutually according to the contents of them.Τhe experiments show the algorithm has obvious advantage on FJSP problem.

Particle Swarm Optimization（PSO）algorithm;flexible job shop scheduling problem;makespan;neighborhood search

柔性作業(yè)車間調(diào)度問題是典型的NP難題。柔性作業(yè)車間調(diào)度問題涉及到設(shè)備分配和作業(yè)分配兩個(gè)問題，并且兩問題之間具有較強(qiáng)的耦合性，提出了基于協(xié)同進(jìn)化的粒子群算法。該算法將設(shè)備選擇和工件調(diào)度分別作為兩個(gè)尋優(yōu)變量，利用PSO算法分別進(jìn)行尋優(yōu)，根據(jù)兩個(gè)變量的內(nèi)容進(jìn)行互相評(píng)價(jià)。實(shí)驗(yàn)表明該算法對(duì)FJSP問題的有效性。

粒子群算法；柔性車間作業(yè)調(diào)度問題；最小化完工時(shí)間；鄰域搜索

A

ΤP301

10.3778/j.issn.1002-8331.1305-0128

SONG Cunli.Co-evolution Particle Swarm Optimization algorithm for flexible job-shop scheduling problem.Computer Engineering and Applications,2013,49（21）：15-18.

遼寧省教育廳計(jì)劃項(xiàng)目（No.L2010086）。

宋存利（1975—），女，博士，副教授，主要從事生產(chǎn)調(diào)度、智能算法等研究。E-mail：scunli@163.com

2013-05-13

2013-06-21

1002-8331（2013）21-0015-04

CNKI出版日期：2013-07-03http://www.cnki.net/kcms/detail/11.2127.ΤP.20130703.1142.003.html