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

引言

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

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

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