求解柔性作業(yè)車間調(diào)度問題算法綜述

田 園，田云娜，劉 雪

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

在制造系統(tǒng)中，生產(chǎn)調(diào)度是非常重要的一個環(huán)節(jié)，直接影響企業(yè)的生產(chǎn)經(jīng)濟效益。經(jīng)典的生產(chǎn)調(diào)度問題主要包括流水車間調(diào)度問題和作業(yè)車間調(diào)度問題。柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem,以下簡稱FJSP)是對經(jīng)典作業(yè)車間調(diào)度問題的擴展，其主要特點是在FJSP中工件的加工路徑并非唯一，而是具有柔性的，這一特點使得問題的靈活性和復(fù)雜性大幅增加。相對于作業(yè)車間調(diào)度問題(JSP)，F(xiàn)JSP具有更廣泛的實際應(yīng)用和更高的求解難度，這引發(fā)了研究者們極大的興趣。

本文主要針對FJSP進行相關(guān)介紹。首先對現(xiàn)有的求解FJSP的方法進行綜述，分別從精確、啟發(fā)式和智能優(yōu)化算法三個方面進行介紹，然后對FJSP的研究現(xiàn)狀進行總結(jié)分析，并討論其進一步的研究前景。

1 問題描述

FJSP通常描述如下：

n個工件在m臺機器上進行加工，每個工件有k道工序，每道工序的可選機器若干，工件內(nèi)工序加工順序及每道工序在不同機器上所需加工時間一定。調(diào)度的主旨是確定每道工序加工所選擇的機器及各機器上工序的加工次序，以使得所關(guān)心的主要指標(biāo)盡可能最優(yōu)。此外，對于FJSP還有以下約束和假設(shè)：

(1)所有工件和機器在零時刻均處于就緒狀態(tài)；

(2)同一時刻一臺機器只能加工一道工序；

(3)同一道工序在同一時刻只能在一臺機器上進行加工且只能加工一次；

(4)工序加工次序的約束僅考慮在同一工件內(nèi)；

(5)不考慮工件在加工過程中發(fā)生中斷；

(6)不考慮機器故障；

(7)各工件加工優(yōu)先級相同。

此處給出FJSP的數(shù)學(xué)模型。首先介紹相關(guān)符號。

模型參數(shù)：

n：工件總數(shù)

M：機器總數(shù)

Oij：工件i的第j道工序

Mij：工序Oij可選的機器集合Pijk：工序Oij在機器k上的加工時間

L：一個無窮大的正數(shù)

決策變量：

Ci：工件i的完工時間

Cmax：最大完工時間

Sijk：Oij在k上的開始加工時間

fijk：Oij在k上的完工時間

約束條件：

Cmax≥Ci,?i

(1.1)

Spqk≥fijk-(1-yijpqk)×L

(1.2)

(1.3)

(1.4)

Ci≥0,?i

(1.5)

Sijk>0,fijk>0,?i,j,k

(1.6)

其中，約束(1.1)定義了最大完工時間；約束(1.2)表示同一時刻一臺機器只能加工一道工序；約束(1.3)表示工序加工次序約束，即一個工件前一道工序結(jié)束后才能開始下一道工序；約束(1.4)表示每道工序會且僅會分配給一臺機器；約束(1.5)和約束(1.6)限制了決策變量的取值范圍。

目標(biāo)函數(shù)：

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

(1.7)

2 FJSP求解方法

FJSP于1990年由Brucker和Schlie[1]提出，其求解方法大致可以分為精確算法、啟發(fā)式算法和智能優(yōu)化算法三類。

2.1 精確算法

