基于改進(jìn)人工魚(yú)群算法的柔性作業(yè)車間調(diào)度

趙　敏　殷　歡　孫棣華　鄭林江　何　偉　袁　川

1.重慶大學(xué)，重慶，400030　　2.重慶信息安全測(cè)評(píng)中心，重慶，401147

?

基于改進(jìn)人工魚(yú)群算法的柔性作業(yè)車間調(diào)度

趙敏1殷歡1孫棣華1鄭林江1何偉1袁川2

1.重慶大學(xué)，重慶，4000302.重慶信息安全測(cè)評(píng)中心，重慶，401147

提出了一種基于改進(jìn)人工魚(yú)群算法的柔性作業(yè)車間調(diào)度問(wèn)題的求解方法。該方法針對(duì)基本人工魚(yú)群算法后期搜索盲目性大、精度不高的不足，在分析算法各個(gè)參數(shù)影響的基礎(chǔ)上，提出了步長(zhǎng)參數(shù)分解和采用柔性參數(shù)設(shè)置等改進(jìn)策略，并在算法后期融入局部遍歷搜索，提高了算法尋優(yōu)能力和尋優(yōu)精度。標(biāo)準(zhǔn)MK算例和對(duì)比試驗(yàn)表明了改進(jìn)人工魚(yú)群算法對(duì)求解柔性作業(yè)車間調(diào)度問(wèn)題的有效性。

柔性作業(yè)車間調(diào)度；人工魚(yú)群算法；柔性參數(shù)設(shè)置；參數(shù)細(xì)分

0　引言

柔性作業(yè)車間調(diào)度問(wèn)題(flexible job shop scheduling problem，F(xiàn)JSSP)是比作業(yè)車間調(diào)度問(wèn)題(job shop scheduling problem，JSSP)更加復(fù)雜的車間調(diào)度問(wèn)題。與JSSP相比，F(xiàn)JSSP考慮了同一個(gè)工藝可在不同機(jī)器上加工，且加工時(shí)間可能不同，增加了問(wèn)題的復(fù)雜性和求解的難度，更符合柔性制造的理念。隨著柔性制造理念被制造業(yè)廣泛接受，其理想化模型FJSSP的求解受到了研究者廣泛關(guān)注。

車間調(diào)度問(wèn)題的求解可分為數(shù)學(xué)規(guī)劃和啟發(fā)式調(diào)度方法兩大類。盡管數(shù)學(xué)規(guī)劃方法較為成熟，但由于其僅限于求解小規(guī)模調(diào)度問(wèn)題，對(duì)具有NP-hard特性的車間調(diào)度問(wèn)題已不適用。目前廣泛應(yīng)用的啟發(fā)式算法主要有余建軍等[1]提出的免疫模擬退火算法、Ho等[2]提出的LEGA(learnable genetic architecture)算法與Xu等[3]提出的IACO(improved ant colony optimization)算法，但上述算法的求解精度仍有待提高。

人工魚(yú)群算法[4]基于行為主義人工智能，模擬動(dòng)物行為尋找全局最優(yōu)。該算法具有克服局部最優(yōu)、尋找全局極值的能力[5-7]，收斂速度快、使用靈活，實(shí)現(xiàn)算法時(shí)無(wú)需目標(biāo)函數(shù)的梯度，對(duì)搜索解空間具有一定程度的自適應(yīng)性，但存在尋優(yōu)精度不高、前期收斂較快而后期搜索盲目性大[7]，或者在局部極值周圍嚴(yán)重聚集[8]，收斂速度大大降低的問(wèn)題。

本文針對(duì)FJSSP解空間巨大及現(xiàn)有求解方法在尋優(yōu)精度上的不足，利用人工魚(yú)群算法收斂速度快、使用靈活等優(yōu)點(diǎn)，采取改進(jìn)措施提高算法尋優(yōu)能力，建立了一種改進(jìn)的FJSSP求解方法，并采用Brandimarte標(biāo)準(zhǔn)問(wèn)題檢驗(yàn)了算法的有效性。

1　FJSSP模型

FJSSP描述的是在具有m臺(tái)加工設(shè)備的生產(chǎn)系統(tǒng)中加工n個(gè)工件，每個(gè)工件需要按次序完成一個(gè)或多個(gè)工藝，每個(gè)工藝有至少一臺(tái)加工設(shè)備可供選擇。

FJSSP模型包含以下約束條件[9-10]：

(1)各個(gè)加工設(shè)備彼此獨(dú)立，任一加工設(shè)備是否工作、是否故障不影響其他加工設(shè)備，且所有加工設(shè)備在開(kāi)始時(shí)刻(t=0)均可開(kāi)始工作。

(2)所有工件彼此獨(dú)立，任一工件的加工狀況不對(duì)其他工件產(chǎn)生影響，所有工件在開(kāi)始時(shí)刻均可開(kāi)始加工。

(3)所有工件的工藝流程在加工開(kāi)始之前已定，加工過(guò)程中不能改變?nèi)魏我粋€(gè)工件的既定工藝流程。

(4)所有工藝可供選擇的加工設(shè)備以及在相應(yīng)設(shè)備上的加工時(shí)間在加工開(kāi)始之前已定，加工過(guò)程中不能改變。

(5)每臺(tái)加工設(shè)備一次只能完成某個(gè)工件的某一道工藝，一個(gè)工件的一道工藝不能在多臺(tái)加工設(shè)備上同時(shí)完成，一道工藝一旦在某臺(tái)加工設(shè)備上開(kāi)始加工就不會(huì)中斷，直到該工藝加工完成。

(6)不考慮臨時(shí)訂單、設(shè)備故障等任何可能中斷加工過(guò)程的突發(fā)事件。

本文研究以最小化最大完工時(shí)間為調(diào)度目標(biāo)的FJSSP。只考慮工件在加工設(shè)備上的加工時(shí)間，不考慮加工設(shè)備的調(diào)整時(shí)間以及工件在各個(gè)加工設(shè)備之間的運(yùn)輸時(shí)間。因此，某個(gè)工件的完工時(shí)間等于該工件的各個(gè)工藝在相應(yīng)加工設(shè)備上的加工時(shí)間與由于某臺(tái)加工設(shè)備正在加工其他工件而造成的等待時(shí)間之和。

綜上所述，F(xiàn)JSSP數(shù)學(xué)描述如下，W={W1，W2，…，Wn}為需要加工的n個(gè)工件的集合；M={M1，M2，…，Mm}為m臺(tái)加工設(shè)備的集合；Oi={Oi1，Oi2，…，Oini}表示工件Wi依次經(jīng)過(guò)的ni道工序集合；Mij={Mij1，Mij2，…，Mijkij}表示可以加工工藝Oij的加工設(shè)備集合，其中，kij為可以加工工藝Oij的機(jī)器數(shù)量，Mij?M。在此基礎(chǔ)上建立的最小化最大完工時(shí)間調(diào)度目標(biāo)函數(shù)為

minEmax

(1)

s.t.

Si(j+1)≥Eij

(2)

i=1,2,…,n;j=1,2,…,ni-1

Sijk≥Emnk

(3)

Oij在Omn之后加工

Sijk=max(Ei(j-1)p,Emnk)

(4)

Mi(j-1)=p；Mij=Mmn=k;Oij在Omn之后加工

Emax≥Einii=1,2,…,n

(5)式中，Emax為最大完工時(shí)間，即所有工件的完工時(shí)間；Oij表示工件i的第j個(gè)工序；Si(j+1)為第i個(gè)工件的第j個(gè)工序的開(kāi)始時(shí)間；p為機(jī)器序號(hào)；Eij為第i個(gè)工件的第j個(gè)工序的完成時(shí)間；Mijk表示第i個(gè)工件的第j個(gè)工序選擇在第k臺(tái)機(jī)器加工；Tijk為工序Oij在設(shè)備Mijk上的加工時(shí)間；Sijk為工序Oij在設(shè)備Mijk上的加工開(kāi)始時(shí)間；Eijk為工序Oij在設(shè)備Mijk上的加工結(jié)束時(shí)間，Eijk=Sijk+Tijk。

式(1)說(shuō)明調(diào)度目標(biāo)為最小化最大完工時(shí)間；式(2)表示工藝有先后約束，工件下一個(gè)工藝的加工需要上一個(gè)工藝完成之后；式(3)表示同一臺(tái)加工設(shè)備同一時(shí)刻只能加工一個(gè)工件，下一個(gè)工件需要等上一個(gè)工藝加工完成；式(4)表示工件在設(shè)備上開(kāi)始加工的時(shí)間取決于工件在上一臺(tái)設(shè)備加工完成的時(shí)間以及設(shè)備加工完上一個(gè)工件的時(shí)間，這兩者中的最大值。

2　求解FJSSP

