多目標柔性Ｊｏｂ Ｓｈｏｐ調度問題的技術現狀和發展趨勢
2007-01-01 00:00:00吳秀麗孫樹棟楊展翟穎妮
計算機應用研究 2007年3期
摘 要：首先概述了多目標柔性Job Shop調度問題的基本概念，包括問題定義、常用假設條件、性能指標和問題的分類，討論了其復雜性；其次，分別從建模、優化方法和原型系統研究方面綜述了其發展過程和研究現狀，對一類更加通用的多目標柔性Job Shop問題進行了簡單的文獻綜述；最后指出了現有研究存在的問題與不足，并對未來的發展趨勢進行了探討。
關鍵詞： 多目標； 柔性工作車間調度； 建模； 優化方法； 原型系統
中圖分類號：TP273.5 文獻標志碼：A
文章編號：1001－3695(2007)03－0001－05
自從1954年Johnson對兩臺機床的Flow Shop型調度問題進行研究后，學術界和實務界對生產調度問題展開了廣泛的探討，并取得了豐碩的成果。但是這些調度理論對現實情況設定了很多假設，很難用于生產實踐中[1]。因此，探討更少假設、能真正體現實際生產的調度理論和方法具有非常重要的現實意義。
柔性Job Shop調度問題[2]（Flexible Job Shop Scheduling Problem， FJSP）就是在這種形勢下產生的。它是對經典Job Shop問題的擴展，不但繼承了Job Shop問題的所有特征，而且增加了新的求解難度：允許某道工序在多臺機器上加工，一臺機器可以加工多種類型的工序。調度的首要工作是將工序分配到機器上，即機器分配問題；其次才是真正的調度問題。多目標下的FJSP擴大了最優調度的搜索空間，而且需要滿足更多約束條件，導致問題更加復雜。這類調度問題的復雜性、約束多樣性、動態性決定了對該問題的研究能夠反映實際生產過程，具有一定的實際意義[3]。本文綜述了多目標FJSP的一系列研究成果。
1 多目標FJSP
（1）調度問題描述。
多目標FJSP是經典Job Shop調度的擴展，可在經典Job Shop的基礎上定義：
在M個機器上加工N個工件，每個工件Jj由nj個工序組成，nj個工序之間有工藝的先后約束，工件的每道工序可由M臺機器中的多臺機器加工。Mij表示第j個工件的第i道工序可用機器集合Mij{1，2，…，M}；Oijk表示第j個工件的第i道工序可用機器k；pijk表示第j個工件的第i道工序在第k個機器上加工需要的時間，即1≤j≤N，1≤i≤nj，1≤k≤M。調度的任務是在M臺機器上安排N個工件的加工任務，同時最優化一系列給定的性能指標，并滿足一些約束條件。
（2）常用假設。
為了簡化問題，經常作出以下假設：
①所有機器在t=0時刻都可用。
②所有工件在t=0時刻都可被加工。
③所有工件的工藝計劃是固定不變的，即工序的先后順序不能違背。
④工序在可供選擇的機器上的加工時間已確定。
⑤每個工件在固定時刻只能在一臺機器上加工。
⑥加工是非搶占式的，即給定時刻機器k只能加工一個工件，只有該工件的此工序加工完畢后才能加工別的工件，即工件的加工不允許中斷。
（3）常用性能指標。
多目標的FJSP研究文獻中，常用的調度指標如下：
①Makespan是調度的最小生產周期，即所有工件的最大完成時間的最小值。這個指標用得最多，可參見文獻[4~8]等。
②流經時間是指工件最后一道工序完成時間與開始釋放時間之間的差值，可分為工件的流經時間、整個調度任務的最大流經時間、平均流經時間和加權流經時間等。這類指標也比較常用，可參見文獻[4，9]等。
③提前時間/延遲時間是指工件的完成時間與交貨期時間的差值。差值為正時是延遲時間；差值為負時是提前時間。在JIT制企業中，這兩個指標是最重要的。其變化形式有最大提前時間/最大延遲時間、平均提前時間/平均延遲時間，可參見文獻[8，10～14]等。
④機器總負荷/瓶頸機器的最大負荷。機器總負荷是指一個調度方案產生的所有機器負荷的總和；瓶頸機器的最大負荷是指負荷最大的機器的負荷值。在帶有機器柔性的FJSP中，這兩個指標最常見，因為它們對于合理分配資源和提高生產效率有著重要的意義，可參見文獻[7，15]等。
⑤成品存儲成本是指工件提前完成又不能提前交貨時，制造商需要一定的費用保管成品，可參見文獻[17]等。
⑥拖工懲罰成本是指工件晚于交貨期完成時，制造商需要提供給客戶額外的罰金和與拖期時間相關的罰金，可參見文獻[17]等。
（4）問題分類。
由FJSP的描述可以看出，該類問題可分為兩類[18]：
①完全FJSP，對于Oij，Mij=M，表示第j個工件的第i道工序可以在所有機器上加工；
②部分FJSP，對于Oij，MijM，表示第j個工件的第i道工序只能在M個機器中的部分機器上加工，即至少有一臺機器不能加工i工序。
（5）復雜性分析。
如前所述，FJSP包含兩個子問題，即機器分配問題和工序調度問題。相對經典Job Shop問題，求解難度增加；當FJSP具有幾個目標函數時，求解難度進一步增加。因為在多目標優化中，最優的定義已發生變化，真正試圖找到的是一種妥協（即有效解），而不是簡單的一個全局最優解。一個有效解（Pareto最優解）是指不可能在不損壞其他目標性能的前提下提高任何一個目標的性能[19]。對于多目標互相沖突的優化問題，最優解不止一個。帶有兩個或單個目標的問題可以從指標圖的含義中清楚地表明選擇，但在高維問題中，顯示結果成為超平面，進行選擇就非常復雜了，復雜程度隨著目標數量的增加而大致呈指數上升趨勢，計算費用也隨著目標數量的增加而顯著上升。唐國春[20]已經證明，如果問題1‖γ1是NPhard的，那么多目標調度問題1‖(γ1，γ2）和線性權函數的多目標調度問題1‖αγ1+βγ2也是NPhard的。Janson[9]證明了對于單目標的FJSP存在近似的多項式求解方法，用m1m|chain，op≤u|Cmax表示FJSP，已經證明212|chain，n=3|Cmax， 312|chain，n=2|Cmax， 212|chain，op≤2|Cmax等問題是NPhard。姜思杰[21]用分步法求解單目標的FJSP的兩個子問題，并討論了問題的復雜性，得出的結論是問題的復雜度不僅與ｍ2ｎ、ｍｎ和ｍ有關，還與總操作數有關。專門針對多目標FJSP的復雜性分析尚未見諸文獻。
2 發展過程與研究現狀
2.1 發展歷史
首先研究FJSP的是Bruker和Schlie[2]，他們開發出了一個多項式方法求解兩個工件的FJSP；當時他們假設能加工同一個工序的機器的加工時間是相同的。在此以后，學者們逐漸展開了對FJSP的研究。文獻中也有將FJSP稱為帶有機器柔性的JSP[22]或者具有柔性加工路徑的JSP[23]。
2.2 建模方法研究現狀
2.2.1 數學模型
一些學者從整數規劃的角度建立了多目標FJSP的數學模型。龐哈利[24]從集成化的角度研究了柔性Job Shop計劃和調度問題，建立了兩層混合整數規劃模型，并用遺傳算法求解最佳加工路徑，用啟發式規則求解調度問題。
2.2.2 析取圖模型
JSSP的析取圖模型G=(N，A，E)由Balas[25]提出，N包含代表所有工序的節點；A包含連接同一工件的鄰接工序的邊；E包含連接同一機器上加工工序的非連接邊，非連接邊可以有兩個可能的方向。調度過程將固定所有非連接邊的方向，以確定同一機器上工序的順序，并采用帶有優先箭頭的連接邊取代非連接邊。DauzèrePérès[22]用非連接圖建模了調度問題，并建立了鄰域結構，進而采用基于鄰域結構的禁忌搜索進行求解。
2.3 優化方法研究現狀
2.3.1 數學規劃方法
數學規劃將生產調度問題簡化為數學規劃模型，采用整數規劃、動態規劃以及決策分析等方法來解決調度最優化或近似優化問題，也稱為優化調度方法。該方法一般能產生一個精確最優解。Hoitomt[11]利用拉氏松弛法求解并行機調度問題，目標是加權延遲。Torabi等人[26]建模了FJSP的批量調度模型，這是一個混合01規劃模型，并用枚舉的方法進行求解。Angel等人[5]研究了用拉氏松弛法近似求解單機環境下雙目標FJSP；這種方法對于小規模問題尚可求解，一旦問題規模增加則很難求解，即使能求解也需要花費大量的計算時間。
2.3.2 啟發式方法
由復雜性分析可知，三個以上工件的FJSP就變成NP hard了。為了能在相對短的時間內獲得近似最優解，所以很自然地想到用啟發式算法求解。
（1）分派規則法。
采用該方法求解多目標FJSP的研究較少，主要有：Ho和Tay[27]利用組合分派規則解決FJSP，詳細地設計了算法，并驗證了算法的性能；AlvarezValdes等人[28] 提出了一個啟發式規則，建模玻璃生產企業的生產調度為FJSP；Dimitr等人[17]從成本的角度優化調度，僅僅考慮了延遲成本和存儲成本，對生產成本沒有考慮，提出了一個啟發式規則，采用中心極限定理解決了調度中的競爭問題。
（2）人工智能法。
人工智能是指模擬人類智能活動進行優化的方法，目前僅見到神經網絡求解FJSP的少量研究。潘全科[16]采用了小腦模型對多目標調度系統進行了研究。通過小腦模型神經網絡對已有的多目標綜合評價調度案例的學習，替代評價群體進行評價，進而可以減少評價的工作量，更能較好地利用和積累專家的經驗，使評價過程具有自學習能力。
（3）鄰域搜索法。該
搜索法包括遺傳算法、禁忌搜索、模擬退火、貪婪算法等。按照求解多目標FJSP時的步驟可以將求解方法分為兩類：
①分步法，它是將FJSP中的機器分配問題和工序調度問題分別求解，這類方法用得比較多。
Brandimarte[29]是第一個采用分步法求解多目標FJSP的，他首先用現存的分派規則求解路線選擇問題，然后利用禁忌搜索求解調度問題。Cintia Rigao[12]也采用禁忌搜索分步求解FJSP，其優化目標是延遲目標和設備總負荷。Kacem等人[18，30]用GA解決FJSP，并且采用兩個方法分別解決機器分配問題和工序調度問題：①局部搜索法，建立理想的資源分配模式；②分配模型控制的遺傳算法，用它求解單目標和多目標的FJSP。多目標問題[7]是Makespan、總負荷和最大負荷均最小化的FJSP，求解出的是一個Pareto解集。他們還提出用模糊集概念[31]處理目標的不可公度性，根據Pareto解的多樣性，Kacem[32]提出最壞邊界分析來估算調度方案的性能。Zribi等人[33]采用的分階段的方法也是分步法，分別建立了數學模型：首先采用定位法和禁忌搜索確定最佳分配方案；再采用GA求解工序調度問題。Tamaki等人[34]利用混合整型規劃建模FJSP，問題特征包括機器的安裝準備/卸工件時間，并采用遺傳算法進行了優化。Cochran等人[35]提出兩階段多目標求解方法：第一階段按照加權合并的思想將多目標轉換為單目標，運行到一定時間切換到第二階段；第二階段采用多種群思想，按照目標的個數將種群劃分為N＋1個子種群分別進化，每一代保留各自的最優解直接遺傳到下一代，直到停止標準滿足。這其實是多種群GA的變形。Mesghouni等人[36]研究了遺傳算法求解多目標FJSP。Zhang[37]針對標準遺傳算法求解FJSP的低效率問題，提出了一種多階段的GA算法，并用來優化Makespan、最大負荷和平均負荷三個指標；結果表明在這三個指標的優化性能上，提出的方法比啟發式規則、標準GA和Kacem、Hammadi等人的方法都要優越。
在遺傳算法的設計上一些學者提出了新的見解。Ho和Tay等人[27]認為求解FJSP的GA染色體需要特殊設計，并給出兩個標準評估染色體性能：計算的時間和空間復雜性；保持解的可行性需要，提出了一種解決機器可以反復使用的FJSP的有效方法。余琦瑋[38]基于遺傳算法的柔性作業車間調度優化，針對模型的特殊性提出了染色體兩層編碼結構，將AOV、AOE網絡圖分別應用到解碼和適應度函數的計算中。楊曉梅[3]也類似地設計了兩層染色體，交叉變異操作分別在各層染色體內進行。盧冰原等人[39，40]對模糊環境下的FJSP進行了研究，模糊加工時間用三角模糊數表示，優化目標是Makespan，采用遺傳算法進行求解；實行雙染色體機制，一個染色體表示工序的機器分配，另外一個染色體表示機器上的工序加工順序。類似地，陳皓等人[41]用遺傳算法求解柔性作業車間調度問題，他設計的基因編碼主串表示調度路徑，副串表示調度次序。在主串中引入交叉算子，主/副串以不同概率發生變異算子，并隨機交換其中兩位。Chen[42]用遺傳算法求解FJSP，并用圖論模擬染色體，染色體同樣分為兩部分。趙巍等人[43]通過輪換的方法提出了一種改進算法，將加工任務分配到不同的并行機器上去執行，有利于機器的負載平衡。潘全科等人[44]結合實際生產過程，考慮到工件的加工受到機床、工人和機器人等資源的制約，并且可以有多種可行的工藝路線。
夏蔚軍等人[15，45]研究了基于微粒群優化和模擬退火集成的方法解決多目標FJSP。多目標的處理方法是采用加權和的方法將多目標問題轉換為單目標問題。求解思路是分別求兩個子問題，即微粒群優化求解機器分配問題和模擬退火求解排序問題。
②集成法，它是同時解決FSJP的兩個子問題。
孫志峻等人[23]用遺傳算法研究了具有柔性加工路徑的作業車間的智能優化調度問題，提出一種將遺傳算法和分派規則相結合的調度算法，將加工計劃與生產調度同時考慮，避免了加工計劃和生產調度相脫節的弊端；他們[46]還針對FJSP的批量加工問題進行了探討。趙偉等人[47]研究了Job Shop類型柔性制造系統的調度問題，其中每個工件都有多個可替代的工藝計劃，并且每個操作均可在多個機器上選擇加工，建立了多目標混合整數規劃模型，利用遺傳算法進行求解。
DauzèrePérès等人[48]定義了鄰域結構方法，不區分分配問題和調度問題，并且基于該鄰域結構提出了禁忌搜索過程求解FJSP。Baykasoglu[49]是第一個采用語法的方法建模FJSP的人，他用資源元來定義機器能力，優化的目標是單目標；考慮到定義資源元的難度和多目標優化的需求，還提出了基于語法的多目標FJSP的調度模型[50]，并詳細討論了模型的求解方法，采用多目標禁忌搜索方法。
Mati等人[51]提出了用貪婪式啟發式規則同時解決FJSP的分配和工序調度兩個子問題。
利用蟻群算法求解FJSP的研究以Vincent T’kindt等人[52，53]為主，他們提出一種交互式求解雙目標調度問題的方法：由優化方法求出一組Pareto解，然后決策者根據自己的偏好信息選擇出最滿意的Pareto解。關于此方面的所有優秀研究成果可參見文獻[54]。
Loukil等人[55]利用模擬退火求解多目標生產調度問題。Maqrini等人[56]提出了化工行業的FJSP的描述，并用模擬退火算法求解。
2.4 調度原型系統研究現狀
對調度原型系統的研究較少，文獻中僅見到Khoo[57]的研究，他提出了一個原型系統——擴展遺傳算法的制造系統多目標調度器。原型系統總體框架的輸入是數據庫文件，輸出是一個可行的近似或最優調度方案，中央處理部分為一個調度工具箱。工具箱集成了各種類型的調度問題，如Job Shop、Flow Shop和制造單元等，但是沒有考慮FJSP。
2.5 面向工件的多目標FJSP研究現狀
上述討論的多目標FJSP中，均默認了各個工件的性能指標集是相同的，稱做I類多目標FJSP。但是實際情況中，因為現代企業的生產能力大大提高，車間調度員一次需要安排并投產一大批各種類型的訂單，常常會碰到工件性能指標集不同的情況，此時必須兼顧各個工件本身的性能指標要求。該類問題稱為面向工件的多目標FJSP調度問題或II類多目標FJSP，定義如下：
在M個機器上加工N個工件，每個工件Jj由nj個工序組成，nj個工序之間有工藝的先后約束，工件的每道工序可由M臺機器中的多臺機器加工。用Mij表示第j個工件的第i道工序可用機器集合Mij{1，2，…，M}；Oijk表示第j個工件的第i道工序可用機器k；pijk表示第j個工件的第i道工序在第k個機器上加工需要的時間，即1≤j≤N，1≤i≤nj，1≤k≤M。每個工件Jj的性能指標集為Aj，如果對任意的1≤i≤N，1≤j≤N，都有Ai＝Aj時，所有工件的性能指標集相同，則該問題轉換為通常的多目標FJSP?？梢姳疚挠懻摰膯栴}是更加通用意義上的多目標FJSP，常說的多目標調度問題只是其中的一個子集。調度的任務是在M臺機器上安排N個工件的加工任務，同時最優化各個工件預定的性能指標集，并滿足一些必要的約束條件。由定義可以看出，II類問題比I類問題更加接近實際，進一步縮小了理論與實踐之間的“代溝”。
遺憾的是這方面的研究非常少，主要是日本大阪大學的學者Murata教授[58～60]所做的一系列工作。他的核心思想是將該類確定的FJSP轉換為模糊交貨期調度問題；他還進一步提出了不同工件重要性的影響[61]，進而提出基于規則的權重定義方法，得出的結論是遺傳算法比模擬退火算法更能有效地求解該類多目標調度問題，研究著重在多工件單目標情況上。Li[62]發展了Murata的理論，他研究了FJSP領域的多工件多目標的情況，建模了這類多目標模糊FJSP，采用滿意度作為多個目標的折中，進而作為優化目標。
3 存在的問題與不足
（1）調度的優化準則中，基于性能的指標研究較多，基于代價指標的研究很少，少量文獻僅涉及到懲罰成本與成品存儲成本問題，很少提及到生產成本和在制品存儲成本的問題。然而這類指標對企業的管理決策又是至關重要的。
（2）FJSP模型的研究很少，文獻中僅見到數學規劃模型和基于語法的模型。關于多目標FJSP框架性的研究幾乎沒有。
（3）對于多目標優化方法的理論分析沒有系統研究，如何保證優化方法的收斂性和Pareto解的多樣性是多目標優化方法亟待解決的問題。
（4）柔性作業車間多目標調度問題的討論僅僅局限在所有工件的目標均相同情況下的多目標調度問題中，關于各種工件目標不同的多目標調度問題的研究很不成熟，而進一步考慮在工件生產批量也不等的情況下的研究更是無人提及。
（5）動態調度問題雖然研究得很多，但都是僅限于單一目標的優化，優化目標隨時間而變的動態多目標調度問題的研究尚未見到。
（6）多目標FJSP原型系統的研究太少，有很多問題值得進一步探討，而且與企業其他控制系統和信息系統存在“信息鴻溝”。
4 發展趨勢
相對經典Job Shop的豐富研究，FJSP的研究還處于初級階段，多目標下的FJSP研究更是如此，有許多值得探索的地方。
（1）建立包括生產成本在內的多目標FJSP模型，充分考慮企業對成本的關注，使得調度模型更好地反映現實情況。指標體系應包括基于性能和基于代價的兩類指標。
（2）經典Job Shop的研究已經取得了豐富的成果，將這些優秀的理論成果應用到FJSP是一個重要的發展方向。尤其是研究數學邏輯嚴密的模型表示方法、規范和描述生產調度框架是當務之急。
（3）工件目標差異的多目標FJSP也是一個重要內容。
（4）多目標問題的一個最大問題是針對同一個問題，采用不同方法得到的解往往不同[63]。如何評價衡量得到的解的質量是一個迫在眉睫的研究方向。
（5）過去的研究大多數是基于禁忌搜索和遺傳算法的。探求其他智能方法如神經網絡方法、Agent技術等，求解多目標FJSP是一個重要的研究方向。多種方法的混合使用能大大避免單純使用一種方法的不足與缺陷，是一個值得關注的方向。盡管文獻中采用GA的方法占多數，但是截至目前為止，采用GA求解高維、多約束、多目標的優化問題仍是一個沒有較好解決的問題，其進展必將推動GA在許多工程領域的應用。
（6）開發實用的多目標FJSP原型系統，尤其是探討ERP環境下生產調度系統與企業其他信息系統之間的信息交流問題，從而真正實現將調度理論應用到生產實踐中。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
