動態調度

出自 MBA智库百科(https://wiki.mbalib.com/)

　　動態調度指在決策時刻，調度環境的部分信息可知，根據逐步獲得的信息，不斷更新調度。

　　動態調度通常是指在調度環境和任務存在不可預測擾動情況下所進行的調度。與靜態調度相比，動態調度能夠針對生產現場的實際情況產生更具可操作性的決策方案。動態調度的實現方式有兩種:一是事先不存在靜態調度方案，直接按照生產系統中工件和設備的狀況以及相關信息，使用某種計算方法，確定工件的加工優先順序，即實時調度;二是在已有靜態調度方案的基礎上，根據生產系統的現場狀態，及時進行靜態調度方案的調整，確定工件的加工優先順序，此種方式常常被稱作“重調度”(又稱線上優化)。

　　以上兩種方式皆可獲得可操作的調度決策方案，但又有所不同。實時調度在決策中往往只考慮局部信息，因此得到的調度結果可能與優化的調度方案有較大的偏差，雖然可行，但與優化方案還有較大距離;重調度則是在已有靜態調度方案的基礎上，根據實際生產狀況，進行靜態方案的動態調整，保證其可操作性。由於靜態調度方案往往是通過優化方法考慮多個性能指標獲得的，因此重調度(即線上優化)能夠獲得更加優化的動態調度結果。

　　目前，關於動態調度研究方法的綜述性文獻僅對動態調度的某類研究方法進行綜述。例如:Ra-mash對動態調度模擬研究方法的綜述，Szelde等對基於知識的反應調度方法的綜述;Suresh等對單件車間動態調度的綜述。這些文獻不但沒有對動態調度的各類研究方法進行全面的綜述，而且對每種方法的適用條件也缺乏必要的分析。近年來，動態調度的理論和應用研究都取得了很大進展，因此有必要對動態調度的研究方法進行系統的分類和評價。本文將研究動態調度的方法分成兩大類，即傳統方法和智能方法。傳統方法包括最優化方法、模擬方法和啟髮式方法;智能方法包括專家系統、人工神經網路、智能搜索演算法和Multiagent方法。

　　1、傳統的研究方法

　　（1）最優化方法

　　最優化方法主要包括數學規劃(動態規劃、混合整數線性規劃等)、分支定界法和消去法等。這類方法通常基於某些簡化的假設，並能產生一個最優調度方案。現已證明，絕大多數調度問題是NP問題，隨著調度問題規模的增大，上述方法的求解難度將急劇增加，因而最優化方法往往不能適應生產實際對實時性的要求。此外，該類方法大多基於某些理想化的假設，遠不能充分反映實際生產環境的複雜性，而且要充分表達實際生產環境的隨機性和動態性也極為困難，所以單獨使用此類方法來解決動態調度問題是不現實的。目前在動態調度的研究中，通常將最優化方法同其它方法相結合，用來解決一定的問題。例如Matsuura提出的重調度演算法，首先用分支定界法產生一個調度，當工況發生變化時，再用調度規則來分配工件。

　　（2）啟髮式方法

　　啟髮式方法針對調度問題的NP特性，並不企圖在多項式時間內求得問題的最優解，而是在計算時間和調度效果之間進行折中，以較小的計算量來得到近優或滿意解。啟髮式方法通常稱為調度規則。關於調度規則的研究在很早以前便開始了，例如Johnson於1954年提出的Johnson演算法等。Panwalker等對113個調度規則做了經典的分類，將調度規則分成3大類，即優先順序規則(包括簡單的優先順序規則、簡單優先順序規則的組合和加權優先順序規則)、啟髮式調度規則及其它規則，並對各規則的適應情況做了總結。關於調度規則比較經典的綜述性文獻還有文獻。

　　由於調度規則計算量小、效率高、實時性好，因而在動態調度研究中被廣泛採用。但由於它通常僅對一個目標提供可行解，並且缺乏對整體性能的有效把握和預見能力，因而在實際應用中常將它與其它方法結合使用，利用其它方法根據具體情況選擇合適的調度規則。此外，新的啟髮式方法也不斷提出。例如Abumizar等提出一種重調度演算法，當擾動發生時，不是全部重新調度也不是等擾動解除後再繼續原調度，而是僅僅重新調度那些直接或間接受擾動影響的工件，從而減少了由於擾動引起的生產周期的增加，同時也減少了與初始調度的偏差，效率和穩定性都較好。

　　（3）模擬方法

　　模擬方法是動態調度研究中最常用的方法。該方法通過對實際生產環境的建模來模擬實際生產環境，從而避開了對調度問題進行理論分析的困難。目前，模擬方法在動態調度研究中主要有以下兩方面內容:

　　1)研究各種模擬參數對模擬結果的影響，以便在進行模擬實驗時能做出恰當選擇，從而使模擬所取得的結論更全面、更具說服力。Ramash總結了大量的相關文獻，對模擬時應考慮的參數及各參數的取值範圍做了詳細介紹。

