多約束條件下基于蒙特卡洛仿真的進度風(fēng)險評估方法

謝子哲，朱耀琴，盧于嘉

（南京理工大學(xué)江蘇南京210094）

?

多約束條件下基于蒙特卡洛仿真的進度風(fēng)險評估方法

謝子哲，朱耀琴，盧于嘉

（南京理工大學(xué)江蘇南京210094）

摘要：復(fù)雜項目的建設(shè)周期長、資源有限、不確定因素多，項目風(fēng)險評估對項目成功與否起關(guān)鍵作用，其中進度風(fēng)險評估是必不可少的一個環(huán)節(jié)。本文針對復(fù)雜項目中任務(wù)多邏輯關(guān)系，提出了基于蒙特卡洛仿真的進度推進算法；針對項目資源有限這個約束條件，提出了基于全拓撲排序的資源沖突解決策略，并給出了全拓撲排序的優(yōu)化方案。最后介紹了實現(xiàn)的進度風(fēng)險評估系統(tǒng)，并結(jié)合項目實例的2 000次仿真闡述了進度風(fēng)險的計算，驗證了算法及系統(tǒng)的可行性。該系統(tǒng)可幫助項目決策者識別關(guān)鍵任務(wù)和評估進度風(fēng)險。

關(guān)鍵詞：進度風(fēng)險評估；蒙特卡洛仿真；任務(wù)邏輯關(guān)系；全拓撲排序

對于復(fù)雜的項目工程，往往項目建設(shè)周期長，投資大，不確定因素多，資源有限。對項目工期的錯誤預(yù)估和項目間任務(wù)資源的競爭，往往導(dǎo)致項目工期的拖延，進而使項目失敗，正因為如此，進度管理在項目管理中有著舉足輕重的地位。而其中風(fēng)險管理又是必不可少的環(huán)節(jié)，項目進度的風(fēng)險評估環(huán)節(jié)對項目的成功與否起著至關(guān)重要的作用。

對風(fēng)險進行評估是建立在對項目進度預(yù)估的基礎(chǔ)上，通過預(yù)警機制來達到規(guī)避風(fēng)險的目的。而對項目進度的預(yù)估至今主要經(jīng)歷了3個階段的發(fā)展。

20世紀50年代之前人們通過甘特圖技術(shù)來規(guī)劃進度。20世紀50年代到20世紀90年代，以CPM/PERT為代表的傳統(tǒng)網(wǎng)絡(luò)計劃技術(shù)出現(xiàn)［1］，并獨占鰲頭。到了20世紀90年代末，人們開始將TOC（約束理論）應(yīng)用到項目管理領(lǐng)域，形成一種新興的基于關(guān)鍵鏈的網(wǎng)絡(luò)計劃技術(shù)［2］。

但是目前的進度預(yù)估方法往往忽略了任務(wù)間邏輯關(guān)系的復(fù)雜性，采用單一模式的圖模型進行處理，本文將在網(wǎng)絡(luò)計劃技術(shù)的基礎(chǔ)上，設(shè)計一種在多約束條件下的進度推進算法。

1　基于蒙特卡洛仿真的進度風(fēng)險評估

本文設(shè)計的進度風(fēng)險評估流程如圖1所示。

圖1　進度風(fēng)險評估流程圖

1）讀入項目任務(wù)結(jié)構(gòu)，包括任務(wù)之間的邏輯關(guān)系（在進度管理中，前驅(qū)節(jié)點和后繼節(jié)點共有4種邏輯關(guān)系，分別是Fjnjsh-to-Start，F(xiàn)jnjsh-to-Fjnjsh，Start-to-Start和Start-to-Fjnjsh）和任務(wù)名稱。

2）設(shè)置每個任務(wù)工時服從的分布，這里可以認為任務(wù)的工時為某個具體的值或者服從某一特定的分布。

3）設(shè)置仿真次數(shù)，開始蒙特卡洛仿真［3］。在每一次仿真過程中，都先根據(jù)步驟（2）中對任務(wù)的工時設(shè)置的分布進行隨機變量抽樣，抽樣算法可以參考［4-5］。抽樣完成后再根據(jù)任務(wù)的拓撲關(guān)系求出所有的優(yōu)先級序列，求全拓撲排序序列算法見3，最后對每一個序列，調(diào)用2中的進度推進仿真算法進行總工期的計算并保存最優(yōu)結(jié)果。

