改進(jìn)GWO算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題

馬隨東，艾爾肯·亥木都拉，鄭威強(qiáng)

(新疆大學(xué)機(jī)械工程學(xué)院，新疆烏魯木齊 830017)

0 前言

車(chē)間調(diào)度任務(wù)的基本目的是根據(jù)不同客戶(hù)的訂單在截止日期內(nèi)完成指定生產(chǎn)任務(wù)的活動(dòng)。柔性作業(yè)車(chē)間調(diào)度問(wèn)題(Flexible Job Shop Scheduling Problem，F(xiàn)JSP)廣泛存在于人類(lèi)生產(chǎn)活動(dòng)的各個(gè)領(lǐng)域，如紡織制造、半導(dǎo)體制造、汽車(chē)裝配以及化學(xué)材料加工等。FJSP由機(jī)器分配和操作排序2個(gè)子問(wèn)題組成，機(jī)器分配解決每個(gè)操作的候選集中機(jī)器選擇問(wèn)題，操作排序是調(diào)整每個(gè)機(jī)器上的所有操作，使得完成所有操作的最大完工時(shí)間最小。眾所周知FJSP是NP難問(wèn)題，求解該問(wèn)題可以采用精確方法和近似方法，由于NP難問(wèn)題的復(fù)雜性，精確方法在復(fù)雜FJSP上不適用，近似方法是目前研究FJSP的主流方法。

國(guó)內(nèi)外學(xué)者利用近似算法對(duì)FJSP的應(yīng)用進(jìn)行了大量研究。在進(jìn)化算法(Evolutionary Algorithms，EA)方面，學(xué)者們根據(jù)FJSP的特點(diǎn)對(duì)編碼、初始種群、選擇、交叉以及變異進(jìn)行了大量研究，很多研究還將局部搜索算法嵌入EA，加強(qiáng)了EA算法的局部開(kāi)發(fā)能力[1-2]。在群體智能算法(SI)方面。姜飛等人[3]以最大完工時(shí)間和客戶(hù)滿(mǎn)意度為目標(biāo)，通過(guò)灰狼優(yōu)化算法對(duì)多目標(biāo)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行了研究。姚遠(yuǎn)遠(yuǎn)、葉春明[4]以最小化最大完工時(shí)間為目標(biāo)，通過(guò)改進(jìn)混合灰狼算法對(duì)作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行了研究，與布谷鳥(niǎo)搜索算法進(jìn)行對(duì)比，驗(yàn)證了改進(jìn)GWO求解作業(yè)車(chē)間調(diào)度問(wèn)題的有效性。吳繼浩、楊濤[5]結(jié)合改進(jìn)GWO算法與模擬退火算法對(duì)FJSP進(jìn)行了研究。姜天華[6]以最小制造時(shí)間為目標(biāo)對(duì)JSP和FJSP設(shè)計(jì)了離散GWO算法。由于FJSP的本質(zhì)是離散的，故對(duì)FJSP應(yīng)用GWO之前要實(shí)現(xiàn)灰狼個(gè)體位置的離散性和多樣性。

考慮到GWO與局部搜索算法集成的便利性，本文作者首先采用機(jī)器和工序的雙層編碼策略，并設(shè)計(jì)種群初始化方案；其次評(píng)估初始種群質(zhì)量，并進(jìn)行精英保留和錦標(biāo)賽選擇；接著為了尋找操作序列的最優(yōu)順序，對(duì)操作序列設(shè)計(jì)了GWO鄰域搜索；然后對(duì)生成的最優(yōu)序列執(zhí)行TS搜索。此外，為了搜索種群中最優(yōu)灰狼個(gè)體位置周?chē)乃阉骺臻g，對(duì)灰狼個(gè)體位置設(shè)計(jì)了變異操作。最后通過(guò)基準(zhǔn)實(shí)例的仿真實(shí)驗(yàn)，評(píng)估改進(jìn)GWO算法求解FJSP的性能。

1 模型建立

