羅 煥，陳浩杰，宋小欣，張 劍

(西南交通大學(xué) 機(jī)械工程學(xué)院,四川 成都 610031)

0 引言

作業(yè)車間調(diào)度問題是最常見的調(diào)度問題之一，長期以來眾多學(xué)者在該領(lǐng)域進(jìn)行了深入廣泛的研究[1-3]。目前的研究在構(gòu)建調(diào)度模型時(shí)，一般將機(jī)器緩存容量設(shè)為無限大，忽略緩存容量對(duì)作業(yè)調(diào)度的影響[4]，導(dǎo)致實(shí)際生產(chǎn)過程中對(duì)許多作業(yè)車間數(shù)學(xué)模型不適用。機(jī)器間的緩存可以容納加工設(shè)備單元后的產(chǎn)品零件或在相鄰的工藝步驟中供應(yīng)給下一個(gè)設(shè)備單元[5]，因此生產(chǎn)中緩存對(duì)于緩解生產(chǎn)線的突然變化至關(guān)重要。在追求“零庫存”甚至“零緩存”從而減少在制品的精益生產(chǎn)中，緩存容量極其有限，顯然考慮緩存約束下的作業(yè)車間調(diào)度數(shù)學(xué)模型和求解方法是解決這些實(shí)際生產(chǎn)問題的有利手段。

帶有緩存約束的作業(yè)調(diào)度問題可分為阻塞約束下的作業(yè)車間調(diào)度問題(Blocking Job Shop Scheduling, BJSS)和有限緩存約束下的作業(yè)車間調(diào)度問題(Limited-Buffer Job Shop Scheduling, LBJSS)。在前一問題的研究中，ZENG等[6]提出一個(gè)整數(shù)非線性數(shù)學(xué)規(guī)劃模型來描述帶有輸出緩存的作業(yè)車間調(diào)度問題，并提出了求解問題的可行解和局部搜索兩階段算法；PRANZO等[7]對(duì)阻塞作業(yè)調(diào)度問題的兩個(gè)擴(kuò)展問題——允許交換的阻塞作業(yè)車間調(diào)度和不允許交換的阻塞作業(yè)車間調(diào)度進(jìn)行研究，并提出迭代貪婪算法對(duì)問題進(jìn)行求解；LOUAQAD等[8]研究了無等待阻塞運(yùn)輸作業(yè)車間調(diào)度問題，并建立了混合整數(shù)線性規(guī)劃模型，提出了一種基于優(yōu)先級(jí)規(guī)則的構(gòu)造性啟發(fā)式算法對(duì)問題進(jìn)行求解。在有關(guān)有限緩存約束下的作業(yè)車間調(diào)度研究中，BRUCKER等[9]將LBJSS分為與機(jī)器相關(guān)的輸出緩存、與機(jī)器有關(guān)的輸入緩存、與工件相關(guān)的緩存3類問題，并給出帶有緩存區(qū)的作業(yè)調(diào)度問題解的一個(gè)緊湊表示；WITT等[10]設(shè)計(jì)了3種啟發(fā)式算法來保證找到高質(zhì)量的LBJSS解，并驗(yàn)證了所提出的方法有效性；LIU等[11]研究了更為普遍的帶有4種緩存約束(無等待、無緩存、有限緩存、無限緩存)的作業(yè)車間調(diào)度問題，對(duì)關(guān)鍵問題性質(zhì)進(jìn)行了深入的分析，建立一個(gè)適用的混合整數(shù)模型，并提出一種高效的啟發(fā)式算法對(duì)問題進(jìn)行求解；曾程寬等[12]針對(duì)緩存區(qū)間有限條件下的作業(yè)車間調(diào)度問題，以最小化完工時(shí)間為目標(biāo)建立非線性混合整數(shù)模型，并提出基于鄰域搜索的兩階段算法對(duì)問題進(jìn)行求解。

