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

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 non-critical 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 noncritical 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.