資源多約束進(jìn)度網(wǎng)絡(luò)的風(fēng)險(xiǎn)評(píng)估

蔡永勇++桑笑楠++張周磊++徐永紅

摘要：在項(xiàng)目管理中由于項(xiàng)目龐大、持續(xù)周期長、影響因素繁多，不可避免地會(huì)面對(duì)潛在的風(fēng)險(xiǎn)。本文對(duì)項(xiàng)目潛在的風(fēng)險(xiǎn)進(jìn)行評(píng)估，讓項(xiàng)目的管理者對(duì)項(xiàng)目有一個(gè)長遠(yuǎn)的認(rèn)識(shí)，防范風(fēng)險(xiǎn)于未然。本文應(yīng)用資源多約束下項(xiàng)目進(jìn)度調(diào)度（resource-constrained project scheduling problem，RCPSP）問題模型，對(duì)進(jìn)度風(fēng)險(xiǎn)評(píng)估系統(tǒng)進(jìn)行了需求分析和模塊劃分，設(shè)計(jì)了系統(tǒng)的框架層次、數(shù)據(jù)庫、資源多約束下的蒙式仿真算法，給出了依據(jù)仿真結(jié)果計(jì)算進(jìn)度風(fēng)險(xiǎn)和成本風(fēng)險(xiǎn)的統(tǒng)計(jì)思路。

關(guān)鍵詞：進(jìn)度風(fēng)險(xiǎn)評(píng)估；蒙式仿真；成本風(fēng)險(xiǎn)；資源多約束

中圖分類號(hào)：TP391. 41

文獻(xiàn)標(biāo)識(shí)碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.008

0 引言

項(xiàng)目管理是通過項(xiàng)目經(jīng)理和項(xiàng)目組織的努力，運(yùn)用系統(tǒng)理論和方法對(duì)項(xiàng)目及其資源進(jìn)行計(jì)劃、組織、協(xié)調(diào)、控制，旨在實(shí)現(xiàn)項(xiàng)目特定目標(biāo)的管理方法體系。項(xiàng)目管理的對(duì)象是項(xiàng)目，即一系列的臨時(shí)任務(wù)，它的目的是通過運(yùn)用科學(xué)的項(xiàng)目管理技術(shù)，更好地實(shí)現(xiàn)項(xiàng)目目標(biāo)。項(xiàng)目管理的職能與其它管理的職能是完全一致的，即是對(duì)組織的資源進(jìn)行計(jì)劃、組織、指揮、控制。資源是指項(xiàng)目所在的組織中可得到的、為項(xiàng)目所需要的那些資源，包括人員、資金、技術(shù)、設(shè)備等，在項(xiàng)目的管理中，時(shí)間是一種特殊的資源。項(xiàng)目管理的任務(wù)是對(duì)項(xiàng)目及其資源的計(jì)劃、組織、協(xié)調(diào)、控制。

任何項(xiàng)目的策劃和執(zhí)行都包含大量不同的活動(dòng)及各種人力、物力資源。資源是項(xiàng)目執(zhí)行過程中不可缺少的重要組成部分，而這些資源的有效的可用量往往是有限的。有的資源是可循環(huán)利用的，而有些則是一次性的。如何以最佳方式安排執(zhí)行項(xiàng)目中的各個(gè)活動(dòng)，以使其順利完成，就構(gòu)成了資源受限下項(xiàng)目進(jìn)度調(diào)度問題的基本概念。

資源約束下項(xiàng)目調(diào)度問題（resource-constrained project scheduling problem，RCPSP）是一類應(yīng)用范圍十分廣泛的組合優(yōu)化問題，它研究在資源稀缺的情況下滿足資源的約束，合理安排任務(wù)的開始時(shí)間和結(jié)束時(shí)間，從而在資源最優(yōu)利用的同時(shí)實(shí)現(xiàn)既定目標(biāo)的最優(yōu)化。它被證明是一種強(qiáng)NP難題。資源約束下項(xiàng)目調(diào)度問題模型豐富，根據(jù)資源類型和項(xiàng)目結(jié)構(gòu)的不同可以分為眾多種類，許多組合優(yōu)化問題是RCPSP的特殊情形。例如作業(yè)車間（job shop）調(diào)度，流水車間（flow shop）調(diào)度等。此外RCPSP廣泛存在于建筑工程，軟件開發(fā)，飛機(jī)和輪船制造等單件或小批量生產(chǎn)方式的企業(yè)中。因此研究RCPSP具有重要的理論和現(xiàn)實(shí)意義，可以廣泛應(yīng)用于實(shí)際。

