王皓宇

(武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070)

檢測車間一般為混合流水車間，并且不設(shè)置中間緩沖區(qū)。中間緩沖為零的混合流水車間調(diào)度問題也被稱為帶阻塞混合流水車間調(diào)度問題(hybrid flow shop scheduling problem with blocking,HFSP-B)，更符合實際的生產(chǎn)環(huán)境[1]。隨著對流水車間調(diào)度問題的研究，近些年有越來越多的文獻(xiàn)考慮了更符合實際生產(chǎn)環(huán)境的約束。Ribas等[2]使用迭代貪婪算法求解了分布式環(huán)境下的阻塞流水車間調(diào)度問題，并以最小化總延遲時間為目標(biāo)。孟磊磊等[3]針對帶阻塞限制的混合流水車間調(diào)度問題，建立了4種不同的整數(shù)規(guī)劃模型，并用改進(jìn)回溯搜索算法進(jìn)行求解。Liu等[4]為有限緩沖的流水車間建立了一個通用模型，模型里考慮了緩沖有限、緩沖為零和無等待3種情況，并提出了一種結(jié)合問題特征的啟發(fā)式算法。軒華等[5]將有限緩沖的混合流水車間調(diào)度轉(zhuǎn)換為帶阻塞的混合流水車間調(diào)度，并混合了遺傳算法和禁忌搜索對問題進(jìn)行求解。

車間調(diào)度通常涉及多個目標(biāo)同時優(yōu)化，其結(jié)果往往不是一個最優(yōu)解，而是符合Pareto最優(yōu)解概念的一組解[6-7]。目前有大量文獻(xiàn)致力于研究一種高效的算法來求解多目標(biāo)車間調(diào)度問題。蔣增強(qiáng)等[8]使用血緣變異對非支配排序遺傳算法進(jìn)行改進(jìn)，并考慮了能源消耗、最大完工時間、加工成本和質(zhì)量成本4個目標(biāo)。Wang等[9]使用NSGA-II(non-dominated sorted genetic algorithm-Ⅱ)算法求解了不確定加工時間條件下的流水車間調(diào)度問題，并加入了局部模擬退火算子和與場景相適應(yīng)的鄰域搜索算子。Gong等[10]考慮了阻塞和分批兩個約束，以最小化最大完成時間和總提前時間為目標(biāo)，使用人工蜂群算法求解。

筆者在HFSP-B模型的基礎(chǔ)上，根據(jù)現(xiàn)實生產(chǎn)環(huán)境，考慮了加工次數(shù)對加工效率和加工合格率的影響，以最小化最大完成時間和最小化總質(zhì)量成本為目標(biāo)展開了研究。

1 問題描述和建模

1.1 問題描述

考慮質(zhì)量成本和加工次數(shù)的HFSP-B描述如下：混合流水車間由m個階段串行組成，階段i(i=1,2，…,m)有ni個相同的并行機(jī)，ni≥1且至少存在一個階段使得ni>1。每個工件必須在其路徑上的每個階段選擇一臺機(jī)器進(jìn)行加工。Pik表示工件k(k=1,2，…,p)在階段i的加工時間。工件k在階段i的完成時間被記為Cik，并且Dik是它在階段i的離開時間。加工過程不能被打斷意味著工件k在階段i的開始加工時間Sik為Cik-Pik。工件k在階段i完成后，需要其在階段i+1分配的機(jī)器可用時再離開。如果在Cik時刻，工件k在階段i+1分配的機(jī)器被占據(jù)，那么其會被阻塞在當(dāng)前階段的機(jī)器上，直到Dik=Si+1,k，如圖1所示，圖1中的斜線部分表示阻塞狀態(tài)。另外，至少存在一個階段，其并行機(jī)加工工件的合格率存在差異，Qijk表示階段i的機(jī)器j(j=1,2，…,ni)在加工工件k時的質(zhì)量成本，0

圖1 阻塞機(jī)制

1.2 調(diào)度模型

建立一個以最小化完成時間和總質(zhì)量成本最小為目標(biāo)的帶阻塞混合流水車間調(diào)度問題模型，其中的符號含義如表1所示。

表1 模型符號及說明

優(yōu)化模型為：

f1=minCmax,k=1,2，…,p

(1)

(2)

Cik=Sik+Pik,i?S,k=1,2，…,p

(3)

Cik=Sik+Pik+EPik,i∈S,k=1,2，…,p

(4)

