周艷平,劉永娟

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

0 引言

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

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

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

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

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

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

1.1 螢火蟲算法

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

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

I=I0e-γrij

(1)

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

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

(2)

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

螢火蟲移動距離：

(3)

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

最亮的螢火蟲位置移動：

(4)

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

螢火蟲算法 FA：

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

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

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

4)由3)更新個體位置，由4)移動最佳個體。

5)計算個體更新位置后的亮度。

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

1.2 粒子群算法

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

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

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

(5)

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

粒子進行速度更新：

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

(6)

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

粒子進行位置更新：

xid=xid+vid

(7)

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

步驟如下：

粒子群算法 PSO:

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

2)初始化種群。

3)計算適應度值，選出個體、全局極值。

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

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

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

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

1.3.1 改進策略

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

由Logistic 映射：

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

(8)

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

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

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

(9)

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

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

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

(10)

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

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

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

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

(11)

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

(12)

f是適應度函數(shù)，第m個變異算子的標準差：

(13)

(14)

(15)

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

(16)

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

位置更新公式如下：

If(vid

Elsevid=rand*Vmax

(17)

其中：Td是設置好的閾值，閾值Td過大會降低算法的深度局部搜索能力，閾值過小會降低算法的搜索速度，因此，自適應設定閾值，不同維的速度設置不同的閾值，當達到該值時，閾值會自動下降，當速度小于閾值時，個體進行逃逸：

其中:

(18)

ifGd(t)>k1then

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

(19)

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

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

1.3.2 算法流程

HFPMCV算法流程如圖1所示。

圖1 HFPMCV算法流程圖

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

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

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

(20)

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

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

圖2 3種算法性能比較圖

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

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

FSP問題[22]:n個工件在m臺機器上加工，i工件工序數(shù)為Li，總工序數(shù)L，工序加工時間固定，并按工序加工。在約束條件下安排工件加工順序以優(yōu)化指標。

具體表述如下：

(21)

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

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

(22)

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

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

1)一個機器不可同時加工多個工件。

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

3)工件零等待，完成當前工序加工的工件必須要立刻被運輸?shù)较屡_機器，準備加工。

4)當前機器沒有需要加工的工件時可以進行等待，直到工件運輸?shù)皆摍C器。

5)工件、機器已知，明確機器上加工工件的時間。

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

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

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

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

步驟1：根據(jù)流水車間調(diào)度問題，采用基于工件的編碼方式，對于整個種群，將位置向量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個類似[pn,1,pn,2,…pn,I]的可行解，即采用混沌映射的方式生成一個可以進化的初始種群。

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

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

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

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

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

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

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)，即復雜度與基本算法仍處于一個數(shù)量級。

2.4 仿真實驗

2.4.1 實驗準備

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

2.4.2 實驗結(jié)果與分析

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

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

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

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

仿真結(jié)果如表3所示，對于同一個規(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算法更佳的完工時間，F(xiàn)APSOMA算法相比FA算法所得到的完工時間更佳。對于同一規(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算法得到的平均值更小。綜合兩個指標來看，HFPMCV算法在求解流水車間調(diào)度問題方面與FA、FAPSOMA算法相比，性能更優(yōu)、強度更高、求解結(jié)果更加精準。

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

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

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

3 結(jié)束語

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