目前FJSP公認(rèn)的數(shù)學(xué)模型是存在一組作業(yè)J={J1，…，Jn}和若干機(jī)器M={M1，…，Mm}，每個(gè)作業(yè)有若干操作，即Ji={Oi，j，…，Oi，ni}，其中ni是Ji的操作總數(shù)，每個(gè)操作都有對(duì)應(yīng)的機(jī)器子集Mi，j?M，問(wèn)題要求是將所有操作分配到對(duì)應(yīng)機(jī)器上且要保證每臺(tái)機(jī)器上的操作序列是最優(yōu)的，即保證所有作業(yè)的最大完工時(shí)間最小min(Cmax)。

2 灰狼優(yōu)化器原理

灰狼優(yōu)化器原理如圖1所示。α、β、δ狼稱(chēng)為領(lǐng)導(dǎo)者，ω狼稱(chēng)為進(jìn)攻者，一個(gè)灰狼個(gè)體代表了一個(gè)可行的調(diào)度方案，位于金字塔頂端的α狼代表最優(yōu)調(diào)度方案。當(dāng)初始種群確定后，按照灰狼個(gè)體的最大制造跨度將所有灰狼個(gè)體進(jìn)行排列，以確定最好的領(lǐng)導(dǎo)者和攻擊者，GWO的搜索行為由領(lǐng)導(dǎo)者進(jìn)行引導(dǎo)。灰狼算法搜索過(guò)程可分為圍捕、狩獵和攻擊3個(gè)階段。

圖1 灰狼領(lǐng)導(dǎo)層級(jí)

2.1 圍捕

圍捕階段，由式(1)(2)完成對(duì)獵物的包圍。

Dp=|C·Xp(t)-X(t)|

(1)

X(t+1)=Xp(t)-A·Dp

(2)

式中：t為迭代次數(shù)；Xp為獵物位置；X為ω狼的位置；Dp為獵物與ω狼之間的絕對(duì)距離；A和C是系數(shù)向量，由式(3)(4)確定。

A=2ar1-a

(3)

C=2r2

(4)

式中：r1、r2∈rand(0，1)是隨機(jī)向量；a是收斂系數(shù)，從2逐漸下降到0，由式(5)確定。

(5)

式中：a1=2和a2=0為收斂系數(shù)的初始值和終止值；n為遞減系數(shù)，n=1-t/tmax。

2.2 狩獵

在狩獵階段，由于獵物位置(最優(yōu)解)未知，故領(lǐng)導(dǎo)狼需預(yù)測(cè)獵物的潛在位置，而進(jìn)攻狼根據(jù)領(lǐng)導(dǎo)狼的位置進(jìn)行調(diào)整，以便攻擊獵物。式(6)—(8)描述如下：

(6)

X1=Xα-A1·Dα

X2=Xβ-A2·Dβ

X3=Xδ-A3·Dδ

(7)

(8)

2.3 攻擊

灰狼是否對(duì)獵物發(fā)動(dòng)攻擊由收斂系數(shù)A決定，當(dāng)|A|≥1時(shí)，灰狼與獵物疏遠(yuǎn)進(jìn)行全局搜索；當(dāng)|A|<1時(shí)，灰狼接近獵物完成獵殺任務(wù)。

3 改進(jìn)GWO算法的實(shí)現(xiàn)

由于GWO算法求解FJSP時(shí)會(huì)很快陷入局部最優(yōu)，故將禁忌搜索算法(Tabu Search，TS)嵌入到GWO算法中，以輔助GWO算法跳出局部最優(yōu)。所提GWO算法工作流程如圖2所示。

圖2 GWO算法的工作流程

3.1 編碼與解碼

