柔性作業(yè)車間調(diào)度問題簡明分析

何　斌，張接信，張富強

（長安大學(xué)工程機械學(xué)院，陜西 西安 710064）

0　引言

調(diào)度是通過一定的手段對有限的人力、物力、財力和時間資源進行科學(xué)合理的配置，在保證能夠獲得某些最優(yōu)性能的前提下使生產(chǎn)或作業(yè)過程高效有序地運行。調(diào)度的概念涉及生產(chǎn)計劃排程、企業(yè)管理、交通運輸工具的運行時刻與運行路徑規(guī)劃，網(wǎng)絡(luò)通訊等。在調(diào)度問題中，柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）最具代表性，F(xiàn)JSP問題所研究的是各個加工任務(wù)“何時何地”進行加工才能使某些性能指標(biāo)達到最優(yōu)，在小批量多品種的生產(chǎn)模式和日趨激烈的市場競爭下，如何合理調(diào)度車間生產(chǎn)任務(wù)，使加工時間和加工成本最小化、生產(chǎn)效益和客戶滿意度最大化，是制造企業(yè)生產(chǎn)過程中不可忽略的重要因素。目前，關(guān)于FJSP問題，前人已做了大量研究，但沒有進行詳細(xì)的歸類與分析，從而難以對FJSP問題有一個深刻的認(rèn)識和理解，也就難以針對具體的問題快速地建立模型并找到合適的解決辦法。因此，本文在總結(jié)已有研究成果的基礎(chǔ)上，對柔性作業(yè)車間調(diào)度問題的內(nèi)容作了簡要分析，并從優(yōu)化目標(biāo)的數(shù)量和是否考慮不確定性因素兩個方面對FJSP問題進行了綜合歸類和對比分析，使實際的調(diào)度問題能夠?qū)?yīng)到具體的調(diào)度類型，從而為調(diào)度模型的建立和問題的求解指明方向。

1　問題描述

車間調(diào)度是指按照被加工件的工藝規(guī)程，在現(xiàn)有生產(chǎn)能力和生產(chǎn)資源情況下，基于一個或多個優(yōu)化目標(biāo)以及相關(guān)約束條件，規(guī)劃出多個工件各工序間最優(yōu)的加工順序組合方案。作業(yè)車間調(diào)度問題（Job Shop Scheduling Problem，JSP）是車間調(diào)度問題的經(jīng)典類型，也是典型的組合優(yōu)化問題，其一般性描述為：n個工件在m臺機器上加工，各工序的加工機床和加工時間已定，所要解決的問題是確定每臺機床上待加工件的最優(yōu)加工順序。而柔性作業(yè)車間調(diào)度問題是JSP問題的擴展，此類問題中，工件每道工序的加工有一至多臺機床可供選擇，所要解決的問題一是為每道工序選擇最合適的機床，二是為每臺機床上的工件安排最優(yōu)的加工順序。FJSP問題約束性較JSP問題弱，故求解難度更大，是典型的NP難題。

2　FJSP問題基本內(nèi)容

FJSP問題主要包含問題類型、優(yōu)化目標(biāo)、約束條件、數(shù)學(xué)模型和求解方法五大要素，如圖1所示：

圖1　FJSP問題組成要素

FJSP問題的優(yōu)化目標(biāo)和約束條件如表1所示，其中的優(yōu)化目標(biāo)是車間調(diào)度問題中最敏感、最關(guān)心的性能指標(biāo)，而約束條件則是任一類型的車間調(diào)度問題都必須滿足的共同的約束條件，具體工況下的約束條件會有所增強。

表1　一般性優(yōu)化目標(biāo)與約束條件

對于一個具體的問題，從問題提出到解決，求解思路是貫穿始終的，F(xiàn)JSP問題的求解思路可分為整體法和分層法，前者同時考慮機器的選擇和工件的排序，通過統(tǒng)一編碼一次性求得結(jié)果，后者將問題一分為二。首先，為每道工序選擇機床，解決了FJSP問題的第一個難題；其次，為每個機床上的工件排序，解決了FJSP問題的第二個難題，分層法使FJSP問題退化為JSP問題，降低了求解難度，是目前大多數(shù)學(xué)者所采用的方法，在求解思路的指導(dǎo)下，采用某種數(shù)學(xué)方法即可對模型進行解算。近年來，隨著智能算法的發(fā)展和不斷完善，其在求解類似于車間調(diào)度一類的組合優(yōu)化問題方面的優(yōu)勢已日漸明顯，雖然屬于近似算法，但可以有效解決傳統(tǒng)算法難以解決的問題，并且求解結(jié)果在一定范圍內(nèi)已為大多數(shù)人所接受，因此，使用智能算法解決FJSP問題已經(jīng)成為了主流。

