一種多尺度協(xié)同變異的螢火蟲粒子群混合算法及在車間調(diào)度中的應(yīng)用

周艷平,劉永娟

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院, 山東 青島 266061)

0 引言

作為有效的資源配置與優(yōu)化手段，生產(chǎn)調(diào)度在整個(gè)制造體系中扮演關(guān)鍵的角色，應(yīng)用范圍非常廣泛，包括工業(yè)、商業(yè)等各方面。作為整個(gè)生產(chǎn)調(diào)度的關(guān)鍵部分，車間調(diào)度同時(shí)也是制造類企業(yè)的核心問題，是一個(gè)典型的NP-hard問題[1]，一直以來也是組合優(yōu)化領(lǐng)域內(nèi)的重點(diǎn)內(nèi)容，對(duì)整個(gè)生產(chǎn)流程能否順利完成有很大的影響。車間調(diào)度問題的本質(zhì)是在符合約束條件的基礎(chǔ)上，根據(jù)生產(chǎn)指標(biāo)，給出每個(gè)工件的加工順序、機(jī)器、操作方式等的組合問題。流水車間調(diào)度作為其中的一類，是流水線生產(chǎn)調(diào)度的簡(jiǎn)化模型，對(duì)流水車間調(diào)度模型進(jìn)行研究，有非常重要的意義。

在研究的初期，學(xué)者們通過使用精確算法來求解流水車間調(diào)度問題，但存在難度大、耗時(shí)長(zhǎng)等問題，求解效果并不理想。后來研究者們采用近似算法去尋找問題的最優(yōu)解，近似算法又叫做啟發(fā)式算法，不斷被研究改進(jìn)的啟發(fā)式算法成為了調(diào)度問題的主要求解辦法。

粒子群算法(PSO,particle swarm optimization)是美國(guó)的社會(huì)心理學(xué)家Eberhart和電氣工程師Kennedy[2]受達(dá)爾文“物競(jìng)天擇、適者生存”的啟發(fā)，模擬了鳥群群聚、覓食的群體性行為，于1995年提出的，算法步驟簡(jiǎn)單、參數(shù)少并且易于實(shí)現(xiàn)；英國(guó)劍橋大學(xué)工程系的X.S.Yang[3]在對(duì)螢火蟲種群的發(fā)光行為進(jìn)行建模的基礎(chǔ)上提出了螢火蟲算法(FA， firefly algorithm)，算法的提出時(shí)間不長(zhǎng)，對(duì)算法的改進(jìn)和優(yōu)化仍然處于初級(jí)階段。但不斷被研究改進(jìn)的螢火蟲、粒子群算法已被應(yīng)用于車間調(diào)度、資源調(diào)度、組合優(yōu)化等領(lǐng)域。

J.I.FISTER等人[4]提出了一種模因螢火蟲算法(MFFA)，將螢火蟲算法與局部搜索啟發(fā)式算法進(jìn)行結(jié)合，并應(yīng)用于組合優(yōu)化問題中，具有一定的實(shí)用性。鄭捷等[5]采用機(jī)器選擇策略進(jìn)行種群生成，并對(duì)適應(yīng)度較優(yōu)的個(gè)體之間進(jìn)行局部搜索，從而產(chǎn)生了一種改進(jìn)的離散螢火蟲算法，并成功地應(yīng)用在柔性作業(yè)車間調(diào)度模型中。劉長(zhǎng)平等[6]提出了一種DFA算法，用NEH構(gòu)造初始解，并根據(jù)問題的特性，重新定義了距離公式，通過交叉、變異操作實(shí)現(xiàn)位置的更新，并對(duì)處在最佳位置的個(gè)體進(jìn)行局部搜索，成功地應(yīng)用在零空閑置換流水車間調(diào)度中。張其亮等[7]結(jié)合了粒子群、貪婪算法，通過變異操作來改變粒子停滯或群體陷入局部最優(yōu)狀態(tài)，并依據(jù)模擬退火接收變異個(gè)體，在置換流水車間調(diào)度問題的求解質(zhì)量上有一定的提高。吳瓊等[8]結(jié)合了粒子群、引力搜索算法，當(dāng)粒子群進(jìn)化停滯時(shí)，引入引力搜索算法，并采用協(xié)同進(jìn)化的思想，使得兩種算法并行優(yōu)化，并且子種群之間交流，以獲得最優(yōu)粒子，并應(yīng)用到對(duì)作業(yè)車間調(diào)度問題的求解中。從實(shí)驗(yàn)數(shù)據(jù)來看，以上算法在不同程度上都提高了算法的性能，但在求解精度上還可以繼續(xù)改進(jìn)，而且隨著車間的日益復(fù)雜化，求解算法也應(yīng)該不斷的被改進(jìn)完善。

