尹瑞雪，馮旭青，吳 拓，李付春，王 澤

(貴州大學(xué)機(jī)械工程學(xué)院，貴陽 550025)

0 引言

零空閑流水車間調(diào)度問題(NIFS)具有很強(qiáng)的工業(yè)背景，廣泛見于集成電路、紡織、玻璃和陶器等產(chǎn)品的生產(chǎn)制造過程中。基于成本及加工工藝要求的考慮，要求每臺機(jī)器一旦開始加工某個工件，則需要不間斷的把所有工作都加工完成，不允許機(jī)器操作之間有空閑時間，即機(jī)器不能空轉(zhuǎn)。

實現(xiàn)零空閑車間調(diào)度將有效節(jié)約機(jī)床閑置能耗，是實現(xiàn)機(jī)加工行業(yè)節(jié)能減排的有效途徑之一。因此，針對該問題，國內(nèi)外學(xué)者展開了一系列研究。BAPTISTE等[1]證明了F/no-idle/Cmax是一個NP難問題。武磊等[2]求解以總流經(jīng)時間和最大完工時間為目標(biāo)的零空閑流水線調(diào)度問題，改進(jìn)了和聲搜索算法的求解模型。王亞敏等[3]以E/T指標(biāo)最優(yōu)為優(yōu)化測度，提出了一種蛙跳求解算法。潘全科等[4]基于PSO算法，提出了離散粒子群算法求解NIFS問題。李麗娟等[5]則改進(jìn)了標(biāo)準(zhǔn)覓食算法，引入交叉優(yōu)化算子、混合復(fù)制策略及自適應(yīng)遷徙概率求解問題。研究表明，采用更有效更穩(wěn)定的優(yōu)化算法是獲得最優(yōu)解的重要前提。

針對該優(yōu)化問題，本文擬采用果蠅優(yōu)化算法(fruit fly optimization algorithm，F(xiàn)OA)[6]，該算法是一種新的基于果蠅覓食行為尋找全局最優(yōu)解的新方法。該算法操作簡單，易于實現(xiàn)，具有較好的局部搜索能力[7]。已有的研究中，僅有少數(shù)學(xué)者采用該算法解決此類優(yōu)化問題。杜利珍等[8]針對不相關(guān)并行機(jī)混合流水車間調(diào)度問題，利用權(quán)重系數(shù)來提高算法的隨機(jī)搜索能力。高兵新[9]將果蠅算法應(yīng)用于煉鋼-連鑄生產(chǎn)中，并設(shè)計動態(tài)搜索半徑求解NIFS問題。以上這些已有的少量研究大多采用的是傳統(tǒng)果蠅算法，其具有局部最優(yōu)的局限性，且尋優(yōu)后期可能存在收斂速度慢、尋優(yōu)精度低的問題。因此，本文提出了一種改進(jìn)的果蠅算法用于解決該優(yōu)化問題，該算法針對種群初始化、嗅覺搜索方式、視覺覓食階段飛行方式等方面均進(jìn)行了改進(jìn)，不僅設(shè)置了多個種群中心，并在嗅覺搜索階段加入破壞重建，多重獨立交換、插入領(lǐng)域搜索及隨機(jī)權(quán)重系數(shù)變換；在視覺覓食階段引入免疫算法激勵度對傳統(tǒng)果蠅算法做出了改進(jìn)，使搜索能力達(dá)到進(jìn)一步增強(qiáng)；最后，通過案例驗證，證明該算法能有效提高全局尋優(yōu)效果，其穩(wěn)定性也有所改善。

1 問題描述與數(shù)學(xué)建模

零空閑車間調(diào)度，即每臺機(jī)器上的兩個連續(xù)操作之間不允許有空閑時間，工件加工一旦開始，不允許中斷。為了滿足零空閑約束即每臺機(jī)器一旦開啟，就必須連續(xù)切削直至把所有工件加工完畢。NIFS問題可描述如下：有n個工件的集合N={1,2,…,n}，m臺機(jī)器的集合為M={M1,M2,…,Mm}。工件在零時刻都可用，且必須按照相同的工藝路線次依次經(jīng)過機(jī)器M1、M2直到機(jī)床Mm。pij為工件i(i=1,2,…,n)在機(jī)器Mj(j=1,2,…,m)上的加工時間(s)。每個工件在任意時刻最多只能被一臺機(jī)器加工，且每臺機(jī)床最多只能加工一個工件。其調(diào)度目標(biāo)就是通過安排工件的生產(chǎn)次序，以達(dá)到最大完工時間最小化。