可見，目前已有的研究對(duì)帶有緩存約束的作業(yè)車間調(diào)度問題特征進(jìn)行了分析，但是在求解方法方面研究甚少，且解決思路集中在粗粒度的工件層級(jí)，由于問題復(fù)雜性超越傳統(tǒng)作業(yè)車間調(diào)度問題，基本上都采用啟發(fā)式算法對(duì)問題求解。本文針對(duì)該問題，將解決方案從工件層級(jí)擴(kuò)展到工序?qū)蛹?jí)，首次提出元啟發(fā)式算法對(duì)問題進(jìn)行求解，即采用遺傳算法進(jìn)行求解，并設(shè)計(jì)工序調(diào)整方式以獲得合法解，結(jié)合自適應(yīng)交叉變異概率和良種交叉算子對(duì)算法進(jìn)行改進(jìn)，以避免遺傳算法過早收斂和陷入局部最優(yōu)的問題。最后通過實(shí)驗(yàn)驗(yàn)證算法的有效性以及求解結(jié)果的優(yōu)越性。

1 帶有緩存約束的作業(yè)車間調(diào)度模型

1.1 問題描述

帶有緩存約束的作業(yè)車間調(diào)度問題可以描述為：有n個(gè)獨(dú)立的、無搶占式的作業(yè)必須在m臺(tái)機(jī)器上加工，考慮緩存容量對(duì)作業(yè)進(jìn)行機(jī)器最優(yōu)分配和排序，通常優(yōu)化目標(biāo)是最小化完工時(shí)間。每道工序都必須在給定的工藝路線上加工，但是不同的作業(yè)對(duì)應(yīng)的工藝路線不一樣。在一臺(tái)機(jī)器上只能處理工件的一道工序，且每臺(tái)機(jī)器一次只能處理一道工序，工件某道工序一旦在設(shè)備上開始加工直至加工完成不能被中斷，每臺(tái)機(jī)器都有指定的緩存容量。與加工時(shí)間、阻塞時(shí)間或存儲(chǔ)時(shí)間相比，機(jī)器之間的工件轉(zhuǎn)移時(shí)間可以忽略不計(jì)，因此在本研究中不考慮工件轉(zhuǎn)移時(shí)間。當(dāng)工件在非最后一道的某道工序機(jī)器上加工完成后，如果其下一道工序?qū)?yīng)加工機(jī)器空閑，則可以進(jìn)入下一臺(tái)機(jī)器進(jìn)行加工;若下一臺(tái)機(jī)器處于繁忙狀態(tài)時(shí)，則判斷當(dāng)前機(jī)器對(duì)應(yīng)的緩存是否可用，可用則將工件移入當(dāng)前機(jī)器對(duì)應(yīng)的緩存(該緩存為機(jī)器對(duì)應(yīng)的輸出緩存)，否則當(dāng)前機(jī)器緩存被占滿的情況下，工件停留在機(jī)器上并對(duì)機(jī)器造成阻塞，阻礙后續(xù)工件在此機(jī)器上的加工。

1.2 符號(hào)和變量

數(shù)學(xué)模型中相關(guān)符號(hào)和變量說明：

(1)符號(hào)

n為工件數(shù)量;

m為機(jī)器數(shù)量;

j為工件索引，j=1,2,…,n;

J為工件集合;

Jj為工件j，Jj∈J;

k為機(jī)器索引，k=1,2,…,m;

M為機(jī)器集合;

Mk為機(jī)器k，Mk∈M;

pj為工件j的工序數(shù);

i為工件j在指定加工路線上的工序索引，i=1,2,…,pj;

Oij為工件j的第i道工序;

Pijk為工件j的第i道工序在機(jī)器Mk上的加工時(shí)間;

lk為機(jī)器Mk對(duì)應(yīng)的緩存容量。

(2)變量

Sijk為工件j的第i道工序在機(jī)器Mk上的開始加工時(shí)間;

Cijk為工件j的第i道工序在機(jī)器Mk上的加工完成時(shí)間，Cijk=Sijk+Pijk;

Bijk為工件j的第i道工序加工完成后在機(jī)器Mk上的阻塞時(shí)間;

Dijk為工件j的第i道工序加工完成后離開機(jī)器Mk的時(shí)間，Dijk=Cijk+Bijk;

STijk為工件j的第i道工序加工完成后在機(jī)器緩存中的存放時(shí)間;

Lijk為工件j的第i道工序離開機(jī)器緩存的時(shí)間，Lijk=STijk+Dijk;

1.3 數(shù)學(xué)模型

(1)

式中Cj為工件j的完工時(shí)間。

