隨機資源受限項目調(diào)度問題的一種算法

本文對隨機資源受限項目調(diào)度問題提出了一種基于任務(wù)關(guān)鍵概率的啟發(fā)式算法。在該算法中，任務(wù)被調(diào)度的優(yōu)先權(quán)值由其屬于項目關(guān)鍵鏈的概率決定，并分別使用了關(guān)鍵鏈率乘以任務(wù)平均工期和單獨使用關(guān)鍵鏈率作為優(yōu)先權(quán)值的兩種計算方法。在項目調(diào)度中，則分別采用了依照優(yōu)先權(quán)值的大小進(jìn)行調(diào)度的標(biāo)準(zhǔn)方法和以優(yōu)先權(quán)值來計算被調(diào)度概率的采樣算法來對任務(wù)進(jìn)行調(diào)度。最后通過算例證明了該算法能夠得到優(yōu)于傳統(tǒng)基于關(guān)鍵路徑的啟發(fā)式方法的調(diào)度結(jié)果。

引言

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

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

本文基于SRCPSP的最小期望工期目標(biāo)提出一種基于任務(wù)關(guān)鍵鏈概率的啟發(fā)式算法。論文的結(jié)構(gòu)如下：第2節(jié)對隨機調(diào)度問題的基本內(nèi)容進(jìn)行了概述；第3節(jié)介紹了本文算法的步驟；在第4節(jié)通過一個算例檢驗了算法的性能；第5節(jié)給出了最后的結(jié)論。