IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v32y1984i4p859-877.html
   My bibliography  Save this article

Determining the K Most Critical Paths in PERT Networks

Author

Listed:
  • Bajis Dodin

    (University of Wisconsin, Milwaukee, Wisconsin)

Abstract

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.

Suggested Citation

  • Bajis Dodin, 1984. "Determining the K Most Critical Paths in PERT Networks," Operations Research, INFORMS, vol. 32(4), pages 859-877, August.
  • Handle: RePEc:inm:oropre:v:32:y:1984:i:4:p:859-877
    DOI: 10.1287/opre.32.4.859
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.32.4.859
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.32.4.859?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhichao Zheng & Karthik Natarajan & Chung-Piaw Teo, 2016. "Least Squares Approximation to the Distribution of Project Completion Times with Gaussian Uncertainty," Operations Research, INFORMS, vol. 64(6), pages 1406-1421, December.
    2. Stephen P. Boyd & Seung-Jean Kim & Dinesh D. Patil & Mark A. Horowitz, 2005. "Digital Circuit Optimization via Geometric Programming," Operations Research, INFORMS, vol. 53(6), pages 899-932, December.
    3. Dediu Magdalena & Dobrea Alina, "undated". "On Calculating Activity Slack In Stochastic Project Networks," Description: Managerial Challenges of the Contemporary Society 10, Faculty of Economics and Business Administration, Babes-Bolyai University.
    4. Bregman, Robert L., 2009. "A heuristic procedure for solving the dynamic probabilistic project expediting problem," European Journal of Operational Research, Elsevier, vol. 192(1), pages 125-137, January.
    5. Gary Mitchell, 2010. "On Calculating Activity Slack in Stochastic Project Networks," American Journal of Economics and Business Administration, Science Publications, vol. 2(1), pages 78-85, March.
    6. Rabbani, M. & Fatemi Ghomi, S.M.T. & Jolai, F. & Lahiji, N.S., 2007. "A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept," European Journal of Operational Research, Elsevier, vol. 176(2), pages 794-808, January.
    7. Li, Haitao & Womer, Norman K., 2015. "Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 246(1), pages 20-33.
    8. Badinelli, Ralph D., 1996. "Approximating probability density functions and their convolutions using orthogonal polynomials," European Journal of Operational Research, Elsevier, vol. 95(1), pages 211-230, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:32:y:1984:i:4:p:859-877. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.