約束條件：

Pijk>0，i=1,2,…,pj；

j=1,2,…,n；k=1,2,…,m;

(2)

i=1,2,…,pj；j=1,2,…,n;

(3)

i=1,2,…,pj；j=1,2,…,n;

(4)

i=1,2,…,pj；k=1,2,…,m;

(5)

i=1,2,…,pj-1；j=1,2,…,n;

(6)

j=1,2,…,n;

(7)

Cj=max(Cijk)，i=1,2,…,pj。

(8)

其中：式(2)為工件的每道工序加工時(shí)間非負(fù)約束；式(3)為不同工件的工序之間無優(yōu)先級(jí)關(guān)系，同一工件要滿足工序間的工藝關(guān)系；式(4)為工件同一時(shí)刻只能在一臺(tái)機(jī)器上加工；式(5)為一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；式(6)為有限緩存約束，不包括每個(gè)作業(yè)的工藝路線中的最后一道工序，工件最后一道工序加工完成則視為離開生產(chǎn)系統(tǒng)不再占用資源，該情況下，Oij完成之后在緩存區(qū)bk中的離開時(shí)間必須等于其同一作業(yè)后一道工序Oi+1,j的開始時(shí)間；式(7)為阻塞約束，緩存不足的情況下會(huì)造成機(jī)器阻塞，不包括每個(gè)作業(yè)的工藝路線中的最后一道工序，該情況下，Oij完成之后Mk可能由于對(duì)應(yīng)的緩存被占滿而被阻塞；式(8)為一個(gè)工件的完工時(shí)間等于該工件所有工序的完工時(shí)間最大值，即工件最后一道工序的完工時(shí)間。

2 改進(jìn)遺傳算法

啟發(fā)式算法在可接受的計(jì)算時(shí)間內(nèi)能夠找到最好的解，但不一定能保證所得解的可行性及最優(yōu)性，甚至大多數(shù)情況下無法闡述所得解與最優(yōu)解之間的近似程度。采用啟發(fā)式算法求解帶有緩存約束的作業(yè)車間調(diào)度問題是以工件層級(jí)為編碼，按照每個(gè)工件的總加工時(shí)間大小進(jìn)行的排序，再基于這個(gè)排序進(jìn)行局部搜索操作，這種基于工件層級(jí)的編碼進(jìn)行的局部搜索很可能導(dǎo)致局部最優(yōu)，從而降低調(diào)度結(jié)果的精度。而元啟發(fā)式算法是啟發(fā)式算法的改進(jìn)，它是隨機(jī)算法與局部搜索算法相結(jié)合的產(chǎn)物。采用元啟發(fā)式算法求解帶有緩存約束的作業(yè)車間調(diào)度問題，將問題編碼從工件層級(jí)擴(kuò)展到工序?qū)蛹?jí)，基于工序排序進(jìn)行搜索操作，隨機(jī)產(chǎn)生工序排序以擴(kuò)大算法對(duì)問題的全局搜索范圍，避免局部最優(yōu)。在求解作業(yè)車間調(diào)度問題的元啟發(fā)式算法中，遺傳算法是運(yùn)用最廣泛的算法之一，對(duì)求解復(fù)雜多項(xiàng)式問題有較強(qiáng)的適用性，且一般能取得較優(yōu)的結(jié)果。

本文首先采用傳統(tǒng)的作業(yè)車間調(diào)度基于工序的編碼方式，將問題的解決方案從工件層級(jí)擴(kuò)展到工序?qū)蛹?jí)，為保證解的合法性，需要對(duì)緩存約束下的基因編碼進(jìn)行調(diào)整。遺傳算法適用性強(qiáng)，但是也存在不足，如遺傳算法在傳統(tǒng)遺傳算子的作用下，容易使一些優(yōu)良基因片段發(fā)生丟失，從而造成算法過早收斂以及在進(jìn)化后期搜索效率低等問題。本文設(shè)計(jì)了合理的工序調(diào)整方法進(jìn)行解碼，提出采用自適應(yīng)交叉變異概率結(jié)合良種交叉算子對(duì)算法進(jìn)行改進(jìn)。這種自適應(yīng)調(diào)節(jié)方法使算法在進(jìn)化前期，有較強(qiáng)的全局搜索能力，算法的全局搜索性隨著進(jìn)化的進(jìn)行慢慢減弱，而局部搜索能力慢慢增強(qiáng)，提高了算法效率和適用性。改進(jìn)遺傳算法流程如圖1所示。