常用的智能算法有神經(jīng)網(wǎng)絡(luò)法、遺傳算法、粒子群算法、蟻群算法、模擬退火算法等等。彭建剛[1]等分析了各種智能算法求解車間調(diào)度問題的優(yōu)缺點，認(rèn)為人工神經(jīng)網(wǎng)絡(luò)法學(xué)習(xí)效率低、計算速度慢、精度低；遺傳算法計算速度快、易于和其他算法結(jié)合，但存在搜索范圍大、搜索時間長、早熟收斂等問題；差分進化算法與其他算法結(jié)合效果較好；粒子群算法收斂速度快、計算簡單，但易陷入局部優(yōu)化；蟻群算法起步較晚，尚不完善；混合蛙跳算法調(diào)整參數(shù)少、計算速度快、適用于多目標(biāo)優(yōu)化問題，但其在多目標(biāo)柔性作業(yè)車間調(diào)度方面的應(yīng)用還處于探索階段；模擬退火算法能夠有效解決多目標(biāo)柔性作業(yè)車間調(diào)度問題，但初始溫度的選擇和早熟收斂等問題還有待研究。同時，人們也在不斷地對基本智能算法進行改進用以解決更為復(fù)雜的車間調(diào)度問題，張于賢[2]等提出了一種基于生物記憶曲線模型的信息素更新規(guī)則對蟻群算法進行改進，克服了蟻群算法收斂速度慢、易陷入局部最優(yōu)的缺陷。孫亮[3]等提出了一種自適應(yīng)超啟發(fā)式遺傳算法求解隨機型作業(yè)車間調(diào)度問題，突破了隨機算法與局部搜索相結(jié)合的傳統(tǒng)算法解決此類問題時計算時間過長的缺陷。吳秀麗[4]等提出了一種改進的細(xì)菌覓食算法。王艷紅[5]等對蟻群算法進行改進，提出了一種動態(tài)平衡自適應(yīng)蟻群算法。

3　FJSP問題的分類

根據(jù)優(yōu)化目標(biāo)的數(shù)量，可將柔性作業(yè)車間調(diào)度問題分為單目標(biāo)調(diào)度問題和多目標(biāo)調(diào)度問題，根據(jù)是否考慮生產(chǎn)過程中的不確定因素，又可將其分為靜態(tài)調(diào)度問題和動態(tài)調(diào)度問題，常見的不確定因素有機器故障、機器的預(yù)防性維修、訂單異動、材料短缺等，表2所示為幾種常見不確定因素及對應(yīng)的解決辦法。通過對已有文獻的分析發(fā)現(xiàn)優(yōu)化目標(biāo)的數(shù)量以及是否考慮不確定因素對FJSP問題的復(fù)雜程度和求解難度有重要影響，據(jù)此，本文將FJSP問題分為單目標(biāo)靜態(tài)調(diào)度、多目標(biāo)靜態(tài)調(diào)度、單目標(biāo)動態(tài)調(diào)度、多目標(biāo)動態(tài)調(diào)度四種類型，并分析比較各自的特點。

表2　常見不確定因素及應(yīng)對策略

3.1　單目標(biāo)靜態(tài)調(diào)度

單目標(biāo)靜態(tài)調(diào)度是柔性作業(yè)車間調(diào)度中最簡單、最基本的調(diào)度類型，是其他調(diào)度類型的基礎(chǔ)，其優(yōu)化目標(biāo)明確且單一，通常為表1所示優(yōu)化目標(biāo)中的一種，約束條件則為表1所示的一般性約束，將優(yōu)化目標(biāo)和約束條件用恰當(dāng)?shù)臄?shù)學(xué)語言或數(shù)學(xué)手段詳細(xì)而準(zhǔn)確地表達出來即得到其數(shù)學(xué)模型，例如，當(dāng)加工時間是隨機變量時，為了方便計算，以最小化最大完工時間的期望值作為優(yōu)化目標(biāo)，并且常用模糊隸屬度函數(shù)來描述某些不確定性因素，并用數(shù)形結(jié)合的思想來表達某些目標(biāo)函數(shù)。楊建斌[6]等用三角模糊數(shù)和半梯形模糊數(shù)分別表示模糊加工時間和模糊交貨期，建立了以最大化最小客戶滿意度為優(yōu)化目標(biāo)的作業(yè)車間模糊調(diào)度模型，并采用自適應(yīng)遺傳算法求解了模型。黃亞平[7]等用三角模糊數(shù)表示模糊加工時間，用梯形模糊數(shù)表示模糊交貨期，以交貨期平均滿意度最大為優(yōu)化目標(biāo)，建立了作業(yè)車間的模糊調(diào)度模型，并采用自適應(yīng)蟻群算法對模型進行了求解。