4）當仿真結(jié)束后，根據(jù)剛才記錄的仿真中間結(jié)果，可以統(tǒng)計出各種信息，包括任務(wù)平均工期直方圖、任務(wù)關(guān)鍵路徑概率、總工期區(qū)間統(tǒng)計和進度風(fēng)險統(tǒng)計圖等，見圖6和圖7，根據(jù)這些信息便能對項目的進度風(fēng)險進行評估。

2　進度推進仿真算法

在網(wǎng)絡(luò)計劃技術(shù)中，通常對圖的研究都僅限于FS型，而在實際的項目管理中，前驅(qū)任務(wù)和后繼任務(wù)之間的邏輯關(guān)系一共有4種：1）Fjnjsh-to-Start（FS），代表前驅(qū)節(jié)點必須先結(jié)束，后繼結(jié)點才能夠開始。2）Start-to-Start（SS），代表前驅(qū)節(jié)點必須先開始，后繼結(jié)點才能夠開始。3）Fjnjsh-to-Fjnjsh（FF），代表前驅(qū)節(jié)點必須先結(jié)束，后繼結(jié)點才能夠結(jié)束。4）Start-to- Fjnjsh （SF），代表前驅(qū)節(jié)點必須先開始，后繼結(jié)點才能夠結(jié)束。基于傳統(tǒng)CPM算法的啟發(fā)，本文設(shè)計了兼容這4種任務(wù)邏輯關(guān)系的進度推進仿真算法。

首先對算法中涉及到的類型進行定義，用一個五元組Task（djstrj，per，prog，expS，expE，accS，accE）來表示項目中的任務(wù)。

其中，djstrj屬性和per屬性屬于任務(wù)的固有屬性，djstrj屬性代表Task的分布類型，比如三角分布、正態(tài)分布和分布；per屬性代表的是任務(wù)的工時。而后面5個屬性是為了在仿真算法中記錄中間結(jié)果添加的屬性，其中prog屬性代表仿真過程中當前任務(wù)的進度，初始值為0，隨著時間的推進，prog不斷變大，當prog的值等于任務(wù)的工時per時，該任務(wù)完成（但還不一定結(jié)束，還需要參考accE屬性）；expS屬性代表的是任務(wù)開始期望數(shù)，屬性accS代表的是任務(wù)的當前開始期望數(shù)，也就是當accS的值等于expS值時，任務(wù)可以開始；同理定義expE為任務(wù)結(jié)束期望數(shù)，而accE代表任務(wù)的當前結(jié)束期望數(shù)，當任務(wù)的當前結(jié)束期望數(shù)達到expE后，任務(wù)才可以結(jié)束。

接著用一個三元組Ljnk（preTask，sucTask，type）來表示任務(wù)之間的邏輯關(guān)系，其中preTask屬性代表的是該關(guān)系連接的前驅(qū)Task，而sucTask屬性代表的是與之相連的后繼Task，屬性type則代表了該關(guān)系的邏輯類型。

算法流程：1）利用Ljnk對所有的Task進行初始化，具體流程如圖2所示。

圖2　初始化流程圖

圖3中對所有的Ljnk進行了遍歷，如果Ljnk是FS或者SS類型，因為前驅(qū)任務(wù)的開始或者結(jié)束才會導(dǎo)致后繼任務(wù)的開始，所以后繼任務(wù)的開始期望數(shù)需要增加。同理如果Ljnk的類型是FF或者SF型，那么需要增加后繼任務(wù)的結(jié)束期望數(shù)。

文中一共對Task定義了3種狀態(tài)，分別用3個集合加以表示，TR為初始任務(wù)的集合，包含的是還未開始的任務(wù)，初始為所有的任務(wù)集合。TP為進行中任務(wù)的集合，當任務(wù)的當前開始期望數(shù)達標后，認為任務(wù)可以開始，這時將任務(wù)從TR移動到TP中，代表任務(wù)開始。TF為已經(jīng)結(jié)束任務(wù)的集合，當任務(wù)可以結(jié)束時，將任務(wù)移動至該集合。

