時(shí)維國(guó)，宋存利

(1.大連交通大學(xué) 電氣信息工程學(xué)院，遼寧 大連 116028;2.大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116052)

0 引言

帶有相同并行機(jī)的混合流水車間調(diào)度問(wèn)題(Hybrid Flow shop Scheduling Problem, HFSP)是典型流水車間調(diào)度問(wèn)題的擴(kuò)展，其所有加工任務(wù)均以相同的順序經(jīng)過(guò)各個(gè)加工階段，而每個(gè)加工階段均配置有一臺(tái)或多臺(tái)相同的加工設(shè)備，且至少有一個(gè)加工階段配置有多臺(tái)相同的加工設(shè)備。HFSP的研究目標(biāo)是如何安排加工任務(wù)的加工順序，以滿足企業(yè)生產(chǎn)追求的目標(biāo)，如每個(gè)加工階段的設(shè)備負(fù)載均衡、總流水時(shí)間最小、最小化最大完工時(shí)間等。典型的生產(chǎn)案例有食品生產(chǎn)、化工生產(chǎn)、鋼鐵生產(chǎn)等，因此對(duì)該類問(wèn)題進(jìn)行研究具有重要的意義。

HOOGEVEEN等[1]對(duì)具有兩階段HFSP的復(fù)雜性進(jìn)行了研究，證明該問(wèn)題屬于NP難題。對(duì)于小規(guī)模的HFSP問(wèn)題常用精確方法，例如BRAH等[2]針對(duì)帶有多處理的流水車間調(diào)度問(wèn)題，提出一種分枝定界算法；HIDRI等[3]對(duì)帶有運(yùn)輸時(shí)間的兩階段HFSP以最小化最大完工時(shí)間為目標(biāo)，提出一種分枝定界法；FATTAHI等[4]對(duì)帶有批操作和設(shè)置時(shí)間的HFSP提出一種分枝定界算法。這些精確算法雖然能求出問(wèn)題的最優(yōu)解，但是當(dāng)問(wèn)題規(guī)模變大時(shí)，求解效率將大大降低，因此學(xué)者們提出各類啟發(fā)式算法和智能優(yōu)化算法：例如宋存利等[5]提出求解無(wú)等待流水車間調(diào)度問(wèn)題的貪婪迭代搜索算法；屈國(guó)強(qiáng)[6]提出一種瓶頸聚焦的啟發(fā)式方法；MOCCELLIN等[7]針對(duì)考慮阻塞和設(shè)置時(shí)間的HFSP，提出一種基于優(yōu)先級(jí)的啟發(fā)式規(guī)則算法。實(shí)驗(yàn)證明，啟發(fā)式方法的優(yōu)點(diǎn)是求解速度快，缺點(diǎn)是尋優(yōu)效果往往受啟發(fā)式規(guī)則影響較大；智能優(yōu)化算法受問(wèn)題特點(diǎn)影響較小，且求解結(jié)果較好，因此受到廣大學(xué)者的青睞，例如針對(duì)HFSP，ALAYKYRAN等[8]提出螞蟻算法；LOW[9]提出模擬退火算法；SHIAU等[10]提出粒子群算法；FIGIELSKA[11]提出遺傳算法和模擬退火算法的混合算法；RABIEE等[12]提出基于帝國(guó)競(jìng)爭(zhēng)算法的混合算法；宋存利[13]提出貪婪遺傳算法；KOMAKI等[14]提出人工免疫算法；LI等[15]提出人工蜂群算法；SUN等[16]和王芳等[17]針對(duì)帶有不相關(guān)并行機(jī)的HFSP提出分布估算算法；SIQUEIRA等[18]和ESKANDARI等[19]提出變鄰域搜索算法解決該問(wèn)題。

灰狼優(yōu)化(Grey Wolf Optimization, GWO)算法是2014年由澳大利亞學(xué)者M(jìn)IRJALILI等[20]提出的一種群體智能優(yōu)化算法，該算法是一種受灰狼捕食獵物活動(dòng)啟發(fā)而開發(fā)的一種優(yōu)化搜索方法，因具有較強(qiáng)的搜索能力，且控制參數(shù)少、易實(shí)現(xiàn)，受到學(xué)者們的廣泛關(guān)注，其在參數(shù)優(yōu)化[21]、圖像分類[22-23]、旅行商問(wèn)題[24]等方面得到成功應(yīng)用。

