含不相關(guān)機(jī)的動(dòng)態(tài)可重入柔性流水車間問題的混合DABC-GA算法

軒 華, 劉淑燕, 王薛苑, 李 冰

(鄭州大學(xué) 管理學(xué)院,河南 鄭州 450001)

0 引言

柔性流水車間問題(flexible flowshop problem, FFP)是工業(yè)領(lǐng)域中較為常見的一類組合優(yōu)化問題，它已被證明是NP-hard問題[1]。經(jīng)典的FFP假設(shè)每個(gè)工件僅訪問每個(gè)工序一次。然而，出于一些技術(shù)要求或質(zhì)量考慮，有些工件需重新進(jìn)入某些工序再次加工。這種特性導(dǎo)致了FFP的擴(kuò)展，稱之為可重入FFP，它廣泛存在于許多實(shí)際生產(chǎn)系統(tǒng)，如半導(dǎo)體晶片制造、印刷電路板制造和薄膜晶體管液晶顯示面板制造等[2,3]?？紤]到制造企業(yè)設(shè)備更新替換需要昂貴的成本以及加工工藝的不同，假設(shè)工件動(dòng)態(tài)到達(dá)生產(chǎn)系統(tǒng)的初端且階段間工件運(yùn)輸不可忽略，本文研究了含不相關(guān)并行機(jī)和工件運(yùn)輸時(shí)間的動(dòng)態(tài)可重入FFP(dynamic re-entrant flexible flowshop problem with unrelated parallel machines and job transportation time, DRFFP-UPM&JTT)。總加權(quán)完工時(shí)間問題已引起了眾多學(xué)者的重視[3,4]，它關(guān)系到在制品庫存水平和準(zhǔn)時(shí)交貨等重要的物流指標(biāo)，故本文以最小化總加權(quán)完工時(shí)間為目標(biāo)解決DRFFP-UPM&JTT。

盡管RFFP-UPM相比經(jīng)典FFP更為復(fù)雜，鑒于其強(qiáng)大的工業(yè)背景，已有不少學(xué)者對其展開了研究。為最小化makespan，Chamnanlor等[5]針對帶時(shí)間窗約束和非等同并行機(jī)的RFFP，提出了混合蟻群優(yōu)化的遺傳算法(genetic algorithm, GA)；Eskandari等[6]為求解含調(diào)整時(shí)間的DRFFP-UPM，提出了基于簡單分派規(guī)則的啟發(fā)式算法和基于變鄰域搜索的元啟發(fā)式算法。為最小化總拖期，Zhang等[7]提出啟發(fā)式算法求解帶非等同并行機(jī)的RFFP。針對RFFP-UPM的多目標(biāo)問題，為最小化makespan和分時(shí)電價(jià)下的能耗成本，Geng等[8]提出了改進(jìn)多目標(biāo)蟻獅優(yōu)化算法。

由于RFFP是NP-hard[3]，難以用精確算法進(jìn)行求解，故研究高效的智能優(yōu)化算法具有重要的理論和實(shí)踐價(jià)值。人工蜂群算法因其控制參數(shù)較少且性能具有競爭力，已成功用于求解車間調(diào)度。為最小化makespan，Li等[9]提出了離散人工蜂群(discrete artificial bee colony, DABC)算法求解帶調(diào)整時(shí)間的分布式FFP；Li等[10]提出了DABC算法來求解含資源約束的FFP；Kheirandish等[11]提出了DABC算法和GA求解具有多級產(chǎn)品結(jié)構(gòu)和非等同并行機(jī)的兩階段FFP；李俊青等[12]給出了混合DABC算法求解等同并行機(jī)或異構(gòu)并行機(jī)FFP；為求解考慮搬運(yùn)設(shè)備和有限緩沖區(qū)的單件車間調(diào)度，張維存等[13]設(shè)計(jì)了采用角色互換的改進(jìn)ABC算法。針對多目標(biāo)FFP，Peng等[14]為煉鋼-精煉-連鑄過程的FF再調(diào)度提出了改進(jìn)ABC算法以優(yōu)化效率目標(biāo)和系統(tǒng)不穩(wěn)定目標(biāo)；Zhang等[15]研究了帶可變加工速度的FF綠色調(diào)度，提出了基于分解的多目標(biāo)DABC算法以最小化makespan和總能耗。

