約束傳播是約束規劃成功套用的關鍵技術之一。針對累積調度問題可提出一種結合工作間優先關係和工作最早開始/最晚完成時間約束的約束傳播算法，保證算法的理論依據。
基本介紹
- 中文名：約束傳播
- 套用領域：約束規劃
- 研究對象：工作間優先關係
簡介,研究進展,約束傳播實驗設計,
簡介
約束規劃(Constraint programming， CP) 是人工智慧領域的研究方法， 適合求解具有多種約束的組合最佳化問題.約束傳播是CP 的關鍵技術之一， 其基本思想是通過循環分析變數、值域和約束， 檢驗並刪除不可能出現在可行解中的變數賦值， 從而約減變數值域.CP 在調度問題研究領域已經獲得了很多成功套用.1989 年Carlier 等在分枝定界算法中使用約束傳播技術，首次成功解決了1963 年Muth 等提出後讓眾多學者孜孜不倦努力求解20 多年的車間調度問題。從此， 約束傳播技術引起了調度問題研究領域學者的廣泛關注， 針對調度問題的約束傳播算法的時間複雜性也不斷獲得改進。
研究進展
調度問題研究領域的約束傳播方法可以分為時間約束傳播和資源約束傳播兩類。時間約束傳播根據工作間優先關係約束計算各工作的[最早開始時間， 最晚完成時間] 區間，約束傳播算法可以基於時間約束網路採用最短路徑算法實現。資源約束傳播通過分析競爭同一資源的工作對資源需求量和資源供應量的關係， 對工作[最早開始時間， 最晚完成時間] 區間進行約減。資源約束傳播方法根據資源特性進一步分為兩類: 一類是分離調度問題，DSP 中資源可用量和工作在執行期間對資源的需求量均為約束傳播， 較好的DSP 約束傳播方法有Edge-nding， Input-or-output， Not-rst/not-last。另一類是累積調度問題(Cumulative schedulingproblem， CuSP) (CuSP 中資源可用量和工作在執行期間對資源的需求量均大於等於約束傳播， 較好的CuSP 約束傳播方法有Edge-nding， Energetic-reasoning。
兩類資源約束傳播技術相比， DSP 約束傳播技術比CuSP 約束傳播技術受到更早的關注和研究， 成果相對較多、較成熟。CuSP 約束傳播更加困難， 起步晚， 成果較少。目前，主流CuSP 約束傳播算法在進行約束傳播時， 首先將工作間的優先關係簡化為工作的最早開始時間， 最晚完成時間區間約束， 而在約束傳播過程中不再考慮工作間的優先關係，這樣的處理方法在工作可行時間區間較大時， 往往得不到較好的約束傳播效果。Laborie針對這一缺陷， 基於優先關係圖提出了改進的約束傳播算法。
約束傳播實驗設計
為了測試本文約束傳播算法的時間效率和約減效果， 利用標準問題庫PSPLIB中J32、J62 兩組問題對算法進行測試。兩組問題根據項目的網路複雜性係數NC (Networkcomplexity)、資源因數係數RF (Resource factor)、資源強度係數RS (Resource strength) 的不同組合隨機生成。其中NC 反映項目網路圖中各工作間優先關係約束的鬆緊， RF 反映工作對資源需要的耦合程度， RF = 1 代表每項工作需要全部種類的資源， RS 反映資源的限制強度.兩組問題分別包含32 項和62 項工作， 需要4 種可更新資源(K = 4)。對參數NC、RF和RS 的48 種不同組合， 每種組合隨機生成10 個問題實例.因此， 每組包含480 個問題實例.