改進(jìn)遺傳算法步驟如下：

(1)初始化參數(shù)。設(shè)置種群大小PopSize，代溝OPT，交叉概率為Pc1、Pc2，變異概率為Pm1、Pm2，最大迭代次數(shù)為Gmax。

(2)初始化種群。采用實(shí)數(shù)編碼隨機(jī)產(chǎn)生工序排序生成初始種群Initial_Pop。

(3)計(jì)算種群適應(yīng)度函數(shù)值。根據(jù)式(1)計(jì)算目標(biāo)函數(shù)值再將目標(biāo)函數(shù)值轉(zhuǎn)化為適應(yīng)度值。

(4)選擇操作。根據(jù)適應(yīng)度值和代溝OPT選擇個(gè)體，采用輪盤賭方式進(jìn)行選擇。

(5)交叉操作。根據(jù)選擇后的種群進(jìn)行良種交叉與整數(shù)交叉相結(jié)合，根據(jù)個(gè)體適應(yīng)度值和式(9)確定是否交叉。良種交叉是用種群的精英個(gè)體和選擇后的適應(yīng)度值較差的部分個(gè)體進(jìn)行交叉操作[14]。選擇操作后，除了進(jìn)行良種交叉?zhèn)€體外的其余個(gè)體進(jìn)行洗牌交叉。

(9)

式中：fmax表示種群中個(gè)體最大適應(yīng)度值;favg表示種群平均適應(yīng)度值;f′表示兩個(gè)交叉?zhèn)€體中較大的適應(yīng)度值;Pc1、Pc2表示最大、最小交叉概率。

(6)變異操作。根據(jù)個(gè)體適應(yīng)度值和式(10)采用兩點(diǎn)變異，隨機(jī)交換兩個(gè)不同工件的工序位置進(jìn)行變異。

(10)

式中：Pm1、Pm2表示最大、最小變異概率;f表示變異個(gè)體適應(yīng)度值。

(7)種群合并。采用精英保留策略，根據(jù)父代和子代個(gè)體適應(yīng)度值保留前10%的精英個(gè)體，剩下的個(gè)體用遺傳操作后的個(gè)體替換父代中的個(gè)體。

(8)判斷是否滿足最大迭代次數(shù)，滿足則輸出結(jié)果，不滿足則返回步驟(2)。

2.1 個(gè)體編碼

2.2 解碼操作

傳統(tǒng)作業(yè)車間調(diào)度的基于工序編碼的解碼方法只考慮工序約束和機(jī)器約束，沒有考慮緩存約束，因此解碼方式較簡單且不會(huì)產(chǎn)生工序間的沖突。而帶有緩存約束的作業(yè)車間調(diào)度的解碼方法相對(duì)復(fù)雜，除了考慮工序間的約束和機(jī)器約束以外，還需要考慮機(jī)器緩存約束的影響以及工序之間的沖突。運(yùn)用甘特圖對(duì)比分析兩種解碼方式的不同，如圖2所示。當(dāng)前需要安排工件4的第二道工序402進(jìn)行加工，按照傳統(tǒng)作業(yè)車間調(diào)度解碼方式得到工件4的第二道工序402在機(jī)器2上的加工甘特圖。

在帶有緩存約束下的作業(yè)車間調(diào)度解碼方式下會(huì)出現(xiàn)以下幾種情況：

(1)緩存容量充足時(shí)，如假設(shè)機(jī)器3的緩存容量為1，則在安排工件4的第二道工序402時(shí)需要考慮機(jī)器3的緩存是否夠用，若夠用，則得到如圖3所示的結(jié)果。

(2)緩存容量不足時(shí)，則會(huì)對(duì)機(jī)器形成阻塞，在這種條件下會(huì)發(fā)生不同的情況，如工件的工序401加工完成后先在機(jī)器3上存放一段時(shí)間直到機(jī)器緩存可用時(shí)刻，緩存可用時(shí)刻可能在機(jī)器2可用時(shí)刻之前或之后，如圖4a和4b所示。