FJSSP求解目標(biāo)：一是確定工件Mi的工藝Oij的加工設(shè)備Mijk；二是確定在各個(gè)加工設(shè)備上加工的工藝序列，進(jìn)而確定各個(gè)機(jī)器上加工的各個(gè)工藝的起止時(shí)間?；诟倪M(jìn)人工魚(yú)群算法求解FJSSP，關(guān)鍵在于人工魚(yú)群算法的編碼解碼方式，視距、步長(zhǎng)等參數(shù)的設(shè)置和隨機(jī)行為、覓食行為等的實(shí)現(xiàn)，并針對(duì)傳統(tǒng)人工魚(yú)群算法求解FJSSP中的不足予以改進(jìn)。

2.1基于改進(jìn)人工魚(yú)群算法求解FJSSP

2.1.1編碼解碼策略

針對(duì)FJSSP需要解決的兩個(gè)問(wèn)題，本文采用雙子串編碼方式。設(shè)各個(gè)工件的工藝總數(shù)為t，并從0到t-1按順序編號(hào)；機(jī)器總數(shù)為m，并從0到m-1按順序編號(hào)；工件總數(shù)為n，并從0到n-1按順序編號(hào)。雙子串的兩個(gè)子串A、B都是長(zhǎng)度為t的數(shù)組，A[a1]，A[a2]，…，A[at]為0到t-1號(hào)工藝選擇的加工設(shè)備編號(hào)；B[b1]，B[b2]，…，B[bt]表示n個(gè)工件的優(yōu)先權(quán)排序(序號(hào)為t個(gè)范圍在[0，n-1]的自然數(shù))，排列靠前的工件優(yōu)先占有加工資源。Iijk為工件i的第j個(gè)工藝在第k號(hào)加工臺(tái)上的加工時(shí)間，i為0～n-1的自然數(shù)，j為0～s-1的自然數(shù)，s為需要經(jīng)過(guò)工藝數(shù)量最多的工件具有的工藝數(shù)，k為0～m-1之間的自然數(shù)。當(dāng)工件i的第j個(gè)工藝不在第k號(hào)加工臺(tái)上加工時(shí)，Iijk=-1；數(shù)組L表示各個(gè)工件需要經(jīng)過(guò)的工藝數(shù)量，L[i]表示工件i的工藝數(shù)量，i=0，1，…，n-1。

(1)子串A編碼算法。

步驟1令a=0，i=0；

步驟2若i=n，則轉(zhuǎn)步驟5，否則令j=0，轉(zhuǎn)步驟3；

步驟3若j=s，則i←i+1并轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟4；

步驟4如果工件i存在第j號(hào)工藝，則隨機(jī)生成0～m-1之間的自然數(shù)k，直到Iijk的值不為-1； A[a]=k，即子串A的第a個(gè)數(shù)賦值為k，表示這組工件的第a個(gè)工藝選擇第k號(hào)加工臺(tái)加工；a←a+1，j←j+1，轉(zhuǎn)步驟3；

步驟5結(jié)束子串A編碼。

(2)子串B的編碼算法。

步驟1令 j=0；

步驟2若j=t，則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟3；

步驟3隨機(jī)生成0到n-1的自然數(shù)k，直到L[k]不為0；B[j]=k，L[k]← L[k]-1，j←j+1，轉(zhuǎn)步驟2；

步驟4結(jié)束子串B編碼。

其中，B[j]為子串B的第j個(gè)分量。解碼即根據(jù)雙子串編碼，求出每個(gè)加工機(jī)器上加工的工件的起止時(shí)間。設(shè)H[i]表示工件i已經(jīng)排序的工序數(shù)，解碼開(kāi)始時(shí)，H[i]=0；U[i]表示工件i的第一個(gè)工藝在子串A中的開(kāi)始位置。則解碼算法可描述為：對(duì)于編號(hào)x從0～t-1的t個(gè)工序，將工件B[x]以最早容許加工的加工時(shí)間在機(jī)器A[U[B[x]]+H[B[x]]]上加工，最早容許的加工時(shí)間是從工件B[x]上一次操作結(jié)束時(shí)間開(kāi)始，依次比較機(jī)器A[U[B[x]]+H[B[x]]]的加工空隙是否可以插入該工件，如果可以則插入該工件，否則，將此工件排列在尾端。

2.1.2人工魚(yú)行為的實(shí)現(xiàn)和參數(shù)設(shè)置

