A Label-Correcting Tracing Algorithm for the Approximation of the Probability Distribution Function of the Project Completion Time

在隨機性專案中運用標籤修訂追蹤演算法求取專案完成時間近似的機率分配函數

姚銘忠(Ming-Jong Yao) ； 褚文明(Weng-Ming Chu) ； 曾宗瑤(Tsueng-Yao Tseng)

《工業工程學刊》 24卷2期 (2007/03) Pp. 153-165

https://doi.org/10.29977/JCIIE.200703.0006

摘要

專案經理人多數希望有效地估算專案完成時間的機率分配函數，以便充分掌握隨機性專案中的不確定性。由於大型專案計算的複雜度，在允許專案作業可採通用性的機率分配函數時，專案經理人必須運用「離散式計算技術」解決本問題。本研究發現在運用文獻中的離散式計算技術，求算隨機性專案完成時間的機率分配函數時，存在兩個問題：第一，文獻中既未提供明確的資料結構也沒有系統化的架構，足以將其轉為計算機程式；第二，因為文獻中的離散式計算技術，皆假設隨機性專案網路中的各條子路徑彼此獨立，而造成明顯的誤差。因此本研究提出一個標籤修訂追蹤演算法，以改善上述的兩個缺點。為驗證標籤修訂追蹤演算法的計算效能，我們隨機產生20組100個節點（約有170至250個作業）的專案網路，運用20, 000個樣本的蒙地卡羅模擬所得的機率分配函數作為比較的基準，並與其他文獻中的解法所得的結果進行比較。經由數據實驗顯示，我們提出的標籤修訂追蹤演算法，不管在計算的時間及求解的品質均為較優。

關鍵字

隨機性專案 ； 專案完成時間 ； 機率分配函數 ； 近似解

並列摘要

When facing projects with uncertain factors, most of the project managers are interested to secure the pdf of the completion time of the project so as to have full insights into its randomness. For large-size SAN with general types of pdf for the duration of activities, the project managers must turn to the techniques of discretization since the other approaches in the literature become too demanding in computational loading. In this study, we find that there are two problems when applying the techniques of discretization to obtain an approximated probability density function (pdf) of the project completion time in stochastic activity networks. Namely, first, there exists neither exact data structure nor systematic scheme for the computer programming when applying the techniques of discretization; and second, error may arise from assuming independency between sub-paths in the activity network. Therefore, we are motivated to propose a Label-Correcting Tracing Algorithm (LCTA) to improve the techniques of discretization. To evaluate the performance of the proposed LCTA, we randomly generate 20 sets of 100-node instances in our numerical experiments. Using the pdf's resultant from Monte Carlo simulation using 20, 000 samples as the benchmark, we compared the pdf's obtained from the PERT model, Dodin's [10] algorithm and the proposed LCTA. Based on our experimental results, we conclude that the proposed LCTA significantly outperforms the others in both the run time and the precision aspects.

並列關鍵字

stochastic activity networks ； project completion time ； probability distribution function ； approximation

參考文獻

Adlakha, V. G.(1989).A classified bibliography of research on stochastic PERT networks: 1966-1987.INFOR.27,272-296.

Agrawal, M.K.,S.E. Elmaghraby(2001).On computing the distribution function of the sum of independent random variables.Computers and Operations Research.28,473-483.

Bellman, R.(1958).On a routing problem.Quarterly of Applied Mathematics.16,88-90.

Bertsekas, D.P.(1993).A simple and fast label correcting algorithm for shortest paths.Networks.23,703-709.

Birge, J.R.,F. Louveaux(1997).Introduction to Stochastic Programming.New York:Springer Verlag.