單一算法在適應(yīng)性上是有限的，螢火蟲和粒子群算法有一定的相似性，在全局搜索能力方面也有一定的互補(bǔ)性，為更好地發(fā)揮兩種算法的潛能，取長(zhǎng)補(bǔ)短獲得更優(yōu)的解，本文在螢火蟲粒子群混合算法的基礎(chǔ)上，做出了進(jìn)一步的改進(jìn)，提出了一種多尺度協(xié)同變異的螢火蟲粒子群混合算法(HFPMCV, a hybrid firefly and particle swarm optimization algorithm with multi-scale cooperative variation)，引入多尺度協(xié)同變異算子，提高求解精度，混沌初始化種群以提高初始解質(zhì)量，根據(jù)高斯擬合把種群分為兩組；平行進(jìn)化，提高求解速度，函數(shù)優(yōu)化實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的有效性，流水車間調(diào)度問題實(shí)驗(yàn)，表明了改進(jìn)算法的優(yōu)越性。

1 多尺度協(xié)同變異的螢火蟲粒子群混合算法

1.1 螢火蟲算法

螢火蟲算法的提出是建立在螢火蟲種群中個(gè)體的種種社會(huì)行為的基礎(chǔ)之上的，在實(shí)際的應(yīng)用中，只考慮發(fā)光特性，通過發(fā)光特性搜索目標(biāo)附近特定區(qū)域，向一定范圍內(nèi)定位較優(yōu)的螢火蟲移動(dòng)[9]，螢火蟲進(jìn)化和目標(biāo)函數(shù)尋優(yōu)的最主要的兩個(gè)關(guān)鍵因素就是熒光亮度和吸引度。亮度表明螢火蟲所處方位的好壞，決定了飛行方向，吸引度影響螢火蟲的移動(dòng)距離，利用吸引度和亮度更新、迭代來尋求目標(biāo)函數(shù)最優(yōu)解。數(shù)學(xué)描述如下：

在D維搜索空間內(nèi)螢火蟲i的位置向量Xi=(xi1,xi2,xi3,…xiD)，螢火蟲熒光亮度公式：

I=I0e-γrij

(1)

式中，I0為自身亮度，γ為光吸收系數(shù)，r為距離。

螢火蟲之間的相對(duì)吸引度正比于亮度：

(2)

式中，β0為其初始吸引度。

螢火蟲移動(dòng)距離：

(3)

α是擾動(dòng)的步長(zhǎng)因子，rand()是一個(gè)隨機(jī)擾動(dòng)，取值為[-0.5,0.5]范圍內(nèi)的均勻分布，α取值為[0,1]范圍。

最亮的螢火蟲位置移動(dòng)：

(4)

中心思想就是，所有個(gè)體都飛向比自己更亮的個(gè)體四周，飛行的最后結(jié)果即所有的個(gè)體都圍在了亮度最強(qiáng)的個(gè)體周圍，從而達(dá)到算法求解的目的。

螢火蟲算法 FA：

1)初始化參數(shù)，螢火蟲數(shù)目n，吸引度β0，步長(zhǎng)因子α，迭代次數(shù)Generation，搜索精度ε。

2)初始化個(gè)體位置，最大熒光亮度I0用螢火蟲的目標(biāo)函數(shù)值表示。

3)由1)、2)計(jì)算群體中個(gè)體的I、β，飛行方向由相對(duì)亮度決定。

4)由3)更新個(gè)體位置，由4)移動(dòng)最佳個(gè)體。

5)計(jì)算個(gè)體更新位置后的亮度。