另一方面，為了使調(diào)度模型更符合生產(chǎn)實際，往往需要添加新的約束條件，如考慮工序調(diào)整時間和工件在機器間的移動時間等，此時，所建立的數(shù)學(xué)模型中還應(yīng)當(dāng)包含新增加的約束條件所對應(yīng)的數(shù)學(xué)語言。張國輝[8]等在考慮工件移動時間的情況下建立了柔性作業(yè)車間的析取圖調(diào)度模型，并通過重構(gòu)遺傳操作方法對模型進行了求解。

由于單目標(biāo)靜態(tài)調(diào)度無需考慮不確定因素，且不存在優(yōu)化目標(biāo)之間相互沖突的問題，因此，其建模和求解均比較容易實現(xiàn)。

3.2　多目標(biāo)靜態(tài)調(diào)度

從字面上看，多目標(biāo)靜態(tài)調(diào)度與單目標(biāo)靜態(tài)調(diào)度的區(qū)別只在于前者至少要考慮兩個優(yōu)化目標(biāo)，然而，在多目標(biāo)靜態(tài)調(diào)度中，各優(yōu)化目標(biāo)間可能相互沖突，如既要保證最小完工時間，又要避免提前完工而增加庫存成本，因此，二者在建模和求解方面也有所不同。陳明[9]等建立了多目標(biāo)柔性作業(yè)車間調(diào)度模型，設(shè)計了一種擴展的基于工序的編碼，采用一種插入式貪婪解碼算法進行解碼，將染色體解碼后產(chǎn)生主動調(diào)度，并使用粒子群算法求解模型。黃利福[10]等提出了一種基于模糊物元模型與粒子群算法的模糊粒子群算法，用以解決高維多目標(biāo)柔性作業(yè)車間調(diào)度問題。

多目標(biāo)靜態(tài)調(diào)度模型中通常具有至少兩個目標(biāo)函數(shù)，為了同時兼顧各項優(yōu)化指標(biāo)，常用的做法是根據(jù)對各項指標(biāo)的關(guān)心程度，按不同的權(quán)值通過線性變換將多個目標(biāo)函數(shù)轉(zhuǎn)換為一個目標(biāo)函數(shù)，從而降低求解難度，并且多采用改進的算法或混合算法對模型進行求解。

3.3　單目標(biāo)動態(tài)調(diào)度

對于動態(tài)柔性作業(yè)車間調(diào)度問題，有三種調(diào)度策略：周期型調(diào)度、事件驅(qū)動型調(diào)度、周期和事件混合驅(qū)動型調(diào)度。茍海燕[11]等開發(fā)了一套事件驅(qū)動的動態(tài)作業(yè)車間實時調(diào)度系統(tǒng)，設(shè)計了三種重調(diào)度方案，根據(jù)不同的不確定因素來觸發(fā)相應(yīng)的重調(diào)度方案。宋李俊[12]等設(shè)計了一種基于滾動時域的機器故障情況下周期和事件共同驅(qū)動的動態(tài)調(diào)度策略，并采用基于雙層編碼的遺傳算法求解了模型。李保[13]等采用事件驅(qū)動的調(diào)度策略把帶有不確定因素的動態(tài)調(diào)度問題分解為多個靜態(tài)調(diào)度問題，并使用自適應(yīng)蟻群算法對子問題進行求解。潘穎[14]等提出了一種基于故障處理算法的柔性作業(yè)車間調(diào)度問題的動態(tài)仿真求解模型，采用事件驅(qū)動策略判斷重調(diào)度時機，并利用右移啟發(fā)算法實現(xiàn)重調(diào)度。

同單目標(biāo)靜態(tài)調(diào)度一樣，單目標(biāo)動態(tài)調(diào)度的優(yōu)化目標(biāo)也是表1所列優(yōu)化目標(biāo)中的一種，但由于考慮了不確定因素，其調(diào)度模型中優(yōu)化目標(biāo)的描述方法將可能發(fā)生變化，并且除了滿足三個一般性約束條件之外，還要考慮不確定因素所帶來的約束，例如，當(dāng)考慮機器故障時，其約束條件中還應(yīng)包含故障機器的維修時間與該機器上工件的加工時間之間關(guān)系的約束。在算法方面，通常先在不考慮動態(tài)因素的情況下采用傳統(tǒng)的優(yōu)化算法求解得到初始調(diào)度方案，然后，在不確定因素觸發(fā)重調(diào)度后采用改進的優(yōu)化算法或混合算法求得新的調(diào)度方案。

