一種改進(jìn)的求解柔性作業(yè)車間調(diào)度問(wèn)題的灰狼算法

田云娜，田 園,劉 雪,趙彥霖

(延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

0 引 言

在制造系統(tǒng)中，生產(chǎn)調(diào)度是其中非常重要的一個(gè)環(huán)節(jié)，會(huì)直接影響企業(yè)的生產(chǎn)經(jīng)濟(jì)效益。經(jīng)典的生產(chǎn)調(diào)度問(wèn)題主要包括流水車間調(diào)度問(wèn)題和作業(yè)車間調(diào)度問(wèn)題。柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job-shop Scheduling Problem, FJSP)是對(duì)經(jīng)典作業(yè)車間調(diào)度問(wèn)題的擴(kuò)展，它是一類復(fù)雜的組合優(yōu)化問(wèn)題，已被證明屬于NP-hard問(wèn)題，主要特點(diǎn)是工件的加工路徑具有柔性，這大大增加了問(wèn)題的靈活性和復(fù)雜度。相對(duì)于作業(yè)車間調(diào)度問(wèn)題，F(xiàn)JSP具有更廣泛的實(shí)際應(yīng)用和更高的求解難度，因而其一經(jīng)提出便引起了高度關(guān)注。

在現(xiàn)有的關(guān)于FJSP的研究中，此類問(wèn)題的求解方法主要可以分為精確算法、啟發(fā)式算法和智能優(yōu)化算法3大類[1]。

精確算法指能夠求出問(wèn)題最優(yōu)解的算法，主要包括分支定界法、割平面法、動(dòng)態(tài)規(guī)劃等。雖然它能夠?yàn)檎{(diào)度找到全局最優(yōu)解，但它需要對(duì)問(wèn)題進(jìn)行統(tǒng)一建模。而對(duì)于復(fù)雜多變的生產(chǎn)調(diào)度問(wèn)題，單一的數(shù)學(xué)模型并不能考慮到所有因素，并且當(dāng)問(wèn)題規(guī)模和計(jì)算復(fù)雜度不斷增加時(shí)，尋求最優(yōu)解的時(shí)間將會(huì)呈指數(shù)級(jí)上升。啟發(fā)式算法被用于解決精確算法難以在短時(shí)間內(nèi)求解的問(wèn)題。啟發(fā)式規(guī)則是一類常見(jiàn)的啟發(fā)式方法，它憑借計(jì)算復(fù)雜度低、可實(shí)時(shí)調(diào)度等特點(diǎn)在生產(chǎn)調(diào)度問(wèn)題中被廣泛使用[2]。然而啟發(fā)式規(guī)則對(duì)于調(diào)度環(huán)境和目標(biāo)的依賴性較強(qiáng)，并不存在某一規(guī)則能在所有環(huán)境和評(píng)價(jià)標(biāo)準(zhǔn)下都表現(xiàn)出良好的性能。同時(shí)，啟發(fā)式規(guī)則尋優(yōu)能力較差，在復(fù)雜的加工環(huán)境下無(wú)法保證解的質(zhì)量[3]。

智能優(yōu)化算法是一類隨機(jī)搜索進(jìn)化算法，這類算法利用學(xué)習(xí)策略和已知信息搜索解，通過(guò)不斷迭代優(yōu)化生成問(wèn)題的解。經(jīng)典的智能優(yōu)化算法包括遺傳算法[4]、進(jìn)化策略[5]、遺傳規(guī)劃[6]、差分進(jìn)化等進(jìn)化算法和蟻群優(yōu)化算法[7]、粒子群優(yōu)化算法、人工蜂群算法[8]、飛蛾撲火算法[9]等群智能算法。由于算法原理簡(jiǎn)單、易于實(shí)現(xiàn)等特點(diǎn)，智能優(yōu)化算法被很多學(xué)者應(yīng)用于求解復(fù)雜的、大規(guī)模的組合優(yōu)化問(wèn)題。

本文擬解決的FJSP就是一類復(fù)雜離散組合優(yōu)化問(wèn)題，這類問(wèn)題規(guī)模大，計(jì)算復(fù)雜度高，很難通過(guò)精確算法求得全局最優(yōu)值，群智能算法的出現(xiàn)為解決這類問(wèn)題提供了新思路。董蓉等人[10]將遺傳算法和蟻群算法相結(jié)合提出一種混合算法求解FJSP；賈兆紅等人[11]提出了一種基于粒子群優(yōu)化和禁忌搜索的混合算法用以求解多目標(biāo)FJSP；李俊萱等人[12]提出了一種混合量子粒子群算法用以求解加工時(shí)間不確定的FJSP；鄭小操等人[13]提出了一種改進(jìn)人工蜂群算法用以求解模糊FJSP；Caldeira等人[14]針對(duì)3個(gè)目標(biāo)的多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題，提出了一種離散Jaya算法。

灰狼算法(Grey Wolf Optimizer, GWO)是由Mirjalili等人[15]根據(jù)灰狼捕食原理提出的一種新的群智能算法。由于GWO算法原理簡(jiǎn)單，需要調(diào)整的參數(shù)少，且搜索能力強(qiáng)，收斂速度快，因而被應(yīng)用于生產(chǎn)調(diào)度問(wèn)題的求解。姜天華[16]提出了一種混合灰狼優(yōu)化算法用以求解以優(yōu)化最大完工時(shí)間為目標(biāo)的FJSP；Lu等[17]提出了一種多目標(biāo)離散灰狼優(yōu)化求解焊接車間調(diào)度問(wèn)題；Komaki等[18]設(shè)計(jì)了一種混合多目標(biāo)灰狼優(yōu)化算法來(lái)解決多目標(biāo)動(dòng)態(tài)焊接調(diào)度問(wèn)題。

本文基于經(jīng)典的灰狼算法，在迭代過(guò)程中加入新的優(yōu)化策略，提出一種改進(jìn)的灰狼算法(IGWO)以求解FJSP。算法采用基于權(quán)值的編碼方式，將工序選擇不同機(jī)器進(jìn)行加工的概率用權(quán)值表示，以此實(shí)現(xiàn)連續(xù)編碼的離散化；然后通過(guò)隨機(jī)游走策略加強(qiáng)局部搜索能力，并采用尾部淘汰策略進(jìn)行種群更新；最后，在基準(zhǔn)算例上進(jìn)行仿真實(shí)驗(yàn)，通過(guò)與其他算法進(jìn)行對(duì)比，驗(yàn)證IGWO求解FJSP的有效性。

1 問(wèn)題模型

本文優(yōu)化目標(biāo)為最大完工時(shí)間，接下來(lái)對(duì)所求問(wèn)題建立數(shù)學(xué)模型并求解。

1.1 問(wèn)題描述

設(shè)n個(gè)工件在m臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件有k道工序，每道工序可在若干臺(tái)機(jī)器上加工，工件內(nèi)工序加工順序及工序在不同機(jī)器上加工的時(shí)間一定。調(diào)度的目標(biāo)是為工序選擇合適的機(jī)器，并確定各機(jī)器上工序的加工順序，使某些指標(biāo)盡可能達(dá)到最優(yōu)。此外，還需滿足以下假設(shè)：

1)所有工件和機(jī)器在0時(shí)刻均處于就緒狀態(tài)。

2)同一時(shí)刻一臺(tái)機(jī)器只能加工一道工序。

3)同一道工序在同一時(shí)刻只能在一臺(tái)機(jī)器上進(jìn)行加工且只能加工一次。

4)工件一旦開(kāi)始加工就不允許中斷。

5)僅考慮同一工件內(nèi)工序加工的先后次序約束，不同工件間工序優(yōu)先級(jí)相同。

6)忽略機(jī)器的準(zhǔn)備時(shí)間，且不考慮機(jī)器故障。

