陳 志, 白思俊, 郭云濤

(西北工業(yè)大學(xué) 管理學(xué)院,陜西 西安 710072)

0 引言

項(xiàng)目進(jìn)度計(jì)劃是指在項(xiàng)目工作分解結(jié)構(gòu)(Work Breakdown Structure, WBS)的基礎(chǔ)上合理安排每個(gè)活動(dòng)的開始、結(jié)束時(shí)間以滿足特定的目標(biāo)。傳統(tǒng)上項(xiàng)目進(jìn)度計(jì)劃的主要目標(biāo)為確保項(xiàng)目能夠按時(shí)完成，然而對于一些工期要求比較寬松，資金密集型的項(xiàng)目，如何最大化項(xiàng)目的凈現(xiàn)值(Net Present Value, NPV)往往成為項(xiàng)目管理者關(guān)注的首要目標(biāo)。項(xiàng)目進(jìn)度計(jì)劃顯然與項(xiàng)目凈現(xiàn)值息息相關(guān)：活動(dòng)的執(zhí)行需要消耗資源，產(chǎn)生一定的成本，同時(shí)項(xiàng)目的支付也往往以特定活動(dòng)的完成為依據(jù)進(jìn)行，因此伴隨著活動(dòng)的執(zhí)行，項(xiàng)目會(huì)產(chǎn)生一系列正向和負(fù)向的現(xiàn)金流。對于活動(dòng)不同的進(jìn)度安排將導(dǎo)致活動(dòng)所產(chǎn)生的現(xiàn)金流發(fā)生在不同的時(shí)刻，從而會(huì)影響整個(gè)項(xiàng)目的凈現(xiàn)值。傳統(tǒng)上，在進(jìn)行項(xiàng)目進(jìn)度計(jì)劃之前，項(xiàng)目管理者會(huì)對WBS中的每個(gè)活動(dòng)給予一個(gè)期望時(shí)間，然后依據(jù)此期望時(shí)間對項(xiàng)目進(jìn)行調(diào)度，然而現(xiàn)實(shí)中項(xiàng)目總是會(huì)受到各種不確定因素的影響，如：資源不到位導(dǎo)致活動(dòng)不能夠按計(jì)劃進(jìn)行，天氣原因使得活動(dòng)不得不推遲進(jìn)行等。所以，活動(dòng)的工期實(shí)際上為一隨機(jī)變量。當(dāng)活動(dòng)的工期為一隨機(jī)變量時(shí)，如何對活動(dòng)進(jìn)行安排使得項(xiàng)目的期望凈現(xiàn)值最大是本文研究的問題。

本文在文獻(xiàn)[11～13]的基礎(chǔ)上考慮了指數(shù)分布工期下具有資源約束的折現(xiàn)現(xiàn)金流項(xiàng)目調(diào)度問題。對于該問題的優(yōu)化本文仍采用動(dòng)態(tài)規(guī)劃算法，但是由于考慮了資源的約束，需要重新設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法狀態(tài)的生成及最優(yōu)解的求解過程，使得最優(yōu)解滿足資源的約束。與現(xiàn)有文獻(xiàn)不同的是本文重新設(shè)計(jì)了動(dòng)態(tài)規(guī)劃算法狀態(tài)的生成過程并對其進(jìn)行了優(yōu)化，使得生成的狀態(tài)既能滿足活動(dòng)之間的邏輯關(guān)系及資源的約束，又大大減小了生成重復(fù)狀態(tài)的數(shù)量。同時(shí)本文分析了不同狀態(tài)最優(yōu)目標(biāo)值之間的關(guān)系，使得滿足一定條件的多個(gè)狀態(tài)只需要計(jì)算一個(gè)狀態(tài)的最優(yōu)目標(biāo)值，從而減少了算法的計(jì)算時(shí)間。最后本文將設(shè)計(jì)的算法在504個(gè)案例上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

1 問題的描述

(1)