6)滿足終止條件則輸出最優(yōu)解，否則轉(zhuǎn)3)步。

1.2 粒子群算法

粒子群算法的核心思想在于利用粒子與種群之間的信息改變粒子的速率和定位，在飛行范圍內(nèi)，粒子隨機(jī)飛行，飛行過程中通過學(xué)習(xí)、模仿周圍粒子的信息來獲取個(gè)體、全體最佳位置，綜合分析經(jīng)驗(yàn)后，調(diào)整自身的飛行經(jīng)驗(yàn)以實(shí)現(xiàn)更好的飛行，完成種群間個(gè)體協(xié)作探索，利用速率和定位的不斷更新迭代來尋求目標(biāo)函數(shù)的最佳解[10]。數(shù)學(xué)描述如下：

D維搜索區(qū)域內(nèi)，任意一個(gè)粒子都在以一定的初速度隨機(jī)飛行，粒子i的當(dāng)前位置向量Xi=(xi1,xi2,xi3,…xiD)，第i個(gè)粒子當(dāng)前速率：

Vi=(vi1,vi2,…viD)，i=1,2,…N

(5)

Pbest=(pi1,pi2,…piD)i=1,2,…,N為個(gè)體極值,全局極值為gbest=(pg1,pg2,…pgD)。

粒子進(jìn)行速度更新：

vid=w*vid+c1r1(pid-xid)+c2r2(pgd-xid)

(6)

ω是慣性權(quán)重，平衡全局、局部搜索能力，c1、c2是學(xué)習(xí)因子，r1、r2是[0,1]里的隨機(jī)數(shù)。速度公式包含三部分，w*vid表示個(gè)體之前的速度對(duì)現(xiàn)在速度的影響，c1r1(pid-xid)是個(gè)體歷史最好位置對(duì)現(xiàn)在速度的影響，c2r2(pgd-xid)是個(gè)體之間的信息傳遞對(duì)現(xiàn)在速度的影響。

粒子進(jìn)行位置更新：

xid=xid+vid

(7)

c1、c2是學(xué)習(xí)因子，r1、r2是[0,1]區(qū)間的隨機(jī)數(shù)。

步驟如下：

粒子群算法 PSO:

1)設(shè)置參數(shù)，包括種群規(guī)模、個(gè)體的速度和位置，并設(shè)置其它參數(shù)。

2)初始化種群。

3)計(jì)算適應(yīng)度值，選出個(gè)體、全局極值。

4)粒子飛行，據(jù)式(6)、(7)更新個(gè)體的速度、位置。

5)符合終止條件就輸出最優(yōu)解，反之返回3)。

1.3 多尺度協(xié)同變異的螢火蟲粒子群混合算法

考慮到螢火蟲算法和粒子群算法的優(yōu)缺點(diǎn)，楊小東等提出了螢火蟲粒子群混合算法FAPSOMA[11]，本文在此基礎(chǔ)上引入多尺度協(xié)同變異算子，提出了HFPMCV算法，初期，通過多尺度變異算子快速找到全局最優(yōu)解空間，不斷迭代，靠近最優(yōu)解領(lǐng)域時(shí)，通過小尺度變異算子快速收斂到最優(yōu)解,以有效的進(jìn)行變異，并且對(duì)種群進(jìn)行混沌初始化，同時(shí)動(dòng)態(tài)自適應(yīng)策略把種群分成兩組，兩組種群平行進(jìn)化以尋找優(yōu)化問題的精確解。

1.3.1 改進(jìn)策略

1)混沌初始化：隨機(jī)初始化會(huì)造成個(gè)體位置分布不均，個(gè)體間差異較大，阻礙全局尋優(yōu)，影響求解效果[12]，為了獲得質(zhì)量較好的初始解，對(duì)種群進(jìn)行混沌初始化，將變量映射到混沌變量的取值區(qū)域，通過線性變換把混沌序列轉(zhuǎn)化到搜索空間[13]。

由Logistic 映射：

Zn+1=μZn(1-Zn)，n=0,1,2,…

(8)

得混沌序列，μ為控制參量，μ∈[0,4]，當(dāng)μ=4時(shí)為完全混沌狀態(tài)。

將混沌序列映射為求解空間范圍的混沌變量：

pn,i=ai+(bi-ai)Zn,i，i=1,2,…，I

(9)

Zn,i為個(gè)體在第i維迭代n次得到的混沌序列值，I為搜索空間維度，pn,i為一個(gè)混沌變量，[pn,1,pn,2,…pn,I]代表一個(gè)可行解。

因?yàn)镻SO算法主要更新速度、位置、目標(biāo)函數(shù)值，而FA算法主要更新位置和目標(biāo)函數(shù)值，本文用FA算法中的個(gè)體位置和目標(biāo)值來替代PSO算法中的位置和目標(biāo)值，并在FA算法中創(chuàng)建速度信息，所以在本改進(jìn)算法中，創(chuàng)建FA算法的速度序列：

zi(n)=μzi(n-1)(1-zi(n-1))

(10)

zi(n)是[0,1]中符合正態(tài)分布的隨機(jī)數(shù)，n是迭代數(shù)，μ值為4。

2)動(dòng)態(tài)自適應(yīng)控制策略：在傳統(tǒng)算法中，種群分組采用隨機(jī)分組、平均分組的方法，沒有充分考慮種群中個(gè)體的運(yùn)動(dòng)軌跡。

HFPMCV算法采用高斯擬合函數(shù)[14]進(jìn)行種群分組，在混沌初始化種群后，計(jì)算并按照種群中各個(gè)體的適應(yīng)度值進(jìn)行高斯擬合，因適應(yīng)度值是由目標(biāo)函數(shù)得來，因此擬合曲線與目標(biāo)函數(shù)曲線有較強(qiáng)關(guān)聯(lián)度[15]，求解擬合曲線峰值的加權(quán)平均數(shù)[16]，并以此為根據(jù)把整個(gè)種群劃分為兩組族群。

3)多尺度協(xié)同變異算子：為了提高求解精度，避免陷入局部最優(yōu)，引入多尺度協(xié)同變異算子[17]，多尺度協(xié)同變異利用方差不同的高斯變異機(jī)制探索解空間，初期，通過大尺度變異算子快速找到全局最優(yōu)解空間，不斷迭代，靠近最優(yōu)解領(lǐng)域時(shí)，通過小尺度變異算子快速收斂到最優(yōu)解,以有效的進(jìn)行變異[18]，設(shè)尺度個(gè)數(shù)為M，首先初始化方差:

(11)

對(duì)方差、優(yōu)化變量設(shè)置一樣的取值范圍，隨著迭代次數(shù)的增加，方差會(huì)一直變化，所有個(gè)體生成M個(gè)子群，個(gè)體個(gè)數(shù)為P=N/M，迭代次數(shù)為K，子種群適應(yīng)度：

(12)

f是適應(yīng)度函數(shù)，第m個(gè)變異算子的標(biāo)準(zhǔn)差：

(13)

(14)

(15)

變異算子的進(jìn)化過程為一個(gè)遞歸的過程，HFPMCV算法要求的是隨著迭代次數(shù)的增加變異算子逐漸減小，因此需要規(guī)范變異算子的標(biāo)準(zhǔn)差：

(16)

W為待優(yōu)化變量空間的寬度。

位置更新公式如下：

If(vid

Elsevid=rand*Vmax

(17)

其中：Td是設(shè)置好的閾值，閾值Td過大會(huì)降低算法的深度局部搜索能力，閾值過小會(huì)降低算法的搜索速度，因此，自適應(yīng)設(shè)定閾值，不同維的速度設(shè)置不同的閾值，當(dāng)達(dá)到該值時(shí)，閾值會(huì)自動(dòng)下降，當(dāng)速度小于閾值時(shí)，個(gè)體進(jìn)行逃逸：

其中:

(18)

ifGd(t)>k1then

Gd(t)=0;Td=Td/k2

(19)

k1、k2是常數(shù)，Size為種群大小，Gd(t)是種群在第d維速度的逃逸次數(shù)。

4)平行進(jìn)化：結(jié)合FA和PSO的優(yōu)點(diǎn)，使FA和PSO平行的單獨(dú)進(jìn)化[19]，每一代進(jìn)化結(jié)束后，各自保存最優(yōu)個(gè)體，選出較優(yōu)個(gè)體，并與父代最優(yōu)個(gè)體進(jìn)行比較選出更優(yōu)個(gè)體作為本代最優(yōu)個(gè)體，全部迭代結(jié)束后，輸出整體最優(yōu)值，大大提升了求解速度[20]。

