改進(jìn)人工蜂群算法求解柔性作業(yè)車間調(diào)度問題

陳 少，吉衛(wèi)喜,b，仇永濤，張國祥

(江南大學(xué) a.機(jī)械工程學(xué)院；b.江蘇省食品先進(jìn)制造裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122)

0 引言

柔性作業(yè)車間調(diào)度問題(Flexible Job Shop Problem, FJSP)[1]歷年來一直是國內(nèi)外研究的熱點(diǎn)問題之一，研究已證明該類問題是典型的NP-hard問題。盡管近年來學(xué)者們已將諸如遺傳算法[2]、蟻群算法[3-4]、粒子群算法[5]等人工智能算法應(yīng)用到該問題上的求解上，并取得了一定的效果，但至今仍沒有得出一套完全良好的解決方案，因此該問題仍具有很大的研究空間。

本文所研究的人工蜂群算法(Artificial Bee Colony, ABC)是由土耳其學(xué)者Karaboga[6]于2005年提出。該算法具有搜索速度快、精度高、參數(shù)少、魯棒性強(qiáng)等優(yōu)點(diǎn)，文獻(xiàn)[7]也指出它與GA、PSO等算法相比，所求得的解的質(zhì)量相對較好。而在車間調(diào)度問題上，近年來的ABC算法研究大多集中在流水車間的問題上[8-9]，在柔性作業(yè)車間調(diào)度問題上，田野等[10]雖有一定研究，但仍存在易陷入“早熟”收斂特性、局部搜索能力較弱、收斂速度較慢等缺陷，故該算法仍具有很大的改進(jìn)空間。本文在介紹其標(biāo)準(zhǔn)算法的基礎(chǔ)上，針對算法中三類蜜蜂的特點(diǎn)分別進(jìn)行改進(jìn)，使算法能適用于FJSP問題求解的同時(shí)，具有較快搜索速度和良好的跳出局部解的能力，最后選用標(biāo)準(zhǔn)算例求解并與其他算法結(jié)果對比證明該改進(jìn)算法的有效性。

1 問題描述

FJSP問題可進(jìn)行如下描述: 有n個(gè)工件，用Ji(i=1,2,…,n)表示第i個(gè)工件，每個(gè)工件之間相互獨(dú)立，每個(gè)工件都有Oi道工序組成，Oij表示工件Ji的第j道加工工序。n個(gè)工件需要在m臺機(jī)床上進(jìn)行加工，Mk(k=1,2,…,m)表示第k臺設(shè)備，每個(gè)工件的加工工序是確定的。對于每道工序Oij有一臺或多臺設(shè)備可進(jìn)行加工，用mij表示其可選設(shè)備集，mij?(1,2,…,m)調(diào)度的目的就是為每道工序選擇最佳的加工設(shè)備并確定每臺設(shè)備上所有工序的加工順序，使加工完所有工序的總時(shí)間最小。此外，還需滿足以下約束條件：

(1)同一時(shí)間同一臺設(shè)備上只能加工一個(gè)工件的某一道工序；

(2)同一時(shí)間一個(gè)工序只能在某一臺設(shè)備上加工，且加工過程不可以中斷直至該工序加工完成；

(3)同一工件的各工序存在先后順序約束，但對于不同工件的各工序而言，它們相互獨(dú)立；

(4)所有工件可選擇的加工設(shè)備及設(shè)備相應(yīng)的加工時(shí)間是確定的。

上述問題的數(shù)學(xué)描述如下：

(1)

s.t.

(2)

cij≤si(j+1),i=1,2,…,n，k=1,2,…,m

(3)

sij+cij≤saq+Y(1-yijaqk),
i,a=1,2,…,n，k=1,2,…,m,j,q=1,2,…,oi

(4)

cij≤si(j+1)+Y(1-yaqi(j+1)k),
i=1,2,…,n;k=1,2,…,m;j,q=1,2,…,oi

(5)

sij≥0且cij≥0

(6)

(7)

cij≤Cmax,i=1,2,…,n,j=1,2,…,oi

(8)