由于編碼策略不僅影響算法各部分的連接和解碼效率，而且對(duì)GWO與局部搜素算法的集成至關(guān)重要。因此采用機(jī)器分配和操作排序雙層編碼策略，將作業(yè)、機(jī)器和加工時(shí)間一一對(duì)應(yīng)。首先在區(qū)間[-n，n]內(nèi)生成一個(gè)由實(shí)數(shù)組成的灰狼位置向量，向量中的元素符合均勻分布，且該向量與作業(yè)操作數(shù)量的長(zhǎng)度相等，其中n表示作業(yè)數(shù)量，接著利用ROV規(guī)則將灰狼位置向量中的元素轉(zhuǎn)換為對(duì)應(yīng)的操作序列，圖3所示為轉(zhuǎn)換之后的操作序列：1→3→3→2→1→2→3→1→2。序列中相同數(shù)字出現(xiàn)的次數(shù)表示作業(yè)的第幾次操作。如序列中第一個(gè)1代表第一個(gè)作業(yè)第一個(gè)操作O11，第二個(gè)1代表第一個(gè)作業(yè)第二個(gè)操作O12，其余作業(yè)操作依次類(lèi)推。然后根據(jù)每個(gè)操作的可選機(jī)器集長(zhǎng)度為每個(gè)操作隨機(jī)分配一臺(tái)機(jī)器。

圖3 編碼策略

3.2 種群初始化

根據(jù)第3.1節(jié)獲得的機(jī)器序列和操作序列生成初始種群，方法如下：在機(jī)器分配階段，首先依據(jù)操作Oi，j的加工條件，在可選機(jī)器集中為操作Oi，j選擇加工時(shí)間最短的機(jī)器M1和可行時(shí)間最早的機(jī)器M2，分別計(jì)算操作Oi，j在機(jī)器M1和M2上的完成時(shí)間T1和T2，若T1

3.3 搜索獵物

應(yīng)用GWO算法求解FJSP的關(guān)鍵是保證GWO算法的全局性和多樣性。故針對(duì)操作序列設(shè)計(jì)了交叉鄰域、插入鄰域和路徑重連鄰域3種鄰域函數(shù)，鄰域函數(shù)表達(dá)式為式(9)，所設(shè)計(jì)GWO算法鄰域搜索結(jié)構(gòu)如圖4所示。式(9)中Xk表示由鄰域函數(shù)得到第k個(gè)灰狼的調(diào)度方案，Insertion函數(shù)定義了對(duì)Xβ進(jìn)行插入鄰域，Swapping函數(shù)定義了對(duì)Xα進(jìn)行交叉鄰域，PathRelinking函數(shù)定義了對(duì)Xδ進(jìn)行路徑重連鄰域，r∈[0，1]是隨機(jī)數(shù)。

(9)

圖4 GWO算法鄰域搜索結(jié)構(gòu)

GWO算法鄰域搜索步驟如下：

步驟1，設(shè)置迭代次數(shù)k=1和鄰域數(shù)量Δ，令Δ=1，2，…，Δmax，選擇較優(yōu)的灰狼個(gè)體Xk(t)。

步驟2，隨機(jī)生成一個(gè)隨機(jī)數(shù)r≤[0,1]，執(zhí)行以下程序：

(1)若r≤1/3，則執(zhí)行Swapping鄰域產(chǎn)生一個(gè)新的調(diào)度方案α。

(2)若1/3

(3)若r>2/3，則執(zhí)行PathRelinking領(lǐng)域產(chǎn)生一個(gè)新的調(diào)度方案δ。

步驟3，判斷k≤Δmax是否成立，若條件成立，令k=k+1，則轉(zhuǎn)到步驟2，否則轉(zhuǎn)到步驟4。

步驟4，根據(jù)式(6)—(8)更新α、β和δ狼的個(gè)體位置。

步驟5，按照α、β和δ狼的makespan進(jìn)行排列。

步驟6，輸出最優(yōu)調(diào)度方案α。

3.3.1 交叉鄰域

首先在OS序列中隨機(jī)選擇2個(gè)不同的位置k1和k2，然后將k1和k2位置上的序列交換，其余序列的位置不變。交叉鄰域如圖5所示。

圖5 交叉鄰域

3.3.2 插入鄰域

首先在OS序列中隨機(jī)選擇2個(gè)不同的位置k1和k2，若k1

圖6 插入鄰域

3.3.3 路徑重連鄰域