　　2)將某些方法應用於某個模擬環境，通過模擬評價現有方法之間或新方法與現有方法之間的優劣，從而總結出各方法的適用範圍，或根據結論數據建立知識庫或產生神經網路的訓練樣本。Liu等做了大量模擬實驗，從模擬數據中產生出訓練樣本用於訓練神經網路，並將訓練後的神經網路用於動態調度。

　　由於模擬方法在模擬實際環境時做了某些假設和近似，而且模擬模型的建立較多地依賴於諸如隨機分佈等參數的選擇，因而模擬結論往往因模型的不同而不同，很難取得一個一致的結論。然而，對多數生產調度問題而言，在缺乏有效的理論分析的情況下，模擬仍不失為一種最受歡迎的方法。

　　2、智能的調度方法

　　（1）專家系統

　　專家系統在動態調度研究中占有重要地位，目前已有一些較成熟的調度專家系統，例如ISIS和OPIS等。調度專家系統通常將領域知識和現場的各種約束表示成知識庫，然後按照現場實際情況從知識庫中產生調度方案，並能對意外情況採取相應的對策。

　　有效的領域模型和知識表示對於動態調度專家系統的設計十分重要。此外，約束在調度知識庫中也占據重要地位，因為調度的好壞在很大程度上依賴於其對約束的滿足程度。動態調度的決策參數具有很強的不確定性，為了有效地表示這種不確定性，許多學者選擇了概率論，而應用模糊集理論則是一種更為有效的方法。在調度問題中應用模糊方法的優點在於，可為不精確約束的表示和應用提供豐富的表述語言和系統的框架，並且能對模糊目標進行評價。

　　ISIS是最早的基於AI的調度系統之一。該系統採用約束指導的搜索方法產生一個調度，動態情況則由重調度組件進行處理，當衝突發生時，它通過有選擇地放鬆某些約束來重新調度那些受影響的定單。基於ISIS開發的OPIS是現有的基於知識的車間調度系統中最成熟的系統之一，它根據情況使用面向資源或面向定單的動態調度策略。SONI-A是一個包含預測和反應調度組件的單件車間調度系統，反應組件用於解決由於各種原因產生的調度效果與預期效果間的偏差，系統考慮的意外事件有操作延誤、容量衝突和機器故障。OPAL也是一個為單件車間設計的調度系統，它採用調度規則和啟髮式方法進行調度。儘管OPAL中沒有反應調度組件，但是當調度延誤時，它可以根據車間的當前狀態重新產生一個調度。

　　（2）神經網路方法

　　神經網路應用於調度問題已有十多年的歷史，它在動態調度研究中的應用主要集中在以下兩方面:1)將調度問題看成一類組合優化問題，利用其並行處理能力來降低計算的複雜性;2)利用其學習和適應能力將它用於調度知識的獲取，以構造調度決策模型。目前，利用神經網路解決動態調度問題已成為動態調度研究的一個熱點。在動態調度研究中應用最多的是BP網，通過對它的訓練來構造調度決策模型。