近年來(lái)，GWO算法開始應(yīng)用在生產(chǎn)調(diào)度領(lǐng)域。孟榮華等[25]提出基于十進(jìn)制GWO算法的金屬板材切割調(diào)度，該算法重新設(shè)計(jì)了灰狼的游走和奔襲等智能行為，改進(jìn)后的GWO算法以一種全新的機(jī)制進(jìn)化，不再受參數(shù)A和C的影響；KOMAKI等[26]將GWO算法應(yīng)用于兩階段裝配流水車間調(diào)度問(wèn)題，在GWO算法找到較好的解后再對(duì)其實(shí)施一種鄰域?qū)?yōu)操作，以便最大限度提高解的質(zhì)量；YANG等[27]將GWO算法應(yīng)用于帶有阻塞的流水車間調(diào)度問(wèn)題，通過(guò)將一種變鄰域搜索算法應(yīng)用于GWO算法來(lái)提高算法的局部搜索能力；LU等[28]提出一種多目標(biāo)細(xì)胞GWO算法，該算法將細(xì)胞自動(dòng)機(jī)的優(yōu)點(diǎn)融于算法，以提高灰狼種群的多樣性，同時(shí)將變鄰域搜索算法運(yùn)用于頭狼，以提高算法的局部搜索能力。然而目前對(duì)HFSP，GWO算法的應(yīng)用研究極少。

針對(duì)HFSP以求解最小化最大完工時(shí)間為目標(biāo)，本文對(duì)GWO算法的應(yīng)用展開了研究。同其他群體智能優(yōu)化算法一樣，GWO算法同樣存在早熟收斂、易陷入局部最優(yōu)等問(wèn)題，很多學(xué)者對(duì)其提出了改進(jìn)。例如，文獻(xiàn)[26-28]將其他算法算子混入GWO算法，以提高其局部搜索能力；文獻(xiàn)[29-30]對(duì)GWO算法的距離控制參數(shù)a進(jìn)行改進(jìn)，較好地控制灰狼的全局搜索和局部探索能力；文獻(xiàn)[25,30]對(duì)GWO算法的位置更新公式進(jìn)行了改進(jìn)；文獻(xiàn)[31-32]分析了控制參數(shù)C對(duì)GWO算法的影響，分別提出改進(jìn)控制參數(shù)C的策略來(lái)提高算法探索能力。本文對(duì)GWO算法的改進(jìn)體現(xiàn)在以下方面：

(1)鑒于GWO算法的控制參數(shù)C對(duì)狼群全局探索和局部搜索能力有重要影響，提出一種新的控制參數(shù)C的設(shè)置策略，以平衡狼群的全局探索和局部搜索能力。

(2)在算法后期提出一種平面鏡成像學(xué)習(xí)策略應(yīng)用于灰狼種群，以提高狼群的多樣性。

(3)考慮到基于工件加工順序的編碼在解碼時(shí)的效果受設(shè)備配置影響較大，采用正序解碼和逆序解碼相補(bǔ)充的策略。

1 混合流水車間調(diào)度問(wèn)題

1.1 問(wèn)題描述

HFSP可描述為N個(gè)工件以相同的加工順序經(jīng)過(guò)S個(gè)加工階段進(jìn)行加工，M臺(tái)不同的加工設(shè)備分布在S個(gè)加工階段，每個(gè)加工階段的加工設(shè)備數(shù)量大于等于1臺(tái)，且相同階段的加工設(shè)備完全一樣，不同加工階段的加工工藝不同。問(wèn)題的目標(biāo)是如何安排N個(gè)工件在每個(gè)階段加工設(shè)備上的加工順序，使最大總完成時(shí)間最小。問(wèn)題的假設(shè)條件如下：

(1)一個(gè)工件同一時(shí)間只能在一臺(tái)設(shè)備上加工，而且在加工過(guò)程中不能被其他工件搶占。

(2)每臺(tái)設(shè)備同一時(shí)間只能加工一個(gè)工件。

(3)每個(gè)工件均需按照相同的順序經(jīng)過(guò)各個(gè)加工階段，且在每個(gè)加工階段都有一道工序需要加工，但加工時(shí)間因工件不同而不同。

(4)同一階段的加工設(shè)備完全相同。

(5)不同階段之間有無(wú)限緩沖區(qū)間。

(6)忽略設(shè)備故障和到達(dá)延遲等問(wèn)題。

1.2 問(wèn)題建模

為了方便問(wèn)題建模，定義數(shù)學(xué)符號(hào)如下：

N為待加工的工件數(shù)量；