式中，Cmax為最大完工時(shí)間；Ci為工件Ji的完工時(shí)間；sij為工序Oij開始加工時(shí)間、cij為該工序完成加工時(shí)間、tijk為該工序在設(shè)備Mk上的加工時(shí)間；Y表示一個(gè)足夠大的正數(shù)；Xijk和yijaqk是標(biāo)志數(shù)，它們代表的含義如下：

(9)

(10)

上述公式中，式(1)表示所求問題的目標(biāo)函數(shù)，即最后完工時(shí)間最小化；式(2)和式(3)表示對于同一工件的各工序之間必須按確定的工藝路線進(jìn)行加工；式(4)和式(5)代表一臺設(shè)備在同一時(shí)間只能加工某個(gè)工件的某一道工序；式(6)表示所有工序開始加工和結(jié)束加工時(shí)間必須大于0；式(7)表示某個(gè)工件的某道工序在同一時(shí)刻只能在一臺設(shè)備上加工; 式(8)表示任何一個(gè)工序的完工時(shí)間小于或等于總工序的完工時(shí)間。

2 標(biāo)準(zhǔn)人工蜂群算法簡介

人工蜂群算法源是一種基于群智能的隨機(jī)搜索算法。蜂群內(nèi)蜜蜂個(gè)體根據(jù)職能不同分為三類：

(1)引領(lǐng)蜂(employed bees)：負(fù)責(zé)發(fā)現(xiàn)蜜源并將信息傳遞給跟隨蜂,所采用的搜索方式如下：

vij=xij+φij(xij-xkj)

i,k∈{1,2,3…,SN}，j∈{1,2,3,…,D}

(11)

上式中，SN表示蜜源個(gè)數(shù)，vij表示經(jīng)變換后所得到的新的蜜源，xij為原蜜源，xkj是一個(gè)隨機(jī)選取的一個(gè)不同于xij的蜜源。φij表示在區(qū)間[0,1]上產(chǎn)生的一個(gè)隨機(jī)數(shù)。

(2)跟隨蜂(onlooker bees)：根據(jù)引領(lǐng)蜂所傳遞蜜源豐富程度信息，依據(jù)一定的概率對蜜源進(jìn)行選擇，并對選擇后的蜜源采用公式(11)的方式進(jìn)行開發(fā)，依據(jù)的概率公式為：

(12)

其中，fiti代表對應(yīng)蜜源xij的適應(yīng)度值，pi則代表該蜜源被選中的概率。

(3)偵察蜂(scout bees):當(dāng)一個(gè)蜜源的適應(yīng)度值在給定的步驟內(nèi)(定義為控制參數(shù)“l(fā)imit”) 沒有被提高, 則丟棄該蜜源并通過公式(13)搜索新的蜜源:

(13)

在算法中，蜜源的一個(gè)位置即表示問題的一個(gè)潛在解，而蜜源的豐富程度則對應(yīng)于解的優(yōu)劣(即適應(yīng)度值的大小)，所以蜂群尋找高收益度蜜源的過程既是對應(yīng)問題尋求最優(yōu)解的過程。

3 改進(jìn)ABC算法求解FJSP問題

3.1 編碼與解碼

這種編碼方式一個(gè)編碼方案就代表問題的一個(gè)可行解，且方便算法的搜索過程，既能保證編碼的唯一性，解碼過程也相對簡單。

3.2 種群初始化

大多算法的初始種群是采用隨機(jī)方法產(chǎn)生的。單一的隨機(jī)方法具有很大的不確定性，所產(chǎn)生的種群有可能是較為分散的優(yōu)良種群，也可能是個(gè)體間較為相似的劣質(zhì)種群，難以保證初始群的質(zhì)量。因此，本文采用基于混沌序列思想[11]、基于加工時(shí)間越短越優(yōu)先(SPT)啟發(fā)式規(guī)則和隨機(jī)方法三種不同的方式共同產(chǎn)生工序碼初始種群，保證初始解的質(zhì)量。三種方式所占的比例如下所示：

初始機(jī)器碼的產(chǎn)生則采用隨機(jī)方式，即在對應(yīng)工序的可用機(jī)器集中隨機(jī)選擇一臺機(jī)器號填入機(jī)器碼對應(yīng)的位置上。