PR鄰域如圖7所示。具體表述如下：首先從初始種群中隨機(jī)確定起始解OS和導(dǎo)向解OS′，然后建立路徑解，即比較OS與OS′中第i個(gè)位置上的序列是否相等，若相等，則保持OS中第i個(gè)位置上的序列不變，否則在OS中找到與OS′序列相等的第j個(gè)序列，將OS中第j個(gè)序列插入到第i-1個(gè)序列的后面，重復(fù)上述過(guò)程直到最后一個(gè)路徑解與導(dǎo)向解完全一致，最后計(jì)算每個(gè)路徑解的最大制造跨度，選擇最大制造跨度最小的路徑解作為新的個(gè)體。

圖7 PR鄰域

3.3.4 機(jī)器變異

根據(jù)操作序列OS的長(zhǎng)度，變異位置個(gè)數(shù)取OS長(zhǎng)度的一半并左取整，接著將所選位置的機(jī)器更改為對(duì)應(yīng)操作的可選機(jī)器集中的其他機(jī)器。機(jī)器變異如圖8所示。圖8中OS長(zhǎng)度為9，變異位置為4，選擇操作O1，1、O2，2、O2，3和O3，2的機(jī)器序列進(jìn)行變異，例如O1，1的可選機(jī)器為M1和M3，變異前為M3，變異后為M1。

圖8 機(jī)器變異

3.4 TS搜索

TS算法[7]從一個(gè)可行解出發(fā)，通過(guò)關(guān)鍵加工路徑的Nopt1鄰域搜索最優(yōu)解[8]。TS的初始調(diào)度方案為α，TS搜索流程如圖9所示，執(zhí)行步驟如下：

圖9 TS搜索流程

步驟1，設(shè)置TS迭代次數(shù)k、s，置禁忌表為空，初始調(diào)度方案為α，禁忌迭代次數(shù)Tn，禁忌閾值Tu。

步驟2，判斷k≥Tn是否成立，若條件成立，則執(zhí)行步驟8，否則執(zhí)行步驟3。

步驟3，獲取α的關(guān)鍵加工路徑上的操作和機(jī)器分配，改變關(guān)鍵操作的機(jī)器分配生成新鄰域，估計(jì)每種鄰域的最佳制造跨度。

步驟4，判斷s≥Tu是否成立，若條件成立，則執(zhí)行步驟5，否則執(zhí)行步驟6。

步驟5，將滿(mǎn)足藐視準(zhǔn)則的候選解作為當(dāng)前解，并執(zhí)行步驟7。

步驟6，判斷候選解的禁忌屬性，選擇鄰域中非禁忌的最佳解作為當(dāng)前解，并執(zhí)行步驟7。

步驟7，更新禁忌列表，轉(zhuǎn)到步驟2。

步驟8，輸出最優(yōu)調(diào)度方案。

在GWO鄰域搜索階段，首先通過(guò)Swapping、Inserting和PathRelinking鄰域和機(jī)器變異得到操作分配的最優(yōu)方案α，然后對(duì)α分配方案進(jìn)行TS搜索，對(duì)于每個(gè)Nopt1鄰域要先確定關(guān)鍵加工路徑中的關(guān)鍵操作，調(diào)整這些操作可以有效優(yōu)化makespan。在TS搜索過(guò)程中，TS迭代次數(shù)隨著GWO迭代次數(shù)的增加而增加，TS禁忌閾值由關(guān)鍵加工路徑上操作數(shù)量的倍數(shù)組成。

3.5 變異操作

由于當(dāng)前個(gè)體的位置更新依賴(lài)于最佳狼α、β和δ的位置信息，這種更新機(jī)制往往缺失種群多樣性，易使算法早熟收斂。故通過(guò)式(10)對(duì)最佳領(lǐng)導(dǎo)個(gè)體進(jìn)行變異操作，以使領(lǐng)導(dǎo)個(gè)體從自身搜索空間周?chē)剿餍碌淖顑?yōu)解[9]。

(10)

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

4.1 實(shí)驗(yàn)設(shè)置