(3)除上述兩種情況外還存在兩個(gè)工序之間沖突的情況，如工序401完成時(shí)刻到工序402開始加工時(shí)刻緩存不足且阻塞時(shí)間段機(jī)器3上有其他已安排的工序在加工(如圖5a)，這時(shí)需要對(duì)401進(jìn)行調(diào)整，調(diào)整后的結(jié)果如圖5b所示。

解碼和工序調(diào)整步驟如下：

步驟1根據(jù)工序排序進(jìn)行解碼，找到當(dāng)前解碼工序在機(jī)器上最早的開始加工時(shí)間。

步驟2若工序?yàn)楣ぜ牡谝坏拦ば颍瑒t返回第一步繼續(xù)解碼下一個(gè)工序，否則轉(zhuǎn)步驟3。

步驟3根據(jù)當(dāng)前工序的開工時(shí)間Si+1,j,k與前一道工序的結(jié)束時(shí)間Cijk進(jìn)行判斷，若Si+1,j,k=Cijk，則轉(zhuǎn)步驟4;若Si+1,j,k

步驟4更新機(jī)器加工時(shí)間、緩存時(shí)間、機(jī)器阻塞時(shí)間，判斷當(dāng)前工序是否為工件最后一道工序，若是，則轉(zhuǎn)步驟6;否則，轉(zhuǎn)步驟1。

步驟5判斷時(shí)間段[Si+1,j,k,Cijk]前一道工序機(jī)器對(duì)應(yīng)的輸出緩存是否可用，若可用，則轉(zhuǎn)步驟4;否則,轉(zhuǎn)步驟7。

步驟6判斷所有工件是否均已完工，若是，則結(jié)束;否則,轉(zhuǎn)步驟1。

步驟7緩存不可用的情況下判斷時(shí)間段[Si+1,j,k,Cijk]前一道工序?qū)?yīng)的機(jī)器上是否已安排其他工件加工，若沒有安排其他工序，則轉(zhuǎn)步驟4;否則,轉(zhuǎn)步驟8。

步驟8找到時(shí)間段[Si+1,j,k,Cijk]內(nèi)緩存可用的時(shí)刻，判斷從前一道工序完成到緩存可用時(shí)刻機(jī)器上有無其他已安排的工序且從緩存可用時(shí)刻到本工序開始時(shí)刻緩存都能滿足，若阻塞時(shí)間段無其他已安排工序且緩存時(shí)間段緩存容量滿足，則轉(zhuǎn)步驟4;否則,轉(zhuǎn)步驟9。

步驟9根據(jù)時(shí)間段[Si+1,j,k,Cijk]的沖突點(diǎn)對(duì)前一道工序進(jìn)行調(diào)整，直到該工件已調(diào)度的所有工序之間沒有沖突為止，轉(zhuǎn)步驟4。

2.3 交叉操作

傳統(tǒng)的交叉操作一般采用洗牌交叉，雖然保證了種群的多樣性，但缺乏種群中的優(yōu)秀個(gè)體對(duì)種群進(jìn)化的指導(dǎo)作用，因此本文提出將洗牌交叉和良種交叉相結(jié)合的方法進(jìn)行交叉操作，交叉操作均采用整數(shù)交叉法，首先選擇兩個(gè)需要進(jìn)行交叉的個(gè)體，然后隨機(jī)產(chǎn)生交叉位置進(jìn)行交叉。交叉操作如圖6所示，交叉位置為4。

交叉后某些工件會(huì)發(fā)生工序多余和缺失的情況，如個(gè)體1中工件1在交叉之后丟失了一道工序，工件3在交叉之后多出了一道工序，因此需要將工件多余工序變成工件丟失的工序，交叉修正操作如圖7所示。

2.4 變異操作

遺傳算法中變異操作是對(duì)染色體產(chǎn)生較小的擾動(dòng)以產(chǎn)生新的個(gè)體，從而增加種群多樣性和算法的局部搜索能力。采用自適應(yīng)變異概率可以避免算法在進(jìn)化后期陷入局部最優(yōu)。變異操作算子采用隨機(jī)交換工序位置的方法進(jìn)行，根據(jù)自適應(yīng)變異概率選擇需要進(jìn)行變異的個(gè)體，然后采用兩點(diǎn)變異方法隨機(jī)選擇兩個(gè)變異位置，將變異位置對(duì)應(yīng)的加工工序進(jìn)行交換，如果隨機(jī)產(chǎn)生的變異位置對(duì)應(yīng)的工件相同則重新產(chǎn)生變異位置。變異操作圖如8所示。

3 實(shí)驗(yàn)驗(yàn)證

本文選用標(biāo)準(zhǔn)的作業(yè)車間benchmark算例測(cè)試算法的性能。標(biāo)準(zhǔn)算例La01～La20來自文獻(xiàn)[15]，參照文獻(xiàn)[12]構(gòu)建機(jī)器緩存容量與加工工件數(shù)的百分比，例如算例La01的規(guī)模為10×5，表示工件數(shù)量為10，機(jī)器數(shù)量為5，如果機(jī)器緩存容量與加工工件數(shù)的百分比為10%，則表示每臺(tái)機(jī)器的緩存容量都為1。

(1)實(shí)驗(yàn)參數(shù)設(shè)置

改進(jìn)遺傳算法的初始種群規(guī)模大小、交叉變異概率、迭代次數(shù)均會(huì)影響算法的收斂性。本文通過將種群規(guī)模設(shè)置在50～200、迭代次數(shù)50～200進(jìn)行多次實(shí)驗(yàn)比較，當(dāng)種群規(guī)模PopSize=100、迭代次數(shù)Gmax=100時(shí)算法收斂性較好。自適應(yīng)交叉變異參數(shù)參考文獻(xiàn)[13]，具體參數(shù)賦值如表1所示。

表1 改進(jìn)遺傳算法參數(shù)表

(2)實(shí)驗(yàn)結(jié)果分析

本文使用提出的改進(jìn)遺傳算法(Improved Genetic Algorithm, IGA)對(duì)構(gòu)建算例進(jìn)行求解，應(yīng)用MATLAB R2014a軟件編程實(shí)現(xiàn)問題模型算法。每個(gè)算例在同等機(jī)器緩存容量與工件數(shù)量百分比下運(yùn)行10次，得到的最優(yōu)解如表2所示。表2中，GAP的百分比為機(jī)器緩存容量與工件數(shù)量比例為50%時(shí)與現(xiàn)有無限緩存容量下的最優(yōu)解之間的差值百分比?？梢钥闯觯瑢?duì)于經(jīng)典JSP，本文提出的IGA即使在機(jī)器緩存容量與工件比例僅為10%的情況下也能達(dá)到無限緩存容量下的現(xiàn)有最優(yōu)解(Best Known Solution, BKS)。例如La06和La10，機(jī)器緩存容量與工件數(shù)的比例達(dá)到20%時(shí)，算例La02、La03、La05～La15均能達(dá)到無限緩存容量下的現(xiàn)有最優(yōu)解;而當(dāng)機(jī)器緩存容量與工件數(shù)量比例達(dá)到50%時(shí)，La01～La15均可達(dá)到無限緩存容量下的現(xiàn)有最優(yōu)解，復(fù)雜的大規(guī)模LA16～LA20算例雖然沒有達(dá)到無限緩存下的最優(yōu)解，但是與最優(yōu)解之間的GAP值也很小，由此可以看出所提出的IGA對(duì)于求解該問題是有效的。從算例LA21～LA40可以看出，隨著算例規(guī)模和算例自身復(fù)雜性的增加，機(jī)器緩存容量對(duì)算例求解結(jié)果影響將大大提高，即使機(jī)器緩存容量與工件數(shù)量比例達(dá)到50%時(shí)部分算例求解得到的最優(yōu)解與無限緩存容量下的最優(yōu)解之間的存在一定的差距。

表2 改進(jìn)遺傳算法求解不同緩存容量與工件數(shù)量百分比下的完工時(shí)間

續(xù)表2