式(1)中γ為折現(xiàn)因子。一般來說項(xiàng)目在完成一些特定的活動(dòng)V′?V后才會(huì)得到一筆固定的收入gi>0(i∈V′)，其中n+1∈V′，即整個(gè)項(xiàng)目結(jié)束后會(huì)得到一筆固定收入，對于其他活動(dòng)i∈VV′,gi=0。

(2)

圖1為該問題的一個(gè)案例。假設(shè)該項(xiàng)目只需要使用一種資源，該資源總的供給量為10個(gè)單位。圖1中活動(dòng)上方的數(shù)字分別為該活動(dòng)的期望工期、期望現(xiàn)金流，下方的數(shù)字為該活動(dòng)對資源的需求量。由于活動(dòng)1和活動(dòng)2對資源的總需求量超過了該種資源的總供給量，因此活動(dòng)1和活動(dòng)2不能同時(shí)執(zhí)行。假設(shè)折現(xiàn)因子γ=0.04，可以計(jì)算在策略π1={將活動(dòng)2推遲至活動(dòng)1結(jié)束之后，其他活動(dòng)在其緊前活動(dòng)結(jié)束的時(shí)刻即開始}下該項(xiàng)目的期望凈現(xiàn)值為28.599，策略π2={將活動(dòng)2推遲至活動(dòng)1結(jié)束之后，同時(shí)若活動(dòng)1的結(jié)束時(shí)間早于時(shí)刻6，則將活動(dòng)3推遲至?xí)r刻6再開始，其他活動(dòng)在其緊前活動(dòng)結(jié)束的時(shí)刻即開始}下該項(xiàng)目的期望凈現(xiàn)值為32.789，最后在策略π3={將活動(dòng)1推遲至活動(dòng)2結(jié)束之后，活動(dòng)3推遲至活動(dòng)4結(jié)束之后，其他活動(dòng)在其緊前活動(dòng)結(jié)束的時(shí)刻即開始}下該項(xiàng)目的期望凈現(xiàn)值為51.166。可見不同的調(diào)度策略下項(xiàng)目最后的期望凈現(xiàn)值是不一樣的。可以證明上述3個(gè)策略中π3為全局最優(yōu)調(diào)度策略。

2 動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)

由圖1所給出的案例可知，通常情況下該問題的求解會(huì)比較復(fù)雜，由于活動(dòng)的時(shí)間為隨機(jī)數(shù)，而一個(gè)活動(dòng)可以在其所有緊前活動(dòng)結(jié)束后的任意時(shí)刻開始，這樣單就一個(gè)活動(dòng)來說其解就有無限多種可能性。但當(dāng)活動(dòng)時(shí)間服從指數(shù)分布時(shí)，文獻(xiàn)[11～13]證明了如下的定理：

定理1當(dāng)活動(dòng)時(shí)間服從指數(shù)分布時(shí)，該問題的最優(yōu)解中每一個(gè)活動(dòng)總是在其他活動(dòng)結(jié)束的時(shí)刻開始，即最優(yōu)策略中每一次決策總是發(fā)生在某一活動(dòng)結(jié)束的時(shí)刻。

定理1大幅簡化了該問題的求解過程，使得該問題的解空間由無窮變?yōu)榱擞邢?。本?jié)在定理1的基礎(chǔ)上針對第2節(jié)所描述的問題設(shè)計(jì)了一種動(dòng)態(tài)規(guī)劃算法。

2.1 階段的劃分，狀態(tài)，決策及狀態(tài)之間的轉(zhuǎn)移

