帶不相關(guān)并行機(jī)的阻塞FFP的混合遺傳算法

軒 華，鄭倩倩，李 冰

(鄭州大學(xué) 管理工程學(xué)院，河南 鄭州 450001)

0 引 言

柔性流水車間問題(flexible flowshop problem，F(xiàn)FP)最初是從石油工業(yè)提煉出來的[1]，它由多個(gè)生產(chǎn)階段組成，至少有一個(gè)階段含兩臺(tái)或兩臺(tái)以上的并行機(jī)。在經(jīng)典FFP中，多假定同一階段的并行機(jī)是同構(gòu)的，然而完成同一工序的機(jī)器由于新舊程度等可能會(huì)導(dǎo)致加工時(shí)間有所不同，因此，引起含不相關(guān)并行機(jī)的FFP的研究，考慮到實(shí)際生產(chǎn)中很多車間無中間緩沖，即當(dāng)工件完成一道工序后若下游機(jī)器正處于繁忙狀態(tài)，則它需停留在該工序的機(jī)器上直至下游機(jī)器空閑。這類問題稱之為含不相關(guān)并行機(jī)的阻塞FFP(blocking FFP with unrelated parallel machines，BFFP-UPM)，由于一般的多階段FFP是NP-hard[2]，故所研究的更復(fù)雜的BFFP-UPM也是NP-hard問題。

針對(duì)帶阻塞約束的車間調(diào)度問題多圍繞流水車間展開[3-7]，但近幾年也有一些文獻(xiàn)關(guān)于帶阻塞約束的FFP進(jìn)行了研究，在同構(gòu)機(jī)環(huán)境下，以最小化最大完成時(shí)間為目標(biāo)，文獻(xiàn)[8,9]研究了含阻塞約束的兩階段可重入FFP，分別提出了元啟發(fā)式和混合粒子群優(yōu)化算法；文獻(xiàn)[10]將同貝同步裝卸抽象為柔性流水車間，結(jié)合阻塞、批處理和無等待要求，提出了一種融和啟發(fā)式分配規(guī)則和禁忌搜索的優(yōu)化方法；文獻(xiàn)[11]以外科資源成本為目標(biāo)，構(gòu)造了兩種混合整數(shù)規(guī)劃模型。在不相關(guān)并行機(jī)條件下，文獻(xiàn)[12]結(jié)合雙信息素和遺傳算法提出了蟻群優(yōu)化解決帶運(yùn)輸時(shí)間和釋放時(shí)間的FFP；文獻(xiàn)[13]提出了一種離散布谷鳥分散算法，測試了多達(dá)20個(gè)工件的小規(guī)模問題；文獻(xiàn)[14]為最小化最大完成時(shí)間建立了4個(gè)混合整數(shù)線性規(guī)劃模型，設(shè)計(jì)了改進(jìn)回溯搜索算法求解中大規(guī)模問題；文獻(xiàn)[15]考慮最大完成時(shí)間和總機(jī)器分配成本雙目標(biāo)函數(shù)，建立了混合整數(shù)線性規(guī)劃模型，提出了魯棒可能性規(guī)劃方法來解決加工時(shí)間、調(diào)整時(shí)間和費(fèi)用的不確定性。

遺傳算法(genetic algorithm，GA)作為一類智能優(yōu)化算法，已成功求解車間調(diào)度問題。為解決流水車間最大完成時(shí)間問題，文獻(xiàn)[16]提出一種有效的GA；文獻(xiàn)[17]提出一種結(jié)合CDS啟發(fā)式的混合GA；文獻(xiàn)[18]針對(duì)序列相關(guān)集調(diào)度問題，提出了一種結(jié)合隨機(jī)抽樣搜索法的混合GA。為解決FFP總加權(quán)完成時(shí)間問題，文獻(xiàn)[19]提出結(jié)合NEH啟發(fā)式的混合GA。

