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

Ming-Jong Yao*, Weng Ming Chu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)282-295
Number of pages14
JournalComputers and Mathematics with Applications
Volume54
Issue number2
DOIs
StatePublished - 1 Jul 2007

Keywords

  • Approximation
  • Completion time
  • Discretization
  • Probability distribution function
  • Stochastic activity networks

Fingerprint Dive into the research topics of 'A new approximation algorithm for obtaining the probability distribution function for project completion time'. Together they form a unique fingerprint.

Cite this