對于含有n+2個(gè)活動(dòng)的項(xiàng)目G，可以將該問題的求解劃分為n+2個(gè)階段。其中每一個(gè)階段至少包含1個(gè)狀態(tài)。第m階段所有狀態(tài)集合為Sm，第i個(gè)狀態(tài)為Sm,i=(φm,i,φm,i)，其中φm,i和φm,i為V的一個(gè)子集，即φm,i,φm,i?V并且φm,i∩φm,i=?。φm,i表示該狀態(tài)下已經(jīng)完成的活動(dòng)，φm,i表示該狀態(tài)下正在進(jìn)行的活動(dòng)。S1,1=({0},?)為第一階段唯一的狀態(tài)，表示虛擬開始活動(dòng)被完成，Sn+2,1=(V,?)為最后一階段唯一的狀態(tài)，表示項(xiàng)目所有活動(dòng)已經(jīng)被完成。圖2給出了求解圖1中問題的階段及狀態(tài)，圖中圓角矩形表示狀態(tài)，狀態(tài)中分號(hào)前邊的活動(dòng)集合為φ，分號(hào)后邊的活動(dòng)集合為φ，若分號(hào)后無活動(dòng)則表示φ為空。連接不同狀態(tài)邊上的數(shù)字表示狀態(tài)之間轉(zhuǎn)移所采取的決策，如當(dāng)處于狀態(tài)S3,1=(0,1,3;)時(shí)，若開始活動(dòng)2則可以到達(dá)狀態(tài)S4,1=(0,1,2,3;)。圖中圓形則表示決策之后的狀態(tài)可能會(huì)發(fā)生多種不同的情況，如當(dāng)處于狀態(tài)S2,2=(0,2;)時(shí)，若同時(shí)開始活動(dòng)1和4，則當(dāng)活動(dòng)1早于活動(dòng)4結(jié)束時(shí)會(huì)到達(dá)狀態(tài)S3,5=(0,1,2;4)，當(dāng)活動(dòng)4早于活動(dòng)1結(jié)束時(shí)會(huì)到達(dá)狀態(tài)S3,6=(0,2,4;1)。在圖1所示的案例中第二階段省略了狀態(tài)(0,1;2)和(0,2;1)，這兩個(gè)狀態(tài)雖然滿足邏輯關(guān)系，但是由于資源的約束，活動(dòng)1和活動(dòng)2不能夠同時(shí)開始，因此它們?yōu)椴豢尚袪顟B(tài)。

假設(shè)E(S)為當(dāng)處于狀態(tài)S時(shí)的允許決策集合，E(S)中包含了狀態(tài)S下可以開始的活動(dòng)集合，若活動(dòng)i∈E(S)，則活動(dòng)i的所有緊前活動(dòng)在狀態(tài)S時(shí)已經(jīng)被完成，即E(S)={i∈VS|?(j,i)∈E,j∈φ}。如圖1中所示的項(xiàng)目，當(dāng)活動(dòng)0，1，2被完成時(shí)，可以開始活動(dòng)3和4，所以E(S3,4)={3,4}。決策變量D(S)表示當(dāng)處于狀態(tài)S時(shí)實(shí)際開始執(zhí)行的活動(dòng)集合，顯然D(S)?E(S)。決策變量的取值應(yīng)當(dāng)考慮資源的約束，即同一時(shí)刻正在執(zhí)行的活動(dòng)對任何一種資源的需求不應(yīng)當(dāng)超過該種資源的供給量，即∑i∈D(S)∪φri,k≤Rk,?k∈ω。對于某一狀態(tài)S，當(dāng)φ≠?時(shí)，E(S)可能為?，如圖2中E(S3,3)=?；當(dāng)φ=?，同時(shí)決策變量D(S)=?時(shí)表示放棄執(zhí)行該項(xiàng)目剩余的活動(dòng)，本文所建立的模型并不考慮這一決策變量。