S為加工階段數(shù)量；

i為工件編號(hào)，i=1,2,…,N；

j為加工階段編號(hào)，j=1,2,…,S；

Mj為第j階段的加工設(shè)備數(shù)量；

k為某階段的設(shè)備編號(hào)，k=1,2,…,Mj；

mj,k為第j加工階段的第k臺(tái)加工設(shè)備；

Ei,j為工件Ji在第j個(gè)加工階段的完工時(shí)間；

Bi,j為工件Ji在第j個(gè)加工階段的加工開始時(shí)間；

pi,j為工件Ji在第j個(gè)加工階段的加工時(shí)間；

Xi,j,k表示工件Ji在第j個(gè)加工階段是否在設(shè)備mj,k上加工，Xi,j,k=1則在該設(shè)備上加工，Xi,j,k=0則不在該設(shè)備上加工；

Cmax為所有工件的最大完工時(shí)間；

Ri,j為工件Ji在第j階段之后的剩余加工時(shí)間。

HFSP問(wèn)題的目標(biāo)函數(shù)為

Cmax=min{max{Ei,j|

i=1,2,…,N;j=1,2,…,S}}。

(1)

s.t.

Ei,j=Bi,j+pi,j≤Bi,j+1；

(2)

Bi,1≥0；

(3)

(4)

(5)

(6)

其中：式(2)約定每個(gè)工件在相應(yīng)加工階段的完工時(shí)間為其在該階段的開始加工時(shí)間加上其工序?qū)?yīng)的加工時(shí)間，而且下一階段的開始加工時(shí)間大于等于前一階段工件的完工時(shí)間；式(3)表示每個(gè)工件第一道工序的開始加工時(shí)間大于等于0；式(4)表示每個(gè)工件在第j階段只能在其中一臺(tái)設(shè)備上加工；式(5)表示每個(gè)工件在每個(gè)階段必須選擇一臺(tái)且只能在其中一臺(tái)設(shè)備上加工；式(6)為工件在階段j之后的剩余加工時(shí)間。

2 灰狼優(yōu)化算法

GWO算法是受自然界狼群捕獵行為啟發(fā)而提出的一種智能群體優(yōu)化算法，是將狼群的捕獵行為歸結(jié)為追蹤、圍獵和攻擊3種行為而構(gòu)建的一種優(yōu)化算法，適用于求解組合優(yōu)化問(wèn)題。該算法將每只狼抽象為問(wèn)題的一個(gè)解，適應(yīng)度最好的解為頭狼，稱為α狼，適應(yīng)度次好的解為β狼，適應(yīng)度第3的解為δ狼，其他解為ω狼。ω狼在α狼、β狼和δ狼的引領(lǐng)下進(jìn)行追蹤、圍獵和攻擊，不斷接近獵物，最終抓住獵物。對(duì)于N維組合優(yōu)化問(wèn)題，每只狼為一個(gè)N維向量，一般表示為Xi(xi,1,xi,2,…,xi,N)，狼群圍獵的數(shù)學(xué)模型為：

X(t+1)=Xp(t)+A·|C·Xp(t)-X(t)|；

(7)

A=2a·r1-a；

(8)

C=2·r2；

(9)

(10)

式中：X為灰狼個(gè)體；Xp為獵物位置；A和C為系數(shù)向量；t為當(dāng)前迭代的代數(shù)；MaxIter為最大迭代次數(shù)；r1和r2為[0,1]之間的隨機(jī)變量；a為距離控制參數(shù)，其值隨迭代次數(shù)的增加而逐漸減小為0。

狼群攻擊獵物的模型為：

X1=Xα+A1·|C1·Xα-X|；

(11)

X2=Xβ+A2·|C2·Xβ-X|；

(12)

X3=Xδ+A3·|C3·Xδ-X|；

(13)

(14)

式中：參數(shù)A1，A2，A3根據(jù)式(8)計(jì)算；C1，C2，C3根據(jù)式(9)計(jì)算。

3 改進(jìn)的灰狼優(yōu)化算法

3.1 控制參數(shù)C的確定

文獻(xiàn)[32]通過(guò)實(shí)驗(yàn)驗(yàn)證了控制參數(shù)C對(duì)GWO算法的影響規(guī)律，即在算法的早期階段，若C>1則算法的勘探能力不足，算法進(jìn)化較慢；在算法中后期，若C<1，則算法容易出現(xiàn)早熟收斂的情況。鑒于此，本文提出一種新的控制參數(shù)C的方法，控制C在算法早期以較大概率小于1而在中后期以較大概率大于1，從而平衡算法的勘探能力和后期的局部搜索能力，具體公式為