改進(jìn)GWO算法在Intel(R) Core(TM) i5-6300HQ CPU @2.30 GHz,4 GB RAM的PC上運(yùn)行，運(yùn)行系統(tǒng)為Windows10專(zhuān)業(yè)版，代碼在MATLAB2021a上實(shí)現(xiàn)。實(shí)驗(yàn)中選擇58個(gè)測(cè)試實(shí)例驗(yàn)證改進(jìn)GWO算法的有效性。這些測(cè)試基準(zhǔn)分別是Brandimate(1993)的10個(gè)實(shí)例(MK01-MK10)、Kacem(2002)的5個(gè)實(shí)例(K01-K05)、Hurink(1994)等的43個(gè)實(shí)例(mt06、mt10、mt20以及LA01-LA40)。表1為改進(jìn)GWO算法的參數(shù)設(shè)置。

表1 改進(jìn)GWO算法參數(shù)設(shè)置

4.1.1 實(shí)驗(yàn)一

表2為改進(jìn)GWO算法與其他算法在Kacem測(cè)試實(shí)例上的結(jié)果對(duì)比。HA[1]、HGWO[6]、TS[7]、VNSGA[10]、Heuristic[11]、MA[12]、IWOA[13]、GLNSA[14]為對(duì)比算法，在以上算法中只有 GLNSA、Heuristic、HGWO以及IWOA算法獲得了Kacem算例的完整解，其中僅有GLNSA算法達(dá)到目前已知的最優(yōu)解，改進(jìn)GWO算法獲得的最優(yōu)解優(yōu)于HGWO，與GLNSA算法的最優(yōu)解相當(dāng)，此外改進(jìn)GWO算法運(yùn)行時(shí)間也優(yōu)于HGWO算法。

表2 Kacem算例實(shí)驗(yàn)數(shù)據(jù)對(duì)比

4.1.2 實(shí)驗(yàn)二

表3為改進(jìn)GWO算法與其他算法在Brandimate測(cè)試實(shí)例上的結(jié)果對(duì)比。HA[1]、GA-RRHC[2]、HGWO[6]、Heuristic[11]、MA[12]、IWOA[13]、GLNSA[14]、HLOA[15]、PSO+TS[16]為對(duì)比算法。在對(duì)比算法中HLOA和HA算法結(jié)果較好，Heuristic算法運(yùn)行時(shí)間最短，但運(yùn)行結(jié)果最差；改進(jìn)GWO算法優(yōu)于HGWO算法，取得了5個(gè)測(cè)試實(shí)例的最佳解，且改進(jìn)算法具有更短的運(yùn)行時(shí)間，與其他算法相比，改進(jìn)算法具有一定的競(jìng)爭(zhēng)性。

表4 對(duì)比算法在Brandimate算例上的RPD值對(duì)比

4.1.3 實(shí)驗(yàn)三

表5為改進(jìn)GWO算法與其他算法在Hurink測(cè)試實(shí)例上的結(jié)果對(duì)比。HA[1]、GA-RRHC[2]、GLNSA[14]、IATS[15]為對(duì)比算法，其中GLNSA、GA-RRHC和HA算法獲得的最優(yōu)解相當(dāng)，都獲得了32個(gè)測(cè)試實(shí)例的最佳解，改進(jìn)GWO算法獲得了30個(gè)測(cè)試實(shí)例的最優(yōu)解，高于IATS算法所獲得測(cè)試實(shí)例最優(yōu)解的個(gè)數(shù)。

表5 Hurink vdata實(shí)例實(shí)驗(yàn)結(jié)果對(duì)比

5 結(jié)論

文中以最大完工時(shí)間為目標(biāo)，應(yīng)用改進(jìn)GWO求解了柔性作業(yè)車(chē)間的調(diào)度問(wèn)題。首先改進(jìn)了GWO的編碼方案、種群初始化、灰狼變異以及種群更新機(jī)制，其次通過(guò)交叉鄰域、插入鄰域以及PR鄰域得到GWO算法全局搜索鄰域，接著提出禁忌搜索鄰域以增強(qiáng)GWO算法局部開(kāi)發(fā)能力。最后將所提算法在已知的著名算例上進(jìn)行仿真實(shí)驗(yàn)，并與其他算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)GWO算法具有一定的優(yōu)越性。