由于最后一個(gè)階段的狀態(tài)及該狀態(tài)下的目標(biāo)值是已知的，因此對該問題的優(yōu)化需要采用逆推的方式進(jìn)行。第m-1階段的所有狀態(tài)也是由第m階段的狀態(tài)生成。當(dāng)不考慮資源的約束時(shí)，對于一個(gè)具有m個(gè)已完成活動(dòng)和w個(gè)正在執(zhí)行活動(dòng)的狀態(tài)，其滿足邏輯關(guān)系的前驅(qū)狀態(tài)及相應(yīng)的決策如圖3所示。若當(dāng)前狀態(tài)有m個(gè)已完成活動(dòng)，則前一階段狀態(tài)必然有m-1個(gè)已完成活動(dòng)，同時(shí)前一階段狀態(tài)中正在執(zhí)行活動(dòng)的個(gè)數(shù)加上決策集合中的活動(dòng)個(gè)數(shù)必然等于w+1。與一個(gè)狀態(tài)的前驅(qū)狀態(tài)相似，一個(gè)狀態(tài)的后繼狀態(tài)個(gè)數(shù)往往也多于一個(gè)，如當(dāng)|φ|=m-1，|φ|=0，|D(S) |=w+1時(shí)，其后繼狀態(tài)就多達(dá)w+1個(gè)。因此，若對于第m階段的每一個(gè)狀態(tài)考慮其所有可能的前驅(qū)狀態(tài)則會(huì)生成大量重復(fù)的狀態(tài)，使得計(jì)算需要大量的時(shí)間。為了節(jié)省計(jì)算時(shí)間，同時(shí)又不遺漏任何可能的狀態(tài)，本文設(shè)計(jì)了一種新的計(jì)算方法來計(jì)算前一階段所有滿足邏輯關(guān)系和資源約束的狀態(tài)，其計(jì)算過程如算法1所示。對第m階段的狀態(tài)Sm,i=(φm,i,φm,i)∈Sm，首先計(jì)算集合H(Sm,i)，H(Sm,i)中包含了那些在第m-1階段中可以從φm,i中去掉的活動(dòng)。若活動(dòng)j在第m-1階段可以從φm,i中去掉，則活動(dòng)j的后繼活動(dòng)集合Sucj中的任何活動(dòng)必然不屬于φm,i∪φm,i。對于狀態(tài)Sm,i=(φm,i,φm,i)，若|φm,i|=w≥1則只需要產(chǎn)生|φm-1,j|=w+1的所有滿足邏輯關(guān)系的狀態(tài), 若|φm,i|=0則需要產(chǎn)生|φm-1,j|=0和|φm-1,j|=1的所有滿足邏輯關(guān)系的前驅(qū)狀態(tài)。定理2保證了算法1能夠產(chǎn)生第m-1階段所有滿足邏輯關(guān)系的狀態(tài)。

算法1 計(jì)算前一階段所有滿足邏輯關(guān)系及資源約束狀態(tài)的偽代碼

Algorithm 1Determine all the states of stage m-1Input: Sm,i(m=1,2,…,n+2),rj,k(j∈V,k∈ω),Rk(k∈ω)1.for every state Sm,i=(?m,i,φm,i)∈Sm2.determine H(Sm,i)={j∈?m,i|Sucj∩(?m,i∪φm,i)=?}3.if|H(Sm,i)|>14.move every activity j∈H(Sm,i)from ?m,ito φm,i, generate new state Sm-1,i′=(?m,i-j,φm,i+j)∈Sm-1, check the feasibility of re-source demands5.end if6.if|φm,i|=07.remove every activity j∈H(Sm,i)from ?m,i, generate new stateSm-1,i′=(?m,i-j,?)∈Sm-18.end if9.end for

定理2對于第m階段的狀態(tài)Sm,i=(φm,i,φm,i)∈Sm，若|φm,i|=w≥1，則只需要產(chǎn)生|φm-1,j|=w+1的所有滿足邏輯關(guān)系的狀態(tài)，若|φm,i|=0，則需要產(chǎn)生|φm-1,j|=0和|φm-1,j|=1的所有滿足邏輯關(guān)系的狀態(tài)，該過程足以產(chǎn)生第m-1階段所有滿足邏輯關(guān)系的狀態(tài)。

定理2簡化了由第m階段狀態(tài)產(chǎn)生第m-1階段所有狀態(tài)的過程，使得產(chǎn)生重復(fù)狀態(tài)的數(shù)量大大減少。

定理3對于任意狀態(tài)Sm,i=(φm,i,φm,i)∈Sm，|φm,i|=w，活動(dòng)j∈H(Sm,i)，狀態(tài)Sm-1,i′=(φm,i-j,φm,i+j)滿足邏輯關(guān)系的充分必要條件是|H(Sm,i)|>1。