(15)

式中r3為一個(gè)[0，1]之間的隨機(jī)數(shù)。

3.2 灰狼編碼

HFSP需要確定N個(gè)工件在每個(gè)加工階段的加工順序，其結(jié)果是由S個(gè)1～N的整數(shù)排列構(gòu)成，本文編碼只表示工件在第一階段的加工順序，其他階段的加工順序采用3.4節(jié)的解碼規(guī)則確定，從而將問(wèn)題的解空間減小為N!。該編碼是N維空間中的一些離散點(diǎn)，而GWO算法更適合解決連續(xù)解空間中的問(wèn)題。為了便于用GWO算法解決HFSP，這里將離散的解空間連續(xù)化，方法是將N維空間的每一位用一個(gè)(0,2)之間的實(shí)型數(shù)據(jù)表示，而該實(shí)數(shù)對(duì)應(yīng)的工件編號(hào)是按照實(shí)數(shù)在向量中的數(shù)值大小確定，其中最小的實(shí)數(shù)對(duì)應(yīng)工件號(hào)1，次小的實(shí)數(shù)對(duì)應(yīng)工件號(hào)2，依次類推，最大的實(shí)數(shù)對(duì)應(yīng)工件號(hào)N。例如5個(gè)工件對(duì)應(yīng)的5維向量編碼為(1.24,0.28,1.37,0.82,0.56)，其由小到大的排序結(jié)果為(0.28,0.56,0.82,1.24,1.37)，可確定5個(gè)工件的加工順序?yàn)?4,1,5,3,2)，該順序?yàn)楣ぜ诘谝浑A段的加工順序。

3.3 鏡面成像學(xué)習(xí)策略

平面鏡成像是指將一個(gè)物體放置在平面鏡前，則在平面鏡中將呈現(xiàn)一個(gè)和物體大小相同、與鏡面距離相同，且物與像的連線垂直于鏡面的像，如圖1所示。

若考慮三維空間，物O對(duì)應(yīng)的點(diǎn)坐標(biāo)為(x,y,z)，將平面鏡放置在y軸和z軸確定的平面上，且x軸坐標(biāo)為0的位置，則像O′的坐標(biāo)為(-x,y,z)。為簡(jiǎn)化問(wèn)題，不考慮鏡子的其他不規(guī)則放置。利用該原理，對(duì)于N維空間的物O，假設(shè)其所在的位置為(x1,x2,…,xN)，隨機(jī)產(chǎn)生兩個(gè)1～N之間的隨機(jī)數(shù)i和j，從而確定鏡子的放置位置為(1,…,xi,…,xj,…,1)，則像O′的坐標(biāo)分量為

k=1,2,…,N,k≠i,k≠j；

(16)

(17)

利用平面鏡成像原理，在狼群圍獵后，對(duì)每只灰狼進(jìn)行鏡面學(xué)習(xí)，若像的適應(yīng)值優(yōu)于其自身的適應(yīng)值，則用像替換它，這種操作既有利于增加種群多樣性，又可避免早熟收斂。

以3.2節(jié)的5個(gè)工件編碼(1.24,0.28,1.37,0.82,0.56)為例，其確定的工件加工順序?yàn)?4,1,5,3,2)。對(duì)其進(jìn)行鏡面學(xué)習(xí)，假如隨機(jī)確定1～5之間兩個(gè)不相等的整數(shù)為3和5，根據(jù)式(16)和式(17)，該編碼的像為(0.76,1.72,1.37,1.18,0.56)，確定工件加工順序?yàn)?2,5,4,3,1)。

3.4 解碼算法

(1)先到先加工解碼算法(First arrive First process, FF) 該算法的思想是對(duì)于第一個(gè)加工階段，工件完全按照編碼順序安排加工，其他加工階段則按照工件到達(dá)該階段的順序安排加工設(shè)備。因?yàn)槊總€(gè)加工階段的加工設(shè)備可能不止一臺(tái)，所以選擇最早可加工該工件的設(shè)備進(jìn)行加工，直到安排完每個(gè)工件。

