資源多約束進度網絡的風險評估

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

摘要：在項目管理中由于項目龐大、持續周期長、影響因素繁多，不可避免地會面對潛在的風險。本文對項目潛在的風險進行評估，讓項目的管理者對項目有一個長遠的認識，防范風險于未然。本文應用資源多約束下項目進度調度（resource-constrained project scheduling problem，RCPSP）問題模型，對進度風險評估系統進行了需求分析和模塊劃分，設計了系統的框架層次、數據庫、資源多約束下的蒙式仿真算法，給出了依據仿真結果計算進度風險和成本風險的統計思路。

關鍵詞：進度風險評估；蒙式仿真；成本風險；資源多約束

中圖分類號：TP391. 41

文獻標識碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.008

0 引言

項目管理是通過項目經理和項目組織的努力，運用系統理論和方法對項目及其資源進行計劃、組織、協調、控制，旨在實現項目特定目標的管理方法體系。項目管理的對象是項目，即一系列的臨時任務，它的目的是通過運用科學的項目管理技術，更好地實現項目目標。項目管理的職能與其它管理的職能是完全一致的，即是對組織的資源進行計劃、組織、指揮、控制。資源是指項目所在的組織中可得到的、為項目所需要的那些資源，包括人員、資金、技術、設備等，在項目的管理中，時間是一種特殊的資源。項目管理的任務是對項目及其資源的計劃、組織、協調、控制。

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

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

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

1 系統需求分析與設計

本文在功能方面，針對管理者的日常需求，將資源多約束下進度風險評估系統功能分為：項目管理，資源管理，項目網絡圖（任務屬性設置），項目仿真，項目仿真版本管理等項功能。

項目管理：對項目的任務節點信息和節點之間的約束關系等進行記錄和管理，并可以對項目進行資源分配。

資源管理：對資源的屬性和數量等進行記錄和管理。

項目網絡圖：展示項目各個任務節點之間的約束關系，形成網絡圖。可以對每個非概要任務節點進行任務屬性的設置和資源需求的設置，為仿真進行準備。

項目仿真：對設置好任務節點屬性的項目進行帶資源約束的仿真或不帶資源約束的仿真。

項目仿真版本管理：管理所有項目仿真好的版本.可以選擇某個版本進行查看，也可以刪除某個版本。

因此，本系統包括項目管理模塊、項目網絡圖模塊、仿真版本和新仿真模塊、仿真結果模塊、資源管理模塊。

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

項目網絡圖模塊：展示項目的任務節點信息和它們的相互關系，以網絡圖的形式表示出來。用戶可以通過點擊某個具體節點設置它的屬性（統計學分布、期望、方差等）和需求資源的情況，為帶資源的仿真和不帶資源的仿真做進一步準備。

仿真版本和新仿真模塊：管理和顯示已經存在的仿真版本和新建一個版本開始仿真。用戶可以選擇一個已經存在的仿真版本進行查看或者刪除，也可以新建某個項目的一個版本，進行一定次數的帶資源的仿真或不帶資源的仿真。

仿真結果模塊：展示某個版本的仿真結果，以圖表的方式展現如關鍵路徑、平均工期、任務關鍵路徑概率、總工期區間分布、進度風險、成本風險、進度成本聯合風險等信息。用戶可以通過瀏覽這些圖表形式的仿真結果，直觀地了解系統對于項目的風險評估信息，方便地做出最有利的決策。

資源管理模塊：管理和顯示資源的相關信息，用戶可以創建、修改、刪除某個資源。也可以設置資源的相關屬性（名稱、數量、是非為消耗性資源等）。

2 大數據多約束進度風險評估算法

本算法的核心類似銀行家算法，運用到了拓撲排序和隊列的相關知識，其思路是：枚舉出所有可能的全拓撲資源分配序列（按優先級剔除部分），然后對其逐一進行模擬比較，算出最優分配序列。在分配資源和計算節點工期的過程中，按照銀行家算法的思想，節點在申請資源的時候直接申明所需的最大資源，而且項目盡量滿足節點的申明，除非超過擁有資源的最大數量。這樣使得至少有一個節點是出于就緒狀態的，避免死鎖。