對于第m階段狀態(tài)Sm,i=(φm,i,φm,i)，在計(jì)算出H(Sm,i)之后，生成第m-1階段狀態(tài)時(shí)只需要將H(Sm,i)之中的活動(dòng)逐個(gè)從φm,i中移至φm,i。若|φm,i|=0，則還需要將H(Sm,i)之中的活動(dòng)逐個(gè)從φm,i移除。在將H(Sm,i)之中的活動(dòng)逐個(gè)從φm,i中移至φm,i時(shí)還需要考慮資源的約束，若新的狀態(tài)不滿足資源的約束則可以將其直接刪除，從而節(jié)省程序?qū)Υ鎯?chǔ)的需求及計(jì)算時(shí)間。

推論1對于任意狀態(tài)Sm,i=(φm,i,φm,i)∈Sm，|φm,i|=w，活動(dòng)j∈H(Sm,i)，狀態(tài)Sm-1,i′=(φm,i-j,φm,i+j)是滿足資源需求的，則必然存在著另一活動(dòng)j′∈H(Sm,i)，滿足rj,k+rj′k+∑q∈φm,irq,k≤Rk,?k∈ω。

推論1是定理3的一個(gè)直接結(jié)果，由于第m-1階段狀態(tài)Sm-1,i′=(φm,i-j,φm,i+j)是第m-2階段狀態(tài)Sm-2,i″=(φm-2,i″,φm-2,i″)的后繼狀態(tài)，而狀態(tài)Sm-2,i″產(chǎn)生Sm-1,i′必須滿足條件|φm-2,i″|+|D(Sm-2,i″)|=w+2，即w+2個(gè)活動(dòng)可以同時(shí)被執(zhí)行。

以圖2為例，當(dāng)狀態(tài)為S4,1時(shí)，H(S4,1)={2,3}，按照算法1可以生成狀態(tài)S3,1，S3,2，S3,3，S3,4。當(dāng)狀態(tài)為S4,2時(shí)，H(S4,2)={3}，無需生成任何前驅(qū)狀態(tài)。當(dāng)狀態(tài)為S4,3時(shí)，H(S4,3)={4}，無需生成任何前驅(qū)狀態(tài)。當(dāng)狀態(tài)為S4,4時(shí)，H(S4,4)={1,4}，按照算法1可以生成狀態(tài)S3,4，S3,5，S3,6，S3,7，其中狀態(tài)S3,4為重復(fù)生成的狀態(tài)。

2.2 目標(biāo)函數(shù)及最優(yōu)值函數(shù)

當(dāng)處于狀態(tài)S時(shí)，若以V(S)表示決策D(S)下的目標(biāo)函數(shù)值，則采用逆推的方法可以得到V(S)的表達(dá)式如下：

(3)

=1-e-t∑j∈D(S)∪φλj=1-e-tρ

(4)

活動(dòng)j∈D(S)∪φ最先完成的概率為

(5)

(6)

f(t,j)=λje-t∑i∈D(S)∪φλi=λje-tρ

(7)

則由式(7)計(jì)算可得

(8)

最后將式(8)帶入式(3)中可以得到V(S)的最終表達(dá)式為

(9)

而最優(yōu)值函數(shù)V*(S)的表達(dá)式為

V*(S)=maxD(S)?E(S)V(S)

(10)

以圖2為例，當(dāng)處于狀態(tài)S3,4時(shí)，允許決策集合E(S3,4)={3,4}。假設(shè)V*(S4,1)=187.59，V*(S4,2)=220.59，V*(S4,3)=277.78，V*(S4,4)=166.78，則當(dāng)D(S3,4)={3}時(shí)，后續(xù)狀態(tài)只有S4,1，此時(shí)V(S3,4)=62.69，當(dāng)D(S3,4)={4}時(shí)，后續(xù)狀態(tài)只有S4,4，此時(shí)V(S3,4)=89.63，當(dāng)D(S3,4)={4,5}時(shí)，則狀態(tài)S3,4會(huì)以9/11的概率轉(zhuǎn)移至狀態(tài)S4,2，以2/11的概率轉(zhuǎn)移至狀態(tài)S4,3，此時(shí)V(S3,4)=72.80。綜上可知V*(S3,4)=89.63，而最優(yōu)決策D*(S3,4)={4}，即當(dāng)活動(dòng)0、1、2結(jié)束時(shí)，只開始活動(dòng)4，推遲活動(dòng)3的開始時(shí)間。