(2)基于剩余未加工時(shí)間優(yōu)先的解碼算法(Remaining unprocessed Time first process, RT) 該算法的思想是對(duì)于第一個(gè)加工階段，每個(gè)工件完全按照其編碼順序安排加工。對(duì)于其他加工階段，首先將工件按其到達(dá)時(shí)間的先后順序排序，選擇可最早開工的設(shè)備，并確定該設(shè)備的最早開工時(shí)間，然后對(duì)剩余未調(diào)度的工件進(jìn)行調(diào)度。若在設(shè)備的最早開工時(shí)間沒(méi)有工件到來(lái)，則將最早到來(lái)的工件安排在該設(shè)備加工；若有多個(gè)工件同時(shí)到來(lái)，則選擇剩余未加工時(shí)間最長(zhǎng)的工件優(yōu)先加工；若在設(shè)備可開工時(shí)間之前已有多個(gè)工件到來(lái)且未加工，則在這些工件中選擇剩余未加工時(shí)間最長(zhǎng)的工件優(yōu)先加工。

(3)FF聯(lián)合RT解碼策略(簡(jiǎn)稱FFRT) 該算法的思想是瓶頸階段及瓶頸階段之前的加工階段均采用FF策略解碼，瓶頸階段的后續(xù)階段采用RT策略。因此當(dāng)瓶頸階段在第一階段時(shí)，該策略退化為RT策略；若瓶頸階段在最后一個(gè)階段，則該策略退化為FF策略。

3.5 逆序解碼策略

鑒于瓶頸加工階段對(duì)調(diào)度結(jié)果影響較大，為增加尋找最優(yōu)解的機(jī)率，將文獻(xiàn)[21]的逆序調(diào)度方法用于本文解碼，具體為將工件原有加工工藝的逆序工藝作為其加工工藝，對(duì)同一個(gè)編碼按照逆序工藝進(jìn)行解碼調(diào)度，即對(duì)于有S道工序的加工任務(wù)，其正常工序的第1道工藝對(duì)應(yīng)逆序調(diào)度中的第S道工藝，第2道工藝對(duì)應(yīng)逆序調(diào)度中的第S-1道工藝，依次類推。采用逆序解碼的案例，需對(duì)最后最優(yōu)解的調(diào)度結(jié)果進(jìn)行正序化。具體方法是保持每個(gè)加工設(shè)備上分配的加工任務(wù)不變，加工順序?yàn)榕c逆序解碼結(jié)果相反的順序，相應(yīng)設(shè)備上每個(gè)任務(wù)的開始加工時(shí)間和完工時(shí)間如下：

(18)

(19)

3.6 改進(jìn)的灰狼優(yōu)化算法步驟

改進(jìn)的灰狼優(yōu)化(Improved Grey Wolf Optimization, IGWO)算法的具體步驟如下：

步驟1初始化狼群規(guī)模為size，初始化算法的最大迭代次數(shù)為MaxIter，令當(dāng)前迭代次數(shù)t=0，采用隨機(jī)算法初始化狼群。

步驟2對(duì)每只狼解碼并計(jì)算適應(yīng)度，找出適應(yīng)度最好的3只狼，依次為α狼、β狼和δ狼。

步驟3當(dāng)t≥MaxIter時(shí)，轉(zhuǎn)步驟4；否則，對(duì)每只狼依次進(jìn)行如下操作：

(1)用式(11)～式(14)更新狼的位置，其中控制參數(shù)C用式(15)計(jì)算，控制參數(shù)A用式(8)計(jì)算。根據(jù)3.3節(jié)的鏡面學(xué)習(xí)策略找到狼的像，分別計(jì)算狼和狼的像的適應(yīng)度，比較其適應(yīng)度的值，若像的適應(yīng)值小于狼的適應(yīng)值，則用像替換狼進(jìn)行下一輪捕獵行動(dòng)。

(2)更新新狼群α，β，δ狼的位置及其對(duì)應(yīng)的適應(yīng)度值，返回步驟3。

步驟4輸出α的解碼結(jié)果。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證本文所提算法的有效性，在PC機(jī)(i7-8550U/2 GHzCPU，16 G內(nèi)存空間，WIN10)采用VC++2006實(shí)現(xiàn)了算法。HFSP實(shí)驗(yàn)案例選自Carlier and Néron(2000年)[33]提出的benchmark案例，包括47個(gè)a類和b類簡(jiǎn)單案例與30個(gè)c類和d類復(fù)雜案例。a類和b類案例的特點(diǎn)是只有一個(gè)瓶頸階段，且瓶頸階段只有一臺(tái)加工設(shè)備，而其他加工階段均有3臺(tái)加工設(shè)備，其中a類的瓶頸階段在中間階段，b類的瓶頸階段在開始階段或結(jié)束階段；c類案例瓶頸階段在中間階段，且有2臺(tái)加工設(shè)備，其他階段有3臺(tái)加工設(shè)備；d類案例沒(méi)有明顯的瓶頸階段，每個(gè)階段均有3臺(tái)加工設(shè)備。案例名稱中的j表示待加工工件，c表示加工階段，a表示a類案例。