近年來，RCPSP得到了許多擴(kuò)充。鑒于應(yīng)用背景和目標(biāo)函數(shù)的不同，RCPSP可擴(kuò)展為時(shí)間/費(fèi)用權(quán)衡問題（TCTP），資源水平問題（RLP）和凈現(xiàn)值（NPV）問題等。進(jìn)一步考慮不確定因素，又產(chǎn)生了隨機(jī)調(diào)度問題。作為項(xiàng)目調(diào)度的有效工具，甘特圖、關(guān)鍵路徑法和計(jì)劃評(píng)審技術(shù)已廣泛應(yīng)用于各種項(xiàng)目調(diào)度問題。在算法方面，尤其是求解算法（包括智能算法）得到了廣泛而深入的討論，同時(shí)得到了許多成功應(yīng)用。

1 系統(tǒng)需求分析與設(shè)計(jì)

本文在功能方面，針對(duì)管理者的日常需求，將資源多約束下進(jìn)度風(fēng)險(xiǎn)評(píng)估系統(tǒng)功能分為：項(xiàng)目管理，資源管理，項(xiàng)目網(wǎng)絡(luò)圖（任務(wù)屬性設(shè)置），項(xiàng)目仿真，項(xiàng)目仿真版本管理等項(xiàng)功能。

項(xiàng)目管理：對(duì)項(xiàng)目的任務(wù)節(jié)點(diǎn)信息和節(jié)點(diǎn)之間的約束關(guān)系等進(jìn)行記錄和管理，并可以對(duì)項(xiàng)目進(jìn)行資源分配。

資源管理：對(duì)資源的屬性和數(shù)量等進(jìn)行記錄和管理。

項(xiàng)目網(wǎng)絡(luò)圖：展示項(xiàng)目各個(gè)任務(wù)節(jié)點(diǎn)之間的約束關(guān)系，形成網(wǎng)絡(luò)圖?？梢詫?duì)每個(gè)非概要任務(wù)節(jié)點(diǎn)進(jìn)行任務(wù)屬性的設(shè)置和資源需求的設(shè)置，為仿真進(jìn)行準(zhǔn)備。

項(xiàng)目仿真：對(duì)設(shè)置好任務(wù)節(jié)點(diǎn)屬性的項(xiàng)目進(jìn)行帶資源約束的仿真或不帶資源約束的仿真。

項(xiàng)目仿真版本管理：管理所有項(xiàng)目仿真好的版本.可以選擇某個(gè)版本進(jìn)行查看，也可以刪除某個(gè)版本。

因此，本系統(tǒng)包括項(xiàng)目管理模塊、項(xiàng)目網(wǎng)絡(luò)圖模塊、仿真版本和新仿真模塊、仿真結(jié)果模塊、資源管理模塊。

項(xiàng)目管理模塊：提供了必要的項(xiàng)目管理及資源分配功能。用戶可以對(duì)項(xiàng)目進(jìn)行管理，例如，通過讀人XML配置文件添加項(xiàng)目、修改項(xiàng)目描述、查看項(xiàng)目XML文件等功能。用戶也可以將已經(jīng)存在的資源分配給某一個(gè)具體項(xiàng)目，以便為有資源約束的仿真做準(zhǔn)備。

項(xiàng)目網(wǎng)絡(luò)圖模塊：展示項(xiàng)目的任務(wù)節(jié)點(diǎn)信息和它們的相互關(guān)系，以網(wǎng)絡(luò)圖的形式表示出來。用戶可以通過點(diǎn)擊某個(gè)具體節(jié)點(diǎn)設(shè)置它的屬性（統(tǒng)計(jì)學(xué)分布、期望、方差等）和需求資源的情況，為帶資源的仿真和不帶資源的仿真做進(jìn)一步準(zhǔn)備。