混沌序列思想是指通過特定的映射方式產(chǎn)生一組具有隨機(jī)性、遍歷性及規(guī)律性的序列。本文采用常用的Logistic映射，其系統(tǒng)方程如下：

X(k+1)=u*X(k)*[1-X(k)]
(k=0,1,2,…,n)

(14)

式中，u表示控制參數(shù)，當(dāng)u=4時(shí)表示系統(tǒng)處于完全混沌的狀態(tài)。

用混沌序列方式產(chǎn)生初始解步驟如下：

(1)隨機(jī)產(chǎn)生一個(gè)在(0,1)之間的初始值X(0)；

(3)將序列中的每一個(gè)元素與工序碼中元素一一對應(yīng)，然后將該序列從小到大排序，并將對應(yīng)位置的工序也隨之排序，即得到一個(gè)工序調(diào)度方案。

例如要產(chǎn)生某個(gè)3個(gè)工件，每個(gè)工件有2道加工工序的工序碼，用混沌序列產(chǎn)生初始工序碼的過程如表1所示。

表1 混沌序列產(chǎn)生工序碼過程

3.3 搜索過程的改進(jìn)

標(biāo)準(zhǔn)的ABC算法的搜索方式是針對連續(xù)優(yōu)化問題的，而FJSP屬于離散優(yōu)化問題，且考慮到ABC算法目前仍存在易陷入“早熟”的收斂特性、局部搜索能力較弱、收斂速度較慢等缺陷，因此本文提出以下改進(jìn)方式。

3.3.1 引領(lǐng)蜂搜索過程的改進(jìn)

對于一般算法的搜索過程而言，種群適應(yīng)度較差時(shí)需要較大范圍的鄰域搜索方式以加快算法的收斂速度，而適應(yīng)度值較好時(shí)則需要較小范圍的鄰域搜索方式來加強(qiáng)局部搜索能力。為實(shí)現(xiàn)針對不同適應(yīng)度值的個(gè)體有不同的搜索范圍，本文根據(jù)引入相似度φ概念，定義如下：

(15)

其中，fiti表示個(gè)體i的適應(yīng)度值，fitbest表示種群中最優(yōu)個(gè)體的適應(yīng)度值。

根據(jù)個(gè)體相似度φ的大小，根據(jù)定義的分群比例C把種群分為當(dāng)前群體中較優(yōu)的先進(jìn)群Q和較差的后進(jìn)群P，對兩個(gè)子群分別采用不同范圍的搜索方式，如下所示。

同時(shí)，公式(11)的鄰域搜索方式是針對連續(xù)問題優(yōu)化的搜索，根據(jù)兩個(gè)子群的特點(diǎn)，本文參考遺傳算法相關(guān)搜索策略，對公式(11)進(jìn)行變換，分別定義了針對兩個(gè)子群工序碼的兩種不同搜索方式：

vij=xij⊕insert(swap(xij))

(16)

vij=xij⊕reverse(xij·cross·xkj)

(17)

其中，"swap"表示交換操作，即在工序碼任意選取兩個(gè)位置，然后交換這兩個(gè)位置上的對應(yīng)的工序；"insert"表示插入操作，即在工序碼中隨機(jī)選取一個(gè)位置的工序，將該工序插到另一任意位置上；"cross"表示交叉操作，在選取的兩個(gè)工序碼之間執(zhí)行交叉操作；"reverse"表示反序操作，表示隨機(jī)選取兩個(gè)位置，將兩個(gè)位置之間的所有元素進(jìn)行倒序排列。根據(jù)文獻(xiàn)[12]的研究表明，基于工序編碼交叉(Precedence Preserving Orderbased Crossover, POX)的交叉方式能較好的繼承父代的特性，因此本文"cross"步驟中采用該交叉方式。

同時(shí)文獻(xiàn)[12]也指出，在鄰域搜索的范圍上，交叉?反轉(zhuǎn)?交換?插入，根據(jù)之前所說的分群目標(biāo)，本文中先進(jìn)群Q采用公式(16)的搜索方式，后進(jìn)群P采用公式(17)的搜索方式。根據(jù)機(jī)器碼的編碼特點(diǎn)，這里兩個(gè)種群機(jī)器碼均使用均勻交叉方式進(jìn)行鄰域搜索。

