隨機資源受限項目調度問題的一種算法

本文對隨機資源受限項目調度問題提出了一種基于任務關鍵概率的啟發式算法。在該算法中，任務被調度的優先權值由其屬于項目關鍵鏈的概率決定，并分別使用了關鍵鏈率乘以任務平均工期和單獨使用關鍵鏈率作為優先權值的兩種計算方法。在項目調度中，則分別采用了依照優先權值的大小進行調度的標準方法和以優先權值來計算被調度概率的采樣算法來對任務進行調度。最后通過算例證明了該算法能夠得到優于傳統基于關鍵路徑的啟發式方法的調度結果。

引言

許多關于資源受限項目調度問題（Resource-constrained　Project　Scheduling　Problem，RCPSP）的文獻討論了生成項目的確定性調度計劃的方法[1～3]，即在任務工期和資源確定的條件下進行調度。這個計劃將作為項目實際執行階段的指導，因此它被稱作基準調度計劃或預期調度計劃[4]。然而，在項目執行的過程中，一些不確定因素的出現會造成項目計劃的偏離，如天氣變化、機械設備故障、人員受傷等等。大多數不確定因素對項目的影響會體現在任務工期和資源的增加或減少上。

目前對于不確定項目調度的研究主要有兩種方法。第一種方法稱為主動（魯棒）—反應式調度。這種方法首先使用主動（魯棒）調度在預測了可能出現的不確定因素的基礎上，生成保護性的確定基準調度計劃，然后在項目執行階段不確定因素出現時使用反應式調度對計劃進行修正。這種調度方法已經得到了廣泛的研究[5～8]。第二種方法稱為隨機資源受限項目調度（Stochastic　RCPSP　或　SRCPSP）。在SRCPSP中，項目的執行由調度策略（Scheduling　Policy）替代確定性的基準調度計劃來決定[9～10]，它是一個多階段的決策過程。在項目開始以及每個任務完工的決策時刻，調度策略將決定哪些任務可以開工。隨機資源受項目調度最常見的目標是最小化項目的預期完工時間，Stork[11]在他的博士論文中使用了分支定界算法來對其進行精確求解，而另一些文獻則對求解這個目標的啟發式算法進行了研究[12～14]。另外，Sobel等[15]基于最小化期望凈現值目標提出一套算法，而Deblaere等[16]則對隨機調度的穩定性目標進行了研究。

本文基于SRCPSP的最小期望工期目標提出一種基于任務關鍵鏈概率的啟發式算法。論文的結構如下：第2節對隨機調度問題的基本內容進行了概述；第3節介紹了本文算法的步驟；在第4節通過一個算例檢驗了算法的性能；第5節給出了最后的結論。