Abstract
Due to the practical importance of stochastic project networks (PERT-networks), many methods have been developed over the past decades in order to obtain information about the random project completion time. Of particular interest are methods that provide (lower and upper) bounds for its distribution, since these aim at balancing efficiency of calculation with accuracy of the obtained information.
We provide a thorough computational evaluation of the most promising of these bounding algorithms with the aim to test their suitability for practical applications both in terms of efficiency and quality. To this end, we have implemented these algorithms and compare their behavior on a basis of nearly 2000 instances with up to 1200 activities of different test-sets. These implementations are based on a suitable numerical representation of distributions which is the basis for excellent computational results. Particularly a distribution-free heuristic based on the Central Limit Theorem provides an excellent tool to evaluate stochastic project networks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V.G. Adlakha and V.G. Kulkarni, A classified bibliography of research on stochastic PERT networks: 1966-1987, INFOR 27 (1989) 272–296.
K.P. Anklesaria and Z. Drezner, A multivariate approach to estimating the completion time for PERT networks, Journal of the Operational Research Society 40 (1986) 811–815.
W.W. Bein, J. Kamburowski and M.F.M. Stallmann, Optimal reduction of two-terminal directed acyclic graphs, SIAM Journal on Computing 21 (1992) 1112–1129.
C.G. Bigelow, Bibliography on project planning and control by network analysis, Operations Research 10 (1962) 728–731.
E. Demeulemeester, B. Dodin and W. Herroelen, A random activity network generator, Operations Research 41 (1993) 972–980.
B. Dodin, Determining the K most critical paths in PERT networks, Operations Research 32 (1984) 859–877.
B. Dodin, Bounding the project completion time distribution in PERT networks, Operations Research 33 (1985) 862–881.
J.D. Esaray, F. Proschan and D.W. Walkup, Association of random variables, with applications, Annals of Mathematical Statistics 38 (1967) 1466–1474.
D. Golenko, Statistische Methoden der Netzplantechnik (Teubner Verlagsgesellschaft, 1972).
J.N. Hagstrom, Computational complexity of PERT problems, Networks 18 (1988) 139–147.
G.B. Kleindorfer, Bounding distributions for a stochastic acyclic network, Operations Research 19 (1971) 1586–1601.
R. Kolisch and A. Sprecher, PSPLIB-a project scheduling problem library, European Journal of Operational Research 96 (1996) 205–216.
S. Lerda-Olberg, Bibliography on network-based project planning and control techniques, Operations Research 14 (1966) 925–931.
J.J. Martin, Distribution of the time through a directed acyclic network, Operations Research 13 (1965) 46–66.
I. Meilijson and A. Nadas, Convex majorization with an application to the length of critical paths, Journal of Applied Probability 16 (1979) 671–677.
R.H. Möhring and R. Müller, A combinatorial approach to bound the distribution function of the makespan in stochastic project networks, Technical Report 610/1998, Technical University of Berlin, Department of Mathematics, Germany (1998).
P. Robillard and M. Trahan, Expected completion time in PERT networks, Operations Research 24 (1976) 177–182.
D. Sculli and Y.W. Shum, An approximate solution to the PERT problem, Computers and Mathematics with Applications 21 (1991) 1–7.
M. Shaked and J.G. Shanthikumar, Stochastic Orders and their Applications (Academic Press, 1994).
A.W. Shogan, Bounding distributions for a stochastic PERT network, Networks 7 (1977) 359–381.
H. Soroush, Risk taking in stochastic PERT networks, European Journal of Operational Research 67 (1993) 221–241.
H.G. Spelde, Stochastische Netzpläne und ihre Anwendung im Baubetrieb, Ph.D. thesis, Rheinisch-Westfälische Technische Hochschule Aachen (1976).
J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series-parallel digraphs, SIAM Journal on Computing 11 (1982) 298–314.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ludwig, A., Möhring, R.H. & Stork, F. A Computational Study on Bounding the Makespan Distribution in Stochastic Project Networks. Annals of Operations Research 102, 49–64 (2001). https://doi.org/10.1023/A:1010945830113
Issue Date:
DOI: https://doi.org/10.1023/A:1010945830113