1.2 變量定義

變量定義如下：

J={Ji|1≤i≤n}，表示工件集；

M={Mk|1≤k≤m}，表示機(jī)器集；

Oi={Oij|1≤j≤ni}，表示工件Ji的工序集；

Mij表示工序Oij的可選機(jī)器集合；

Pijk表示工序Oij在機(jī)器k上的加工時(shí)間；

L表示一個(gè)無(wú)窮大的正數(shù)；

Ci表示工件Ji的完工時(shí)間；

Cmax表示最大完工時(shí)間；

sijk表示Oij在k上的開(kāi)始加工時(shí)間；

fijk表示Oij在k上的完工時(shí)間；

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

本文以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式如公式(1)所示。

minCmax=min max(Ci), 1≤i≤n

(1)

根據(jù)實(shí)際生產(chǎn)中的問(wèn)題特性，本文約束條件描述如下:

Cmax≥Ci, ?i

(2)

spqk≥fijk-(1-yijpqk)×L

(3)

(4)

(5)

Ci≥0, ?i

(6)

sijk≥0,fijk≥0, ?i,j,k

(7)

其中，約束式(2)定義了最大完工時(shí)間；約束式(3)表示同一時(shí)刻一臺(tái)機(jī)器只能加工一個(gè)工件的一道工序；約束式(4)表示加工次序約束，即同一工件內(nèi)只有前一道工序完成后才能開(kāi)始加工下一道工序；約束式(5)表示每道工序會(huì)且僅會(huì)分配給一臺(tái)機(jī)器；約束式(6)和式(7)限制了決策變量的取值范圍。

2 改進(jìn)灰狼算法

2.1 經(jīng)典灰狼優(yōu)化算法

灰狼算法是通過(guò)模擬自然界中灰狼種群的社會(huì)等級(jí)和捕食行為而提出的一種群智能算法。在算法中，將狼群個(gè)體依照適應(yīng)度值由大到小排序，排在前3的個(gè)體分別定義為α、β和δ，其余個(gè)體均定義為ω，以此模仿灰狼的社會(huì)等級(jí)。為模擬灰狼狩獵過(guò)程，假定α、β和δ能夠獲得潛在獵物的位置。每次迭代開(kāi)始前，先找出α、β和δ，并保存好位置信息，其余個(gè)體均以此為依據(jù)更新自己的位置，按此方式迭代直至獵物被捕獲。上述過(guò)程可用以下公式表示：

(8)

(9)

(10)

A=2a·r1-a

(11)

C=2r2

(12)

(13)

其中，X是表示灰狼個(gè)體位置的向量，A和C是系數(shù)向量，可以根據(jù)公式(11)和(12)得到，r1和r2是[0,1]上的隨機(jī)向量，t表示當(dāng)前迭代次數(shù)，T表示最大迭代次數(shù)。公式(8)計(jì)算個(gè)體到α、β、δ的距離，公式(9)確定個(gè)體的移動(dòng)方向，a在迭代過(guò)程中根據(jù)公式(13)從2遞減到0。

2.2 編碼解碼

2.2.1 編碼機(jī)制

FJSP包含機(jī)器分配和工序排序2個(gè)子問(wèn)題，本文采用基于權(quán)值的方式，對(duì)2個(gè)子問(wèn)題分別進(jìn)行編碼。

1)機(jī)器分配。

對(duì)于具有柔性的工件，每道工序選擇不同的機(jī)器進(jìn)行加工時(shí)所對(duì)應(yīng)的權(quán)值是不同的，在對(duì)一道工序進(jìn)行機(jī)器分配時(shí)，權(quán)值較大的機(jī)器被選中的概率較高。部分示例編碼如表1所示。

表1 機(jī)器分配編碼

表1表示一個(gè)有3道工序的工件，每道工序?qū)?yīng)不同的機(jī)器有相應(yīng)的權(quán)值，例如，第1道工序O11選擇機(jī)器1加工的權(quán)值為0.1，選擇機(jī)器2加工的權(quán)值為0.5，O11不能在機(jī)器3上加工，依此類推。

2)工序排序。

機(jī)器分配結(jié)束后，對(duì)于被分配到同一臺(tái)機(jī)器的工序而言，權(quán)值大的被優(yōu)先加工的概率較高。部分示例編碼如表2所示。

表2列舉了M1和M5這2臺(tái)機(jī)器緩沖池中待加工工序，以及每道工序?qū)?yīng)的權(quán)值。其中O11、O22和O31被分配到M1上，O12、O21和O32被分配到M5上。每道工序的權(quán)值將作為解碼時(shí)的選擇依據(jù)。

表2 工序排序編碼

2.2.2 解碼機(jī)制

1)機(jī)器分配。

機(jī)器分配部分解碼過(guò)程如圖1所示。機(jī)器分配部分，得到的解形如[[1,2,0],[3,1,0]]，其中0、1、2等數(shù)字為位置索引，O11的可選機(jī)器集MO11={M1,M2,M4,M5}，于是O11選擇的加工機(jī)器為MO11[1]=M2，以此方式解碼，可得到機(jī)器分配方案。

圖1 機(jī)器分配解碼過(guò)程

2)工序排序。

工序排序部分解碼過(guò)程如圖2所示。

圖2 工序排序解碼過(guò)程

圖2中，(0,(0,2))表示工件1的第3道工序在機(jī)器1上加工，(1,(0,0))表示工件1的第1道工序在機(jī)器2上加工，按照此方法解碼，最終可得到一個(gè)完整的調(diào)度方案。

2.3 隨機(jī)游走

隨機(jī)游走能夠擴(kuò)大人工狼的搜索范圍，在一定程度上增加種群多樣性，以達(dá)到增強(qiáng)搜索廣度、加強(qiáng)算法局部搜索能力的目的。

令種群中除α、β、δ以外的Nr匹人工狼進(jìn)行以自我為中心的局部搜索，Nr取[ns·wr]，ns為種群大小，ωr為隨機(jī)游走率。記人工狼i向第p(p=1,2,…,h)個(gè)方向游走前后的適應(yīng)度值分別為Yi和Yip，當(dāng)Yip

將人工狼i向第p(p=1,2,…,h)個(gè)方向游走定義為：在人工狼i的編碼Xi=[xi1,xi2,…,xin]中隨機(jī)選取2個(gè)值xip和xiq，對(duì)其進(jìn)行交換操作，并將此操作執(zhí)行h次。交換操作如圖3所示。

圖3 交換操作

人工狼i的編碼Xi=[0.1,0.2,0.5,0.3,0.2,0.2,0.1,0.3]，當(dāng)i向方向p游走時(shí)，隨機(jī)選取2個(gè)值xip=0.2和xiq=0.3，對(duì)xip和xiq執(zhí)行交換操作，于是Xi的編碼變?yōu)閇0.1,0.3,0.5,0.3,0.2,0.2,0.1,0.2]。

2.4 種群更新

種群更新采用尾部淘汰策略。在種群更新的過(guò)程中，一輪迭代結(jié)束后，淘汰適應(yīng)度值差的R匹狼，為使狼群規(guī)模不發(fā)生變化，再隨機(jī)產(chǎn)生R匹人工狼。由于R的取值會(huì)影響算法的尋優(yōu)性能，R過(guò)小不利于維護(hù)種群的多樣性，R過(guò)大會(huì)導(dǎo)致算法接近于隨機(jī)搜索。這里參考吳虎勝等人[19]的論文，令R的取值為[ns/(β+1),ns/β]之間的隨機(jī)整數(shù)，ns為種群大小，β為種群更新比例因子。

2.5 算法步驟

IGWO算法的具體步驟如下：

Step1設(shè)置參數(shù)并初始化種群：設(shè)置種群大小、最大迭代次數(shù)、最大游走次數(shù)、隨機(jī)游走率ωr等參數(shù)；創(chuàng)建初始種群，隨機(jī)產(chǎn)生一批初始解。