魚(yú)群的隨機(jī)行為實(shí)現(xiàn)，就是對(duì)于子串A，隨機(jī)生成0～t-1的之間自然數(shù)u來(lái)決定改變編碼的哪一位，對(duì)于第u位(從0開(kāi)始計(jì)數(shù))，重新隨機(jī)選取可以加工機(jī)器；對(duì)于子串B隨機(jī)選取2個(gè)位置p、k，若2個(gè)位置的工件號(hào)不同，則調(diào)換2個(gè)位置上的工件號(hào)。魚(yú)群的覓食行為具體實(shí)現(xiàn)方法為，隨機(jī)選取視距內(nèi)的人工魚(yú)，如果被選取的魚(yú)的位置優(yōu)于當(dāng)前魚(yú)的位置則往其方向前進(jìn)一步，否則再隨機(jī)選取視距內(nèi)人工魚(yú)(已經(jīng)嘗試過(guò)的魚(yú)除外)，直到超過(guò)規(guī)定的嘗試次數(shù)，或所有魚(yú)都嘗試過(guò)，仍然沒(méi)有找到更優(yōu)的人工魚(yú)，則隨機(jī)移動(dòng)一步。向某條魚(yú)前進(jìn)一步指的是，從兩條魚(yú)編碼中不相同的位里隨機(jī)選取數(shù)量等于步長(zhǎng)的位，將當(dāng)前魚(yú)的這些位修改與目標(biāo)魚(yú)相同。聚群行為具體的實(shí)現(xiàn)方法如下：如果視距內(nèi)中心位置的食物濃度優(yōu)于當(dāng)前魚(yú)處食物濃度且中心位置不擁擠，則向中心位置前進(jìn)一步，否則執(zhí)行覓食行為。

人工魚(yú)中食物濃度為所有工件完工時(shí)間。人工魚(yú)A1B1與人工魚(yú)A2B2的間距定義為

(6)

式中，A(i)、B(i)分別為工設(shè)備序列和加工優(yōu)先級(jí)序列字串的第i個(gè)分量.

魚(yú)群的移動(dòng)策略為先執(zhí)行覓食行為，再執(zhí)行聚群行為，最后執(zhí)行追尾行為。在魚(yú)群移動(dòng)過(guò)程中，用公告板來(lái)保存算法迭代過(guò)程中找到的最優(yōu)解，即每次執(zhí)行完一個(gè)行為，就與公告板上的最優(yōu)魚(yú)比較，如果優(yōu)于最優(yōu)魚(yú)，則代替公告板上的最優(yōu)魚(yú)。

人工魚(yú)群算法對(duì)初始參數(shù)設(shè)置不是很敏感，參數(shù)可選擇范圍較廣。總體來(lái)說(shuō)，步長(zhǎng)較大有利于加快收斂，但過(guò)大可能導(dǎo)致震蕩無(wú)法收斂；步長(zhǎng)小就會(huì)降低收斂速度，但有利于提高尋優(yōu)精度。視距較大，算法全局搜索能力較強(qiáng)，但超過(guò)一定值后對(duì)算法性能改進(jìn)沒(méi)有明顯效果；視距過(guò)小，人工魚(yú)找不到更優(yōu)位置，始終執(zhí)行隨機(jī)行為，算法不能收斂。較大的擁擠度因子不容許局部聚集過(guò)多的魚(yú)，迫使魚(yú)群搜索更廣的解空間；擁擠度因子較小有利于魚(yú)群收斂，但也易陷入局部最優(yōu)。種群規(guī)模越大，算法尋優(yōu)能力越強(qiáng)，找到最優(yōu)解的概率越大，種群規(guī)模超過(guò)一定限度后，對(duì)提高尋優(yōu)能力作用不明顯。迭代越多，算法尋優(yōu)能力越強(qiáng)，但算法運(yùn)行時(shí)間同樣正比于迭代次數(shù)，且迭代次數(shù)超過(guò)一定限度后對(duì)尋優(yōu)能力的提高不再起作用。本文根據(jù)大量實(shí)驗(yàn)總結(jié)了求解FJSSP時(shí)基本人工魚(yú)群算法的經(jīng)驗(yàn)參數(shù)設(shè)置方法：步長(zhǎng)為編碼長(zhǎng)度(其中一個(gè)子串的長(zhǎng)度)的1/60～1/30，視距在編碼長(zhǎng)度的1～2倍之間，擁擠度因子設(shè)為0. 05～0. 1之間的數(shù)值，嘗試次數(shù)在種群規(guī)模的1/2左右，種群規(guī)模設(shè)置30～50之間較為合適，迭代次數(shù)約為1500。

2.1.3魚(yú)群算法的改進(jìn)

