Groupe d’études et de recherche en analyse des décisions

G-90-47

PERT and Crashing Revisited: Mathematical Generalizations

et

We consider a generalization of PERT where task durations are variable and the cost of each task is a convex function of its duration. Moreover, each precedence constraint between tasks can be violated with a cost that is a convex function of the duration of the forced task overlaps. Computing the optimal schedule and the cost of the project, in function of a given completion deadline, amounts to minimizing a non-linear function with one linear constraint for each task. This becomes computationally costly when the number of tasks involved exceeds the order of a thousand. This paper presents a reformulation as a flow problem with non-linear costs, allowing minicomputers to handle the computations for projects with several thousand tasks.

, 18 pages