IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v7y2003i1d10.1023_a1021964105322.html
   My bibliography  Save this article

Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models

Author

Listed:
  • Eugene Shragowitz

    (University of Minnesota)

  • Habib Youssef

    (King Fahd University of Petroleum and Minerals)

  • Bing Lu

    (University of Minnesota)

Abstract

Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on noncritical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on non-critical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.

Suggested Citation

  • Eugene Shragowitz & Habib Youssef & Bing Lu, 2003. "Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models," Journal of Combinatorial Optimization, Springer, vol. 7(1), pages 5-22, March.
    • Handle: RePEc:spr:jcomop:v:7:y:2003:i:1:d:10.1023_a:1021964105322
    DOI: 10.1023/A:1021964105322
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1021964105322
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1021964105322?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    2. Chen, Yen-Liang & Rinks, Dan & Tang, Kwei, 1997. "Critical path in an activity network with time constraints," European Journal of Operational Research, Elsevier, vol. 100(1), pages 122-133, July.
    3. Kamburowski, J., 1997. "New validations of PERT times," Omega, Elsevier, vol. 25(3), pages 323-328, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    2. Wendi Tian & Erik Demeulemeester, 2014. "Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment," Annals of Operations Research, Springer, vol. 213(1), pages 271-291, February.
    3. Byung-Cheon Choi & Changmuk Kang, 2019. "A linear time–cost tradeoff problem with multiple milestones under a comb graph," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 341-361, August.
    4. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    5. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    6. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    7. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    8. Park, Jongyoon & Han, Jinil & Lee, Kyungsik, 2024. "Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem," European Journal of Operational Research, Elsevier, vol. 317(1), pages 43-59.
    9. Mattfeld, D. C. & Kopfer, H., 2003. "Terminal operations management in vehicle transshipment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(5), pages 435-452, June.
    10. M. Vanhoucke, 2006. "A scatter search procedure for maximizing the net present value of a project under renewable resource constraints," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 06/417, Ghent University, Faculty of Economics and Business Administration.
    11. Ip, W. H. & Yung, K. L. & Wang, Dingwei, 2004. "A branch and bound algorithm for sub-contractor selection in agile manufacturing environment," International Journal of Production Economics, Elsevier, vol. 87(2), pages 195-205, January.
    12. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    13. Pérez, José García & Martín, María del Mar López & García, Catalina García & Sánchez Granero, Miguel Ángel, 2016. "Project management under uncertainty beyond beta: The generalized bicubic distribution," Operations Research Perspectives, Elsevier, vol. 3(C), pages 67-76.
    14. Yamashita, Denise Sato & Armentano, Vinicius Amaral & Laguna, Manuel, 2006. "Scatter search for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 169(2), pages 623-637, March.
    15. Moukrim, Aziz & Quilliot, Alain & Toussaint, Hélène, 2015. "An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration," European Journal of Operational Research, Elsevier, vol. 244(2), pages 360-368.
    16. Hongbo Li & Zhe Xu & Wenchao Wei, 2018. "Bi-Objective Scheduling Optimization for Discrete Time/Cost Trade-Off in Projects," Sustainability, MDPI, vol. 10(8), pages 1-15, August.
    17. Dorndorf, Ulrich & Drexl, Andreas & Nikulin, Yury & Pesch, Erwin, 2005. "Flight gate scheduling: State-of-the-art and recent developments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 584, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Philippe Lacomme & Aziz Moukrim & Alain Quilliot & Marina Vinot, 2019. "Integration of routing into a resource-constrained project scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 421-464, December.
    19. Cédric Verbeeck & Vincent Peteghem & Mario Vanhoucke & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "A metaheuristic solution approach for the time-constrained project scheduling problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 353-371, March.
    20. F. Perez & T. Gomez, 2016. "Multiobjective project portfolio selection with fuzzy constraints," Annals of Operations Research, Springer, vol. 245(1), pages 7-29, October.

    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:spr:jcomop:v:7:y:2003:i:1:d:10.1023_a:1021964105322. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.