在算法中，每一次循環(huán)就相當于一次時間的推進，在循環(huán)中，算法會檢查和修改任務(wù)的狀態(tài)。其中，時間的推進用prog屬性來表示，通過從零增加prog的值到其工時，代表任務(wù)從開始到結(jié)束。而檢查任務(wù)是否能夠開始則通過判斷任務(wù)的當前開始期望數(shù)accS是否等于其開始期望數(shù)expS，檢查任務(wù)是否能夠結(jié)束則通過判斷任務(wù)的當前結(jié)束期望數(shù)accE是否等于其結(jié)束期望數(shù)expE。每當一個任務(wù)開始的時候，都需要對其后繼任務(wù)進行修改，如果它們之間的關(guān)系為SS型，則將后繼任務(wù)的accS屬性加1，如果它們之間的關(guān)系為SF型，則將后繼任務(wù)的accE屬性加1。同理每當一個任務(wù)結(jié)束的時候，需要對其后繼任務(wù)進行更新，如果它們之間的關(guān)系為FS型，則將后繼任務(wù)的accS屬性加1，如果它們之間的關(guān)系為FF型，則將后繼任務(wù)的accE屬性加1。

3　基于全拓撲排序的資源沖突解決策略

圖3　進度推進仿真算法

在考慮資源的情況下，因為關(guān)鍵任務(wù)并不一定在關(guān)鍵鏈上，所以任務(wù)執(zhí)行的邏輯順序不一定就是任務(wù)執(zhí)行的實際順序，關(guān)鍵任務(wù)工時的和也并非一定等于總工期。因此需要對2中的進度推進仿真算法進行改進。由于考慮資源的沖突，此時關(guān)鍵路徑不再是唯一制約進度的因素，非關(guān)鍵路徑上的任務(wù)也可以由于資源缺乏而拖延總工期。跟關(guān)鍵鏈法不同，本文的焦點是放在總工期的計算上，而上述算法也是拋棄了原來關(guān)鍵路徑的思想，以模擬的角度來考慮問題，以最小任務(wù)工時為單位，每次計算往前推進時間。但是，本法與關(guān)鍵鏈的思想并不矛盾，同樣可以往關(guān)鍵任務(wù)和非關(guān)鍵任務(wù)兩端加上緩沖時間更精確的為項目管理者提供進度規(guī)劃方面的建議，本文算法相當于為關(guān)鍵鏈提供了一個可行的拉動式進度計劃方案，關(guān)于如何設(shè)置緩沖區(qū)可以參考文獻［6］。

當調(diào)用進度推進仿真算法時可以發(fā)現(xiàn)，資源沖突的問題其實可以等價于任務(wù)優(yōu)先級的問題，即有多個任務(wù)并行時，先將資源分配給哪個任務(wù)，擁有資源的任務(wù)可以隨著時間的推進而推進，而缺少資源的任務(wù)雖然在任務(wù)進行集合TP中，但是卻不往前推進時間（即每次prog屬性不變）。因此問題的關(guān)鍵在于求出任務(wù)的優(yōu)先級，一般來說，在設(shè)置任務(wù)屬性的時候，也會一起設(shè)置任務(wù)的優(yōu)先級，而對于設(shè)置了相同優(yōu)先級的任務(wù)，可以通過枚舉的方式，進而運行進度推進仿真算法。具體步驟是：

1）求出任務(wù)網(wǎng)絡(luò)圖所有的拓撲排序序列，每一個序列就相當于一種潛在的任務(wù)優(yōu)先級序列，下面給出通過回溯來找出所有拓撲排序序列的算法，為了方便表示，用Indegree這個屬性儲存任務(wù)的入度，而且假設(shè)可以通過Suc這個屬性來獲取所有的后繼任務(wù)。

算法GetA11Prjorjty

輸入：所有Task的集合

輸出：Ta11所有可能的拓撲排序序列

V=｛｝//初始化為空

for each task Ttjn Ta11

jf Tt.Indegree == 0

for each task Tsucjn Tt.Suc

Tsuc.Indegree—

V+= +GetA11Prjorjty（Ta11-Tt）

Return V

2）對上述序列進行優(yōu)化。當任務(wù)數(shù)目較多且任務(wù)邏輯關(guān)系復(fù)雜時，全拓撲排序序列數(shù)會非常大，甚至達到百萬數(shù)量級，使得實際程序的運行效率低下。不過所幸實際中任務(wù)之間往往存在著各種約束，通過這些約束就能去除絕大部分的無用序列，從而使程序的效率得到保障。

這里給出兩種優(yōu)化方案：

①任務(wù)的完整性約束：在比較復(fù)雜的項目結(jié)構(gòu)中存在子項目的概念，而在計算中，一般是通過展開子項目得到全圖來進行計算，而正因為展開了子項目而導(dǎo)致圖非常大，拓撲排序序列眾多。其實在實際項目中，某些項目的子項目是不可分割的，也就是說當前項目進行過程不可暫停，對于這種項目，無需將其展開進行排序，可將其視為一個整體，只有當資源全部滿足時，才可以開始，并且一旦開始就會一直到其所有子項目完成。

②資源的相關(guān)性約束：任務(wù)的優(yōu)先級是用來判別當資源沖突時，優(yōu)先選擇哪個任務(wù)。然而，如果兩個任務(wù)并不存在資源沖突（現(xiàn)實情況非常常見），那么我們是不需要判斷這兩個任務(wù)孰優(yōu)孰劣。因此不論是一維的資源或者是多維的資源，當使用GetA11Prjorjty算法檢查可能并行的資源并對它們進行全排列之前，可以先檢查這些任務(wù)是否有資源沖突，如果不存在資源沖突，那么可以跳過這些資源繼續(xù)下面的步驟。

3）最后對每一種優(yōu)先級序列，運行進度推進仿真算法，保存其中的最優(yōu)結(jié)果。

4　進度風(fēng)險評估與系統(tǒng)實現(xiàn)

在N次仿真過程中，記錄了N個工期，根據(jù)大數(shù)定理，當N足夠大時（一般取N為1 000到10 000次），便可以用這N個樣本值來代表實際值。項目風(fēng)險同樣通過這N個樣本值來進行計算，本文通過總工期區(qū)間統(tǒng)計圖和進度風(fēng)險圖來對風(fēng)險進行評估。其中，總工期區(qū)間統(tǒng)計圖表示的是N個總工期樣本值的分布情況，等價于之前設(shè)置的每個任務(wù)工時服從分布之和，也就是它們的組合分布，而該分布的期望則代表了最可能出現(xiàn)的總工期。進度風(fēng)險圖表示的是在不同總工期約束下，項目完成的風(fēng)險（即失敗率）。對于在工期M下的進度風(fēng)險，計算公式為。也就是統(tǒng)計總工期小于等于M的個數(shù)，再用1減去其占總個數(shù)N的比例。

本文所有算法都在基于C#語言的.NET平臺上的風(fēng)險評估軟件中得到了實現(xiàn)。下面以一個具體的項目為例，進行評估流程說明。

首先讀入某工程任務(wù)的網(wǎng)絡(luò)圖（如圖4），由于每個任務(wù)都有子任務(wù)，因此圖4相當于概要任務(wù)圖，雙擊概要任務(wù)進入子任務(wù)圖后，點擊子任務(wù)可設(shè)置任務(wù)屬性（如圖5），這里將每個任務(wù)都設(shè)置成正態(tài)分布。

圖4　任務(wù)網(wǎng)絡(luò)拓撲圖

任務(wù)設(shè)置完成后設(shè)置仿真次數(shù)為2000次，進行蒙特卡洛仿真，仿真用時3分鐘，結(jié)束后查看仿真結(jié)果，圖6為總工期區(qū)間統(tǒng)計圖，可以發(fā)現(xiàn)其大致服從正態(tài)分布（正態(tài)分布的疊加性），而該正態(tài)分布的期望代表最可能出現(xiàn)的總工期；圖7是進度風(fēng)險圖，表示的是隨時間的增大，項目無法完成的概率，當給定總工期低于所有統(tǒng)計值中的最小值時，可以當作項目風(fēng)險為100%，即不可能完成，同理給定工期大于所有統(tǒng)計值中的最大值時，可以認為項目風(fēng)險為0，即一定能完成，從圖中可以看出，當總工期超過270天時，項目風(fēng)險為0，而當總工期低于170天時，項目風(fēng)險為100%。