綜上所述，在不相關(guān)并行機(jī)環(huán)境下的RFFP的研究多聚焦于makespan問題，而且很少探討工件的動(dòng)態(tài)特征以及工件運(yùn)輸與生產(chǎn)調(diào)度的協(xié)調(diào)問題。既有ABC算法多用于求解FFP，如何有效求解DRFFP還需進(jìn)一步研究?；诖?，本文研究了更貼合實(shí)際生產(chǎn)的含不相關(guān)并行機(jī)和工件運(yùn)輸時(shí)間的DRFFP，在DABC算法中嵌入遺傳算法提出了一種混合DABC-GA算法以得到近優(yōu)解。

1 DRFFP-UPM&JTT模型建立

1.1 問題描述

所研究的DRFFP-UPM&JTT描述如下。有I個(gè)工件經(jīng)一條生產(chǎn)線的T個(gè)生產(chǎn)階段上進(jìn)行加工，工件以S1,S2,…,ST的順序多次往復(fù)加工，每個(gè)工件i訪問特定階段Hi次，故每個(gè)工件共需Hi×T道工序完成加工。每個(gè)階段t有Mt臺(tái)不相關(guān)并行機(jī)，工件在階段t加工時(shí)可指派到該階段的任意一臺(tái)并行機(jī)，其加工時(shí)間取決于處理該工件的機(jī)器。每個(gè)工件i在釋放時(shí)間Ri到達(dá)生產(chǎn)系統(tǒng)，它在完成一道工序的加工后經(jīng)運(yùn)輸送至下道工序的機(jī)器上，其運(yùn)輸時(shí)間由生產(chǎn)階段間的距離來決定。機(jī)器在整個(gè)加工過程連續(xù)可用，每臺(tái)機(jī)器一次至多處理一個(gè)工件，而每個(gè)工件一次至多選擇一臺(tái)機(jī)器加工。調(diào)度目的是在每個(gè)階段將工件分配到機(jī)器且對指派到同一臺(tái)機(jī)器的工件進(jìn)行排序，目標(biāo)是最小化總加權(quán)完工時(shí)間。

1.2 符號表示

定義參數(shù)與變量符號如下。

參數(shù)：

I：總工件數(shù);

T：總階段數(shù);

ktm：階段t上機(jī)器m加工的工件總數(shù);

Mt：階段t可利用的不相關(guān)并行機(jī)數(shù);

Hi：工件i的總重入次數(shù);

i,i′：工件，i,i′=1, 2, …,I;

t,t′：階段，t,t′ =1, 2, …,T;

m：機(jī)器，m=1, 2, …,Mt;

gi：工件i所處的加工層;

rtm：階段t上分派到機(jī)器m加工的工件集內(nèi)第r個(gè)工件，rtm=1,2,3,…,ktm;

Ri：工件i到達(dá)初始生產(chǎn)階段的時(shí)間;

Wi：工件i的權(quán)重;

Vgi,t-1,t：工件i在相鄰兩階段間的運(yùn)輸時(shí)間，Vgi,0,1表示由第gi-1層的最后一個(gè)階段T運(yùn)送至第gi層的第一個(gè)階段的運(yùn)輸時(shí)間，當(dāng)gi>1時(shí)，Vgi,0,1>0，否則，Vgi,0,1=0;

Pitgim：工件i在第gi層的第t階段的機(jī)器m上的加工時(shí)間。

決策變量：

Bitgim：工件i在第gi層的第t階段的機(jī)器m上的開工時(shí)間;

Citgim：工件i在第gi層的第t階段的機(jī)器m上的完工時(shí)間;

LCitgi：工件i在第gi層的第t階段的完工時(shí)間;

Zitgim：若工件i在第gi層的第t階段的機(jī)器m上進(jìn)行加工，Zitgim=1，否則，Zitgim=0。

1.3 模型構(gòu)建

利用上述符號，將DRFFP-UPM&JTT建模如下:

(1)

(11)