為進(jìn)一步分析算法的優(yōu)越性，將IGA與其他算法進(jìn)行對(duì)比。由于現(xiàn)有求解此問題的元啟發(fā)式算法暫時(shí)沒有，采用標(biāo)準(zhǔn)遺傳算法(GA)和文獻(xiàn)[12]的鄰域兩階段算法(Neighborhood Two Stage Algorithm， NTSA)作為對(duì)比算法進(jìn)行驗(yàn)證。分別將NTSA和GA求解最優(yōu)結(jié)果與IGA最優(yōu)值之間進(jìn)行比較。現(xiàn)有研究針對(duì)此問題的求解算法較少，除上述兩種對(duì)比算法外還采用了求解帶有緩沖約束的流水車間調(diào)度問題的方法進(jìn)行比較，選取文獻(xiàn)[16-18]中的3種算法(免疫算法、混沌和聲搜索算法、差分進(jìn)化算法)，計(jì)算在不同緩存容量百分比下的完工時(shí)間，并取3種算法中的最優(yōu)結(jié)果與改進(jìn)遺傳算法求解的最優(yōu)結(jié)果進(jìn)行比較。由于對(duì)比算法NTSA僅對(duì)算例LA01～LA20進(jìn)行計(jì)算，本文算法對(duì)比也選取LA01～LA20進(jìn)行對(duì)比驗(yàn)證。結(jié)果對(duì)比如表3所示，表中I-F表示IGA的最優(yōu)值與文獻(xiàn)[16-18]中的3種算法的最優(yōu)值之間的差值百分比，I-N表示IGA的最優(yōu)值與NTSA最優(yōu)值之間的差值百分比，I-G表示IGA的最優(yōu)值與GA最優(yōu)值之間的差值百分比。從表3中可以看出，IGA比其他算法在同等緩存容量百分比的情況下完工時(shí)間均能減少，在機(jī)器緩存容量與工件數(shù)量百分比為10%、20%、30%、50%的情況下，IGA比其他在帶有緩存約束的流水作業(yè)車間調(diào)度問題的3種算法的最優(yōu)值之間的平均差值百分比分別減小10.96%、7.55%、5.43%、4.83%，IGA比NTSA分別減小9.08%、0.69%、0.62%、0.46%，IGA比GA分別減小2.86%、0.47%、0.62%、0.46%。顯然IGA比對(duì)比算法更加優(yōu)越。

表3 改進(jìn)遺傳算法與其他算法在同等緩存容量百分比下的完工時(shí)間差值百分比

續(xù)表3

為驗(yàn)證IGA的穩(wěn)定性，將每個(gè)算例在不同機(jī)器緩存容量與工件數(shù)量百分比下運(yùn)行10次并取平均值，再計(jì)算平均值與無限緩存容量下的最優(yōu)解之間的差值百分比，最后將同種算例規(guī)模下的差值百分比取其平均值，結(jié)果如表4所示。從表4中可以看出，當(dāng)機(jī)器緩存容量與工件數(shù)量的百分比增加時(shí)，調(diào)度結(jié)果與無限緩存容量下的調(diào)度結(jié)果之間的差值會(huì)越來越來小，特別是在機(jī)器緩存容量與工件數(shù)量的百分比達(dá)到20%后，偏差迅速減小。

表4 偏差對(duì)比

4 結(jié)束語

本文針對(duì)帶有緩存約束的作業(yè)車間調(diào)度方法進(jìn)行研究，將解決方案從工件層級(jí)擴(kuò)展到工序?qū)蛹?jí)，并提出了改進(jìn)遺傳算法對(duì)問題進(jìn)行求解;通過算例驗(yàn)證了算法能在不同的機(jī)器緩存容量與工件數(shù)量百分比的情況下進(jìn)行求解，通過對(duì)比已有求解算法在同等機(jī)器緩存容量與工件數(shù)量百分比下的求解結(jié)果，證明了所提改進(jìn)遺傳算法能求得精度更高的解，由此驗(yàn)證了算法的有效性和優(yōu)越性。后續(xù)研究將考慮更符合實(shí)際生產(chǎn)的問題，構(gòu)建更精確的數(shù)學(xué)模型進(jìn)行求解。如考慮設(shè)備最大負(fù)載、設(shè)備阻塞時(shí)間最小、緩存利用率最高等多個(gè)目標(biāo)，以及多臺(tái)設(shè)備共用緩存、物流運(yùn)輸時(shí)間、批量生產(chǎn)等情況下的約束條件，采用本文算法求解，進(jìn)一步驗(yàn)證其有效性。