Step2計(jì)算適應(yīng)度值，尋找α、β、δ：計(jì)算每匹人工狼的適應(yīng)度值，然后按照適應(yīng)度值的排序選出最佳的3匹狼。

Step3隨機(jī)游走：令種群中滿足隨機(jī)游走條件的人工狼進(jìn)行以自我為中心的局部搜索。重復(fù)這一游走行為，直至某匹狼的適應(yīng)度值Yi

Step4包圍獵物：所有狼均向α、β、δ這3匹狼的方向靠近。位置更新過(guò)程根據(jù)式(8)～式(10)進(jìn)行，靠近的過(guò)程中若Yi

Step5種群更新：根據(jù)式(11)和式(12)更新A、C，并按照尾部淘汰策略進(jìn)行種群更新。

Step6若t>T或滿足停止條件，算法結(jié)束，輸出當(dāng)前最優(yōu)解；否則，轉(zhuǎn)到Step2。

綜上，IGWO算法流程圖如圖4所示。

圖4 IGWO算法流程圖

3 實(shí)驗(yàn)分析

為驗(yàn)證所提算法的優(yōu)化性能，本文進(jìn)行了多組對(duì)比實(shí)驗(yàn)。仿真實(shí)驗(yàn)采用Python語(yǔ)言，在Win10系統(tǒng)下內(nèi)存16 GB的i7-4790 CPU @ 3.60 GHz計(jì)算機(jī)上運(yùn)行。

3.1 實(shí)驗(yàn)設(shè)計(jì)

由于FJSP是一類經(jīng)典的生產(chǎn)調(diào)度問(wèn)題，研究者們?cè)趯?duì)此類問(wèn)題進(jìn)行研究時(shí)普遍選擇一些通用的標(biāo)準(zhǔn)算例作為測(cè)試用例，如Brandimarte[20]和Kacem等人[21]所采用的的測(cè)試用例。這2組測(cè)試用例的規(guī)模分別是從4×5到15×10和10×6到20×15，能較好地測(cè)試算法在各規(guī)模下的有效性。鑒于實(shí)驗(yàn)對(duì)比公平性，本文也選取Brandimarte和Kacem測(cè)試問(wèn)題對(duì)算法進(jìn)行驗(yàn)證。

本章首先將所提算法與GWO相關(guān)算法進(jìn)行比較，對(duì)算法中添加的策略的有效性進(jìn)行驗(yàn)證，然后與其它文獻(xiàn)中的經(jīng)典算法進(jìn)行比較以進(jìn)一步驗(yàn)證所提算法的優(yōu)化性能。

3.2 參數(shù)設(shè)置

本文首先設(shè)置種群大小ns=100，最大迭代次數(shù)T=300，并選取Brandimarte實(shí)例中的Mk01(10×6)、Mk07(20×5)、Mk09(20×10)以及Mk10(20×15)這4個(gè)實(shí)例分別進(jìn)行多次實(shí)驗(yàn)，再選取部分實(shí)驗(yàn)結(jié)果繪制出每個(gè)實(shí)例的收斂曲線，由圖5可知，迭代均可在前150次以內(nèi)完成，因此設(shè)置最大迭代次數(shù)T=200。

然后，分別設(shè)置群大小為20、50、100、150以及200，以Mk07與Mk10為例對(duì)每個(gè)參數(shù)值獨(dú)立運(yùn)行15次后取平均值，得到圖6，可以看出，當(dāng)ns>100時(shí)，結(jié)果沒(méi)有明顯的變化，因此設(shè)置種群大小ns=100。此外，IGWO算法還有3個(gè)關(guān)鍵參數(shù)：游走次數(shù)Trmax、游走步長(zhǎng)μ和游走率ωr。

(a) Mk01收斂曲線

(a) Mk07