目標(biāo)(1)是最小化總加權(quán)完工時(shí)間；約束(2)表示每個(gè)工件在任一階段只能分派到一臺(tái)機(jī)器；約束(3)表示在并行機(jī)上加工的工件總數(shù)為所有工件重復(fù)進(jìn)入生產(chǎn)系統(tǒng)的總次數(shù)；約束(4)說明了分派到同一臺(tái)機(jī)器加工的相鄰兩工件的加工優(yōu)先級關(guān)系；約束(5)表示同一層內(nèi)工件的前道工序完成后運(yùn)送至下一階段才能開始下道工序的加工；約束(6)描述了同一工件在上一層的最后階段與下一層第一個(gè)階段的工序加工優(yōu)先級關(guān)系；約束(7)為加工時(shí)間要求；約束(8)定義了工件完工時(shí)間；約束(9)描述了工件開工時(shí)間不得早于其釋放時(shí)間；約束(10)和(11)定義了變量取值范圍。

2 混合DABC-GA算法

基本ABC算法從隨機(jī)產(chǎn)生的蜜源開始，連續(xù)執(zhí)行三個(gè)階段(雇傭蜂、跟隨蜂和偵察蜂)的搜索，直到滿足給定的終止條件，它主要用于解決連續(xù)型問題，而本文所研究的DRFFP-UPM&JTT為離散組合優(yōu)化問題，故提出了混合DABC-GA算法進(jìn)行求解，在DABC算法中引入GA改善跟隨蜂的搜索效率。首先，設(shè)定迭代數(shù)Maxcycle和與被放棄蜜源相關(guān)的限定搜索次數(shù)Limit，定義蜜源a∈{1,…,N}，設(shè)計(jì)調(diào)度解的編碼和解碼方案，初始化種群A={X1,…,XN}；然后，依次執(zhí)行雇傭蜂、跟隨蜂和偵察蜂階段。

2.1 編碼和解碼

2.1.1 編碼方案

基于上述模型設(shè)計(jì)了基于批量工件的元胞矩陣編碼方案，基于不相關(guān)并行機(jī)機(jī)器號對工件在整個(gè)調(diào)度范圍內(nèi)的加工機(jī)器流進(jìn)行表述，矩陣內(nèi)的每個(gè)元素(即機(jī)器號umitg)服從[1,Mt]均勻分布，蜜源為由I個(gè)矩陣組成的元胞數(shù)組，它對應(yīng)工件的調(diào)度。

圖1 實(shí)例的編碼表述

圖1為I=2、T=2、Hi=2、M1=3且M2=2的一個(gè)實(shí)例編碼，其中，每列表示在層gi工件i在各階段加工時(shí)選擇的機(jī)器號；每行表示在階段t工件的各層工序的機(jī)器分配；虛線框內(nèi)矩陣在蜜源中所處位置即為隨機(jī)生成的工件加工序列β。

2.1.2 解碼過程

通過解碼將上述解表示為可行調(diào)度表。按照加工序列β依次安排各個(gè)工件的加工。對于階段1，在第一層，將工件i分配至各自釋放時(shí)間之后可利用的機(jī)器m(m=umi11)上；在重入層gi(gi≥2)，計(jì)算工件i到達(dá)該階段的時(shí)間Ci,T,gi-1,m+Vgi,0,1，記錄工件i在該階段同一臺(tái)機(jī)器加工的緊前工件i′的完工時(shí)間Ci′1gi′m，則工件i在重入層gi的第一階段的機(jī)器m(m=umi1gi)上的開工時(shí)間Bitgim=max(Ci,T,gi-1,m+Vgi,0,1,Ci′1gi′m)。對于其它階段t，比較工件i到達(dá)該階段的時(shí)間Ci,t-1,gi,m+Vgi,t-1,t與工件i在該階段同一臺(tái)機(jī)器加工的緊前工件i′的完工時(shí)間Ci′tgi′m，取max(Ci,t-1,gi,m+Vgi,t-1,t,Ci′tgi′m)作為工件i在重入層gi階段t的機(jī)器m(m=umitgi)上的開工時(shí)間。

下面以圖1為例詳細(xì)說明上述解碼過程，其中工件釋放時(shí)間Ri、權(quán)重Wi、加工時(shí)間Pitgim以及運(yùn)輸時(shí)間Vgi,t-1,t見表1。由圖1可知，工件加工序列為β={1,2}，工件的機(jī)器分配方案及完工時(shí)間計(jì)算如下:

表1 實(shí)例數(shù)據(jù)

Z1111=Z1112=Z1211=Z1213=Z1122

=Z1123=Z1222=Z1223=0

Z1113=Z1212=Z1121=Z1221=1

B1113=R1=5

C1113=B1113+∑mP111mZ111m=5+9=14

B1212=C1113+V112=14+3=17

C1212=B1212+∑mP121mZ121m=17+10=27

B1121=C1212+V201=27+1=28

C1121=B1121+∑mP112mZ112m=28+5=33

B1221=C1121+v212=33+3=36

C1221=B1221+∑mP122mZ122m=36+5=41

W1LC122=7×41=287

Z2111=Z2113=Z2211=Z2213=Z2121

=Z2122=Z2222=Z2223=0

Z2112=Z2212=Z2123=Z2221=1

B2112=R2=3

C2112=B2112+∑mP211mZ211m=3+7=10

B2212=max{C2112+V112,C1212}=max{10+3,27}=27

C2212=B2212+∑mP221mZ221m=27+9=36

B2123=max{C2212+V201,C1113}=max{36+1,14}=37

C2123=B2123+∑mP212mZ212m=37+6=43

B2221=max{C2123+V212,C1221}=max{43+3,41}=46

C2221=B2221+∑mP222mZ222m=46+10=56

W2LC222=10×56=560

minO=∑iWiLCi22=287+560=847

據(jù)此可得到如圖2的調(diào)度時(shí)間表，圖中矩形框內(nèi)(i,gi)對應(yīng)處于加工層gi的工件i。

圖2 實(shí)例調(diào)度甘特圖

2.2 初始種群

圖3 初始種群

2.3 雇傭蜂階段

在雇傭蜂階段，在蜜源Xa附近采用高斯變異進(jìn)行搜索。設(shè)計(jì)一種由當(dāng)前最佳解引導(dǎo)的高斯變異搜索策略，基于Xa添加一個(gè)服從高斯分布的隨機(jī)擾動(dòng)項(xiàng)，借助該擾動(dòng)項(xiàng)進(jìn)行鄰域搜索。因此，新蜜源Xnew產(chǎn)生如下:

Xnew=Xa·(1+N(0,1))

(12)

上式中，N(0,1)為滿足正態(tài)分布、期望值為0且標(biāo)準(zhǔn)差為1的隨機(jī)數(shù)。

2.4 跟隨蜂階段

在跟隨蜂階段，對雇傭蜂反饋的蜜源采用GA進(jìn)行搜索以獲得較好的鄰域解。

2.4.1 適應(yīng)度評估和選擇

用于混合DABC-GA算法的評估函數(shù)定義為總加權(quán)完工時(shí)間的倒數(shù)，即第a個(gè)蜜源的適應(yīng)度函數(shù)表示為式(13)。采用輪盤賭規(guī)則進(jìn)行選擇，目標(biāo)值越優(yōu)則它被選擇的概率越大。

(13)

2.4.2 自適應(yīng)交叉和變異算子

設(shè)計(jì)自適應(yīng)交叉和變異概率Pc、Pm，使其隨迭代數(shù)及適應(yīng)度值而變化。令σ和τ表示權(quán)重因子；定義fmax和favg分別為種群A的最大適應(yīng)度值和平均適應(yīng)度值；令h為當(dāng)前迭代數(shù)，Pcmax和Pcmin、Pmmax和Pmmin分別為交叉概率和變異概率的上下界。

當(dāng)交叉蜜源中較大的適應(yīng)度值f′高于favg時(shí)，Pc計(jì)算如下:

Pc=Pcmax-(Pcmax-Pcmin)×

(14)

否則，Pc=Pcmax。

當(dāng)變異蜜源適應(yīng)度值f高于favg時(shí)，Pm計(jì)算如下:

Pm=Pmmax-(Pmmax-Pmmin)×

(15)

否則，Pm=Pmmax。

圖4 基于工件加工序列的交叉算子

變異算子采用基于工件加工機(jī)器流的單點(diǎn)變異方式，在A中隨機(jī)選擇某個(gè)蜜源中一個(gè)變異位λ∈(1,I)，重新生成第λ個(gè)位置的工件加工機(jī)器流，使其轉(zhuǎn)化為近似解再進(jìn)行擇優(yōu)，如圖5所示。