3.4　多目標(biāo)動態(tài)調(diào)度

多目標(biāo)動態(tài)調(diào)度是求解難度最大的一類調(diào)度問題，是多目標(biāo)靜態(tài)調(diào)度和單目標(biāo)動態(tài)調(diào)度問題的擴展，相對于前者而言，多目標(biāo)動態(tài)調(diào)度要考慮不確定因素的影響，往往要在預(yù)調(diào)度方案的基礎(chǔ)上進行方案的調(diào)整或重調(diào)度以應(yīng)對不確定因素，其調(diào)度模型中的約束條件更多、更復(fù)雜，求解過程更加繁瑣，但同時也更符合實際，因此是當(dāng)前的研究熱點。劉勝[15]等研究了機器隨機故障情況下的多目標(biāo)柔性作業(yè)車間調(diào)度問題，假設(shè)機器故障服從指數(shù)分布，提出了一種兼顧調(diào)度魯棒性與穩(wěn)定性的改進的兩階段多種群遺傳算法。鄒攀[16]等提出了一種基于分層蟻群遺傳算法的車間資源驅(qū)動的柔性作業(yè)車間調(diào)度算法，適用于不確定情境下的車間動態(tài)調(diào)度。張國輝[17]等提出了一種多階段人機協(xié)同調(diào)度策略，包括制定初始調(diào)度方案、判斷機器故障并記錄相關(guān)信息、啟用重調(diào)度方案，采用自適應(yīng)遺傳算法求解調(diào)度方案集，并結(jié)合調(diào)度人員經(jīng)驗從中選擇一種最合適的調(diào)度方案。劉曉冰[18]等針對交貨期與完工時間的不確定性，以最小化最大完工時間、加工成本和懲罰值為目標(biāo)，建立了模糊柔性作業(yè)車間調(diào)度模型，并采用混沌量子粒子群算法對模型進行了求解。

與后者相比，多目標(biāo)動態(tài)調(diào)度問題中除了考慮一般性的優(yōu)化目標(biāo)以外，更加關(guān)注不確定因素之前的預(yù)調(diào)度方案與不確定因素之后的重調(diào)度方案在某些指標(biāo)上的差值，一方面是為了保證預(yù)調(diào)度方案能具有一定的穩(wěn)定性，另一方面是為了能夠更好的地指導(dǎo)重調(diào)度。張國輝[19]等針對考慮機器故障的柔性作業(yè)車間調(diào)度方案，提出了兩種魯棒性測度指標(biāo)：初始調(diào)度與實際調(diào)度的最大完工時間偏差、每臺機器的空閑時間與工作負(fù)荷比，指出預(yù)測機器的故障和維修時間以及保證每臺機器擁有一定的空閑時間均可減小因機器故障而導(dǎo)致的工期延遲。

4　總結(jié)與展望

從單目標(biāo)靜態(tài)調(diào)度到多目標(biāo)靜態(tài)調(diào)度，再到單目標(biāo)動態(tài)調(diào)度，最后到多目標(biāo)動態(tài)調(diào)度，是一個從特殊到一般、從理想化到現(xiàn)實化的過程，多目標(biāo)動態(tài)調(diào)度考慮了生產(chǎn)過程中的不確定因素，同時兼顧了現(xiàn)實中客戶所要求達到的多項性能指標(biāo)，因而是最符合實際生產(chǎn)情況的調(diào)度類型。

但是，目前的研究主要集中于單因素的動態(tài)調(diào)度，很少同時考慮多個不確定因素的綜合影響，也沒有對車間底層數(shù)據(jù)加以很好的利用來指導(dǎo)形成一種不確定情況下的數(shù)據(jù)驅(qū)動的動態(tài)調(diào)度模式，從而無法及時有效地消除不確定因素帶來的擾動，也就不能最大程度地降低損失，因此，探索一種數(shù)據(jù)驅(qū)動下的滿足多個優(yōu)化目標(biāo)且能夠有效應(yīng)對多種不確定因素的動態(tài)作業(yè)車間調(diào)度模型是今后的一個研究方向，為此，可從以下幾方面入手：

（1）充分挖掘生產(chǎn)過程中的有用信息，為調(diào)度方案的制定和調(diào)整提供實時的、第一手的資料；

（2）結(jié)合現(xiàn)有的調(diào)度模型和相關(guān)數(shù)學(xué)知識探索建立數(shù)據(jù)驅(qū)動的動態(tài)作業(yè)車間調(diào)度模型；

（3）改進、融合現(xiàn)有的調(diào)度算法，充分利用各種算法各自的優(yōu)勢，或設(shè)計新的算法，為模型的求解提供有力的工具。