就目前所查閱的文獻(xiàn)來看，關(guān)于BFFP的探討大多針對(duì)最大完成時(shí)間問題，極少研究總加權(quán)完成時(shí)間問題；已有的含不相關(guān)并行機(jī)的BFFP多是針對(duì)小規(guī)模問題，文獻(xiàn)[15]雖考慮了工件動(dòng)態(tài)到達(dá)時(shí)間，解決了中大規(guī)模完成時(shí)間問題，但未考慮運(yùn)輸時(shí)間，而在生產(chǎn)實(shí)際中運(yùn)輸時(shí)間相對(duì)加工時(shí)間常常不可忽略，并且對(duì)于總加權(quán)完成時(shí)間問題的研究有助于縮短生產(chǎn)時(shí)間和降低在制品庫存，能夠很大程度提高制造商生產(chǎn)力和市場競爭力。因此，本文以總加權(quán)完成時(shí)間作為目標(biāo)函數(shù)，考慮工件動(dòng)態(tài)到達(dá)特征，兼顧生產(chǎn)與協(xié)調(diào)問題提煉出帶運(yùn)輸時(shí)間的BFFP-UPM，進(jìn)而給出了融合鄰域搜索的有效遺傳算法(effective GA with local search，EGA&LS)以求解不同規(guī)模問題。

1 問題描述

本文所研究的BFFP-UPM可描述為：共有N個(gè)工件(n=1, 2, …,N)進(jìn)入連續(xù)的S個(gè)生產(chǎn)階段(s=1, 2,…,S)進(jìn)行加工，每個(gè)階段s有UMs臺(tái)不相關(guān)并行機(jī)(k=1, 2,…,UMs)，工件n在每個(gè)階段s加工時(shí)選擇的機(jī)器k不同則其加工時(shí)間Tnsk也不同，至少存在一個(gè)階段UMs>1，結(jié)構(gòu)如圖1所示(S=5,umsk表示階段s的機(jī)器k)。所研究問題的其它特征描述如下[20]：

圖1 BFFP-UPM結(jié)構(gòu)

(1)每個(gè)工件有一個(gè)釋放時(shí)間，即表示它到達(dá)系統(tǒng)初端的時(shí)間，令Rn表示釋放時(shí)間，則工件在第1階段的開始時(shí)間不能少于Rn；

(2)相鄰兩生產(chǎn)階段間不存在中間緩沖區(qū)，故當(dāng)后一階段的機(jī)器處于繁忙狀態(tài)時(shí)上游加工完的工件會(huì)停留在當(dāng)前機(jī)器，直至后一階段的機(jī)器釋放出來，當(dāng)工件停留在當(dāng)前機(jī)器時(shí)，該機(jī)器無法處理其它工件。因此，若s

圖2 不同機(jī)器分配策略時(shí)3個(gè)工件完成時(shí)間的比較

(4)工件完成當(dāng)前生產(chǎn)階段s的加工后，由運(yùn)輸機(jī)等將其傳送至下個(gè)階段，即需運(yùn)輸時(shí)間Ys,s+1才能到達(dá)下階段的機(jī)器，因此，對(duì)于同一工件，它的相鄰兩道工序之間有Ens+Ys,s+1≤En,s+1-Tn,s+1,k，其中Ens為工件n在階段s的完成時(shí)間。

目標(biāo)設(shè)為最小化所有工件的加權(quán)完成時(shí)間之和，即

2 基于GA的優(yōu)化方法

GA已廣泛用于求解強(qiáng)NP-hard問題，它具有計(jì)算時(shí)間較短的優(yōu)點(diǎn)，但易過早收斂，為解決此問題，本文設(shè)計(jì)多種領(lǐng)域結(jié)構(gòu)提出了鄰域搜索方法以得到GA解的鄰域解，即，在每次迭代，執(zhí)行完GA的交叉和變異操作，將得到的子代與父代進(jìn)行比對(duì)，篩選出較優(yōu)個(gè)體，繼而對(duì)這些個(gè)體根據(jù)適應(yīng)度值進(jìn)行降序排列，對(duì)得到的序列中前40%的個(gè)體執(zhí)行鄰域搜索，從而有效提高了GA解的質(zhì)量。