人工魚(yú)的隨機(jī)行為保證了魚(yú)群跳出局部、探索更多解空間的可能性，但過(guò)強(qiáng)的隨機(jī)行為不利于算法收斂，導(dǎo)致搜索精度降低；反之，有利于算法收斂和局部搜索，但易陷入局部最優(yōu)，降低全局搜索能力。隨機(jī)行為的強(qiáng)弱與隨機(jī)移動(dòng)的步長(zhǎng)、隨機(jī)移動(dòng)執(zhí)行的次數(shù)有關(guān)，隨機(jī)移動(dòng)次數(shù)多且隨機(jī)移動(dòng)步長(zhǎng)大，魚(yú)群表現(xiàn)出強(qiáng)隨機(jī)行為。向目標(biāo)前進(jìn)一步與隨機(jī)移動(dòng)行為的作用相反，前進(jìn)步長(zhǎng)大有利于快速向最優(yōu)魚(yú)聚攏，增強(qiáng)收斂性，弱化隨機(jī)行為；較小的前進(jìn)步長(zhǎng)讓聚攏速度較慢，避免早熟收斂，陷入局部最優(yōu)。因此，本文將隨機(jī)移動(dòng)步長(zhǎng)和向目標(biāo)前進(jìn)步長(zhǎng)分為兩個(gè)參數(shù)，細(xì)化控制算法執(zhí)行過(guò)程。

擁擠度用來(lái)判斷某一領(lǐng)域內(nèi)的魚(yú)群是否擁擠，較大的擁擠度迫使過(guò)多的魚(yú)群離開(kāi)局部聚集區(qū)域，盡可能分散，增大搜索廣度而不利于魚(yú)群收斂；反之，對(duì)魚(yú)群的聚攏容忍度高，有助于算法收斂。同時(shí)，局部聚集的較大魚(yú)群有利于增強(qiáng)局部搜索能力，但有可能引發(fā)早熟收斂，陷入局部最優(yōu)。

本文采用柔性參數(shù)設(shè)置，前期設(shè)置較大的擁擠度和隨機(jī)步長(zhǎng)、較小的前進(jìn)步長(zhǎng)，增強(qiáng)隨機(jī)行為，使魚(yú)群分散而活躍，搜索全局解空間；后期減小擁擠度和隨機(jī)步長(zhǎng)，增大前進(jìn)步長(zhǎng)，弱化隨機(jī)行為，容許魚(yú)群聚集，增強(qiáng)算法收斂性和局部尋優(yōu)能力。另外，如果還不滿足要求，覓食、聚群、追尾都會(huì)執(zhí)行隨機(jī)行為。為弱化算法隨機(jī)性，算法后期減小隨機(jī)移動(dòng)次數(shù)。

柔性參數(shù)設(shè)置的具體方案是，將隨機(jī)移動(dòng)步長(zhǎng)、前進(jìn)步長(zhǎng)、擁擠度按照由大到小的順序設(shè)置為5個(gè)等級(jí)，算法執(zhí)行過(guò)程按照迭代次數(shù)的多少均分為5個(gè)階段，每過(guò)一個(gè)階段相應(yīng)地改變參數(shù)等級(jí)。

另外，針對(duì)算法尋優(yōu)精度不高的問(wèn)題，本文將人工魚(yú)群算法與局部遍歷搜索算法結(jié)合。局部遍歷搜索算法的策略：改變子串A的一位；對(duì)調(diào)子串B的某兩個(gè)值不同的位，即對(duì)調(diào)兩個(gè)工件的加工優(yōu)先順序。遍歷即是嘗試上述局部算法策略，直到新的編碼比之前更優(yōu)或嘗試完所有可能的局部搜索。必須指出的是，局部遍歷搜索算法將導(dǎo)致算法執(zhí)行時(shí)間的劇增，因此，本文僅將局部遍歷搜索算法應(yīng)用到算法執(zhí)行即將結(jié)束(迭代次數(shù)可以人為指定)的階段。

2.2調(diào)度算法流程

基于前述對(duì)人工魚(yú)群算法的改進(jìn)，以最小化最大完成時(shí)間為調(diào)度目標(biāo)，求解FJSSP的改進(jìn)人工魚(yú)群算法流程如圖1所示。

圖1　改進(jìn)人工魚(yú)群算法流程圖

求解FJSSP的改進(jìn)人工魚(yú)群算法的具體步驟如下：

(1)初始化人工魚(yú)群，按照2.1節(jié)的編碼策略，隨機(jī)初始化40條人工魚(yú)。

(2)從魚(yú)群中選取最優(yōu)魚(yú)，即解碼得到完工時(shí)間最小的魚(yú)，存入公告板。

(3)執(zhí)行覓食、聚群、追尾行為，若是最后10次迭代則執(zhí)行局部搜索。

(4)將當(dāng)前迭代次數(shù)加1，判斷當(dāng)前的參數(shù)等級(jí)與迭代階段是否匹配，不匹配則更新參數(shù)。