2.3 最優(yōu)策略的求解

對于每一狀態(tài)下最優(yōu)決策的求解為一組合優(yōu)化問題，該問題與背包問題十分相似，資源的約束為背包容量，活動(dòng)對資源的需求為物品重量，目標(biāo)為在資源的約束下最大化狀態(tài)的凈現(xiàn)值。針對該問題本文設(shè)計(jì)了一種分支算法來求解最優(yōu)決策。圖4給出了一個(gè)求解最優(yōu)決策的案例，圖中狀態(tài)節(jié)點(diǎn)右邊的數(shù)字為該狀態(tài)的最優(yōu)目標(biāo)值，活動(dòng)上邊的數(shù)字為期望工期、期望現(xiàn)金流，下邊的數(shù)字為該活動(dòng)對資源的需求。4種資源的總供給量為(12,11,10,13)。圖5給出了求解圖4中問題的分支算法的過程。圖5中方框中的數(shù)字表示決策變量D(S)，有向邊上的數(shù)字+i表示該狀態(tài)下的決策包括活動(dòng)i，相反若有向邊上的數(shù)字為-i，則表示該狀態(tài)下的決策不包括活動(dòng)i。對于狀態(tài)S，若|E(S)|=m，則該分支樹最多有m層。對于第j層節(jié)點(diǎn)，若j

2.4 算法流程

算法2求解隨機(jī)活動(dòng)工期下資源約束項(xiàng)目最大期望凈現(xiàn)值的動(dòng)態(tài)規(guī)劃算法流程

Algorithm2 Determine the maximum expected NPVInput: G=(V,E),ri,k,cFi,dEi(i∈V,k∈ω)Output: V?(S1,1)1.Sn+2,1←(V,?),V?(Sn+2,1)←cFn+22.for stage m←from n+2 to 2 do3.based onSm, generate statesSm-14.for state Sm-1,i∈Sm-15.determine the D?(Sm-1,i)and V?(Sm-1,i)6.end for7.free memory occupied bySm8.end9.free memory occupied byS1

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果

為了驗(yàn)證算法的有效性，本文對2節(jié)設(shè)計(jì)的動(dòng)態(tài)規(guī)劃算法利用C++在Microsoft Visual Studio 2017中進(jìn)行了測試。測試環(huán)境為Intel Core i5-2400 4核處理器，3.10 GHz主頻及4 GB RAM。

(11)

(12)

表1 項(xiàng)目案例參數(shù)的取值水平

表2給出了不同活動(dòng)數(shù)量及次序強(qiáng)度下算法求得項(xiàng)目案例最優(yōu)值所需要的平均時(shí)間?？偟膩碚f隨著項(xiàng)目活動(dòng)數(shù)量的增加，算法所需的時(shí)間也在增加；隨著項(xiàng)目案例次序強(qiáng)度的增加，算法所需時(shí)間在減小。其中項(xiàng)目案例的次序強(qiáng)度對算法所需時(shí)間有著較大的影響。表3給出了這一影響的具體原因：對比表3的不同列，會(huì)發(fā)現(xiàn)項(xiàng)目的次序強(qiáng)度越小，動(dòng)態(tài)規(guī)劃算法所產(chǎn)生的狀態(tài)數(shù)量越多，由于每個(gè)狀態(tài)均需要計(jì)算其最優(yōu)決策與最優(yōu)目標(biāo)值，因此算法需要較長的時(shí)間。表4給出了不同項(xiàng)目活動(dòng)數(shù)量下資源強(qiáng)度對案例狀態(tài)數(shù)量的影響，從表中可以看出項(xiàng)目案例的狀態(tài)數(shù)量隨著資源強(qiáng)度的增加也在增加。這一現(xiàn)象很好理解，隨著可利用資源的增加每一狀態(tài)S的允許決策集合E(S)中的活動(dòng)數(shù)量也會(huì)增加，從而其后續(xù)可能的狀態(tài)數(shù)量也會(huì)增加，這導(dǎo)致了整個(gè)案例狀態(tài)數(shù)量的增加。