仿真版本和新仿真模塊：管理和顯示已經(jīng)存在的仿真版本和新建一個(gè)版本開始仿真。用戶可以選擇一個(gè)已經(jīng)存在的仿真版本進(jìn)行查看或者刪除，也可以新建某個(gè)項(xiàng)目的一個(gè)版本，進(jìn)行一定次數(shù)的帶資源的仿真或不帶資源的仿真。

仿真結(jié)果模塊：展示某個(gè)版本的仿真結(jié)果，以圖表的方式展現(xiàn)如關(guān)鍵路徑、平均工期、任務(wù)關(guān)鍵路徑概率、總工期區(qū)間分布、進(jìn)度風(fēng)險(xiǎn)、成本風(fēng)險(xiǎn)、進(jìn)度成本聯(lián)合風(fēng)險(xiǎn)等信息。用戶可以通過瀏覽這些圖表形式的仿真結(jié)果，直觀地了解系統(tǒng)對(duì)于項(xiàng)目的風(fēng)險(xiǎn)評(píng)估信息，方便地做出最有利的決策。

資源管理模塊：管理和顯示資源的相關(guān)信息，用戶可以創(chuàng)建、修改、刪除某個(gè)資源。也可以設(shè)置資源的相關(guān)屬性（名稱、數(shù)量、是非為消耗性資源等）。

2 大數(shù)據(jù)多約束進(jìn)度風(fēng)險(xiǎn)評(píng)估算法

本算法的核心類似銀行家算法，運(yùn)用到了拓?fù)渑判蚝完?duì)列的相關(guān)知識(shí)，其思路是：枚舉出所有可能的全拓?fù)滟Y源分配序列（按優(yōu)先級(jí)剔除部分），然后對(duì)其逐一進(jìn)行模擬比較，算出最優(yōu)分配序列。在分配資源和計(jì)算節(jié)點(diǎn)工期的過程中，按照銀行家算法的思想，節(jié)點(diǎn)在申請(qǐng)資源的時(shí)候直接申明所需的最大資源，而且項(xiàng)目盡量滿足節(jié)點(diǎn)的申明，除非超過擁有資源的最大數(shù)量。這樣使得至少有一個(gè)節(jié)點(diǎn)是出于就緒狀態(tài)的，避免死鎖。

具體步驟：

A.輸入項(xiàng)目基本信息和結(jié)構(gòu)（輸入項(xiàng)目XML）。

B.輸入項(xiàng)目資源信息

C.輸入項(xiàng)目每個(gè)節(jié)點(diǎn)的統(tǒng)計(jì)學(xué)屬性、優(yōu)先級(jí)關(guān)系和資源需求。

D.按照優(yōu)先級(jí)計(jì)算項(xiàng)目節(jié)點(diǎn)的全拓?fù)渑判蛸Y源分配序列。

E.按順序選擇一個(gè)資源分配序列進(jìn)行模擬。

F.將所有人度為零的節(jié)點(diǎn)加入等待隊(duì)列。

G.按順序給等待隊(duì)列節(jié)點(diǎn)分配資源，如果節(jié)點(diǎn)資源滿足則把它改為加入就緒隊(duì)列并將其所有后繼節(jié)點(diǎn)人

度減一。

H.如果就緒隊(duì)列不為空，則計(jì)算節(jié)點(diǎn)工期，按最小工期的節(jié)點(diǎn)推進(jìn)項(xiàng)目。否則說明沒有就緒節(jié)點(diǎn)，本資

源分配序列無法完成，返回E。

I.計(jì)算在等待隊(duì)列的節(jié)點(diǎn)的等待資源時(shí)間。

J.計(jì)算完成節(jié)點(diǎn)的成本。

K.回收完成節(jié)點(diǎn)的資源，將其剔除就緒隊(duì)列。

L.如果所有節(jié)點(diǎn)都已經(jīng)完成則本資源分配序列結(jié)束，計(jì)算總工期。否則返回F。

