TY - JOUR

T1 - A new approximation algorithm for obtaining the probability distribution function for project completion time

AU - Yao, Ming-Jong

AU - Chu, Weng Ming

PY - 2007/7/1

Y1 - 2007/7/1

N2 - This paper focuses on the application of the techniques of discretization to obtain an approximated probability density function (pdf) for the completion time of large-size projects, in which we allow any type of pdf for the duration of activities. In this study, we improve the techniques of discretization in the following two ways: first, we propose to replace the max operation with an approximation procedure to save significant computational loading; and second, to reduce the error from assuming independence between paths using a simple heuristic rule. To evaluate the performance of our proposed algorithm, we randomly generated 20 sets of 100-node instances in our numerical experiments. Taking the results from a Monte Carlo simulation using 20,000 samples as a benchmark, we demonstrate that the proposed algorithm significantly outperforms the PERT model and Dodin's [B.M. Dodin, Approximating the distribution function in stochastic networks, Comput. Oper. Res. 12 (3) (1985) 251-264] algorithm in both the running time and the precision aspects.

AB - This paper focuses on the application of the techniques of discretization to obtain an approximated probability density function (pdf) for the completion time of large-size projects, in which we allow any type of pdf for the duration of activities. In this study, we improve the techniques of discretization in the following two ways: first, we propose to replace the max operation with an approximation procedure to save significant computational loading; and second, to reduce the error from assuming independence between paths using a simple heuristic rule. To evaluate the performance of our proposed algorithm, we randomly generated 20 sets of 100-node instances in our numerical experiments. Taking the results from a Monte Carlo simulation using 20,000 samples as a benchmark, we demonstrate that the proposed algorithm significantly outperforms the PERT model and Dodin's [B.M. Dodin, Approximating the distribution function in stochastic networks, Comput. Oper. Res. 12 (3) (1985) 251-264] algorithm in both the running time and the precision aspects.

KW - Approximation

KW - Completion time

KW - Discretization

KW - Probability distribution function

KW - Stochastic activity networks

UR - http://www.scopus.com/inward/record.url?scp=34249865056&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2007.01.036

DO - 10.1016/j.camwa.2007.01.036

M3 - Article

AN - SCOPUS:34249865056

VL - 54

SP - 282

EP - 295

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 2

ER -