1.3.2 算法流程

HFPMCV算法流程如圖1所示。

圖1 HFPMCV算法流程圖

1.3.3 函數(shù)優(yōu)化測(cè)試

為了測(cè)試和解釋HFPMCV算法的性能和優(yōu)越性，將HFPMCV算法與FA算法、FAPSOMA算法進(jìn)行了對(duì)比，分別采用HFPMCV算法以及FA算法、FAPSOMA算法對(duì)以下函數(shù)[21]進(jìn)行尋優(yōu)：

xi∈[-5.12,5.12]，i=1,2,…,30

(20)

是一個(gè)多峰函數(shù)，在30維可行域中有230-1個(gè)局部求解，最優(yōu)值是0，對(duì)3個(gè)算法中的各參數(shù)設(shè)定一樣的值以提高計(jì)算有效性和結(jié)果精確度，迭代500次，種群規(guī)模是100，維度是30等。

3種算法的性能對(duì)比如圖2所示，圖中可以看出，迭代次數(shù)相同時(shí)，HFPMCV算法收斂更快，精度更高，求解結(jié)果相同時(shí)，F(xiàn)A、FAPSOMA需要迭代更多次才能得到最優(yōu)解，通過函數(shù)測(cè)試驗(yàn)證了HFPMCV算法的優(yōu)良性能。

圖2 3種算法性能比較圖

2 HFPMCV算法求解流水車間調(diào)度問題

2.1 流水車間調(diào)度問題模型

FSP問題[22]:n個(gè)工件在m臺(tái)機(jī)器上加工，i工件工序數(shù)為L(zhǎng)i，總工序數(shù)L，工序加工時(shí)間固定，并按工序加工。在約束條件下安排工件加工順序以優(yōu)化指標(biāo)。

具體表述如下：

(21)

凡事都有一個(gè)標(biāo)準(zhǔn)，評(píng)價(jià)調(diào)度方案好壞的標(biāo)準(zhǔn)就是是否達(dá)到指標(biāo)，如客戶滿意度指標(biāo)、完工時(shí)間指標(biāo)、性能指標(biāo)等。本章選取的指標(biāo)為最大完工時(shí)間，以最大完工時(shí)間中的最小值作為優(yōu)化目標(biāo)[23]，目標(biāo)函數(shù)如下：

min{maxTi,j},i=1,…,n;j=1,…,m

(22)

maxTi,j為所有工件中最后完成加工的結(jié)束時(shí)間；min{maxTi,j}為最大完工時(shí)間中的最小值。

以流水車間調(diào)度問題為模型，公式(21)中的約束如下：

1)一個(gè)機(jī)器不可同時(shí)加工多個(gè)工件。

2)每個(gè)待加工工件的加工工序是固定的，只有完成了前面工序的加工工作，才可以進(jìn)行之后工序的加工工作。

3)工件零等待，完成當(dāng)前工序加工的工件必須要立刻被運(yùn)輸?shù)较屡_(tái)機(jī)器，準(zhǔn)備加工。

4)當(dāng)前機(jī)器沒有需要加工的工件時(shí)可以進(jìn)行等待，直到工件運(yùn)輸?shù)皆摍C(jī)器。

5)工件、機(jī)器已知，明確機(jī)器上加工工件的時(shí)間。

2.2 HFPMCV算法求解流水車間調(diào)度問題步驟

HFPMCV算法求解流水車間調(diào)度問題的求解步驟如下：

輸入：種群規(guī)模popsize、迭代次數(shù)iteration、搜索范圍bound、維度vardim

輸出：工件加工最優(yōu)次序、最小完工時(shí)間

步驟1：根據(jù)流水車間調(diào)度問題，采用基于工件的編碼方式，對(duì)于整個(gè)種群，將位置向量xi[D]，由公式(8)生成向量xi+1[D],xi+2[D],…,xN[D]，N為種群數(shù)，通過公式(9)將xi[D],xi+1[D],xi+2[D],…,xN[D]映射到位置變量的取值空間，獲取最初位置X1[D],X2[D],…,XN[D]，生成n個(gè)類似[pn,1,pn,2,…pn,I]的可行解，即采用混沌映射的方式生成一個(gè)可以進(jìn)化的初始種群。

步驟2：根據(jù)動(dòng)態(tài)自適應(yīng)控制策略，計(jì)算并依據(jù)初始適應(yīng)度值進(jìn)行高斯擬合，把整個(gè)種群劃分為兩組族群。

步驟3：根據(jù)初始適應(yīng)度值，選出兩族群各自的最優(yōu)個(gè)體，通過比較，選出較優(yōu)個(gè)體作為本代最優(yōu)個(gè)體，即第一代最優(yōu)加工次序。

步驟4：開始平行進(jìn)化，F(xiàn)A和PSO分別搜索最優(yōu)值：PSO加入多尺度協(xié)同變異算子，據(jù)式(17)更新速度、位置，重新計(jì)算適應(yīng)度值，F(xiàn)A加入多尺度協(xié)同變異算子，據(jù)式(1)、(2)更新亮度、吸引度，據(jù)式(17)更新位置、速度，重新計(jì)算適應(yīng)度值，F(xiàn)A和PSO各自保存本代最優(yōu)個(gè)體。根據(jù)式(13)～(15)分別更新兩族群中多尺度協(xié)同變異算子的方差，根據(jù)變異次數(shù)更新閾值。

步驟5：判斷兩者保存的最優(yōu)值哪一個(gè)更優(yōu)，比較更優(yōu)個(gè)體與上一代最優(yōu)個(gè)體，選出較優(yōu)者作為本代最優(yōu)個(gè)體，即最優(yōu)方案。

步驟6：達(dá)到最大迭代次數(shù)則輸出最優(yōu)加工次序和相對(duì)應(yīng)的最優(yōu)加工時(shí)間，否則轉(zhuǎn)步驟4，開始下一次并行迭代。

2.3 HFPMCV算法求解流水車間調(diào)度問題復(fù)雜度分析