由于不同的參數(shù)設(shè)置對(duì)算法性能有不同影響，因此，本文以Brandimarte實(shí)例中的Mk06算例為測(cè)試用例，通過(guò)正交試驗(yàn)設(shè)計(jì)方法進(jìn)行參數(shù)設(shè)置實(shí)驗(yàn)。實(shí)驗(yàn)參考謝銳強(qiáng)等人[22]的方法，利用正交試驗(yàn)表L9(33)進(jìn)行實(shí)驗(yàn)，算法中3個(gè)關(guān)鍵參數(shù)的選取參考現(xiàn)有狼群算法。表3為實(shí)驗(yàn)中3個(gè)參數(shù)不同的水平值設(shè)置。

表3 參數(shù)水平

參數(shù)實(shí)驗(yàn)中將每個(gè)參數(shù)組合獨(dú)立運(yùn)行15次，所選正交組數(shù)以及對(duì)應(yīng)的適應(yīng)度平均值(AVG)匯總統(tǒng)計(jì)見(jiàn)表4。

表4 正交表和AVG統(tǒng)計(jì)

為了查看每個(gè)參數(shù)在不同水平下的總體表現(xiàn)，取每個(gè)水平值下3個(gè)組合的平均值進(jìn)行衡量，表5展示了3個(gè)關(guān)鍵參數(shù)的響應(yīng)值。根據(jù)表5得到每個(gè)參數(shù)的影響因子水平趨勢(shì)，如圖7所示。

表5 各參數(shù)響應(yīng)值

(a) 游走次數(shù)靈敏度分析

綜合考慮算法的復(fù)雜度及搜索質(zhì)量，建議的參數(shù)組合為：

Trmax=5,μ=0.4,ω=0.5

3.3 結(jié)果分析

本文實(shí)驗(yàn)驗(yàn)證主要分2部分進(jìn)行，首先是與經(jīng)典狼群和其他狼群相關(guān)算法的對(duì)比實(shí)驗(yàn)，然后是與其他群智能算法的對(duì)比實(shí)驗(yàn)。

與其他狼群算法的比較目的是出于對(duì)本文所提算法中添加的改進(jìn)策略的有效性進(jìn)行驗(yàn)證。對(duì)比對(duì)象包括經(jīng)典灰狼算法(GWO)、文獻(xiàn)[23]的DGWO算法、文獻(xiàn)[24]的GIWO算法。算法針對(duì)不同算例分別獨(dú)立運(yùn)行20次后進(jìn)行比較，對(duì)比結(jié)果如表6所示。

表6中Best表示算法獨(dú)立運(yùn)行20次獲得的最佳結(jié)果，粗體表示各算法經(jīng)過(guò)比較后IGWO在該算例下取到的最佳結(jié)果。Gap表示相對(duì)百分比偏差，其計(jì)算方法見(jiàn)公式(14)。

表6 GWO相關(guān)算法對(duì)比

(14)

其中，Best表示各算法運(yùn)行20次所得的最好結(jié)果，Min表示所有算法最好結(jié)果中的最小值。

根據(jù)表6中的數(shù)據(jù)和計(jì)算結(jié)果可以看出，相較于GWO，IGWO在每個(gè)算例中都能得到比GWO更好的解；作為改進(jìn)的灰狼算法，相較于DGWO和GIWO，10個(gè)標(biāo)準(zhǔn)算例中，GIWO取得了4個(gè)最好值，DGWO和IGWO各取得了7個(gè)最好值，且由Gap值的計(jì)算可知，雖然IGWO在剩余的3個(gè)算例中未取得最佳結(jié)果，但其Gap平均值為最小，說(shuō)明整體仍有較好的表現(xiàn)。

分析其原因:1)本文隨機(jī)游走策略是讓一部分狼進(jìn)行局部探索，這種方法有效提升了算法的廣度搜索能力；2)尾部淘汰策略去除了表現(xiàn)較差的解，用新生成的解替代差的解，在補(bǔ)充解多樣性的同時(shí)，有利于提升算法的收斂能力。