精確算法是指可求出最優(yōu)解的算法，主要包括分支定界法、割平面法、整數(shù)線性規(guī)劃，混合線性規(guī)劃等。針對柔性制造系統(tǒng)優(yōu)化問題，Lloyd等[2]提出了一種基于Petri網(wǎng)建模和改進分支定界搜索的調(diào)度算法，該算法首先對系統(tǒng)的Petri網(wǎng)建模進行了討論，然后采用改進的分支定界搜索算法實現(xiàn)調(diào)度算法；Jiang等[3]采用了0-1整數(shù)規(guī)劃，同時考慮了運行調(diào)度問題和交替過程計劃的生產(chǎn)路徑；Torabi等[4]提出了一種新的混合整數(shù)非線性規(guī)劃，對機器的分配、排序、批量大小和調(diào)度進行決策，以解決柔性作業(yè)車間中的公共周期多產(chǎn)品批量調(diào)度問題，其中問題的規(guī)劃周期是有限的。

精確算法是為調(diào)度目標(biāo)找到最優(yōu)的調(diào)度解，而非近優(yōu)解。當(dāng)問題規(guī)模很小時，利用精確算法找到問題的最優(yōu)解所需要的計算時間是可以接受的，然而當(dāng)問題規(guī)模逐漸增加，計算復(fù)雜度逐漸變高時，依照現(xiàn)有的計算條件，想要求出問題的最優(yōu)解就變得十分困難。

2.2 啟發(fā)式算法

啟發(fā)式算法實質(zhì)上是一組帶有建議性質(zhì)的規(guī)則集[5]，這個規(guī)則集可以用于指導(dǎo)算法搜索方向。在此規(guī)則集的指導(dǎo)下，可求得問題的較優(yōu)解，但不一定是最優(yōu)解?，F(xiàn)有啟發(fā)式算法大部分以啟發(fā)式規(guī)則為主，這些規(guī)則多來自于實際的調(diào)度問題。目前，包括調(diào)度規(guī)則在內(nèi)的許多啟發(fā)式算法已經(jīng)應(yīng)用于處理FJSP。

Panwalkar和Iskander[6]于1977年提出了113個分配規(guī)則，這些規(guī)則到今天仍然具有極為廣泛的應(yīng)用；Scrich等[7]在求解以最小化總拖期為優(yōu)化目標(biāo)的FJSP時，基于禁忌搜索提出了兩種啟發(fā)式算法，即分層過程和多重啟動過程，該方法利用調(diào)度規(guī)則得到初始解，然后在析取圖表示的關(guān)鍵路徑所生成的鄰域中搜索改進解；Shanker等[8]將啟發(fā)式算法與精確混合整數(shù)規(guī)劃進行比較，并結(jié)合FIFO，SPT，LPT以及MOPR四種調(diào)度規(guī)則，提出了系統(tǒng)性能評價的一種仿真模型；針對柔性制造系統(tǒng)，Chang等[9]提出了一種波束搜索啟發(fā)式算法，雖然這一算法比較復(fù)雜，但是與傳統(tǒng)的調(diào)度規(guī)則相比，其性能更好；針對以最小化生產(chǎn)訂單的平均拖期為優(yōu)化目標(biāo)，且具有轉(zhuǎn)移批次的FJSP，Calleja等[10]提出了一種具有一定優(yōu)先級的調(diào)度規(guī)則的算法，該算法考慮了有序變量和隨機變量兩個變量，使得分配規(guī)則具有優(yōu)先級，同時用戶可以為優(yōu)先級規(guī)則分配權(quán)重；Teymourifar等[11]設(shè)計了一種有效的調(diào)度規(guī)則來求解具有有限緩沖區(qū)的FJSP；針對動態(tài)調(diào)度問題，Ozturk等[12]通過模擬和基因表達式提出了兩種新的調(diào)度問題復(fù)合優(yōu)先級規(guī)則的提取方法，該方法能夠根據(jù)問題的特點得到特定的優(yōu)先級規(guī)則；Ortiz等[13]提出了一種解決實際FJSP的調(diào)度規(guī)則，并通過實例驗證了算法的性能。

針對實際具體的問題，啟發(fā)式算法能夠較快地作出反應(yīng)并給出可行的調(diào)度方案，更重要的是算法的求解復(fù)雜度對問題規(guī)模不敏感，即算法在問題規(guī)模很大時依然可行。因而在求解FJSP時啟發(fā)式算法發(fā)揮了重要作用。