具體步驟：

A.輸入項目基本信息和結構（輸入項目XML）。

B.輸入項目資源信息

C.輸入項目每個節點的統計學屬性、優先級關系和資源需求。

D.按照優先級計算項目節點的全拓撲排序資源分配序列。

E.按順序選擇一個資源分配序列進行模擬。

F.將所有人度為零的節點加入等待隊列。

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

度減一。

H.如果就緒隊列不為空，則計算節點工期，按最小工期的節點推進項目。否則說明沒有就緒節點，本資

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

I.計算在等待隊列的節點的等待資源時間。

J.計算完成節點的成本。

K.回收完成節點的資源，將其剔除就緒隊列。

L.如果所有節點都已經完成則本資源分配序列結束，計算總工期。否則返回F。

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

N.輸出任務等待的時間和等待的資源。

0.輸出項目總工期和總成本。

算法流程圖如圖2所示。

設Sequence_List為資源分配序列數組，Sequence為資源分配序列，Wait List為等待隊列，Ready_List為就緒隊列，Task_List為節點列表。算法的偽代碼可以表示為：

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（）

本系統的資源約束仿真算法還運用到了關鍵路徑算法，它為資源約束仿真算法的子過程。其算法步驟如下：

A. 拓撲排序，將所有人度為零的點壓人堆棧

B. 計算棧頂節點最早開始工期Ve并將其所有后繼節點人度

減一

C. 彈出堆棧。

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

E. 如果還有節點未完成則返回A

F. 逆拓撲排序，將所有出度為零的點壓人堆棧

G. 計算棧頂節點最遲開始工期Vl并將其所有前驅節點出度減

H 如果Vl=Ve，將節點標記為關鍵路徑上的節點。

I. 彈出堆棧。

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

K. 如果還有節點未完成則返回F

L 算法結束

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

3 系統仿真及驗證

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

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

本系統運用了蒙式仿真的基本思想，也就是說按照一定的數學分布用多次模擬取隨機數的辦法去估計實際的值，模擬的次數越多則越貼合實際。由統計結果可以很容易地獲得項目進度和成本的區間分布（進度包括了工期和等待資源的時間，成本包括了直接成本和間接成本），從而知道項目進度和成本大于某個閾值的概率是多少，也就是發生風險的概率是多少。如進度風險圖4，成本風險圖5，進度成本聯合風險圖6。

進度風險的統計思路：假設仿真次數為N，N次仿真結果中最大工期為D_max，最小工期為D_min。則依次取基準點Sn=（D_max-Dmin）/lO*n+D_min，即將區間十等分。后統計工期大于基準點S_n的結果數量Nn則進度風險概率P_n=N_n/N。（n=l，2，3…10）

成本風險的統計思路：同理，假設仿真次數為N，N次仿真結果中最大成本為C_max，最小成本為C_min。則依次取基準點S_n=（C_max-C_min）/lO*n+C_min，即將區間十等分。后統計成本大于基準點S_n的結果數量Nn則成本風險概率P_n=N_n/N。（n=l，2，3…10）

進度成本聯合風險是將進度風險和成本風險兩個二維圖統計結果結合，進而生成的三維散點圖統計結果。散點的坐標可以表示為（S_x，S_y，P）。S_x對應工期X軸上的某個點，S_y對應成本Y軸上的某個點，P為風險概率。則散點所表示的意義是工期大于S_x，成本大于S_y的聯合風險概率為P。

4 結論

本文對項目潛在的風險進行評估，讓項目的管理者對項目有一個長遠的認識，防范風險于未然。本文應用資源多約束下項目進度調度（resource-constrained project scheduling problem，RCPSP）問題模型，對進度風險評估系統進行了需求分析和模塊劃分，設計了系統的框架層次、數據庫、資源多約束下的蒙式仿真算法，給出了依據仿真結果計算進度風險和成本風險的統計思路。