　　Sim等提出一種專家神經網路方法，該方法用16個神經網路分別從相應的訓練樣本集中獲取調度知識，用專家系統確定各子網的輸入。由於神經網路的訓練由16個子網分擔，並且各子網可以並行訓練，從而減少了訓練時間。Cho等提出一種基於神經網路和模擬的魯棒自適應調度器，該方法根據他人研究的結論確定神經網路的結構和訓練樣本。儘管該網路結構具有較強的通用性，但由於每個人研究的背景不盡相同，因此通過量化他人結論來產生訓練樣本必然會對網路性能造成影響。Jones等提出一種解決實時排序和調度問題混合方法的框架，綜合運用了神經網路、遺傳演算法和實時模擬等方法。但只是提供了一個框架，真正實施起來還需進一步研究。Liu等提出一種用神經網路選擇調度規則的方法，神經網路的輸入對應於所有待調度工件的加工路線和加工時間信息，輸出對應於待選的調度規則。但該方法需要大量的訓練樣本和很長的訓練時間才能保證調度的效果;另外，隨著問題規模的增大，網路的規模也將急劇增大。

　　（3）智能搜索演算法

　　應用於調度問題的智能搜索方法包括模擬退火、禁忌搜索和遺傳演算法等。目前在動態調度中使用最多的是遺傳演算法。遺傳演算法解決調度問題的優勢在於它可以隨機地從一個調度跳到另一個調度，從而可以解決其它方法易於使解陷入局部最優的問題。此外，它還具有計算速度快且易與其它演算法相結合的優點，非常適合於解決動態調度問題。應用遺傳演算法解決動態調度的文獻較多，其中大多將遺傳演算法與其它方法結合使用。Lee等用遺傳演算法和機器學習來解決單件車間的調度問題，用機器學習來產生將工件下發到車間層的知識庫，而用遺傳演算法在各台機器上分配工件。Jian等提出一種FMS的調度和重調度演算法，該演算法考慮了4種動態事件，即機器損壞、定單優先順序提高、緊急定單下達和定單取消，用穩態遺傳演算法產生一個初始調度，當意外事件發生時，根據具體情況僅重新調度那些直接受影響的工序。Jones等提出一種實時排序和調度演算法，它集成了神經網路、實時模擬和遺傳演算法等方法，其中遺傳演算法主要用於對幾個備選的調度規則進行優選。

　　（4）Multi-agent方法

　　Multiagent通過在一系列分散的智能單元(Agent)間進行協調來解決問題。這些單元有各自的目標和自治的行為，並且可以有子單元。但是沒有一個單元能夠解決全局問題，因而它們之間必須進行協調。

　　關於Multiagent系統的結構，不同的人有不同的觀點。例如Kouiss等根據車間的物理佈局來確定系統的結構，為每一個加工中心配備了一個Agent，用於解決對應加工中心內的調度。另外還設計了一個全局Agent，用於監視整個製造系統的狀態，必要時為滿足全局的需要可在各Agent間進行協調。Nof等提出了自適應/預測調度系統框架，將調度系統按功能劃分成5個模塊:調度器/重調度器、監視器、比較器、分辨器和調度恢復適應器。關於每個Agent的結構，不同的人有不同的理解。但是每個Agent至少應有以下3個組成部分:1)知識庫，包含Agent執行其功能所必需的知識和數據;2)控制功能，根據環境狀態及與其它Agent間的相互作用，從知識庫中提取知識來完成調度功能;3)通訊功能，用來與其它Agent和環境之間進行信息傳遞。

　　研究表明，Multiagent特別適用於解決複雜問題，尤其是那些經典方法無法解決的單元間有大量交互作用的問題。其優點是速度快、可靠性高、可擴展性強、能處理帶有空間分佈的問題、對不確定性數據和知識有較好的容錯性;此外，由於是高度模塊化系統，因而能澄清概念和簡化設計。