(5)判斷是否達(dá)到算法終止條件，達(dá)到則結(jié)束算法并輸出執(zhí)行結(jié)果，否則轉(zhuǎn)到第步驟(2)繼續(xù)。

3　試驗(yàn)驗(yàn)證

為驗(yàn)證算法性能，以FJSSP常用的Brandimarte問(wèn)題作為算例，將改進(jìn)后的人工魚(yú)群算法與基本人工魚(yú)群算法以及國(guó)外其他柔性作業(yè)車間調(diào)度算法，如Nhu等[2]提出的學(xué)習(xí)進(jìn)化型遺傳算法、Xu等[3]提出的增強(qiáng)蟻群算法比較。

柔性參數(shù)設(shè)置將參數(shù)分為5個(gè)漸進(jìn)的等級(jí)，隨著迭代次數(shù)的不同選取不同參數(shù)設(shè)置，參數(shù)設(shè)置與迭代次數(shù)之間的關(guān)系見(jiàn)表1。

表1　改進(jìn)人工魚(yú)群算法柔性參數(shù)設(shè)置

表2給出了改進(jìn)人工魚(yú)群算法(IAFSA)、基本人工魚(yú)群算法(AFSA)、Brandimarte算法、LEGA算法、IACO算法尋找到的最優(yōu)解，表中的相對(duì)改進(jìn)表示IAFSA求得的最優(yōu)解相對(duì)于其他算法提高了多少時(shí)間單位。從表2可以看出，IAFSA尋找到的最優(yōu)解相對(duì)于AFSA、Brandimarte算法、LEGA分別平均提高了3.44、19.67、2.75個(gè)時(shí)間單位，有顯著的提高；與IACO相比，MK01、MK05、MK10最優(yōu)解稍差，但MK02和MK04的最優(yōu)解有較大幅度提高，平均來(lái)看有小幅度提高?？梢?jiàn)，本文提出的改進(jìn)人工魚(yú)群算法能夠有效求解柔性作業(yè)車間調(diào)度問(wèn)題。

表2　各種算法的最優(yōu)值比較

表3～表5對(duì)比了幾種算法的平均值、方差和平均執(zhí)行時(shí)間，LEGA算法的平均值、方差和平均執(zhí)行時(shí)間數(shù)據(jù)來(lái)源于文獻(xiàn)[2]，另外兩種算法的相關(guān)數(shù)據(jù)統(tǒng)計(jì)方法是每種算法連續(xù)執(zhí)行20次，計(jì)算20次解的平均值、方差和算法平均執(zhí)行時(shí)間，文獻(xiàn)[3，11-13]未提供平均值、方差和執(zhí)行時(shí)間數(shù)據(jù)。從表3、表4可以看出，與AFSA和LEGA算法相比，IAFSA的平均值有一定幅度的提高，分別平均提高3.54時(shí)間單位和2.63時(shí)間單位，但方差較大。這表明，改進(jìn)后的算法尋找最優(yōu)解的能力及解的平均值都有提高，但算法穩(wěn)定性略有下降。原因可能是算法在執(zhí)行的后半段追求提高搜索精度，增強(qiáng)局部搜索能力，導(dǎo)致算法在一定程度上承擔(dān)了更高的陷入局部最優(yōu)的風(fēng)險(xiǎn)。文獻(xiàn)[2]使用的電腦CPU是2 GHz主頻Pentium IV，本文使用的電腦CPU是2 GHz主頻Intel P7350，兩者主頻相同，試驗(yàn)統(tǒng)計(jì)的執(zhí)行時(shí)間具有可比性。表5說(shuō)明三種算法執(zhí)行時(shí)間相差不大，但由于加入局部搜索，IAFSA執(zhí)行時(shí)間略長(zhǎng)。

表3　各種算法平均值對(duì)比

表4　各種算法方差對(duì)比

表5　各種算法平均執(zhí)行時(shí)間對(duì)比　s

圖2是求解MK04問(wèn)題時(shí)，IAFSA和AFSA的迭代曲線圖，圖中曲線均為兩種算法執(zhí)行效果最好的一次，IAFSA求得最優(yōu)解60，AFSA求得最優(yōu)解66。圖2中，橫坐表示是迭代次數(shù)，縱坐標(biāo)表示完工時(shí)間Emax?？梢钥闯?，兩種算法執(zhí)行初期類似，算法的平均值和最優(yōu)值均快速收斂，且平均值與最優(yōu)值有一定距離——反映了魚(yú)群分布較為廣泛；迭代400次時(shí)，兩種算法找到的最優(yōu)值相近，但I(xiàn)AFSA的魚(yú)群已經(jīng)收斂；400次迭代之后，AFSA尋找最優(yōu)解的效率明顯降低，且魚(yú)群一直分布廣泛，不能收斂，因此，AFSA后半段表現(xiàn)出漫無(wú)目的全局搜索。IAFSA在后半段受到柔性參數(shù)設(shè)置的影響，魚(yú)群逐步收斂到局部區(qū)域，增強(qiáng)了搜索精度，后半段最優(yōu)解仍有較大程度的提高。