2.1 GA解的生成過程

(1)染色體編碼及初始種群的產(chǎn)生

對(duì)于所研究的BFFP-UPM，當(dāng)工件選擇機(jī)器時(shí)利用隨機(jī)空閑機(jī)器篩選原則，為解決機(jī)器分配和每臺(tái)機(jī)器上工件的加工序列問題，提出了二維矩陣編碼方案，令每個(gè)矩陣對(duì)應(yīng)一個(gè)染色體，矩陣內(nèi)的每個(gè)元素表示一個(gè)基因位。首先確定基因位的取值范圍，然后應(yīng)用隨機(jī)自然整數(shù)賦值方式生成矩陣，為均衡機(jī)器加工任務(wù)，令取值服從均勻分布。圖3為染色體的二維矩陣編碼的表述，其中Kns表示工件n在階段s分配的機(jī)器號(hào)，服從[1,UMs]的均勻分布。

圖3 二維染色體編碼方案

應(yīng)用上述二維矩陣編碼方式隨機(jī)生成G個(gè)染色體矩陣，從而形成初始種群元胞組{X1,X2, …,XG}，如圖4所示。

圖4 初始種群元胞組

(2)解碼

產(chǎn)生染色體后需通過解碼得到可行解。當(dāng)工件n完成生產(chǎn)階段s的加工后，需確定它在下一階段被分配機(jī)器ums+1,k的加工時(shí)間段，而這臺(tái)機(jī)器的空閑時(shí)間段的選擇依賴于在機(jī)器k上加工的前一個(gè)工件的釋放時(shí)間Cn-1,s和工件n在階段s的完成時(shí)間Ens，若Ens+Ys,s+1

圖5 N=6的最優(yōu)調(diào)度甘特圖

步驟1 計(jì)算第一個(gè)工件在所有階段的完成時(shí)間和開始時(shí)間ST1s，并標(biāo)記機(jī)器占用時(shí)間段

步驟2 計(jì)算第n個(gè)工件在s階段的探索是否存在空閑的時(shí)間點(diǎn)PTns(n>1)

步驟3 設(shè)置一個(gè)計(jì)數(shù)點(diǎn)a=0，最大時(shí)間點(diǎn)為MT，循環(huán)[PTns,MT]時(shí)間段，在每次循環(huán)時(shí)刻t中，當(dāng)機(jī)器k空閑時(shí)，執(zhí)行a=a+1，直到a=Tnsk+1，那么工件n在s階段的完成時(shí)間Ens=t和開始時(shí)間STns=Ens-Tnsk，再次標(biāo)記機(jī)器占用時(shí)間段。