M.如果所有資源分配序列都已經(jīng)模擬過則算法結(jié)束，否則返回E。

N.輸出任務(wù)等待的時(shí)間和等待的資源。

0.輸出項(xiàng)目總工期和總成本。

算法流程圖如圖2所示。

設(shè)Sequence_List為資源分配序列數(shù)組，Sequence為資源分配序列，Wait List為等待隊(duì)列，Ready_List為就緒隊(duì)列，Task_List為節(jié)點(diǎn)列表。算法的偽代碼可以表示為：

Foreach Sequence in Sequence_List

Foreach task in Task_ List

If （task.InDegree=0）then

Wait_List.Add（task） For i=l to Sequence.length do

Forj=l to Wait_List.count do

If（Wait_List.count[j].id！=Sequence[i]）

Continue

If（allocateResource（Wait_List.count[j]）=OK）

Ready_List.Add（task）

For k=l to task.succeed.lengh do

task.succeed[k]-

Wait_List.Remove（task）

If（Ready_List！=null）

minValue←Findmin（Ready_List）

Duration+=minValue；

Foreach task in Wait_List

Task.waittime+=minValue

For i=l to Ready_List.count do

If（Ready_List[i].Value<=minValue）

Mo ney+= getMo ney（Ready_List [i]）

recycleRe source （Ready_List[i]）

Ready_List[i].Remove（task）

Else

Ready_List[i].Value-=minValue

Else

Finish（）

本系統(tǒng)的資源約束仿真算法還運(yùn)用到了關(guān)鍵路徑算法，它為資源約束仿真算法的子過程。其算法步驟如下：

A. 拓?fù)渑判颍瑢⑺腥硕葹榱愕狞c(diǎn)壓人堆棧

B. 計(jì)算棧頂節(jié)點(diǎn)最早開始工期Ve并將其所有后繼節(jié)點(diǎn)人度

減一

C. 彈出堆棧。

D. 如果堆棧不為空則返回B。

E. 如果還有節(jié)點(diǎn)未完成則返回A

F. 逆拓?fù)渑判颍瑢⑺谐龆葹榱愕狞c(diǎn)壓人堆棧

G. 計(jì)算棧頂節(jié)點(diǎn)最遲開始工期Vl并將其所有前驅(qū)節(jié)點(diǎn)出度減

H 如果Vl=Ve，將節(jié)點(diǎn)標(biāo)記為關(guān)鍵路徑上的節(jié)點(diǎn)。

I. 彈出堆棧。

J. 如果堆棧不為空則返回G。

K. 如果還有節(jié)點(diǎn)未完成則返回F

L 算法結(jié)束

算法的流程圖如圖3所示。

3 系統(tǒng)仿真及驗(yàn)證

蒙式仿真（Monte Carlo）方法是通過大量的計(jì)算機(jī)模擬來檢驗(yàn)系統(tǒng)的動(dòng)態(tài)特性并歸納出統(tǒng)計(jì)結(jié)果的一種隨機(jī)分析方法，也稱為統(tǒng)計(jì)模擬法或隨機(jī)采樣技術(shù)。它包括偽隨機(jī)數(shù)的產(chǎn)生，蒙式仿真設(shè)計(jì)以及結(jié)果解釋等內(nèi)容，其作用在于用數(shù)學(xué)方法模擬真實(shí)物理環(huán)境，并驗(yàn)證系統(tǒng)的可靠性與可行性。它不僅適用于處理隨機(jī)型問題，如存儲(chǔ)系統(tǒng)、排隊(duì)系統(tǒng)、質(zhì)量檢驗(yàn)問題、社會(huì)救急系統(tǒng)問題、生態(tài)競爭問題和傳染病蔓延問題等；也可處理確定型問題，如計(jì)算多重積分、解積分方程及微分方程、解整數(shù)規(guī)劃（特別是非線形整數(shù)規(guī)劃）等。

蒙式仿真解決問題的基本思想是：首先建立與描述該問題相似的概率模型，然后對(duì)模型進(jìn)行隨機(jī)模擬或統(tǒng)計(jì)抽樣，在利用所得到的結(jié)果求出特征的統(tǒng)計(jì)估計(jì)值作為原問題的近似解，并對(duì)解的精度做出某些估計(jì)。蒙式仿真方法的主要理論依據(jù)是大數(shù)定理，其主要手段為隨機(jī)變量的抽樣分析。