表2 不同活動(dòng)數(shù)量及次序強(qiáng)度下項(xiàng)目案例的平均計(jì)算時(shí)間(s)

表3 不同活動(dòng)數(shù)量及次序強(qiáng)度下項(xiàng)目案例的平均狀態(tài)數(shù)量

表4 資源強(qiáng)度對項(xiàng)目案例狀態(tài)數(shù)量的影響

4 結(jié)語

本文研究了隨機(jī)活動(dòng)工期下如何調(diào)度資源約束項(xiàng)目使得項(xiàng)目的期望凈現(xiàn)值最大化。首先對問題進(jìn)行了描述和界定，并建立了優(yōu)化模型。該模型假設(shè)項(xiàng)目活動(dòng)時(shí)間為一已知分布的隨機(jī)變量，項(xiàng)目管理者需要在滿足活動(dòng)邏輯關(guān)系和有限資源的約束下對項(xiàng)目調(diào)度進(jìn)行優(yōu)化，使得項(xiàng)目的期望凈現(xiàn)值最大。由于活動(dòng)時(shí)間為不確定的值，項(xiàng)目的調(diào)度不再是給出每個(gè)活動(dòng)的開始時(shí)間，而是確定一動(dòng)態(tài)調(diào)度策略。針對該問題的特點(diǎn)本文設(shè)計(jì)了一種動(dòng)態(tài)規(guī)劃算法。在動(dòng)態(tài)規(guī)劃算法中狀態(tài)變量和決策變量具有組合屬性，隨著項(xiàng)目活動(dòng)的增多，狀態(tài)空間和決策空間的規(guī)模會(huì)呈指數(shù)級(jí)增長，因此如何高效地生成狀態(tài)并求得狀態(tài)的最優(yōu)決策和目標(biāo)值是算法設(shè)計(jì)的關(guān)鍵。本文在分析了項(xiàng)目網(wǎng)絡(luò)圖結(jié)構(gòu)的基礎(chǔ)上優(yōu)化了狀態(tài)的生成過程，使得算法能高效地生成滿足活動(dòng)邏輯關(guān)系及資源的約束的狀態(tài)。同時(shí)本文發(fā)現(xiàn)了在求解狀態(tài)最優(yōu)決策和目標(biāo)值的過程中滿足一定條件的多個(gè)狀態(tài)只需要計(jì)算一個(gè)狀態(tài)的最優(yōu)決策和目標(biāo)值，從而減少了算法的計(jì)算時(shí)間。最后，本文將設(shè)計(jì)的算法在540個(gè)不同規(guī)模和不同特征的仿真案例上進(jìn)行了測試，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。同時(shí)實(shí)驗(yàn)發(fā)現(xiàn)：在相同規(guī)模的項(xiàng)目之間，次序強(qiáng)度對算法所需時(shí)間有著較大的影響，隨著項(xiàng)目次序強(qiáng)度的減小，算法生成的狀態(tài)數(shù)量會(huì)增加，從而計(jì)算時(shí)間也會(huì)增加。本文給出的動(dòng)態(tài)規(guī)劃算法只能對活動(dòng)時(shí)間為指數(shù)分布的案例進(jìn)行優(yōu)化，當(dāng)項(xiàng)目活動(dòng)時(shí)間為非指數(shù)分布時(shí)定理1不再成立，因此動(dòng)態(tài)規(guī)劃算法并不能給出該問題的最優(yōu)解。如何求解非指數(shù)分布工期下項(xiàng)目的最大期望凈現(xiàn)值是值得進(jìn)一步研究的方向。