1.改進(jìn)人工魚(yú)群算法的公告板值　　2.改進(jìn)人工魚(yú)群算法的均值　3.基本人工魚(yú)群算法的公告板值　　4.基本人工魚(yú)群算法的均值圖2　算法改進(jìn)前后迭代曲線圖

本文算法求解MK02和MK04問(wèn)題時(shí)，所得最優(yōu)解較其他算法有較大幅度提高，圖3、圖4給出了MK02、MK04最優(yōu)解的甘特圖。橫坐標(biāo)表示完工時(shí)間，縱坐標(biāo)表示加工機(jī)器編號(hào)，圖中不同灰度的色塊代表色塊旁邊號(hào)數(shù)的工件在某一個(gè)加工機(jī)器上的加工時(shí)間段。

圖3　MK02最優(yōu)解甘特圖

圖4　MK04最優(yōu)解甘特圖

4　結(jié)語(yǔ)

FJSSP解空間巨大，人工魚(yú)群算法求解該問(wèn)題時(shí)可快速找到全局極值的領(lǐng)域，但存在尋優(yōu)精度不高、后期搜索盲目性大等缺點(diǎn)。本文提出的改進(jìn)人工魚(yú)群算法，將步長(zhǎng)分解為隨機(jī)移動(dòng)步長(zhǎng)和向目標(biāo)前進(jìn)步長(zhǎng)，并采用柔性參數(shù)設(shè)置策略，并在算法后期融入局部遍歷搜索。改進(jìn)的人工魚(yú)群算法在前期具有較強(qiáng)的全局搜索能力，避免早熟收斂，陷入局部最優(yōu)；在后期增強(qiáng)了算法局部搜索能力，提高了算法尋優(yōu)精度。與其他算法相比，算法的尋優(yōu)能力有較大幅度的提升，在算法的穩(wěn)定性稍有下降的情況下，算法的整體性能(解的平均值)仍然有不小的提高。穩(wěn)定性下降可能是因?yàn)榫植克阉髂芰Φ脑鰪?qiáng)導(dǎo)致算法在后半段易陷入某個(gè)次優(yōu)極值。因此，如何在提高算法求解精度的同時(shí)避免陷入局部，保證算法的全局性，兼顧尋優(yōu)能力和穩(wěn)定性，將是本文后續(xù)的研究方向。

[1]余建軍，徐學(xué)軍.基于免疫和模擬退火原理的柔性Job-Shop調(diào)度研究[J].計(jì)算機(jī)應(yīng)用研究,2010, 11(27)：4094-4097.

Yu Jianjun, Xu Xuejun, Flexible Job-Shop Scheduling Based on Immune and Simulated Annealing [J]. Application Research of Computers, 2010,11(27)：4094-4097

[2]Ho N B，Tay 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.

[3]Xu Dongsheng，Ai Xiaoyan，Xing Lining.An Improved Ant Colony Optimization for Flexible Job Shop Scheduling Problems[C]//International Joint Conference on Computational Science and Optimation.Sanya，Hainan：IEEE，2009：517-519.

[4]李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐，2002，22(11)：32-38.

Li Xiaolei, Shao Zhijiang, Qian Jixin. An Optimizing Method Based on Autonomous Animals: Fish-swarm Algorithm[J]. Systems Engineering-Theory & Practice，2002，22(11)：32-38.

[5]任彥君，黎冰，顧幸生.改進(jìn)的人工魚(yú)群算法在置換Flow Shop 調(diào)度中的應(yīng)用[J].華東理工大學(xué)學(xué)報(bào)，2010，36(1)：93-98.

Ren Yanjun，Li Bing，Gu Xingsheng. Application of Improved Artificial Fish Swarm Algorithm to Permutation Flow Shop Scheduling Problem[J]. Journal of East China University of Science and Technology，2010，36(1)：93-98.

[6]袁坤，朱劍英.一種求解多目標(biāo)柔性Job Shop調(diào)度的改進(jìn)遺傳算法[J].中國(guó)機(jī)械工程，2007，18(2)：156-160.