步驟4 計(jì)算第n個(gè)工件在s階段的機(jī)器k阻塞時(shí)間Bnsk=STn,s+1-Ens-Ys,s+1(s

步驟5 計(jì)算目標(biāo)值TWC。

(3)基于適應(yīng)度函數(shù)的選擇操作

采用輪盤賭規(guī)則從當(dāng)前種群篩選出執(zhí)行交叉和變異操作的染色體，個(gè)體選中的概率由對(duì)應(yīng)的適應(yīng)度值決定，因此，在進(jìn)行選擇操作前，需計(jì)算適應(yīng)度函數(shù)以對(duì)個(gè)體進(jìn)行評(píng)估，由于BFFP-UPM的目標(biāo)是最小化總加權(quán)完成時(shí)間，定義個(gè)體X的適應(yīng)度函數(shù)為

(4)交叉操作

為了擴(kuò)大解的搜索范圍，同時(shí)調(diào)整工件的加工序列和機(jī)器分配，采用單點(diǎn)倒置交叉，設(shè)計(jì)基于工件和基于機(jī)器的兩種交叉方式，過程如下：

步驟1 隨機(jī)選擇兩個(gè)父代染色體Z1和Z2；

步驟2 隨機(jī)產(chǎn)生一個(gè)[0, 1]之間的小數(shù)r，若交叉概率pc>r，則執(zhí)行步驟3；否則，Z1和Z2直接成為子代染色體O1和O2；

步驟3 任意選擇一種交叉方式，若選擇采用基于工件的交叉方式，則執(zhí)行步驟4；否則執(zhí)行步驟5；

步驟4 隨機(jī)產(chǎn)生工件號(hào)μ(1≤μ≤N)，將染色體Z1中前μ行基因與染色體Z2中后N-μ行基因進(jìn)行交叉組合生成子代染色體O1和O2，如圖6(a)所示(以N=3,S=2為例)；

圖6 單點(diǎn)交叉方式類型

步驟5 隨機(jī)選擇機(jī)器位η(1≤η≤S)，將染色體Z1中前η列基因與染色體Z2中后S-η列基因進(jìn)行交叉組合生成子代染色體O1和O2，如圖6(b)所示(以N=2，S=3為例)。

(5)變異操作

變異操作是對(duì)種群個(gè)體進(jìn)一步篩選擇優(yōu)的過程，采用單點(diǎn)變異，隨機(jī)選擇一個(gè)基因ξ重新安排機(jī)器編號(hào)，如圖7所示。

圖7 基于基因的單點(diǎn)變異方式

2.2 基于LS的GA新解更新過程

為提高GA的搜索能力，考慮到上述二維矩陣編碼方式，借鑒文獻(xiàn)[22]，提出了基于工件的多點(diǎn)交換(JME)、基于機(jī)器號(hào)的單點(diǎn)交換(MNSE)和基于工件的多點(diǎn)變異(JMM)這3種鄰域生成規(guī)則。計(jì)算GA產(chǎn)生的G個(gè)個(gè)體的適應(yīng)度值，將這些個(gè)體按照其適應(yīng)度值的降序進(jìn)行排列，從中選取排在前面的40%個(gè)個(gè)體，對(duì)這些個(gè)體Z執(zhí)行如下過程：

步驟1 設(shè)置最大迭代數(shù)IT，令it=1，BS=Z，BF=FZ；

步驟2 從JME，MNSE和JMM中隨機(jī)選擇一種規(guī)則NS：

若NS=JME，則隨機(jī)產(chǎn)生兩個(gè)工件號(hào)λ和γ(1≤λ,γ≤N)，交換相應(yīng)的機(jī)器號(hào)，如圖8所示。

圖8 基于工件的多點(diǎn)交換

若NS=MNSE，則隨機(jī)選擇一個(gè)生產(chǎn)階段σ(1≤σ≤S)的兩個(gè)機(jī)器號(hào)，將其進(jìn)行交換，如圖9所示。

圖9 基于機(jī)器號(hào)的單點(diǎn)交換

若NS=JMM，則隨機(jī)產(chǎn)生兩個(gè)工件號(hào)λ和γ(1≤λ,γ≤N)，對(duì)其相應(yīng)的機(jī)器號(hào)重新分派，如圖10所示。

圖10 基于工件的多點(diǎn)變異

步驟3 由NS生成新個(gè)體Z′，計(jì)算適應(yīng)度值FZ′，若FZ′>BF，則更新可行解，BS=Z′，BF=FZ′，否則保留原解；

步驟4 令it=it+1，若it

步驟5 輸出BS和BF。

3 實(shí)驗(yàn)測試與分析

為評(píng)估所提算法的有效性，分別實(shí)現(xiàn)傳統(tǒng)GA(TGA)和NEH-IGA[19]，IAGA[23]以及本文提出的融合局部搜索和GA的優(yōu)化算法EGA&LS，所有測試均采用Matlab R2014a編程，在CPU為AMD A8-4500M,1.9 GHz，內(nèi)存為4.00 G的計(jì)算機(jī)上運(yùn)行。

實(shí)驗(yàn)數(shù)據(jù)隨機(jī)產(chǎn)生如下。Tnsk服從[1, 8]的均勻分布；Rn和Ys-1,s均滿足U～[1, 5]的均勻分布；Wn服從U～[0, 1]；N∈{20, 50, 80, 100}；S∈{2, 3, 4}；每個(gè)生產(chǎn)階段所含的不相關(guān)并行機(jī)數(shù)量包括A、B和C這3種類型：A類，UMs=3，即所有階段的并行機(jī)數(shù)相同；B類，UMs滿足[1, 5]的均勻分布，即每個(gè)階段并行機(jī)數(shù)在[1, 5]之間隨機(jī)產(chǎn)生；C類，UMs=5。

3.1 中小規(guī)模問題的實(shí)例測試

在中小規(guī)模實(shí)例問題中工件數(shù)N取為20和50,UMs∈{A,B,C},S∈{2, 3, 4}, 則{N,UMs,S}的不同組合共產(chǎn)生18種不同規(guī)模問題，每個(gè)問題規(guī)模隨機(jī)測試10組實(shí)例，故本節(jié)共執(zhí)行了180次測試，得到如表1所示的結(jié)果，圖11表示N=20和50時(shí)4種算法求解得到的目標(biāo)值變化趨勢(S=2,UMs=5)。

圖11 中小規(guī)模問題目標(biāo)變化趨勢

由表1可以總結(jié)出：

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

(1)當(dāng)工件數(shù)為20時(shí)，在平均運(yùn)行時(shí)間247.492 s內(nèi)，由TGA、NEH-IGA、IAGA和EGA&LS求解得到的總加權(quán)完成時(shí)間平均值分別為329.525、320.888、325.897和310.594，相對(duì)于TGA、NEH-IGA、IAGA和EGA&LS求解性能分別提升了7.491%、4.139%、7.491%；

(2)當(dāng)工件數(shù)為50時(shí)，在平均運(yùn)行時(shí)間874.715 s內(nèi)，由TGA、NEH-IGA、IAGA和EGA&LS得到的總加權(quán)完成時(shí)間平均值分別為1443.380、1406.949、1427.272和1352.000，相較于TGA、IAGA、NEH-IGA這3種算法，改進(jìn)率IR值分別為7.519%、4.803%、6.402%。

3.2 大規(guī)模問題的實(shí)例測試

在工件數(shù)N取為80和100的大規(guī)模問題中，同上節(jié)類似，也運(yùn)行了180組實(shí)驗(yàn)測試，得到如表2結(jié)果所示的實(shí)驗(yàn)結(jié)果，圖12表示N取為80和100時(shí)4種算法求解得到的目標(biāo)值變化趨勢(S=2,UMs=5)。

圖12 大規(guī)模問題的目標(biāo)變化趨勢

從表2可以看出：

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

(1)當(dāng)工件數(shù)為80時(shí)，在總平均運(yùn)行時(shí)間1200 s內(nèi)，經(jīng)TGA、NEH-IGA、IAGA和EGA&LS這4種算法運(yùn)行，TGA得到的結(jié)果最差，求解得到的平均目標(biāo)值為4030.549，EGA&LS求解質(zhì)量最好，得到的平均總加權(quán)完成時(shí)間為3716.833，相對(duì)于TGA、NEH-IGA、IAGA，所提算法的改進(jìn)率IR值分別為8.527%、5.833%、7.795%。

(2)當(dāng)工件數(shù)為100時(shí)，在總平均運(yùn)行時(shí)間1200 s內(nèi)，由求解性能最差的TGA運(yùn)行得到的目標(biāo)值平均為6302.079，計(jì)算效果最好的EGA&LS得到平均總加權(quán)完成時(shí)間為5791.812，相對(duì)于TGA、NEH-IGA以及IAGA這3種算法，所提EGA&LS算法求解性能分別提升了8.886%、5.987%、7.992%。

3.3 結(jié)果分析

(1)對(duì)于所有規(guī)模問題，在總平均運(yùn)行時(shí)間880.552 s內(nèi)，由TGA、NEH-IGA、IAGA和EGA&LS計(jì)算得到的目標(biāo)平均值分別為3026.383、2954.736、3001.327和2792.809。相較于TGA、NEH-IGA、IAGA，所提算法得到的總加權(quán)完成時(shí)間目標(biāo)分別改善了8.106%、5.190%和7.133%，這表明在相同的CPU時(shí)間內(nèi)所提算法能得到較高質(zhì)量的近優(yōu)解。

(2)當(dāng)工件數(shù)相同時(shí)，隨著不相關(guān)并行機(jī)數(shù)量的增加，總加權(quán)完成時(shí)間整體呈下降趨勢，這是由于并行機(jī)的增多會(huì)降低工件對(duì)機(jī)器的競爭程度，使得問題更容易求解。

(3)圖11～圖12的變化趨勢圖呈現(xiàn)了不同規(guī)模的具體實(shí)例的目標(biāo)值變化趨勢。由此可看出，隨著問題規(guī)模的擴(kuò)大，4種算法求解得到的目標(biāo)值均呈上升趨勢，盡管NEH-IGA在迭代前期表現(xiàn)良好，但所提出的EGA&LS在迭代后期收斂速度較快，而且解的質(zhì)量也更好，由此說明，引入JME、MNSE和JMM這3種鄰域結(jié)構(gòu)在很大程度上擴(kuò)大了解得搜索范圍，改善了解的質(zhì)量。

(4)圖13表示不同規(guī)模下所提算法相對(duì)于3種算法改進(jìn)率變化曲線，由圖13可知：隨著問題規(guī)模的擴(kuò)大，EGA&LS相對(duì)TGA、NEH-IGA和IAGA的改進(jìn)率逐漸增加，因此，所提出算法在求解質(zhì)量上表現(xiàn)更佳，這種優(yōu)勢隨問題規(guī)模的增大而更突顯。

4 結(jié)束語

本文研究了以最小化總加權(quán)完成時(shí)間為目標(biāo)的BFFP-UPM，考慮工件動(dòng)態(tài)到達(dá)特征和運(yùn)輸時(shí)間，提出了一種有效的EGA&LS算法。應(yīng)用二維矩陣編碼方案，設(shè)計(jì)基于工件和基于機(jī)器的兩種單點(diǎn)交叉操作和一種基于基因的單點(diǎn)變異方式；為避免GA過早陷入局部最優(yōu)，設(shè)計(jì)并引入JME、MNSE和JMM這3種鄰域生成規(guī)則更新GA解。仿真實(shí)驗(yàn)測試了多達(dá)100個(gè)工件的問題規(guī)模，通過EGA&LS與TGA、NEH-IGA以及IAGA的對(duì)比測試，結(jié)果表明，所提出的EGA&LS算法對(duì)于不同規(guī)模問題的求解均表現(xiàn)出較好的求解能力，尤其是大規(guī)模問題。進(jìn)一步的研究可圍繞下述方面展開：①零等待方式下含不相關(guān)并行機(jī)的FFP；②用EGA&LS算法求解多目標(biāo)BFFS-UPM問題；③將多種領(lǐng)域結(jié)構(gòu)思想運(yùn)用在模擬退火、人工蜂群等智能算法中來改進(jìn)GA；④采用參數(shù)自適應(yīng)調(diào)整策略或者引進(jìn)啟發(fā)式算法改進(jìn)初始種群解的質(zhì)量。