在建立該調(diào)度問題數(shù)學(xué)模型的過程中，一個工件的加工排列可用π=(π(1),π(2),…,π(n))表示，即工件按π(1)到π(n)的順序依次加工；相鄰的機(jī)器j和j+1之間存在的開工時間差記為Ej,j+1(π)，pπ(i),j表示工件在π(i)位置上的加工時間，具體計算方法如式(1)所示；加工排列π對應(yīng)的最大完工時間(s)記為Cmax(π)，故某個具有加工排列π的工件的最大完工時間可用式(2)進(jìn)行計算。

(1)

(2)

用A表示具有不同工件生產(chǎn)次序的調(diào)度方案的集合，則NIFS問題的目標(biāo)是在集合A中找到一個最優(yōu)的調(diào)度方案A*，使A*得的總完工時間在集合A中最小，即調(diào)度A*的最大完工時間小于其它具有不同工件生產(chǎn)次序的調(diào)度方案的最大完工時間，如式(3)所示。

Cmax(A*)≤Cmax(A) ?A*∈A

(3)

式中，Cmax(A*)和Cmax(A)分別為調(diào)度方案A*與集合A對應(yīng)的完工時間。

2 問題求解

本文擬采用改進(jìn)果蠅算法進(jìn)行求解。傳統(tǒng)果蠅算法獨特的嗅覺與視覺搜索特性使其原理易懂、易于實現(xiàn)，并且具有較強(qiáng)的局部搜索能力，但其全局搜索能力相對較弱，容易陷入局部最優(yōu)，進(jìn)而早熟收斂[10]。

改進(jìn)果蠅算法在傳統(tǒng)果蠅算法基礎(chǔ)上，建立了多種群中心搜索模式，改進(jìn)嗅覺搜索方式，引入破壞重建、插入領(lǐng)域局部搜索；并將免疫算法激勵度引入果蠅視覺覓食階段。首先，編碼和解碼將使用矩陣來表示，采用1×n的矩陣π=[a11,a12,…,a1n]表示一個個體的編碼，其中n為工件的個數(shù)。用元素a1j(j=1,2,…,n)表示矩陣π=[a11,a12,…,a1n]中的任意一個工件，將其按照a11～a1n的順序依次進(jìn)行加工；此外，設(shè)置多個種群中心來提高全局搜索能力。種群中心位置采用隨機(jī)生成的方式產(chǎn)生，種群中心數(shù)目為Csize，種群規(guī)模為Psize。

(1)嗅覺搜索

在嗅覺搜索階段，從種群中心出發(fā)，在中心果蠅產(chǎn)生其他果蠅個體。為了改進(jìn)基本果蠅算法給予的隨機(jī)方向和距離的方式，本文采用多階段方法進(jìn)行搜索，主要分為以下三個階段：

第一階段：在迭代次數(shù)小于給定迭代次數(shù)D時，半數(shù)果蠅個體引入IG算法[11]的破壞與重建過程產(chǎn)生個體位置，剩余果蠅個體數(shù)減1的位置采用多重領(lǐng)域交換結(jié)構(gòu)產(chǎn)生。

IG算法的破壞與重建過程中，首先隨機(jī)從排列πa中刪除d個工件進(jìn)行破壞，并將這d個工件構(gòu)成排列πd；接著從πd中取出第一個工件并插入到πa的可能位置，根據(jù)目標(biāo)函數(shù)來評估得到的部分序列的插入位置的好壞，選擇最優(yōu)的部分序列進(jìn)入下一代迭代；然后再取出第二個工件插入到最優(yōu)的部分序列中，依次迭代，直到πd中所有工件取出完畢進(jìn)行重建。

采用多重獨立交換結(jié)構(gòu)對領(lǐng)域作搜索，是在排列中隨機(jī)選擇兩個位置的工件，然后交換這兩個工件。評估交換后的排列的適應(yīng)度值，若交換后的適應(yīng)度值比當(dāng)前解好，則更新當(dāng)前解并替換之前的排列，然后繼續(xù)選擇位置，交換工件，重復(fù)上述操作，直達(dá)操作次數(shù)達(dá)到閾值M為止。

第二階段：當(dāng)?shù)螖?shù)大于等于給定迭代次數(shù)D時，所有果蠅個體位置用隨機(jī)權(quán)重系數(shù)變換產(chǎn)生以增強(qiáng)后期跳出局部最優(yōu)的能力。

第三階段：因為中心果蠅相對上一代果蠅位置占優(yōu)，故對此插入局部的領(lǐng)域進(jìn)行不斷的搜索，將得到的優(yōu)勢個體放入種群。

插入領(lǐng)域的局部搜索是對于排列πa，依次取πa(1),πa(2),…,πa(n)。首先取出πa(1)插入到πa-πa(1)排列的所有可能位置，得到最優(yōu)排列；然后取出πa(2)，重復(fù)上述操作直到取盡所有工件，得到最終的最優(yōu)排列后替換原排列πa的位置。

