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

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

10.29977/JCIIE.200703.0006

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

隨機性專案 ； 專案完成時間 ； 機率分配函數 ； 近似解 ； stochastic activity networks ； project completion time ； probability distribution function ； approximation

工業工程學刊

24卷2期（2007 / 03 / 01）

153 - 165

英文

專案經理人多數希望有效地估算專案完成時間的機率分配函數，以便充分掌握隨機性專案中的不確定性。由於大型專案計算的複雜度，在允許專案作業可採通用性的機率分配函數時，專案經理人必須運用「離散式計算技術」解決本問題。本研究發現在運用文獻中的離散式計算技術，求算隨機性專案完成時間的機率分配函數時，存在兩個問題：第一，文獻中既未提供明確的資料結構也沒有系統化的架構，足以將其轉為計算機程式；第二，因為文獻中的離散式計算技術，皆假設隨機性專案網路中的各條子路徑彼此獨立，而造成明顯的誤差。因此本研究提出一個標籤修訂追蹤演算法，以改善上述的兩個缺點。為驗證標籤修訂追蹤演算法的計算效能，我們隨機產生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.

1. Adlakha, V. G.(1989).A classified bibliography of research on stochastic PERT networks: 1966-1987.INFOR,27,272-296.
2. 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.
3. Bellman, R.(1958).On a routing problem.Quarterly of Applied Mathematics,16,88-90.
4. Bertsekas, D.P.(1993).A simple and fast label correcting algorithm for shortest paths.Networks,23,703-709.
5. Birge, J.R.,F. Louveaux(1997).Introduction to Stochastic Programming.New York:Springer Verlag.
6. Burt, J.M.,M.B. Garman(1971).Conditional Monte Carlo: A simulation technique for stochastic network analysis.Management Science,18,207-217.
7. Chatzoglou, P.,L. Macaulay(1996).A review of existing models for project planning and estimation and the need for a new approach.International Journal of Project Management,14,173-183.
8. Clark, C.E.(1961).The greatest of a finite set of random variables.Operations Research,9,146-162.
9. Coppendale, J.(1995).Manage risk in product and process development and avoid unpleasant surprises.Engineering Management Journal,5,35-38.
10. Dodin, B.M.(1985).Approximating the distribution function in stochastic networks.Computers and Operations Research,12,251-264.
11. Dodin, B.M.,M. Sirvanci(1990).Stochastic networks and the extreme value distribution.Computers and Operations Research,17,207-217.
12. Elmaghraby, S.E.,R. Slowinski,J. Weglarz(1989).Advances in Project Scheduling.Amsterdam:Elsevier.
13. Fisher, D.L.,D. Saisi,W.M. Goldstein(1985).Stochastic PERT networks: OP diagrams critical paths and the project completion time.Computers and Operations Research,12,471-482.
14. Gallo, G.,S. Pallottino(1988).Shortest path algorithms.Annals of Operations Research,7,3-79.
15. Glover, F.,D. Klingman,N. Philips(1986).A new polynomial bounded shortest path algorithm.Operations Research,33,65-73.
16. Hagstrom, J.N.(1990).Computing the probability distribution of project duration in a PERT network.Networks,20,231-244.
17. Hagstrom, J.N.(1988).Computational complexity of PERT problems.Networks,18,139-147.
18. Kolisch, R.,A. Sprecher(1996).PSPLIB-A project scheduling problem library.European Journal of Operational Research,96,205-216.
19. Kulkarni, V.G.,V.G. Adlakha(1986).Markov and Markov-Regenerative PERT networks.Operations Research,34,769-781.
20. Malcolm, D.G.,J.H. Roseboom,C.E. Clark,W. Fazar(1959).Application of a technique for research and development program evaluation.Operations Research,7,646-669.
21. Martin, J.J.(1965).Distribution of the time through a directed acyclic networks.Operations Research,13,46-66.
22. Mehrotra, K.,J. Chai,S. Pillutla(1996).A study of approximating the moments of the job completion time in PERT networks.Journal of Operations Management,14,277-289.
23. Pape, U.(1974).Implementation and efficiency of Moore-algorithms for the shortest route problem.Mathematical Programming,7,212-222.
24. Pontrandolfo, P(2000).Project duration in stochastic networks by the PERT-path technique.International Journal of Project Management,18,215-222.
25. Sculli, D.(1983).The completion time of PERT networks.Journal of the Operational Research Society,25,155-158.
26. Sigal, C.E.,A.A.B. Pritsker,J.J. Solberg(1979).The use of cutsets in Monte Carlo analysis of stochastic networks.Mathematics and Computers in Simulation,21,376-384.
27. Van Slyke, R.M.(1963).Monte Carlo methods and the PERT problem.Operations Research,11,839-861.

1. (2013).Evaluating the BOT project of sport facility: an application of fuzzy net present value method.工業工程學刊,30(4),220-229.