2.3 智能優(yōu)化算法

智能優(yōu)化算法作為求解FJSP問題的重要研究方法，又可以分為進化算法(Evolution Algorithm，EA)和群智能算法(Swarm Intelligence，SI)等。

2.3.1 進化算法

EA的提出是受到自然界進化的啟發(fā)。經(jīng)典的EA包括遺傳算法[14](Genetic Algorithm，GA)、進化策略[15](Evolution Strategy，ES)、遺傳規(guī)劃[16](Genetic Programming，GP)和差分進化(Differential Evolution，DE)等。以上方法中，GA的研究與應(yīng)用最為廣泛和深入。

Yuan等[17]結(jié)合局部搜索提出了一種混合差分進化算法用以求解以最大完工時間最小化為優(yōu)化目標(biāo)的FJSP，算法首先通過轉(zhuǎn)換機制完成了從連續(xù)域到離散空間的轉(zhuǎn)變，然后在DE的基礎(chǔ)上嵌入一種基于關(guān)鍵路徑的局部搜索算法，通過算法局部搜索能力的增強來平衡搜索的廣度與深度；Wang等[18]針對動態(tài)FJSP提出了一種動態(tài)重調(diào)度方法，算法引入了重調(diào)度策略，另外還提出了改進的遺傳算法以優(yōu)化調(diào)度目標(biāo)；Cao等[19]選取多個優(yōu)化指標(biāo)建立模型，然后利用一種改進的差分進化算法求解多目標(biāo)FJSP，算法通過使用帕累托非支配排序方法，并引入設(shè)計良好的變異算子和交叉算子對DE進行改進；Huang等[20]在求解FJSP時采用一種基于反對學(xué)習(xí)的遺傳算法，算法采用雙鏈結(jié)構(gòu)完成對染色體的編碼，然后在進行遺傳操作時提出了兩種有效的交叉方法和兩種變異方法；Gu等[21]在進行復(fù)雜FJSP的求解時提出了一種基于模擬退火和遺傳算法的混合算法，算法利用云模型理論中的X條件云生成器生成遺傳操作中的變異概率，并將模擬退火操作作用于結(jié)果的變異性；趙詩奎[22]針對FJSP，將鄰域搜索嵌入遺傳算法然后進行求解；朱光宇等[23]針對多目標(biāo)FJSP選取多個優(yōu)化指標(biāo)建立模型，并采用基于直覺模糊相似度集的遺傳算法求解FJSP，首先為提高種群質(zhì)量，算法設(shè)計了一種考慮權(quán)重的啟發(fā)式規(guī)則，然后引入了一種新的染色體交叉方法以優(yōu)化算法性能，最后將解集中相似度值最大的解作為最優(yōu)解。

2.3.2 群智能算法

群體智能(Swarm Intelligence,SI)是指具有簡單智能的個體通過相互協(xié)作和組織表現(xiàn)出群體智能行為的特性[24]。通過觀察動物群體的機制或包括覓食、捕獵、求偶、飛行等在內(nèi)的某些社會行為，研究者們設(shè)計出了相應(yīng)的群智能優(yōu)化算法，這類算法提出后為人們解決科學(xué)、工業(yè)等領(lǐng)域的實際問題提供了新思路、新方法，得到了極為廣泛的應(yīng)用。在FJSP的求解上，它們也發(fā)揮了重要作用。