Sik≥Ci-1,k,i=2,3，…,m,k=1,2，…,p

(5)

Dik=Si+1,k,i=1,2，…,m-1,k=1,2，…,p

(6)

(7)

yikk′+yik′k≤1,i=1,2，…,m,

k=1,2,…,p,k′=1,2，…,p,k≠k′

(8)

Sik′≥Dik+L×(3-yikk′-xijk-xijk′),

i=1,2，…,m,k=1,2，…,p,k≠k′

(9)

其中，Cmax為最大完工時間，式(1)為最小化最大完工時間；式(2)為最小化總質(zhì)量成本；式(3)和式(4)為處理過程不允許被打斷；式(5)為工件只能在一道工序完成后才能開始下一道工序；式(6)為阻塞關(guān)系，只有當(dāng)工件的下一道工序可以被加工時才允許離開當(dāng)前機(jī)器，否則會被阻塞；式(7)為每個工件在每個階段只能選擇一臺機(jī)器；式(8)和式(9)為每臺機(jī)器最多同時處理一個工件。

2 改進(jìn)的NSGA-II算法

筆者提出了一種改進(jìn)的NSGA-II算法來求解上述問題。改進(jìn)NSGA-II的流程如圖2所示。這些改進(jìn)的程序主要包括：編解碼規(guī)則，精英保留機(jī)制，多種遺傳算子，以及鄰域搜索策略。

圖2 改進(jìn)NSGA-II算法流程圖

2.1 染色體表達(dá)

在將改進(jìn)NSGA-II算法應(yīng)用于問題求解之前，編碼是一個非常重要的部分。本文的多目標(biāo)調(diào)度不僅需要同時處理工件的輸入序列和每個階段的機(jī)器分配，并且還要決定工件的加工次數(shù)。因此，筆者提出了由序列向量X、分配矩陣Y以及次數(shù)矩陣Z3部分組成的染色體結(jié)構(gòu)。其中，向量X決定了工件的輸入序列，矩陣Y決定了每個階段工件分配的機(jī)器，矩陣Z決定了工件在有質(zhì)量差異的階段S中需要額外加工的次數(shù)。圖3為一個3階段4工件的解的染色體表達(dá)式，階段S={3}可以進(jìn)行多次加工。

圖3 一個解的染色體表達(dá)

2.2 交叉與變異

交叉是種群進(jìn)化的基本方式，通過交換兩個父代個體中的基因來獲得新的個體。鑒于本文的染色體由3部分組成，這里選擇3種不同的交叉方式，各部分根據(jù)交叉概率Pc決定是否交叉。對于輸入序列部分，選擇的是基于順序的交叉(order crossover, OX)，即隨機(jī)產(chǎn)生兩個交叉點，將其中一個父代的中間部分復(fù)制給子代，然后根據(jù)另一個父代的基因順序補(bǔ)齊剩余基因。對于機(jī)器分配部分，則選擇部分匹配交叉(partial-mapped crossover, PMX)，即隨機(jī)產(chǎn)生兩個交叉點，交換中間部分的基因片段。對于額外次數(shù)部分，采用的是基于位置的交叉(position-based crossover, PBX)，首先隨機(jī)選擇多個基因位，然后交換這些基因位上的基因。

變異是保持種群多樣性的基本方式，通過改變、插入或重組個體中的基因來產(chǎn)生新的個體。本文對序列向量部分采用的是重組變異，首先隨機(jī)選擇兩個變異點，然后逆序排列中間的基因片段。其余部分采用多點變異，對存在多種選擇的基因位上的每個點以變異率Pm進(jìn)行判定，改變后的基因碼要與原來的值不同。

2.3 鄰域搜索

鄰域搜索是對NSGA-II算法在局部搜索能力上的補(bǔ)充，是一種主動尋找更優(yōu)解的策略。為了不破壞解的特征，鄰域搜索應(yīng)該發(fā)生在一個較小的范圍。根據(jù)解的染色體表達(dá)方式，制定了3種鄰域結(jié)構(gòu)。

(1)針對輸入序列部分，采用插入的方式搜索鄰域。首先隨機(jī)選擇一個基因位，將該基因隨機(jī)插入到其他位置。

(2)針對機(jī)器分配部分，采用重組的方式，隨機(jī)交換各產(chǎn)品選擇的機(jī)器。即首先隨機(jī)選擇一個存在并行機(jī)的階段，然后對該階段機(jī)器碼中的基因片段進(jìn)行隨機(jī)排列。