3.3.2 跟隨蜂搜索過程的改進(jìn)

在跟隨蜂階段，引領(lǐng)蜂依據(jù)輪盤賭概率選擇方式選擇蜜源并搜索，這種選擇方式容易使算法陷入局部最優(yōu)解中，故本文采用錦標(biāo)賽選擇策略[13]。因其只把適應(yīng)度值的相對大小作為選擇的標(biāo)準(zhǔn)，在一定程度上能減小超級個(gè)體的影響，對于防止算法的過早收斂有一定的作用。同時(shí)為加強(qiáng)兩個(gè)子群間的信息交流，重新將兩個(gè)子群合并為一個(gè)種群，根據(jù)錦標(biāo)賽策略選出個(gè)體xij后，在種群中任選一個(gè)個(gè)體與其進(jìn)行交叉并進(jìn)行貪心選擇。這樣加強(qiáng)了種群間的信息交流，在一定程度上降低了單一種群易陷入局部最優(yōu)解的風(fēng)險(xiǎn)，且貪心選擇使算法不會丟棄目前的最優(yōu)值，保證了較快的收斂速度。這里機(jī)器碼采用多點(diǎn)變異方式，在機(jī)器碼某些位置上隨機(jī)選擇可用機(jī)器替換當(dāng)前機(jī)器，并同樣采用貪心選擇策略進(jìn)行選擇。

3.3.3 偵察蜂搜索過程的改進(jìn)

ABC算法中若一個(gè)蜜源在搜索次數(shù)達(dá)到“l(fā)imit”次后沒有改變，則放棄該蜜源并通過偵察蜂隨機(jī)搜索方式產(chǎn)生一個(gè)新蜜源。該操作雖然在一定程度上可以使算法跳出局部最優(yōu)解，但若放棄的解恰好是全局最優(yōu)解，則會導(dǎo)致算法重新搜索最優(yōu)解，降低搜索效率。此外，考慮到算法陷入局部解的特點(diǎn)是種群中多個(gè)個(gè)體趨于相同，即擁有相同的適應(yīng)度值，本文采取以下替換方式：

(1)設(shè)定全局最優(yōu)解未改變次“l(fā)imit”；

(2)每次迭代時(shí)記錄當(dāng)前種群的全局最優(yōu)解gbesti；

(3)若gbesti在循環(huán)達(dá)到“l(fā)imit”次為發(fā)生改變，則判斷當(dāng)前種群中最優(yōu)適應(yīng)度值的個(gè)數(shù)g；

(4)若g?1，則按照定義的比例r，隨機(jī)生成r×g新的個(gè)體取代該種群中部分適應(yīng)值相同的最優(yōu)個(gè)體。

3.4 改進(jìn)ABC算法流程

基于以上所述，針對柔性作業(yè)車間調(diào)度問題改進(jìn)后的ABC算法流程如圖1所示。

圖1 改進(jìn)ABC算法流程圖

4 實(shí)例驗(yàn)證

為驗(yàn)證該算法的有效性，本文選取了柔性作業(yè)車間Kacem基準(zhǔn)函數(shù)[14]中的8×8和10×10兩個(gè)案例進(jìn)行求解。本文改進(jìn)的人工蜂群算法參數(shù)設(shè)置為：種群規(guī)模：200；控制次數(shù)limit=10；最大迭代次數(shù)200；相似度比例C=0.93；偵察蜂重新生成比例r=0.8。將該算法運(yùn)行10次，并與文獻(xiàn)[14]中Kacem所得到的結(jié)果、文獻(xiàn)[15]中所提的PSO算法和模擬退火算法(Simulate Anneal,SA)結(jié)合的方法和文獻(xiàn)[16]所提的改進(jìn)的GA算法的運(yùn)行結(jié)果相比較，比較結(jié)果如表2所示(Cmax表示10次運(yùn)行中所得的最優(yōu)值，Aver.表示10次運(yùn)行的平均值)。