蟻群優(yōu)化(ant colony optimization，ACO)是由Dorigo等人受螞蟻覓食啟發(fā)于1991年提出的一種群智能算法，整個蟻群通過在所經(jīng)路徑上釋放信息素尋找蟻穴和食物之間的最短路徑。ACO的提出為解決FJSP提供了新思路。董蓉等[25]結(jié)合遺傳算法和蟻群算法提出了一種混合算法用以求解FJSP，算法首先利用遺傳算法給出信息素的初始分布，然后采取局部更新信息素的策略，最后利用交叉算子擴大解空間；Wang等[26]在利用蟻群算法對FJSP進行求解時，從五個方面對傳統(tǒng)蟻群算法進行了改進，這五方面分別是機器選擇規(guī)則、初始化機制、信息素引導(dǎo)機制、節(jié)點選擇方法、信息素更新機制；趙博選等[27]針對FJSP的兩個子問題提出了一種分層Pareto優(yōu)化框架，并利用該框架構(gòu)建了兩個Pareto蟻群系統(tǒng)分別求解這兩個問題。

粒子群優(yōu)化(Particle Swarm Optimization，PSO)是由Kennedy等學(xué)者受鳥群捕食啟發(fā)于1995年提出的一種群智能算法。Kato等[28]采用分層的方法將FJSP分為兩個子問題，然后利用PSO算法和隨機重啟爬山算法分別求解這兩個子問題，提升了新算法的尋優(yōu)能力；Zhang等[29]在對多目標(biāo)FJSP進行求解時，將禁忌搜索算法應(yīng)用在粒子群優(yōu)化中，并通過實驗證明了該混合算法具有良好的性能；Tang等[30]在求解FJSP時，將模擬退火算法應(yīng)用于PSO，并將PSO離散化，算法采用PSO進行全局搜索以避免過早產(chǎn)生局部最優(yōu)解，并結(jié)合模擬退火完成局部搜索；丁舒陽等[31]在利用改進的PSO求解FJSP時，首先將PSO離散化以使其適用于離散型問題的求解，然后通過引入操作算子完成FJSP兩個子問題的更新，以加快種群的收斂速度；李俊萱等[32]通過在量子粒子群算法中引入交叉算子及一種更新策略，設(shè)計了一種混合算法用以求解加工時間不確定的FJSP；賈兆紅等[33]將粒子群優(yōu)化和禁忌搜索相結(jié)合用以求解復(fù)雜的多目標(biāo)FJSP。

