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

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

0 引言

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

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

由于RFFP是NP-hard[3]，難以用精確算法進(jìn)行求解，故研究高效的智能優(yōu)化算法具有重要的理論和實踐價值。人工蜂群算法因其控制參數(shù)較少且性能具有競爭力，已成功用于求解車間調(diào)度。為最小化makespan，Li等[9]提出了離散人工蜂群(discrete artificial bee colony, DABC)算法求解帶調(diào)整時間的分布式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ì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問題，而且很少探討工件的動態(tài)特征以及工件運(yùn)輸與生產(chǎn)調(diào)度的協(xié)調(diào)問題。既有ABC算法多用于求解FFP，如何有效求解DRFFP還需進(jìn)一步研究?；诖耍疚难芯苛烁N合實際生產(chǎn)的含不相關(guān)并行機(jī)和工件運(yùn)輸時間的DRFFP，在DABC算法中嵌入遺傳算法提出了一種混合DABC-GA算法以得到近優(yōu)解。

1 DRFFP-UPM&JTT模型建立

1.1 問題描述

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

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個工件，rtm=1,2,3,…,ktm;

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

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

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

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

決策變量：

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

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

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

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

2 混合DABC-GA算法

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

2.1 編碼和解碼

2.1.1 編碼方案

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

圖1 實例的編碼表述

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

2.1.2 解碼過程

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

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

表1 實例數(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)度時間表，圖中矩形框內(nèi)(i,gi)對應(yīng)處于加工層gi的工件i。

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

2.2 初始種群

圖3 初始種群

2.3 雇傭蜂階段

在雇傭蜂階段，在蜜源Xa附近采用高斯變異進(jìn)行搜索。設(shè)計一種由當(dāng)前最佳解引導(dǎo)的高斯變異搜索策略，基于Xa添加一個服從高斯分布的隨機(jī)擾動項，借助該擾動項進(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ù)，即第a個蜜源的適應(yīng)度函數(shù)表示為式(13)。采用輪盤賭規(guī)則進(jìn)行選擇，目標(biāo)值越優(yōu)則它被選擇的概率越大。

(13)

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

設(shè)計自適應(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時，Pc計算如下:

Pc=Pcmax-(Pcmax-Pcmin)×

(14)

否則，Pc=Pcmax。

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

Pm=Pmmax-(Pmmax-Pmmin)×

(15)

否則，Pm=Pmmax。

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

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

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

2.5 偵察蜂階段

3 實驗設(shè)計與分析

3.1 實驗設(shè)計

為驗證算法的有效性，將混合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ù){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è)置GA、NEH-IGA、VNS-GA和DABC-GA的種群規(guī)模N=80，Limit=5。以DABC-GA運(yùn)行60次迭代所需的時間作為所有算法的停止條件。定義相對偏差率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 實驗結(jié)果及分析

不同規(guī)模測試結(jié)果見表2和表3。表中，列ARDI表示平均RDI值，列CPU和minO均為同一組實例的十次測試結(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)行時間內(nèi)，由DABC-GA得到的ARDI值和平均目標(biāo)值均低于其它三種算法。

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