整個嗅覺搜索過程流程圖如圖1所示。

圖1 整個嗅覺過程流程圖

(2)視覺覓食

在視覺覓食階段，果蠅個體會根據(jù)味道濃度找出最優(yōu)的個體位置并替換種群中心的位置，并利用視覺引導(dǎo)種群飛向新的種群中心。若此時的最優(yōu)個體不是全局最優(yōu)個體，則易導(dǎo)致算法陷入局部收斂的困境；然而免疫算法具有自身產(chǎn)生多樣性和維持機(jī)制的特點，可以有效保持種群多樣性，避免尋優(yōu)過程中的早熟現(xiàn)象[11]。結(jié)合二者的特點，本文將在免疫反應(yīng)過程中，將用于衡量抗體最終質(zhì)量的激勵度引入果蠅算法，以提高算法穩(wěn)定性，增強(qiáng)尋優(yōu)能力。

果蠅算法中的果蠅個體對應(yīng)于免疫算法中的抗體，食物對應(yīng)于免疫算法中的抗原，味道濃度對應(yīng)于表征免疫細(xì)胞與抗原結(jié)合強(qiáng)度的親和度評價算子。相關(guān)定義如下：

①抗體與抗原之間的親和度評價定義為目標(biāo)函數(shù)的倒數(shù)，即果蠅個體適應(yīng)度值的倒數(shù)，可表示為式(4)：

(4)

式中，Cmax(πa)為排列πa的最大完工時間。

②抗體與抗體之間的親和度代表了兩個抗體之間相似程度，可表示為式(5)：

(5)

式中，πa,k=πb,k時，?k=1，否則?k=0；πa,k和πb,k分別為抗體a的第k位和抗體b的第k位的數(shù)值；n為工件的數(shù)量，即抗體或果蠅個體編碼大小。

③抗體濃度與抗體種群的多樣性相對應(yīng)，可表示為式(6)：

(6)

式中，aff(πa,πb)>δs時，S(πa,πb)=1，否則S(πa,πb)=0；δs為相似度閾值。

④抗體激勵度的計算方法為式(7)：

(7)

式中，sim(πa)為抗體πa的激勵度，exc(πa)=1/den(πa)；ps為多樣性評價因子；由式(7)可以看出，激勵度sim(πa)隨果蠅個體適應(yīng)度值f(πa)的增大而增大，隨抗體濃度值den(πa)的增大而減小。

果蠅視覺覓食階段引入免疫算法激勵度后的具體操作為：首先評估每個種群個體的激勵度；隨后選擇一定比例λ的種群飛向以適應(yīng)度大小排序的種群中心，而剩余的種群則飛向以激勵度大小排序的種群中心，最終獲得新的種群中心群。

整個視覺覓食過程流程圖如圖2所示。

圖2 整個視覺覓食過程流程圖

3 算例試驗

3.1 有效性分析

以平均性能參數(shù)ARI作為評價因子，ARI的值越大，算法的性能越好，其計算式如式(8)所示。其中，Ci表示算法第i次運(yùn)行的結(jié)果值。

(8)

表1 算法比較結(jié)果

通過分析表1可知：

①IAFOA算法在50×5規(guī)模問題下求得的最優(yōu)解相較于IBFO_NEH算法相同；說明二者求解該問題時性能相近；此外，IAFOA在其余5個規(guī)模問題下的求解結(jié)果均明顯優(yōu)于其余兩種算法，這表明求解零空閑流水車間調(diào)度問題時，改進(jìn)的果蠅算法是有效可行的。

②運(yùn)用IAFOA算法相比較IBFO_NEH 算法在平均性能參數(shù)ARI上均有所提高，IAFOA算法在最好情況下的ARI值為9.64%，最低為0.37%，體現(xiàn)了改進(jìn)果蠅算法的全局尋優(yōu)的良好性能。

3.2 算法改進(jìn)元素對比分析

采用平均相對偏差(average percent relative deviation，APRD)和標(biāo)準(zhǔn)差(stand deviation，SD)[14]來衡量算法特性，二者的計算方法參照文獻(xiàn)[14]。APRD用于衡量算法搜索的最優(yōu)解與當(dāng)前最優(yōu)解的平均相對偏差百分比，體現(xiàn)算法的平均尋優(yōu)精度，其值越小平均尋優(yōu)精度越高；SD用于衡量相對偏差百分比的平均離散程度，體現(xiàn)算法的穩(wěn)定性，其值越小算法穩(wěn)定性越好。借助MATLAB軟件對Taillard算例中前6個規(guī)模的第2個算例進(jìn)行求解，設(shè)置具體參數(shù)為：種群中心數(shù)目為Csize=10；種群規(guī)模Psize=50；迭代次數(shù)Maxgen=40；多樣性評價因子ps=0.3；種群比例λ=0.5；相似度閾值δs=0.1n；各算例隨機(jī)運(yùn)行次數(shù)Nr=10。

