何　斌，張接信，張富強(qiáng)

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

0　引言

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

1　問題描述

車間調(diào)度是指按照被加工件的工藝規(guī)程，在現(xiàn)有生產(chǎn)能力和生產(chǎn)資源情況下，基于一個(gè)或多個(gè)優(yōu)化目標(biāo)以及相關(guān)約束條件，規(guī)劃出多個(gè)工件各工序間最優(yōu)的加工順序組合方案。作業(yè)車間調(diào)度問題（Job Shop Scheduling Problem，JSP）是車間調(diào)度問題的經(jīng)典類型，也是典型的組合優(yōu)化問題，其一般性描述為：n個(gè)工件在m臺(tái)機(jī)器上加工，各工序的加工機(jī)床和加工時(shí)間已定，所要解決的問題是確定每臺(tái)機(jī)床上待加工件的最優(yōu)加工順序。而柔性作業(yè)車間調(diào)度問題是JSP問題的擴(kuò)展，此類問題中，工件每道工序的加工有一至多臺(tái)機(jī)床可供選擇，所要解決的問題一是為每道工序選擇最合適的機(jī)床，二是為每臺(tái)機(jī)床上的工件安排最優(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)度問題都必須滿足的共同的約束條件，具體工況下的約束條件會(huì)有所增強(qiáng)。

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

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

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

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

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)確地表達(dá)出來即得到其數(shù)學(xué)模型，例如，當(dāng)加工時(shí)間是隨機(jī)變量時(shí)，為了方便計(jì)算，以最小化最大完工時(shí)間的期望值作為優(yōu)化目標(biāo)，并且常用模糊隸屬度函數(shù)來描述某些不確定性因素，并用數(shù)形結(jié)合的思想來表達(dá)某些目標(biāo)函數(shù)。楊建斌[6]等用三角模糊數(shù)和半梯形模糊數(shù)分別表示模糊加工時(shí)間和模糊交貨期，建立了以最大化最小客戶滿意度為優(yōu)化目標(biāo)的作業(yè)車間模糊調(diào)度模型，并采用自適應(yīng)遺傳算法求解了模型。黃亞平[7]等用三角模糊數(shù)表示模糊加工時(shí)間，用梯形模糊數(shù)表示模糊交貨期，以交貨期平均滿意度最大為優(yōu)化目標(biāo)，建立了作業(yè)車間的模糊調(diào)度模型，并采用自適應(yīng)蟻群算法對(duì)模型進(jìn)行了求解。

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

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

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

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

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

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

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

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

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

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

與后者相比，多目標(biāo)動(dòng)態(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]等針對(duì)考慮機(jī)器故障的柔性作業(yè)車間調(diào)度方案，提出了兩種魯棒性測(cè)度指標(biāo)：初始調(diào)度與實(shí)際調(diào)度的最大完工時(shí)間偏差、每臺(tái)機(jī)器的空閑時(shí)間與工作負(fù)荷比，指出預(yù)測(cè)機(jī)器的故障和維修時(shí)間以及保證每臺(tái)機(jī)器擁有一定的空閑時(shí)間均可減小因機(jī)器故障而導(dǎo)致的工期延遲。

4　總結(jié)與展望

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

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

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

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

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