(3)針對額外次數(shù)部分，鄰域搜索朝著兩個方向進(jìn)行，即增大和縮小加工次數(shù)。具體操作為隨機(jī)選擇一個不為最大值的基因位和一個不為0的基因位，分別使該基因位的值加一和減一。若所有基因位均為最大值，則只執(zhí)行減一操作，若所有基因位均為0，則只執(zhí)行加一操作。

2.4 產(chǎn)生新種群

在經(jīng)過遺傳操作和鄰域搜索后，首先需要剔除重復(fù)個體，保證種群的多樣性。然后判斷當(dāng)前個體數(shù)量和種群規(guī)模的大小，如果小于種群規(guī)模，則加入擾動種群，即通過初始化的方式隨機(jī)產(chǎn)生個體使個體數(shù)量達(dá)到種群規(guī)模；如果大于種群規(guī)模，則通過非支配等級和擁擠度進(jìn)行排序，剔除超出種群規(guī)模的個體。

3 實驗研究

通過實驗研究評估所提出的改進(jìn)NSGA-II算法在處理問題時的性能。所有算法都通過Matlab編程，運(yùn)行在一臺Windows 7操作系統(tǒng)，Inter core i7，2.39 GHz，8 GB RAM的個人計算機(jī)上。

隨機(jī)產(chǎn)生了15種測試數(shù)據(jù)集，問題的大小由工件數(shù)和階段數(shù)決定，階段數(shù)m=[3,4,5]，工件數(shù)p=[10,20,30,40,50]。每個階段的機(jī)器數(shù)量在1～4中隨機(jī)產(chǎn)生，并確保至少有一個階段存在并行機(jī)，工件在每個階段的加工時間PT服從4～9的均勻分布，隨機(jī)產(chǎn)生部分可多次加工的階段，每次額外加工時間EPT=0.8PT，質(zhì)量成本Q服從0～1的均勻分布。

為了驗證提出的改進(jìn)NSGA-II算法在求解阻塞混合流水車間調(diào)度問題時的有效性，筆者將其與NPGA(niched pareto genetic algorithm)算法、SPEA2(strength pareto evolutiorary algorithm 2)算法及改進(jìn)前的NSGA-II算法比較。這些算法的參數(shù)設(shè)置為種群規(guī)模50，迭代次數(shù)200，交叉率0.9，變異率0.1。為了評估多目標(biāo)算法的帕累托前沿，采用了反世代距離(inverted generational distance, IGD)指標(biāo)。每個數(shù)據(jù)集運(yùn)行10次，取這10次結(jié)果IGD的平均值展示在表2中。從表2可知，所提出的改進(jìn)NSGA-II算法在求解大部分問題時IGD明顯小于其他算法，說明其擁有更好的收斂性和多樣性。與改進(jìn)前的NSGA-II算法相比也具有較大的優(yōu)勢，這說明對算法的改進(jìn)是有效的。

表2 實驗結(jié)果的IGD評估

圖4為一次實驗中各算法最優(yōu)結(jié)果的Pareto前沿，從圖4可知，所提出的改進(jìn)NSGA-II算法獲得的非支配解更靠近圖形的左下方并且分布的范圍較廣，說明其獲得的非支配解相比其他算法獲得的解質(zhì)量更好。圖5為由改進(jìn)NSGA-II算法求得的一個非支配解解碼得到的甘特圖，圖5中的虛線框表示機(jī)器處于阻塞狀態(tài)。

圖4 各算法的帕累托前沿

圖5 一個非支配解的調(diào)度圖

4 結(jié)論

以帶阻塞的混合流水車間調(diào)度問題為基礎(chǔ)，考慮了允許通過多次加工來提高加工質(zhì)量的情況，以最小化最大完成時間和總質(zhì)量成本為目標(biāo)建立了問題模型。提出了一個改進(jìn)NSGA-II算法來解決這個實際問題。提出的改進(jìn)NSGA-II算法主要包括結(jié)合問題特征編碼，多樣的遺傳操作算子，與染色體結(jié)構(gòu)相適應(yīng)的領(lǐng)域搜索以及添加擾動種群。通過隨機(jī)生成的案例進(jìn)行測試，驗證了所提出的改進(jìn)NSGA-II算法的效率。與NPGA、SPEA2算法進(jìn)行了比較，結(jié)果顯示在大多數(shù)情況下，所提出的改進(jìn)NSGA-II算法表現(xiàn)更佳。