基本介紹
- 中文名：動態調度
- 外文名：Dynamic scheduling
- 類型：計算機科學
- 學科：跨學科
- 性質：調度
- 方法：傳統方法、智慧型方法
介紹,研究方法,傳統的研究方法,智慧型的調度方法,發展趨勢,
介紹
傳統的對生產調度的研究是在如下假設條件下進行的： 1) 被調度的工件集合是確定的； 2) 工件的加工時間是確定的， 並且在安排計畫時全部工件都已到達； 3) 加工工件的機器是連影祝慨虹續可用的。這類調度問題是靜態調度問題。
實際生產中的大量問題是隨機發生的。如在機械製造業中， 由於工件隨機到達， 加工機器出現故障等隨機事件， 使得預調度不能正常執行， 這就需要安排重調度。同樣， 在鋼鐵企業的煉鋼-連鑄-熱軋一體化生產工藝中， 由於要求工序之間的物流銜接和節奏匹配協調一致， 且高溫連續運作， 故其生產調度系統具有以下特點： 1) 能夠線上產生實時調度； 2) 對隨機擾動實現線上辨識， 並能快速進行自動重調度。這類問題是動態環境下生產調度問題。
動態調度的概念出現較早， Jackson於1957年便對靜態調度和動態調度的概念做了區分。最初的研究主要採用啟發式方法或仿真方法， 與實際套用有較大的距離。近年來， 計算機技術的迅速發展以及人工智慧、神經網路、遺傳算法和仿真技術等新方法的產生和發展， 為動態調度的研究開闢了新思路，也為生產調度的實用化奠企挨定了基礎。目前， 動態調度已成為生產調度研究中的熱點之一。
研究方法
傳統的研究方法
1、最最佳化方法
最最佳化方法主要包括數學規劃( 動態規劃、混合整數線性規劃等) 、分支定界法和消去法等。這類方法通常基於某些簡化的假設， 並能產生一個最優調度方案。
現已證明， 絕大多數調度問題是NP 問題， 隨著調度問題規模的增大， 上述方法的求解難度將急劇增加， 因而最最佳化方法往往不能適應生產實際對實時性的要求。此外， 該類方法大多基於某些理想化的假設， 遠不能充分反映實際生產環境的複雜性， 而且要充分表達實際生產環境的隨機性和動態性也極為困難， 所以單獨使用此類方法來解決動態調度問題是不現實的。目前在動態調度的研究中， 通常將最最佳化方法同其它方法相結合， 用來解決一定的問題。
2、啟發式方法
啟發式方法針對調度問題的NP 特性， 並不企圖在多項式時間內求得問題的最優解， 而是在計算時間和調度效果之間進行折中， 以較小的計算量來得到近優或滿意解。啟發式方法通常稱為調度規則。
由於調度規則計算量小、效率高、實時性好， 因而在動態調度研究中被廣泛採用。但由於它通常僅對一個目標提供可行解， 並且缺乏對整體性能的有效把握和預見能力， 因而在實際套用中常將它與其它方法結合使用， 利用其它方法根據具體情況選擇合適的調度規則。此外， 新的啟發式方法也不斷提出。
3、仿真方法
仿真方法是動態調度研究中最常用的方法。該擔主屑方法通過對實際生產環境的建模來模擬實際生產環境， 從而避開了對調度問題進行理論分析的困難。目前， 仿真方法在動態調度研究中主要有以下兩方面內容：
1) 研究各種仿真參數對仿真照戶良結果的影響， 以便在進行仿真實驗時能做出恰當選擇， 從而使仿真所取得的結論更全面、更具說服力。Ramash總結了大量的相關文獻， 對仿真時應考慮的參數及各參數的取值範圍做了詳細介紹。
2) 將某些方法套用於某個仿真環境， 通過仿真評價現刪習才有方法之間或新方法與現有方法之間的優劣， 從而總結出各方法的適用範圍， 或根據結論數據建立知識庫或產生神經網路的訓練樣本。Liu 等做了大量仿真實驗， 從仿真數據中產生出訓練樣本用於訓練神經網路， 並將訓練後的神經網路用於動態調度。
智慧型的調度方法
1、專家系統
專家系統在動態調度研究中占有重要地位， 目前已有一些較成熟的調度專家系統， 例如ISIS 和OPIS 等。調度專家系統通常將領域知識和現場的各種約束表示成知識庫， 然後按照現場實際情況從知識庫中產生調度方案， 並能對意外情況採取相應的對策。
有效的領域模型和知識表示對於動態調度專家系統的設計十分重要。此外， 約束在調度知識庫中也占據重要地位， 因為調度的好壞在很大程度上依賴於其對約束的滿足程度。動態調度的決策參數具有很強的不確定性， 為了有效地表示這種不確定性， 許多學者選擇了機率論， 而套用模糊集理論則是一種更為有效的方法。在調度問題中套用模糊方法的優點在於， 可為不精確約束的表示和套用提供豐富的表述語言和系統的框架影漏臘， 並且能對模糊目標進行評價。
2、神經網路方法
神經網路套用於調度問題已有十多年的歷史，它在動態調度研究中的套用主要集中在以下兩方面： 1) 將調度問題看成一類組合最佳化問題， 利用其並行處理能力來降低計算的複雜性；2) 利用其學習和適應能力將它用於調度知識的獲取， 以構造調度決策模型。目前， 利用神經網路解決動態調度問題已成為動態調度研究的一個熱點。在動態調度研究中套用最多的是BP 網， 通過對它的訓練來構造調度決策模型。
3、智慧型搜尋算法
套用於調度問題的智慧型搜尋方法包括模擬退火、禁忌搜尋和遺傳算法等。目前在動態調度中使用最多的是遺傳算法。遺傳算法解決調度問題的優勢在於它可以隨機地從一個調度跳到另一個調度， 從而可以解決其它方法易於使解陷入局部最優的問題。此外， 它還具有計算速度快且易與其它算法相結合的優點， 非常適合於解決動態調度問題。
4 Multi-agent 方法
Multi- agent 通過在一系列分散的智慧型單元(Agent) 間進行協調來解決問題。這些單元有各自的目標和自治的行為， 並且可以有子單元。但是沒有一個單元能夠解決全局問題， 因而它們之間必須進行協調。
關於Multi-agent 系統的結構， 不同的人有不同的觀點。例如Kouiss 等根據車間的物理布局來確定系統的結構， 為每一個加工中心配備了一個Agent， 用於解決對應加工中心內的調度。另外還設計了一個全局Agent， 用於監視整個製造系統的狀態， 必要時為滿足全局的需要可在各Agent 間進行協調。Nof 等提出了自適應/ 預測調度系統框架，將調度系統按功能劃分成5 個模組: 調度器/ 重調度器、監視器、比較器、分辨器和調度恢復適應器。
發展趨勢
傳統方法中套用最多的是調度規則( 啟發式算法) 和仿真方法。仿真方法幾乎在每種方法中都有套用。由於調度規則具有計算量小、效率高和實時性好等優點， 非常適用於動態調度。但它也有明顯的缺點， 因而通常需要與智慧型方法結合使用， 通過智慧型方法根據情況在備選規則間進行選擇。典型的研究方法通常同時使用某種智慧型方法、仿真方法和調度規則。
智慧型調度方法如專家系統、神經網路和遺傳算法等， 既有許多優點， 也有各自的缺點。例如: 神經網路的訓練時間較長， 對結果缺乏解釋能力， 並且網路結構及算法參數不易確定; 專家系統知識獲取的難度大且擴展性較差， 當問題偏離知識領域時系統的性能將急劇下降; 遺傳算法的適應函式較難選取， 處理實際問題時有時不能滿足實時性和調度效果的要求。因此上述方法經常結合在一起使用， 如專家系統與神經網路相結合， 遺傳算法與神經網路相結合 ， 遺傳算法與專家系統相結合等。由於Multi-agent 方法具有速度快、可靠性高、可擴展性強等優點， 將成為研究的熱點之一。
動態調度不僅是鋼鐵集成調度的關鍵技術， 也是機械、化工等流程型行業中的必備技術。在科技日益發達的信息技術時代， 動態調度問題必將大量套用於信息流處理。在充分了解現有研究方法優缺點的基礎上， 開發新的更有效的動態調度問題的解決方法十分必要。目前絕大多數調度系統還處於研究原形階段， 工業原形系統也大多由大學或研究機構承擔， 真正套用於實際生產的調度系統並不多。因而今後應以研究能在實際中套用的調度系統為重點。
1) 研究各種仿真參數對仿真結果的影響， 以便在進行仿真實驗時能做出恰當選擇， 從而使仿真所取得的結論更全面、更具說服力。Ramash總結了大量的相關文獻， 對仿真時應考慮的參數及各參數的取值範圍做了詳細介紹。
2) 將某些方法套用於某個仿真環境， 通過仿真評價現有方法之間或新方法與現有方法之間的優劣， 從而總結出各方法的適用範圍， 或根據結論數據建立知識庫或產生神經網路的訓練樣本。Liu 等做了大量仿真實驗， 從仿真數據中產生出訓練樣本用於訓練神經網路， 並將訓練後的神經網路用於動態調度。
智慧型的調度方法
1、專家系統
專家系統在動態調度研究中占有重要地位， 目前已有一些較成熟的調度專家系統， 例如ISIS 和OPIS 等。調度專家系統通常將領域知識和現場的各種約束表示成知識庫， 然後按照現場實際情況從知識庫中產生調度方案， 並能對意外情況採取相應的對策。
有效的領域模型和知識表示對於動態調度專家系統的設計十分重要。此外， 約束在調度知識庫中也占據重要地位， 因為調度的好壞在很大程度上依賴於其對約束的滿足程度。動態調度的決策參數具有很強的不確定性， 為了有效地表示這種不確定性， 許多學者選擇了機率論， 而套用模糊集理論則是一種更為有效的方法。在調度問題中套用模糊方法的優點在於， 可為不精確約束的表示和套用提供豐富的表述語言和系統的框架， 並且能對模糊目標進行評價。
2、神經網路方法
神經網路套用於調度問題已有十多年的歷史，它在動態調度研究中的套用主要集中在以下兩方面： 1) 將調度問題看成一類組合最佳化問題， 利用其並行處理能力來降低計算的複雜性；2) 利用其學習和適應能力將它用於調度知識的獲取， 以構造調度決策模型。目前， 利用神經網路解決動態調度問題已成為動態調度研究的一個熱點。在動態調度研究中套用最多的是BP 網， 通過對它的訓練來構造調度決策模型。
3、智慧型搜尋算法
套用於調度問題的智慧型搜尋方法包括模擬退火、禁忌搜尋和遺傳算法等。目前在動態調度中使用最多的是遺傳算法。遺傳算法解決調度問題的優勢在於它可以隨機地從一個調度跳到另一個調度， 從而可以解決其它方法易於使解陷入局部最優的問題。此外， 它還具有計算速度快且易與其它算法相結合的優點， 非常適合於解決動態調度問題。
4 Multi-agent 方法
Multi- agent 通過在一系列分散的智慧型單元(Agent) 間進行協調來解決問題。這些單元有各自的目標和自治的行為， 並且可以有子單元。但是沒有一個單元能夠解決全局問題， 因而它們之間必須進行協調。
關於Multi-agent 系統的結構， 不同的人有不同的觀點。例如Kouiss 等根據車間的物理布局來確定系統的結構， 為每一個加工中心配備了一個Agent， 用於解決對應加工中心內的調度。另外還設計了一個全局Agent， 用於監視整個製造系統的狀態， 必要時為滿足全局的需要可在各Agent 間進行協調。Nof 等提出了自適應/ 預測調度系統框架，將調度系統按功能劃分成5 個模組: 調度器/ 重調度器、監視器、比較器、分辨器和調度恢復適應器。
發展趨勢
傳統方法中套用最多的是調度規則( 啟發式算法) 和仿真方法。仿真方法幾乎在每種方法中都有套用。由於調度規則具有計算量小、效率高和實時性好等優點， 非常適用於動態調度。但它也有明顯的缺點， 因而通常需要與智慧型方法結合使用， 通過智慧型方法根據情況在備選規則間進行選擇。典型的研究方法通常同時使用某種智慧型方法、仿真方法和調度規則。
智慧型調度方法如專家系統、神經網路和遺傳算法等， 既有許多優點， 也有各自的缺點。例如: 神經網路的訓練時間較長， 對結果缺乏解釋能力， 並且網路結構及算法參數不易確定; 專家系統知識獲取的難度大且擴展性較差， 當問題偏離知識領域時系統的性能將急劇下降; 遺傳算法的適應函式較難選取， 處理實際問題時有時不能滿足實時性和調度效果的要求。因此上述方法經常結合在一起使用， 如專家系統與神經網路相結合， 遺傳算法與神經網路相結合 ， 遺傳算法與專家系統相結合等。由於Multi-agent 方法具有速度快、可靠性高、可擴展性強等優點， 將成為研究的熱點之一。
動態調度不僅是鋼鐵集成調度的關鍵技術， 也是機械、化工等流程型行業中的必備技術。在科技日益發達的信息技術時代， 動態調度問題必將大量套用於信息流處理。在充分了解現有研究方法優缺點的基礎上， 開發新的更有效的動態調度問題的解決方法十分必要。目前絕大多數調度系統還處於研究原形階段， 工業原形系統也大多由大學或研究機構承擔， 真正套用於實際生產的調度系統並不多。因而今後應以研究能在實際中套用的調度系統為重點。
