軒 華，鄭倩倩，李 冰

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

0 引 言

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

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

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

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

1 問題描述

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

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

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

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

圖2 不同機器分配策略時3個工件完成時間的比較

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

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

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

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

2.1 GA解的生成過程

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

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

圖3 二維染色體編碼方案

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

圖4 初始種群元胞組

(2)解碼

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

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

步驟1 計算第一個工件在所有階段的完成時間和開始時間ST1s，并標記機器占用時間段

步驟2 計算第n個工件在s階段的探索是否存在空閑的時間點PTns(n>1)

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

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

步驟5 計算目標值TWC。

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

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

(4)交叉操作

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

步驟1 隨機選擇兩個父代染色體Z1和Z2；

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

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

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

圖6 單點交叉方式類型

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

(5)變異操作

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

圖7 基于基因的單點變異方式

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

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

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

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

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

圖8 基于工件的多點交換

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

圖9 基于機器號的單點交換

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

圖10 基于工件的多點變異

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

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

步驟5 輸出BS和BF。

3 實驗測試與分析

為評估所提算法的有效性，分別實現(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的計算機上運行。

實驗數(shù)據(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}；每個生產(chǎn)階段所含的不相關(guān)并行機數(shù)量包括A、B和C這3種類型：A類，UMs=3，即所有階段的并行機數(shù)相同；B類，UMs滿足[1, 5]的均勻分布，即每個階段并行機數(shù)在[1, 5]之間隨機產(chǎn)生；C類，UMs=5。

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

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

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

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

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

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

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

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

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

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

從表2可以看出：

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

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

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

3.3 結(jié)果分析

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

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

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

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

4 結(jié)束語

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