表2 四種算法結(jié)果對比

從表2可以看出，本文所提的改進(jìn)的人工蜂群算法針對兩種算例獲得的最優(yōu)值均小于或等于其他三種算法，其中8×8問題和10×10問題的兩個(gè)最優(yōu)調(diào)度甘特圖分別如圖2、圖3所示。

圖2 8×8最優(yōu)解甘特圖(最優(yōu)值Cmax=14) 圖3 10×10最優(yōu)解甘特圖 (最優(yōu)值Cmax=7)

5 結(jié)束語

針對柔性車間調(diào)度問題求解難的特點(diǎn)，本文改進(jìn)人工蜂群算法的相關(guān)步驟，并用標(biāo)準(zhǔn)實(shí)例的求解結(jié)果和其他算法對比驗(yàn)證了該改進(jìn)算法的具有良好的尋優(yōu)性能和穩(wěn)定性。下面研究的重點(diǎn)是如何將算法有效的改進(jìn)并應(yīng)用到多目標(biāo)多資源約束的車間調(diào)度問題求解上，使研究更加符合實(shí)際的生產(chǎn)情況。

[參考文獻(xiàn)]

[1] 李傳鵬,王桂從,崔煥勇. 柔性作業(yè)車問調(diào)度問題研究現(xiàn)狀及發(fā)展趨勢[J]. 組合機(jī)床與自動(dòng)化加工技術(shù)，2013 (11):109-112．

[2] 張國輝,黨世杰. 遺傳算法求解低碳柔性車間生產(chǎn)調(diào)度問題[J].組合機(jī)床與自動(dòng)化加工技術(shù),2016(11):141-144.

[3] 武福,張治娟.一種求解柔性作業(yè)車間調(diào)度問題的混合 智能算法[J].組合機(jī)床與自動(dòng)化加工技術(shù),2013(5): 130-133.

[4] Rossi A,Dini G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method[J].Robotics and Computer-Integrated Manufacturing,2007,23:503-516.

[5] 劉韻,胡毅,羅企,等.一種解決柔性車間作業(yè)調(diào)度問題的 粒子群優(yōu)化算法[J].組合機(jī)床與自動(dòng)化加工技術(shù),2015 (12):144-147.

[6] Karaboga D.An idea based on honey bee swarm for numerical optimization[D]: Turkey:Computer Engineering Department,Erciyes University,2005.

[7] Karaboga D,Basturk B.On the performance of artificial bee colony (ABC) algorithm[J].Applied Soft Computing,2008,8(1): 687-697.

[8] 張素君,寧欣,顧幸生. 基于混合離散人工蜂群算法的置換流水車間調(diào)度[J].河南大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(2): 194-201.

[9] 李俊青,潘全科,王法濤.求解混合流水線調(diào)度問題的離散人工蜂群算法[J].運(yùn)籌與管理,2015,24(1):157-163.

[10]田野,徐洪華.求解多目標(biāo)柔性作業(yè)車間調(diào)度問題的離散人工蜂群算法[J].長春理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,38(4): 116-121.

[11] Liao G C,Tsao T P.Application Embedded Chaos Search Immune Genetic Algorithm for Short-term Unit Commitment[J].Electric Power Systems Research, 2004, 71(2):135-144.

[12]肖小城.粒子群求解作業(yè)車間調(diào)度問題的研究[D].鄭州: 鄭州大學(xué),2010.

[13] BAO L,ZENG J C. Comparison and analysis of the selection mechanism in the artifical bee colony algorithm[C]. 2009 9thInternational Conference on Hybrid Intelligent Systems.Los Alamitos,CA:IEEE Computer Society, 2009: 411-416.

[14] Kacem I,Hammadi S,Bome P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man and Cybernetics,Part C, 2002, 32(1):408-419.

[15] Xia W J,Wu Z M.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem[J]. Computer & Industrial Engineering,2005, 48 (2):409-425.

[16] 劉瓊,張超勇,饒運(yùn)清,等.改進(jìn)遺傳算法解決柔性作業(yè) 車間調(diào)度問題[J].工業(yè)工程與管理,2009,14(2):59-66.