通過(guò)正交實(shí)驗(yàn)確定灰狼種群為40，算法的最大迭代代數(shù)為1 000，并設(shè)置了100代內(nèi)最優(yōu)解無(wú)更新算法則自動(dòng)結(jié)束算法。實(shí)驗(yàn)中，每個(gè)案例最多運(yùn)行20次，10次采用正序解碼，10次采用逆序解碼。在表1～表3中：LB為最大完工時(shí)間的下界；BD為該案例的瓶頸度，

(20)

Cmax為最大完工時(shí)間；times為IGWO算法取得最優(yōu)解的最小迭代代數(shù)；PD為最優(yōu)解Cmax相對(duì)下界LB的偏離度，用百分比表示為

(21)

4.1 a類和b類案例的實(shí)驗(yàn)

在實(shí)驗(yàn)過(guò)程中，IGWO算法采用3.3節(jié)設(shè)計(jì)的3種解碼算法，分別記為FF-IGWO, RT-IGWO和FFRT-IGWO，鑒于a類和b類問(wèn)題較為簡(jiǎn)單，實(shí)驗(yàn)只使用正序解碼，每個(gè)算法運(yùn)行10次，實(shí)驗(yàn)結(jié)果如表1所示。

表1 a類案例和b類案例的實(shí)驗(yàn)結(jié)果

續(xù)表1