本系統(tǒng)運(yùn)用了蒙式仿真的基本思想，也就是說按照一定的數(shù)學(xué)分布用多次模擬取隨機(jī)數(shù)的辦法去估計(jì)實(shí)際的值，模擬的次數(shù)越多則越貼合實(shí)際。由統(tǒng)計(jì)結(jié)果可以很容易地獲得項(xiàng)目進(jìn)度和成本的區(qū)間分布（進(jìn)度包括了工期和等待資源的時(shí)間，成本包括了直接成本和間接成本），從而知道項(xiàng)目進(jìn)度和成本大于某個(gè)閾值的概率是多少，也就是發(fā)生風(fēng)險(xiǎn)的概率是多少。如進(jìn)度風(fēng)險(xiǎn)圖4，成本風(fēng)險(xiǎn)圖5，進(jìn)度成本聯(lián)合風(fēng)險(xiǎn)圖6。

進(jìn)度風(fēng)險(xiǎn)的統(tǒng)計(jì)思路：假設(shè)仿真次數(shù)為N，N次仿真結(jié)果中最大工期為D_max，最小工期為D_min。則依次取基準(zhǔn)點(diǎn)Sn=（D_max-Dmin）/lO*n+D_min，即將區(qū)間十等分。后統(tǒng)計(jì)工期大于基準(zhǔn)點(diǎn)S_n的結(jié)果數(shù)量Nn則進(jìn)度風(fēng)險(xiǎn)概率P_n=N_n/N。（n=l，2，3…10）

成本風(fēng)險(xiǎn)的統(tǒng)計(jì)思路：同理，假設(shè)仿真次數(shù)為N，N次仿真結(jié)果中最大成本為C_max，最小成本為C_min。則依次取基準(zhǔn)點(diǎn)S_n=（C_max-C_min）/lO*n+C_min，即將區(qū)間十等分。后統(tǒng)計(jì)成本大于基準(zhǔn)點(diǎn)S_n的結(jié)果數(shù)量Nn則成本風(fēng)險(xiǎn)概率P_n=N_n/N。（n=l，2，3…10）

進(jìn)度成本聯(lián)合風(fēng)險(xiǎn)是將進(jìn)度風(fēng)險(xiǎn)和成本風(fēng)險(xiǎn)兩個(gè)二維圖統(tǒng)計(jì)結(jié)果結(jié)合，進(jìn)而生成的三維散點(diǎn)圖統(tǒng)計(jì)結(jié)果。散點(diǎn)的坐標(biāo)可以表示為（S_x，S_y，P）。S_x對(duì)應(yīng)工期X軸上的某個(gè)點(diǎn)，S_y對(duì)應(yīng)成本Y軸上的某個(gè)點(diǎn)，P為風(fēng)險(xiǎn)概率。則散點(diǎn)所表示的意義是工期大于S_x，成本大于S_y的聯(lián)合風(fēng)險(xiǎn)概率為P。

4 結(jié)論

本文對(duì)項(xiàng)目潛在的風(fēng)險(xiǎn)進(jìn)行評(píng)估，讓項(xiàng)目的管理者對(duì)項(xiàng)目有一個(gè)長遠(yuǎn)的認(rèn)識(shí)，防范風(fēng)險(xiǎn)于未然。本文應(yīng)用資源多約束下項(xiàng)目進(jìn)度調(diào)度（resource-constrained project scheduling problem，RCPSP）問題模型，對(duì)進(jìn)度風(fēng)險(xiǎn)評(píng)估系統(tǒng)進(jìn)行了需求分析和模塊劃分，設(shè)計(jì)了系統(tǒng)的框架層次、數(shù)據(jù)庫、資源多約束下的蒙式仿真算法，給出了依據(jù)仿真結(jié)果計(jì)算進(jìn)度風(fēng)險(xiǎn)和成本風(fēng)險(xiǎn)的統(tǒng)計(jì)思路。