Karaboga從蜂群通過相互協(xié)作完成采蜜這一行為中獲得靈感于2005年提出了人工蜂群算法(artificial bee colony，ABC)；Gao等[34]在ABC的基礎(chǔ)上應(yīng)用啟發(fā)式規(guī)則，提出了一種改進的人工蜂群算法求解具有模糊加工時間的FJSP，并通過實驗對算法的性能進行了驗證；孟冠軍等[35]為求解多目標(biāo)FJSP提出了一種混合算法，該算法由禁忌搜索和改進的人工蜂群算法構(gòu)成；鄭小操等[36]對人工蜂群算法進行了改進，然后用其求解模糊柔性作業(yè)車間調(diào)度問題，算法通過在ABC的框架內(nèi)嵌入鄰域結(jié)構(gòu)以進行局部搜索，然后引入混沌理論，最后設(shè)計了一種交叉操作。通過模擬螢火蟲的閃光行為，Yang等[37]于2009年提出了螢火蟲算法(Firefly Algorithm，F(xiàn)A)；Karthikeyan等[38]提出一種改進的螢火蟲算法用以求解資源受限的多目標(biāo)FJSP，該問題中選取的優(yōu)化指標(biāo)為最大完工時間、關(guān)鍵機器的工作量和所有機器的總工作量，算法首先對螢火蟲算法完成從連續(xù)空間到離散空間的轉(zhuǎn)換，然后將離散的螢火蟲算法與局部搜索相結(jié)合，使得螢火蟲的搜索精度有所提升，同時更好地實現(xiàn)了信息共享。Mirjalili等[39]模擬灰狼內(nèi)部的社會層級和捕獵行為于2014年提出了灰狼優(yōu)化算法(Grey wolf optimizer，GWO)；根據(jù)Muro等[40]的說法，灰狼捕捉獵物主要有以下幾個步驟：追逐和接近獵物；包圍和騷擾獵物；攻擊獵物。GWO自提出后，已被成功應(yīng)用于FJSP的求解。姜天華[41]在求解FJSP時，通過嵌入變鄰域搜索策略及引入遺傳算子，提出了一種混合灰狼優(yōu)化算法，該算法建立起了GWO連續(xù)空間和FJSP離散空間的映射，同時其局部搜索能力和全局搜索能力也得到了很大提升。Mirjalili[42]從自然界中飛蛾的導(dǎo)航方法獲得靈感于2015年提出了飛蛾撲火算法；陶婷婷等[43]在求解以最小化最大完工時間為目標(biāo)的FJSP時，提出了一種改進離散型飛蛾撲火優(yōu)化算法，該方法首先通過集成法的求解思想，設(shè)計了兩段式編碼轉(zhuǎn)化機制，建立起染色體連續(xù)空間與問題離散決策空間的映射關(guān)系，實現(xiàn)了算法的離散化，然后在種群初始化階段采取有效的方法，保證了種群的多樣性和質(zhì)量，最后利用隨機更新算子和基于Levy飛行軌跡的隨機游走策略，以優(yōu)化算法性能。Mirjalili等[44]于2016年提出了鯨魚優(yōu)化算法(Whale Optimization Algorithm，WOA)，其靈感來源于鯨魚捕食。鯨魚進行捕獵時有兩種行為，一種是包圍獵物，所有的鯨魚都向著其他鯨魚前進；另一種是汽包網(wǎng)，鯨魚環(huán)形游動噴出氣泡來驅(qū)趕獵物。在每一代的游動中，鯨魚們會在這兩種行為中隨機選擇并進行捕獵。鯨魚在對獵物進行包圍的過程中，它們將會隨機選擇是向著最優(yōu)位置的鯨魚游去還是隨機選擇一只鯨魚作為自己的目標(biāo)并向其靠近。王思涵等[45]針對FJSP提出了一種改進的鯨魚優(yōu)化算法，首先將鯨魚算法離散化，為此算法設(shè)計了一種新穎的個體位置表達方式并給出了計算距離的方法，然后引入?yún)f(xié)同搜索機制以擴大搜索范圍，最后將變鄰域搜索算法應(yīng)用于改進的算法中以提高算法的局部搜索能力。

除以上提及的幾種算法外，還有多種群智能算法被應(yīng)用于FJSP的求解。Mekni等[46]對入侵雜草優(yōu)化算法進行了改進，用以求解多目標(biāo)FJSP，算法使用啟發(fā)式規(guī)則對算法進行離散化，然后通過實驗對算法性能進行了驗證；王新剛等[47]在求解FJSP時采用了細菌覓食算法(bacteriaforagingoptimization，BFO)，算法設(shè)計了一種改進的自適應(yīng)步停條件，避免了局部最優(yōu)和早熟問題。Ge等[48]針對以最小化最大完工時間為目標(biāo)的FJSP提出了一種有效的人工魚群分布估計模型，該算法首先設(shè)計了一種前原則和后原則的排列機制，通過調(diào)整不同順序的機器分配和操作順序來提高種群的多樣性。在此基礎(chǔ)上，將種群劃分為兩個子種群后采用兩種排列機制；然后基于分布估計設(shè)計了一種捕食行為，使得算法性能有所提升；最后通過一種吸引行為以提升算法的全局搜索能力，并提出了一種基于公共因子的關(guān)鍵路徑搜索策略來提高局部搜索能力。Xu等[49]對蝙蝠算法進行了改進用以求解FJSP，算法首先設(shè)計了一種基于雙柔度的編碼策略，然后設(shè)計了變異和交叉操作以增強算法的搜索能力，最后提出了線性減小慣性權(quán)重的策略以調(diào)整慣性權(quán)重的取值，從而解決BAT算法中參數(shù)固定帶來的問題。Liang等[50]在求解FJSP時提出了一種混合免疫算法，另外，算法為避免過早產(chǎn)生局部最優(yōu)解采用了模擬退火操作。Zheng等[51]提出了一種基于知識引導(dǎo)的果蠅優(yōu)化算法，算法首先采用了兩種基于置換的搜索算子分別對作業(yè)序列和資源分配兩個問題進行基于氣味的搜索，然后引入知識引導(dǎo)搜索階段以提高搜索能力，最后通過設(shè)計兩個新的搜索算子完成對操作順序和資源分配的調(diào)整。通過結(jié)合知識引導(dǎo)搜索與基于氣味的搜索，算法實現(xiàn)了全局搜索與局部搜索的平衡，并利用數(shù)值實驗證明了算法的有效性。