將本文提出的改進(jìn)果蠅算法記為IAFOA；在此基礎(chǔ)上，將僅不采用插入領(lǐng)域的局部搜索的算法記為IAFOA1；僅不采用破壞與重建過程的算法記為IAFOA2。將上述兩種方法都不采用的算法記為FOAS；基于FOAS，在視覺覓食階段采用傳統(tǒng)的飛行方法，即果蠅全部飛向最優(yōu)的個體位置的算法記為FOAF。經(jīng)過對比分析，各改進(jìn)元素對比結(jié)果如表2所示。

表2 各改進(jìn)元素的對比結(jié)果

通過對比表2中FOAF與FOAS的結(jié)果可知：

①FOAS的平均相對偏差的平均值相比FOAF要高0.14，說明FOAS算法相比較于FOAF，平均尋優(yōu)精度要差一點，算法搜索最優(yōu)解和當(dāng)前最優(yōu)解存在一定偏差。

②從SD值來看，F(xiàn)OAS在50×5、50×20規(guī)模問題下的SD值比同等問題下FOAF稍大，但在其余四個規(guī)模問題下的SD均小于采用傳統(tǒng)飛行方式的FOAF算法，并且FOAS的平均標(biāo)準(zhǔn)差比FOAF要低0.044，這些結(jié)果表明 FOAS算法的穩(wěn)定性更高。總的來說，在視覺覓食階段加入作為種群中心飛行引導(dǎo)的免疫算法激勵度，算法穩(wěn)定性會有所提升。

通過對比表2中FOAS與IAFOA1、IAFOA2和IAFOA的結(jié)果可知：

①IAFOA1和IAFOA2、IAFOA相較FOAS，在APRD值上均有所提高，分別提高了1.368、0.633和1.391。這表明在嗅覺搜索階段加入破壞與重建過程和對種群中心進(jìn)行插入領(lǐng)域的局部搜索策略會使算法平均尋優(yōu)精度稍有降低，但這會有助于跳出局部最優(yōu)的困境，增強(qiáng)算法的全局尋優(yōu)能力；以上三種方法的平均SD值相較FOAS更小，分別降低了0.32、0.146和0.332，這些結(jié)果表明了三種算法平均離散程度更小，算法更穩(wěn)定。

②在IAFOA1和IAFOA2、IAFOA三種方法中，可以看出三種算法在求解50×5問題的SD為0，在求解其余5個規(guī)模問題時出現(xiàn)一定的波動；對比不同規(guī)模問題的求解結(jié)果可知，IAFOA2波動較大；此外，IAFOA2的平均APRD最優(yōu)且與IAFOA1相差不大，但穩(wěn)定性相較于其余二者有所降低。總的來說，加入破壞與重建過程相對于插入領(lǐng)域的方法更為重要，表明破壞與重建過程會對算法尋優(yōu)精度有所影響，但能較好的改善算法穩(wěn)定性。

③通過對比不同改進(jìn)元素算法的平均值可知，IAFOA的穩(wěn)定性優(yōu)于其他算法，平均尋優(yōu)精度稍低，全局尋優(yōu)能力有所改善。其中，IAFOA與IAFOA1對相同規(guī)模的算例，APRD與SD值相近。這表明兩種算法具有相互的優(yōu)勢，算法之間的差別并不會有很大影響。而IAFOA2與上面兩種算法相比，表明了破壞與重建過程對于求解零空閑流水車間調(diào)度中的改進(jìn)果蠅算法的尋優(yōu)精度和穩(wěn)定性有更大的權(quán)重。

4 結(jié)束語

本文針對零空閑流水車間調(diào)度問題，在總結(jié)傳統(tǒng)果蠅優(yōu)化算法的基礎(chǔ)上，從種群初始化、嗅覺搜索、視覺覓食過程入手，提出了一種改進(jìn)的果蠅優(yōu)化算法IAFOA。結(jié)合案例驗證了改進(jìn)果蠅算法的有效性，并分析了改進(jìn)因素對算法的尋優(yōu)能力和穩(wěn)定性的效果。其結(jié)果表明：

(1)改進(jìn)果蠅算法IAFOA有較好的最優(yōu)解且穩(wěn)定性較好。

(2)破壞與重建過程更能提高算法的尋優(yōu)精度和穩(wěn)定性，而插入領(lǐng)域的方法對IAFOA影響較小。本文為解決零空閑流水車間調(diào)度生產(chǎn)提供了一種新的思路，通過案例驗證取得了良好效果，對果蠅優(yōu)化算法求解零空閑車間調(diào)度問題的研究具有一定借鑒意義。