從表1可見，47個(gè)案例瓶頸階段的加工負(fù)載是其他階段加工負(fù)載的2倍以上，說(shuō)明其他階段的加工順序?qū)φ麄€(gè)加工任務(wù)的完成時(shí)間影響不大，而瓶頸階段工件的加工順序?qū)φ{(diào)度結(jié)果影響較大；FF-IGWO和RT-IGWO對(duì)47個(gè)案例均找到了下界，而FFRT-IGWO找到了46個(gè)案例的下界；本文算法對(duì)大部分案例在迭代代數(shù)為0時(shí)找到了最優(yōu)解，說(shuō)明算法在初始化階段就能找到大多數(shù)案例的最優(yōu)解，從而說(shuō)明本文所提解碼算法的有效性；FFRT-IGWO在47個(gè)案例上運(yùn)行的平均迭代次數(shù)最小，在一定程度上說(shuō)明FFRT解碼方法對(duì)此類問(wèn)題的有效性。

4.2 c類和d類案例的實(shí)驗(yàn)

由于c類和d類問(wèn)題的復(fù)雜度較高，每個(gè)案例采用3種不同解碼策略的IGWO算法求解，每個(gè)算法最多計(jì)算20次，前10次采用正序解碼，若正序解碼沒(méi)有找到問(wèn)題的下界或目前最優(yōu)解，再采用逆序解碼運(yùn)行后10次，記錄最優(yōu)值。表2中加粗的數(shù)據(jù)為采用逆序解碼求得，表明采用正序解碼無(wú)法求得相應(yīng)最優(yōu)解。將本文IGWO算法與目前其他較好算法，如分布估計(jì)算法[34](Estimation of Distribution Algorithm, EDA)、變鄰域改進(jìn)遺傳算法[35](Improved Genetic Algorithm Variable Neighborhood Search, IGA-VNS)和改進(jìn)的灰狼優(yōu)化算法LIL-GWO[31](lens imaging learning grey wolf optimizer algorithm)進(jìn)行實(shí)驗(yàn)對(duì)比。其中：EDA和IGA-VNS采用原有文獻(xiàn)的實(shí)驗(yàn)結(jié)果；LIL-GWO是目前對(duì)參數(shù)C進(jìn)行改進(jìn)的較好的GWO算法，其解碼算法采用本文提出的較好的解碼方法FFRT，種群規(guī)模、迭代代數(shù)、運(yùn)行次數(shù)也采用本文IGWO算法的設(shè)置。實(shí)驗(yàn)結(jié)果如表2所示。

表2 c類和d類案例的實(shí)驗(yàn)結(jié)果

續(xù)表2

從表2可見，c類和d類案例的平均瓶頸度為1.4，相對(duì)于a類和b類問(wèn)題的瓶頸度大大減小，說(shuō)明瓶頸階段對(duì)調(diào)度結(jié)果的影響變小，其他階段加工順序?qū)φ{(diào)度結(jié)果的影響增加，問(wèn)題的復(fù)雜性增加。

對(duì)前5種算法進(jìn)行分析。從30個(gè)案例的求解平均偏差PD值看，前5種算法中FFRT-IGWO最好，平均PD值為3%；RT-IGWO次之，平均PD值為3.02%；第3為FF-IGWO，平均PD值為3.04%；第4為EDA，平均PD值為3.06%；最差的是IGA-VNS，平均PD為3.26%。從30個(gè)案例的實(shí)驗(yàn)結(jié)果看，前5種算法中，F(xiàn)FRT-IGWO和RT-IGWO找到了28個(gè)案例的目前最優(yōu)解，F(xiàn)F-IGWO找到了27個(gè)，EDA找到了26個(gè)，而IGA-VNS算法只找到23個(gè)，說(shuō)明FFRT-IGWO和RT-IGWO最好。在FFRT-IGWO找到的28個(gè)最優(yōu)解中有4個(gè)案例采用逆序解碼找到，在RT-IGWO找到的28個(gè)最優(yōu)解中有3個(gè)案例采用逆序解碼找到，在FF-IGWO找到的27個(gè)案例的最優(yōu)解中有7個(gè)案例采用逆序解碼獲得，說(shuō)明了逆序解碼策略的必要性，也一定程度說(shuō)明了逆序解碼對(duì)FF解碼策略有較大影響。案例j10c10c1的實(shí)驗(yàn)結(jié)果114是目前找到的最優(yōu)結(jié)果，這一結(jié)果用本文所提的3種解碼方案采用逆序解碼均能找到，進(jìn)一步驗(yàn)證了逆序解碼的必要性。綜上所述，本文提出的FFRT-IGWO算法效果最好。

將本文FFRT-IGWO算法與同樣對(duì)控制參數(shù)C進(jìn)行改進(jìn)并具有學(xué)習(xí)策略的LIL-GWO算法，對(duì)c類和d類案例的實(shí)驗(yàn)結(jié)果進(jìn)行比對(duì)。實(shí)驗(yàn)發(fā)現(xiàn)，在j10c5c4和j10c10c6案例上，F(xiàn)FRT-IGWO算法的尋優(yōu)結(jié)果較LIL-GWO算法好，而在剩余其他28個(gè)案例上兩個(gè)算法的最優(yōu)解完全一樣，說(shuō)明本文對(duì)GWO算法改進(jìn)的有效性。

4.3 算法有效性驗(yàn)證

為了說(shuō)明本文所提策略的有效性，將標(biāo)準(zhǔn)灰狼優(yōu)化算法記為GWO，改進(jìn)控制參數(shù)C的GWO算法記為ICGWO，采用鏡面學(xué)習(xí)策略的GWO記為IMGWO，綜合改進(jìn)后的GWO記為IGWO，所有算法的解碼方法均采用逆序RT方法，實(shí)驗(yàn)案例選擇規(guī)模較大、復(fù)雜度較高的6個(gè)案例j10c10c1～j10c10c6，每個(gè)算法在每個(gè)案例上運(yùn)行10次，統(tǒng)計(jì)10次取得的最優(yōu)解Cmax，以及10次最優(yōu)解的平均值A(chǔ)V和偏差值PD，實(shí)驗(yàn)結(jié)果如表3所示。

表3 算法有效性驗(yàn)證

從表3可見6個(gè)案例中，本文RT-IGWO算法取得的最優(yōu)解均較好。與RT-IGWO算法的實(shí)驗(yàn)結(jié)果相比，RT-ICGWO算法和RT-GWO算法在案例j10c10C6上取得的最優(yōu)解與其相同，其他5個(gè)案例均較差，RT-IMGWO算法有4個(gè)案例取得的最優(yōu)解與其相同，2個(gè)較差，從而說(shuō)明RT-IGWO算法的有效性。比較RT-ICGWO算法與RT-GWO算法發(fā)現(xiàn)，RT-ICGWO算法有3個(gè)案例的最優(yōu)解優(yōu)于RT-GWO算法，有3個(gè)案例的最優(yōu)解與RT-GWO算法相同，但從6個(gè)案例的AV值發(fā)現(xiàn)，RT-ICGWO算法有5個(gè)案例的AV優(yōu)于RT-GWO算法，1個(gè)與之相同，說(shuō)明改進(jìn)控制參數(shù)C的策略有效平衡了算法的局部搜索和局部搜索性能，提高了算法找到最優(yōu)解的概率。比較RT-IMGWO算法與RT-GWO算法發(fā)現(xiàn)，RT-IMGWO算法有4個(gè)案例的最優(yōu)解優(yōu)于RT-GWO算法，有2個(gè)案例的最優(yōu)解與RT-GWO算法相同，但從6個(gè)案例的AV發(fā)現(xiàn)，RT-ICGWO算法有5個(gè)案例的AV優(yōu)于RT-GWO算法，1個(gè)較差，從而說(shuō)明了平面鏡學(xué)習(xí)策略的有效性，最大限度避免了算法陷入局部最優(yōu)。

圖3所示為IGWO算法與GWO算法在較復(fù)雜案例 j10c10c1上進(jìn)行實(shí)驗(yàn)對(duì)比的收斂曲線。設(shè)每個(gè)算法的最大迭代代數(shù)均為1 000次，且均采用逆序解碼，分別采用3種不同的解碼算法形成6種算法，記為RT-IGWO，F(xiàn)F-IGWO，F(xiàn)FRT-IGWO，RT-GWO，F(xiàn)F-GWO，F(xiàn)FRT-GWO。可見，在采用相同解碼算法時(shí)，IGWO算法比GWO算法的收斂速度快，而且很容易找到較好的最優(yōu)解，進(jìn)一步證明了相關(guān)改進(jìn)策略的有效性。圖4所示為案例j10c10c1的調(diào)度甘特圖，其中橫坐標(biāo)為時(shí)間軸，縱坐標(biāo)為工件的10個(gè)加工階段以及每個(gè)階段的設(shè)備信息。

4.4 實(shí)際案例仿真結(jié)果

某汽車發(fā)動(dòng)機(jī)缸體生產(chǎn)線生產(chǎn)1.8 L和2.4 L兩款自然吸氣發(fā)動(dòng)機(jī)以及1.5 T和2.0 T兩款渦輪增壓發(fā)動(dòng)機(jī)。生產(chǎn)線包括定位基準(zhǔn)、粗加工、中間清洗、壓檢、壓裝、精加工、清洗、終檢8道工序，每個(gè)缸體加工工件時(shí)均以相同的順序經(jīng)過(guò)以上8道工序，8道工序配備相同的并行機(jī)，數(shù)量依次為(2,3,1,1,1,3,1,1)，缸體的生產(chǎn)時(shí)間如表4所示。

表4 缸體生產(chǎn)時(shí)間

車間所加工產(chǎn)品相應(yīng)的數(shù)量如表4所示，車間原有的調(diào)度甘特圖如圖5所示，其中最大完工時(shí)間為3 740 s。采用本文FF-IGWO算法進(jìn)行調(diào)度的甘特圖如圖6所示，其中最大完工時(shí)間為3 570 s，總工時(shí)減少170 s，比原來(lái)減少約4%，因此提高了企業(yè)生產(chǎn)效率。

5 結(jié)束語(yǔ)

帶有相同并行機(jī)的HFSP是典型的NP難題，針對(duì)該問(wèn)題，本文提出一種IGWO算法。該算法給出控制參數(shù)C新的計(jì)算公式，從而提高了早期算法的勘探能力和后期算法的局部搜索能力。鑒于算法后期狼群急劇聚集，種群多樣性不足，將鏡面成像學(xué)習(xí)策略應(yīng)用其中，增加了種群多樣性。同時(shí)考慮混合流水車間各加工階段設(shè)備配置不均衡會(huì)影響瓶頸加工階段的解碼結(jié)果，提出正序解碼與逆序互補(bǔ)解碼策略，提高了找到問(wèn)題最優(yōu)解的概率，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性和可靠性。

下一步的研究工作為：

(1)針對(duì)復(fù)雜環(huán)境的生產(chǎn)調(diào)度問(wèn)題進(jìn)一步展開研究，如基于物聯(lián)網(wǎng)的實(shí)時(shí)調(diào)度研究、考慮多約束條件的調(diào)度問(wèn)題研究等。

(2)GWO算法的發(fā)展歷史比較短，還有很多待解決的問(wèn)題，對(duì)GWO算法進(jìn)一步展開理論和應(yīng)用研究將是未來(lái)的一個(gè)研究方向。