群智能算法原理簡單、魯棒性強，可在相對較短的時間內(nèi)尋得近優(yōu)解且易于實現(xiàn)，是一類很好的求解FJSP的方法。

3 結(jié)論及展望

隨著經(jīng)濟和社會的快速發(fā)展，制造業(yè)也必然會遇到越來越多的機遇和挑戰(zhàn)。智能制造是工業(yè)4.0需求的結(jié)果，大數(shù)據(jù)和人工智能等先進技術(shù)不僅為應(yīng)對這些挑戰(zhàn)提供了強有力的工具，同時還可以進一步指導(dǎo)制造業(yè)的新發(fā)展趨勢。而隨著制造業(yè)的快速發(fā)展，F(xiàn)JSP的需求和模式也一定會隨之發(fā)生改變。

3.1 FJSP的新模式

在將來，F(xiàn)JSP必然會有更多的模式，如動態(tài)調(diào)度、在線調(diào)度和實時調(diào)度等，與此同時，優(yōu)化目標(biāo)必然也會隨之增加。因此，為滿足實際需求，多目標(biāo)的FJSP應(yīng)該得到更多的關(guān)注。另外，個性化需求也變得越來越復(fù)雜，這使得現(xiàn)實的生產(chǎn)條件和客戶需求等實際的生產(chǎn)環(huán)境也越發(fā)復(fù)雜。所以在建立FJSP的數(shù)學(xué)模型時，除了考慮到基本的限制條件外，還應(yīng)考慮到如生產(chǎn)資源、緩沖區(qū)大小、批次大小和生產(chǎn)成本等更多的約束。

3.2 FJSP的新解決方法

如今，大數(shù)據(jù)的發(fā)展勢頭正猛，在遇到難以建立數(shù)學(xué)模型的工程優(yōu)化問題時，數(shù)據(jù)分析、機器學(xué)習(xí)以及神經(jīng)網(wǎng)絡(luò)訓(xùn)練等技術(shù)方法為解決這些問題提供了新的有效的求解途徑。例如，在優(yōu)化問題的模型建立過程中，可以通過大數(shù)據(jù)和人工智能技術(shù)從生產(chǎn)數(shù)據(jù)中提取有效的信息用以指導(dǎo)模型的建立，聯(lián)合數(shù)據(jù)模型驅(qū)動的求解方法可用于求解復(fù)雜的FJSP。同時這些技術(shù)還可以用于預(yù)測諸如機器故障、新訂單到達等隨機動態(tài)事件的發(fā)生，對于解決動態(tài)FJSP也有很好的效果。另外，多個案例證明，智能優(yōu)化算法在求解FJSP時具有很大的優(yōu)勢，因此在將來，更多的研究可以集中在新智能優(yōu)化算法的設(shè)計上，同時可以將不同的算法結(jié)合起來，充分利用每個算法的優(yōu)勢以便更好地解決FJSP。

3.3 FJSP的擴展

除了制造業(yè)中的生產(chǎn)調(diào)度問題，在其他領(lǐng)域也存在著大量的調(diào)度問題等待解決，例如電力系統(tǒng)、城市公交管理及醫(yī)療資源分配等。這些調(diào)度問題都可以通過將現(xiàn)有的FJSP數(shù)學(xué)模型和求解方法進行推廣然后求解。因此，將FJSP的數(shù)學(xué)模型和求解方法擴展到其他調(diào)度問題也將是未來的研究趨勢之一。