RESOLVE: An algorithm for the Minimum Dummy Task Problem

Scheduling graphs are used by algorithms such as PERT/CPM in order to determine an optimal schedule for a given project. It is well-known that dummy tasks (requiring zero processing time) must sometimes be incorporated into a scheduling graph.

The main tool in this paper is a new algorithm, RESOLVE, which creates a scheduling graph, typically with fewer dummy tasks than are produced by Richards’ algorithm (1967). A theoretical framework for scheduling graphs is systematically developed through several theorems, culminating in a demonstration of the validity of RESOLVE. A worked example illustrating the application of RESOLVE concludes the paper.