G*O[O(m*D)+2*O(M*D)+O(M)+O(M)

整理后為：

O(G*m*D)+7*O(G*M*D)+2*O(G*M)可近似看作O(G*M*D)，即復(fù)雜度與基本算法仍處于一個(gè)數(shù)量級(jí)。

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

2.4.1 實(shí)驗(yàn)準(zhǔn)備

在Windows10操作系統(tǒng)下的PyCharm軟件上運(yùn)行程序，采用python語言編程。種群規(guī)模為50，迭代800次，保證幾個(gè)算法參數(shù)一致，基于工件編碼，選擇TA類車間調(diào)度數(shù)據(jù)集[24]，用20*5、50*5及100*5這3個(gè)數(shù)據(jù)集為基礎(chǔ)，分別選擇每一個(gè)數(shù)據(jù)集下面的一個(gè)典型問題，來進(jìn)行流水車間調(diào)度問題的實(shí)驗(yàn)以驗(yàn)證算法。

2.4.2 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試和解釋HFPMCV算法的性能和優(yōu)越性，分別使用FA、FAPSOMA、HFPMCV對(duì)3種不同規(guī)模的調(diào)度集進(jìn)行對(duì)比實(shí)驗(yàn)，并以最小化最大完工時(shí)間為指標(biāo)，為避免實(shí)驗(yàn)的偶然性，3種算法在對(duì)3個(gè)不同規(guī)模的數(shù)據(jù)集進(jìn)行求解的時(shí)候，分別運(yùn)行10次，把10次結(jié)果的平均值和最優(yōu)值作為結(jié)果參考指標(biāo)。實(shí)驗(yàn)結(jié)果如表1～3所示。

表1 3種算法在規(guī)模為20*5下的輸出結(jié)果

表2 3種算法在規(guī)模為50*5下的輸出結(jié)果

表3 3種算法在規(guī)模為100*5下的輸出結(jié)果

仿真結(jié)果如表3所示，對(duì)于同一個(gè)規(guī)模的數(shù)據(jù)集，單從最優(yōu)值來看，例如50*5規(guī)模，F(xiàn)A的最優(yōu)值為2 886，F(xiàn)APSOMA的最優(yōu)值為2 837，HFPMCV算法最優(yōu)值為2 739，即HFPMCV算法可以得到比FA、FAPSOMA算法更佳的完工時(shí)間，F(xiàn)APSOMA算法相比FA算法所得到的完工時(shí)間更佳。對(duì)于同一規(guī)模，單從十次結(jié)果的平均值來看，例如100*5規(guī)模，HFPMCV算法的平均值為5 507，F(xiàn)APSOMA的平均值為5 565.9，F(xiàn)A的平均值為5 628.4，HFPMCV算法的平均值小于FA、FAPSOMA算法，F(xiàn)APSOMA算法相比FA算法得到的平均值更小。綜合兩個(gè)指標(biāo)來看，HFPMCV算法在求解流水車間調(diào)度問題方面與FA、FAPSOMA算法相比，性能更優(yōu)、強(qiáng)度更高、求解結(jié)果更加精準(zhǔn)。

甘特圖，別名條狀圖，較為簡(jiǎn)單、直觀，以圖示的方式來向人們展示工程進(jìn)度安排，甘特圖上面標(biāo)識(shí)著工件加工順序，每一個(gè)工件在每一臺(tái)機(jī)器上的開始加工時(shí)間、結(jié)束加工時(shí)間，整個(gè)優(yōu)化方案的用時(shí)等。通過生成的甘特圖可以直觀的看到算法求解流水車間調(diào)度的結(jié)果，即生成的最優(yōu)加工順序以及最小完工時(shí)間。

圖3展示了HFPMCV算法求解一次20*5的車間調(diào)度問題時(shí)所得的甘特圖，X軸表示加工時(shí)間，Y軸表示機(jī)器號(hào)，J代表工件號(hào)，st代表工件開始加工時(shí)間，ft代表工件結(jié)束加工時(shí)間，如工件8在第5臺(tái)機(jī)器上面的開始加工時(shí)間為138，結(jié)束加工時(shí)間為207，加工用時(shí)69，所有的工件在第一臺(tái)機(jī)器上全部加工完成的時(shí)間為1 121，所有的工件在第五臺(tái)機(jī)器上全部加工完成的時(shí)間為1 305，從圖中可以看出工件的加工順序?yàn)閇8,7,16,14,5,13,10,11,1,2,15,12,4,17,3,0,18,9,6,19]，最小完工時(shí)間為1 305。

圖3 HFPMCV算法求解車間調(diào)度問題的甘特圖

3 結(jié)束語

本文針對(duì)流水車間調(diào)度模型求解問題，并考慮到單種算法對(duì)全局最優(yōu)解的收斂局限性，并且結(jié)合前人提出的螢火蟲粒子群混合算法，在螢火蟲粒子群混合算法的基礎(chǔ)上，提出了HFPMCV算法，通過引入多尺度協(xié)同變異算子、混沌初始化、動(dòng)態(tài)自適應(yīng)策略以及平行進(jìn)化模式，提高了算法的求解速率和精度，函數(shù)優(yōu)化實(shí)驗(yàn)驗(yàn)證了HFPMCV算法的可行、有效，用HFPMCV、FA、FAPSOMA算法解決以最小化最大完工時(shí)限為指標(biāo)的流水車間調(diào)度問題，對(duì)比實(shí)驗(yàn)結(jié)果顯示HFPMCV算法得到的完工時(shí)間均小于FA、FAPSOMA算法，說明了HFPMCV算法速率更快、精度更高，與基本算法相比較，在求解流水車間調(diào)度模型時(shí)，更具有一定的實(shí)用價(jià)值。但螢火蟲位置更新公式仍需要優(yōu)化，以改善算法時(shí)間復(fù)雜度，獲得更優(yōu)的求解結(jié)果。接下來將著重于研究HFPMCV算法在其他車間調(diào)度問題中的應(yīng)用。