Determining the K Most Critical Paths in PERT Networks

Dodin, Bajis
July 1984
Operations Research;Jul/Aug84, Vol. 32 Issue 4, p859
Academic Journal
A fundamental problem in PERT networks is to identify a project's critical paths and its critical activities. In this paper we define the criticality index of a path as the probability that the duration of the path is greater than or equal to the duration of every other path in the network and define the criticality index of an activity as the sum of the criticality indices of the paths containing that activity. The most critical path or K most critical paths in a PERT network could be found by enumerating all the paths and calculating the corresponding criticality indices, both of which are burdensome tasks. This paper uses stochastic dominance to develop a procedure to identify the K most critical paths without using this path enumeration. The procedure has been applied to various sized PERT networks generated at random, and the results are found to be very close to those obtained by extensive Monte Carlo sampling.


Related Articles

  • CONDITIONAL MONTE CARLO: A SIMULATION TECHNIQUE FOR STOCHASTIC NETWORK ANALYSIS. Burt Jr., John M.; Garman, Mark B. // Management Science;Nov71, Vol. 18 Issue 3, p207 

    This paper is concerned with a simulation procedure for estimating the distribution functions of the time to complete stochastic networks. The procedure, called conditional Monte Carlo, is shown to be substantially more efficient (in terms of the computational effort required) than traditional...

  • APPROXIMATING THE CRITICALITY INDICES OF THE ACTIVITIES IN PERT NETWORKS. Dodin, Bajis M.; Elmaghraby, Salah E. // Management Science;Feb1985, Vol. 31 Issue 2, p207 

    A stochastic PERT network is a directed acyclic network in which the arc lengths are independent random variables with known distributions. A fundamental problem in PERT networks is to identify the activities which are critical to the achievement of the project objectives. In an activity network...

  • A STATISTICAL THEORY FOR PERT CRITICAL PATH ANALYSIS. Hartley, H. O.; Wortham, A. W. // Management Science;Jun66, Vol. 12 Issue 10, pB-469 

    PERT and Critical Path techniques are enjoying exceptionally broad application in industrial and military activities. These techniques and their application have without doubt contributed significantly to better planning, control, and general organization of many programs. Although some...

  • TIME-COST OPTIMIZATION MODEL FOB DETERMINISTIC NETWORK PROJECTS. Ben-Yair, Avner; Laslo, Zohar; Greenberg, Doron; Golenko-Ginzburg, Dimitri // Journal of Applied Quantitative Methods;2008, Vol. 3 Issue 4, p339 

    A deterministic PERT activity-on-arc network G(N, A) with logical operation "AND" at the event's receiver and "MUST FOLLOW" at the event's emitter, is considered. Each activity (i, j) ∊ A entering the model can be operated within several deterministic durations tij depending on the...

  • A NOTE ON PERT TIMES. Sasieni, M. W. // Management Science;Dec1986, Vol. 32 Issue 12, p1652 

    The article discusses a verification of the PERT formula, which is used for the estimation of the mean task time in program evaluation and review techniques. The author comments on the assumption that the Pert Time equation is derived from the beta distribution in probability theory. It is...

  • Ä°ÅŸ SÃœREÇLERÄ°NÄ°N MODELLENMESÄ°NDE GERT ÅŸEBEKELERÄ°NÄ°N KULLANIMI. Aytulun, S. Kerem; Ermis, Murat // Journal of Aeronautics & Space Technologies / Havacilik ve Uzay ;2010, Vol. 4 Issue 3, p19 

    Recent years, Firms have to use various and complex business processes for providing knowledge needs that is becoming increased. With understanding impact of the business processes on performance and profitableness of the firms, many academicians and managers need to get closer these business...

  • DISTRIBUTION OF THE TIME THROUGH A DIRECTED, ACYCLIC NETWORK. Martin, J. J. // Operations Research;Jan/Feb65, Vol. 13 Issue 1, p46 

    Let there be associated with each arc of a directed, acyclic network a random variable, conveniently referred to as the arc passage time. It is assumed that the arc passage times are independent and have a finite range. A method is presented for the efficient computation of the density function...

  • BIAS IN PERT PROJECT COMPLETION TIME CALCULATIONS FOR A REAL NETWORK. Klingel Jr., A.R. // Management Science;Dec1966, Vol. 13 Issue 4, pB-194 

    Among network techniques recently widely employed in program management, Pert is addressed to the problem of assessing the manager's chances of completing a project on time. Theory and monte carlo simulation have shown that the Pert method yields results which are biased high, and this paper...

  • THE USE OF THE COMPOUND POISSON IN PERT. Parks, William H.; Ramsing, Kenneth D. // Management Science;Apr1969, Vol. 15 Issue 8, pB-397 

    The use of the normal or Beta distributions has become well established for PERT applications. The authors question whether the use of these standardized distributions yields the best answers in some canes and submits an alternative method of computing the critical path using a compound poisson...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics