Finding the Shortest Non-Delay Schedule for a Resource-Constrained Project

Non-delay schedules lack non-essential idle time intervals. Many heuristics for solving the resource-constrained project scheduling problem yield non-delay schedules. This paper presents a technique for finding the shortest non-delay schedule, which should be as good as the heuristics for this purpose. The authors combine branch-and-bound and dynamic programming approaches to yield a surprisingly simple algorithm. (The simplicity is reflected in the number of calculations and memory required.) Due to its simplicity, a project manager should be able to trace the algorithm’s stages and results without difficulty. This simplicity is a result of: (1) the number of stages equals the number of activities; (2) each stage uses only information from the previous stage, and the number of different schedules is typically limited; and (3) the proposed method becomes simpler the more it is constrained. A detailed example illustrates the technique, which is validated by comparisons to models from the literature.