考慮可變加工次數(shù)的多目標(biāo)阻塞混合流水車間調(diào)度

王皓宇

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

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

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

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

1 問(wèn)題描述和建模

1.1 問(wèn)題描述

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

圖1 阻塞機(jī)制

1.2 調(diào)度模型

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

表1 模型符號(hào)及說(shuō)明

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

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

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

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

2.1 染色體表達(dá)

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

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

2.2 交叉與變異

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

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

2.3 鄰域搜索

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

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

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

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

2.4 產(chǎn)生新種群

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

3 實(shí)驗(yàn)研究

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

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

為了驗(yàn)證提出的改進(jìn)NSGA-II算法在求解阻塞混合流水車間調(diào)度問(wèn)題時(shí)的有效性，筆者將其與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。為了評(píng)估多目標(biāo)算法的帕累托前沿，采用了反世代距離(inverted generational distance, IGD)指標(biāo)。每個(gè)數(shù)據(jù)集運(yùn)行10次，取這10次結(jié)果IGD的平均值展示在表2中。從表2可知，所提出的改進(jìn)NSGA-II算法在求解大部分問(wèn)題時(shí)IGD明顯小于其他算法，說(shuō)明其擁有更好的收斂性和多樣性。與改進(jìn)前的NSGA-II算法相比也具有較大的優(yōu)勢(shì)，這說(shuō)明對(duì)算法的改進(jìn)是有效的。

表2 實(shí)驗(yàn)結(jié)果的IGD評(píng)估

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

圖4 各算法的帕累托前沿

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

4 結(jié)論

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