圖5 基于工件加工機(jī)器流的單點(diǎn)變異算子

2.5 偵察蜂階段

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證算法的有效性，將混合DABC-GA算法和傳統(tǒng)GA、嵌入變鄰域搜索的GA(VNS-GA)以及文獻(xiàn)[3]提出的結(jié)合NEH啟發(fā)式算法的改進(jìn)GA(NEH-IGA)做對比。所有算法采用Matlab R2014a編程，在CPU為Inter Core i5-5200U CPU 2.20GHz，內(nèi)存為4.00GB的微機(jī)上運(yùn)行。

測試實(shí)例由參數(shù){I,T,Hi,Mt}的不同組合構(gòu)成，其中I={30,50,70,90,120}，T={3,5}，Hi={2,3}，Mt={5,6,7}，共產(chǎn)生5×2×2×3=60種不同問題規(guī)模，每種規(guī)模運(yùn)行10次。Pitgim∈U[5,10]，Wi∈U[5,10]，Ri∈U[1,5]，Vgi,t-1,t∈U[1,5]。為了公平比較上述四種算法，經(jīng)大量實(shí)驗(yàn)測試，設(shè)置GA、NEH-IGA、VNS-GA和DABC-GA的種群規(guī)模N=80，Limit=5。以DABC-GA運(yùn)行60次迭代所需的時(shí)間作為所有算法的停止條件。定義相對偏差率RDI為:

RDI=(Oξ-Obest)/Obest*100%

(16)

其中，Oξ表示由算法ξ(ξ∈{GA,NEH-IGA, VNS-GA, DABC-GA})獲得的目標(biāo)值，Obest為由所有算法得到的最佳目標(biāo)值。

圖6 基于工件加工序列的反轉(zhuǎn)操作

3.2 實(shí)驗(yàn)結(jié)果及分析

不同規(guī)模測試結(jié)果見表2和表3。表中，列ARDI表示平均RDI值，列CPU和minO均為同一組實(shí)例的十次測試結(jié)果的平均值。

表2 中小規(guī)模問題的測試結(jié)果

表3 大規(guī)模問題的測試結(jié)果

由表2和表3可看出，對于中小規(guī)模和大規(guī)模問題，由GA、NEH-IGA、VNS-GA、DABC-GA得到的ARDI分別為12.62和8.93、8.03和6.18、7.70和5.58、6.92和4.83；得到的平均目標(biāo)值分別為90218.7和323000.1、86971.4和315205.7、86585.7和313247.6、85954.4和311063.8。因此，對于所有規(guī)模問題，在相同運(yùn)行時(shí)間內(nèi)，由DABC-GA得到的ARDI值和平均目標(biāo)值均低于其它三種算法。

從總體性能來看，在平均CPU時(shí)間為49.5s內(nèi)，由GA、NEH-IGA、VNS-GA、DABC-GA得到的ARDI分別為10.775、7.105、6.64、5.875；平均目標(biāo)值分為206609.4、201088.55、199916.65、198509.1，這也說明DABC-GA獲得了更好的近優(yōu)解。

4 結(jié)論

本文研究了每階段含不相關(guān)并行機(jī)的動(dòng)態(tài)可重入柔性流水車間問題，以最小化總加權(quán)完工時(shí)間為目標(biāo)構(gòu)建了整數(shù)規(guī)劃模型，進(jìn)而，提出一種混合DABC-GA算法進(jìn)行求解。根據(jù)DRFFP-UPM&JTT的特性，設(shè)計(jì)了基于批量工件的元胞矩陣編碼，采用高斯變異使雇傭蜂進(jìn)行有效的鄰域搜索，在跟隨蜂階段引入GA進(jìn)一步擴(kuò)大解空間，針對偵察蜂設(shè)計(jì)了基于當(dāng)前最佳解的反轉(zhuǎn)操作，大量的仿真測試驗(yàn)證了所提出的混合算法的有效性。未來研究可繼續(xù)探討其它單目標(biāo)或多目標(biāo)問題；或者引入調(diào)度過程的其它動(dòng)態(tài)特性，以擴(kuò)展所提算法的應(yīng)用；還可研究其它元啟發(fā)式算法求解DRFFP-UPM&JTT的能力。