其次，為驗(yàn)證IGWO算法在求解FJSP時(shí)的性能，對(duì)于Brandimarte數(shù)據(jù)集，將IGWO算法與文獻(xiàn)[25]的DPSO算法、文獻(xiàn)[26]的MATSLO算法、以及文獻(xiàn)[27]的heuristic算法進(jìn)行對(duì)比；對(duì)于Kacem數(shù)據(jù)集，將IGWO算法與DPSO算法、文獻(xiàn)[28]的ABC算法以及heuristic算法進(jìn)行對(duì)比。各種算法在Brandimarte實(shí)例和Kacem實(shí)例上的對(duì)比結(jié)果分別如表7和表8所示，其中，粗體表示相同算例下各算法經(jīng)過(guò)比較后的最佳結(jié)果。

表7 Brandimarte算例對(duì)比

表8 Kacem算例對(duì)比

由表7和表8中的數(shù)據(jù)可以看出，在Brandimarte測(cè)試用例的10個(gè)算例中，IGWO算法在其中5個(gè)算例上均能夠獲得當(dāng)前最優(yōu)解；在Kacem測(cè)試用例的5個(gè)算例中，IGWO算法在其中4個(gè)算例上均有最好的表現(xiàn)。整體來(lái)看，IGWO算法可獲得60%以上的當(dāng)前最優(yōu)解。

同時(shí)，通過(guò)數(shù)據(jù)也可發(fā)現(xiàn)，IGWO算法并未在所有算例上都具有最好表現(xiàn)，尤其是在Brandimarte測(cè)試用例中有5個(gè)算例不是當(dāng)前最優(yōu)解。但結(jié)果展示，其他各個(gè)表現(xiàn)好的算法是分散在不同的算例上的，并未出現(xiàn)總體均優(yōu)的算法。

為進(jìn)一步說(shuō)明IGWO算法的優(yōu)化性能，本文計(jì)算了各種算法在Brandimarte實(shí)例上的Gap值及其平均值，計(jì)算方法參考公式(14)，對(duì)比結(jié)果如表9所示。通過(guò)對(duì)實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)，IGWO的Gap值為6.02%，接近表現(xiàn)最好的DPSO，這說(shuō)明本文所提算法的尋優(yōu)能力還是較好的。

表9 Brandimarte算例Gap值對(duì)比

IGWO與GWO相關(guān)算法和與其他群智能算法在Brandimarte算例上的Gap值比較如圖8所示。

由表9和圖8可知，IGWO算法對(duì)求解FJSP有較好的尋優(yōu)能力。綜合表6～表9中的數(shù)據(jù)以及圖8可得，在求解以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的FJSP問(wèn)題時(shí)，本文提出的IGWO算法具有一定的有效性。

(a) GWO相關(guān)算法Gap值比較

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

本文針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題特點(diǎn)，基于經(jīng)典灰狼算法提出了一種改進(jìn)的灰狼優(yōu)化算法，主要工作在于3個(gè)方面：1)采用基于權(quán)重的編碼，實(shí)現(xiàn)了對(duì)連續(xù)優(yōu)化算法的離散化；2)采用隨機(jī)游走策略，增強(qiáng)了算法的局部搜索能力；3)通過(guò)尾部淘汰策略實(shí)現(xiàn)了種群更新。最后通過(guò)在標(biāo)準(zhǔn)算例上進(jìn)行的仿真對(duì)比實(shí)驗(yàn)以及Gap值的比較，驗(yàn)證了改進(jìn)策略的有效性，并進(jìn)一步提高了灰狼算法在求解FJSP時(shí)的優(yōu)化性能。鑒于本文所提算法的優(yōu)化性能良好，接下來(lái)考慮將灰狼算法應(yīng)用于更為復(fù)雜的車間調(diào)度問(wèn)題中，同時(shí)考慮改進(jìn)算法的計(jì)算性能。