Yuan Kun, Zhu Jianying. Improved Genetic Algorithm for the Flexible Job-shop Scheduling with Multi-object[J]. China Mechanical Engineering，2007，18(2)：156-160.

[7]王聯(lián)國(guó)，洪毅，余冬梅，等.一種改進(jìn)的人工魚(yú)群算法[J].計(jì)算機(jī)工程，2008，34(19)：192-194.

Wang Lianguo, Hong Yi, Yu Dongmei. Improved Artificial Fish Swarm Algorithm [J]. Computer Engineering，2008，34(19)：192-194.

[8]劉白，周永權(quán).基于遺傳算法的人工魚(yú)群優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(22)：5827-5829.

Liu Bai，Zhou Yongquan. Artificial Fish Swarm Optimization Algorithm Based on Genetic Algorithm[J]. Computer Engineering and Design，2008，29(22)：5827-5829.

[9]劉明周，張明偉，蔣增強(qiáng)，等.基于混合粒子群算法的多目標(biāo)柔性Job-Shop 調(diào)度方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2008，39(5)：122-127.

Liu Mingzhou，Zhang Mingwei，Jiang Zengqiang，et al. Multi-objective and Flexible Job-shop Problems Study Based on Hybrid Particle Swarm Optimization[J]. Transactions of the Chinese Society for Agriculture Machinery，2008，39(5)：122-127.

[10]李崢?lè)?多時(shí)間因素作業(yè)車間調(diào)度問(wèn)題的研究與工程應(yīng)用[D].武漢：華中科技大學(xué)，2010.

[11]Brandimarte P.Routing and Scheduling in a Flexible Jobshop by Tabu Search[J].Annals of Operations Research，1993，41(3)：157-183.

[12]張梅鳳，邵誠(chéng).多峰函數(shù)優(yōu)化的生境人工魚(yú)群算法[J].控制理論與應(yīng)用，2008，25(4)：773-776.

Zhang Meifeng，Shao Cheng. Niche Artificial Fish Swarm Algorithm for Multimodal Function Optimization[J]. Control Theory & Applications，2008，25(4)：773-776.

[13]李曉磊，薛云燦，路飛，等.基于人工魚(yú)群算法的參數(shù)估計(jì)方法[J]. 山東大學(xué)學(xué)報(bào)，2004，34(3)：84-87.

Li Xiaolei，Xue Yuncan，Lu Fei，et al. Parameter Estimation Method Based-onartificial Fish School Algorithm[J]. Journal of Shandong University，2004，34(3)：84-87.

(編輯張洋)

Flexible Job Shop Scheduling Based on Modified Artificial Fish Swarm Algorithm

Zhao Min1Yin Huan1Sun Dihua1Zheng Linjiang1He Wei1Yuan Chuan2

1.Chongqing University，Chongqing，400030 2. Chongqing Information Technology Security Evaluation Center, Chongqing，401147

An improved algorithm for solving flexible job shop scheduling was proposed based on the artificial fish swarm algorithm. In view of the blindness and low precision of the basic artificial fish swarm algorithm in its late stage search, the new algorithm presented some strategies like separating the step into the random moving step and target moving step, adopting flexible parameter setting, and infusing local traversal search in the late period of the algorithm based on the analyses of parameter influences of the algorithm, which enhanced the search ability and search precision of the modified algorithm. Finally, the effectiveness of the improved artificial fish swarm algorithm in solving flexible job shop scheduling problem was verified by the standard MK sample and comparison experiments.

flexible job shop scheduling；artificial fish swarm algorithm；flexible parameter setting；parameter subdivision

趙敏，女，1980年生。重慶大學(xué)自動(dòng)化學(xué)院副教授。主要研究方向?yàn)橹悄芸刂婆c智能自動(dòng)化化。發(fā)表論文10余篇。殷歡，男，1988年生。重慶大學(xué)自動(dòng)化學(xué)院碩士研究生。孫棣華，男，1962年生。重慶大學(xué)自動(dòng)化學(xué)院教授、博士研究生導(dǎo)師。鄭林江，男，1983年生。重慶大學(xué)計(jì)算機(jī)學(xué)院副教授。何偉，男，1975年生。重慶大學(xué)自動(dòng)化學(xué)院博士研究生。袁川，男，1981年生。重慶信息安全測(cè)評(píng)中心工程師。

2015-08-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(61203135);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(106112014CDJZR178801)；重慶市自然科學(xué)基金資助項(xiàng)目(CSCT2012JJA40020)；

TP18

10.3969/j.issn.1004-132X.2016.08.012