圖5　任務(wù)屬性設(shè)置圖

圖6　總工期區(qū)間統(tǒng)計圖

圖7　進度風(fēng)險圖

通過以上結(jié)果分析，便能夠夠直觀的對項目的進度風(fēng)險進行判斷，掌握進度風(fēng)險隨總工期變化的曲線以及各關(guān)鍵任務(wù)信息。在項目開始前，項目決策者通過對關(guān)鍵任務(wù)進行調(diào)整迭代仿真過程，可以制定出更合理的項目進度方案。在項目進行中，項目決策者也能夠通過評估及時掌握項目進度走向，以便調(diào)整任務(wù)，規(guī)避進度風(fēng)險。

5　結(jié)束語

文中介紹了多約束條件下基于蒙特卡洛的進度評估方法，從實現(xiàn)的角度給出了常見3種分布變量的抽樣方法，以及設(shè)計了一種進度推進算法，解決了4種任務(wù)邏輯轉(zhuǎn)換的問題，然后給出了當資源沖突時的解決策略。并且在當前技術(shù)條件下，在.NET平臺上對系統(tǒng)進行了實現(xiàn)，證明了研究內(nèi)容的實際價值，支持在項目管理中對項目進行動態(tài)管理進而對整個項目流程進行優(yōu)化。最后在考慮資源沖突的條件下，研究如何進行合理的進度壓縮以及找出找出關(guān)鍵資源，為項目決策者提出更進一步的建議，是下一步研究的方向。

參考文獻：

［1］徐哲，王黎黎.基于關(guān)鍵鏈技術(shù)的項目進度管理研究綜述［J］.北京航空航天大學(xué)學(xué)報：社會科學(xué)版，2011（2）：54-59.

［2］趙道致，廖華，劉一騮.關(guān)鍵鏈法：一種新型的項目進度計劃方法［J］.天津理工大學(xué)學(xué)報，2005（2）：8-12.

［3］程錫禮，張延林，崔新生.蒙特卡洛仿真在工程項目進度管理中的應(yīng)用［J］.工業(yè)工程，2004（3）：51-55.

［4］徐鐘濟.蒙特卡羅方法［D］.上海：上海科學(xué)技術(shù)出版社，1985.

［5］楊自強，魏公毅.任意分布隨機變量抽樣的通用算法與程序［J］.數(shù)值計算與計算機應(yīng)用，2006（3）：191-200.

［6］劉贈英.基于關(guān)鍵鏈技術(shù)的項目進度管理研究［D］.西安：西安電子科技大學(xué)，2010.

Monte carlo slmulatlon based schedule rlsk analysls method under mutl-constralnts

XIE Zj-zhe，ZHU Yao-qjn，LU Yu-jja
（Nanjing University of Science and Technology，Nanjing 210094，China）

Abstract:Comp1ex projects have a 1ong constructjon perjod，1jmjted resources and many uncertajn factors. Project rjsk assessment js the key to success of projects，and schedu1e rjsk ana1ysjs js an jndjspensab1e part of jt. The paper comes up wjth the Monte Car1o sjmu1atjon based schedu1e forward a1gorjthm，ajmjng to so1ve the prob1em of mu1tjp1e 1ogjc re1atjonshjps of tasks. It a1so comes up wjth the overa11 topo1ogjca1 sort a1gorjthm，ajmjng to so1ve the prob1em of 1jmjted resources. At 1ast，the paper jntroduces the schedu1e rjsk ana1ysjs software and e1aborates on the ca1cu1atjon of schedu1e rjsk through 2000 sjmu1atjons of a samp1e project. The software can he1p project manager recognjze the crjtjca1 tasks and assess schedu1e rjsk.

Key words:schedu1e rjsk ana1ysjs；monte car1o sjmu1atjon；1ogjc re1atjonshjps of tasks；topo1ogjca1 sortjng

中圖分類號：TN957.52

文獻標識碼：A

文章編號：1674-6236（2016）07-0029-04

收稿日期：2015-05-13稿件編號：201505115

基金項目：南京理工大學(xué)畢業(yè)設(shè)計重點課題立項資助（29）

作者簡介：謝子哲（1992—），男，四川德陽人。研究方向：計算機仿真，數(shù)據(jù)決策。