A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem

• Published in: Management science 1992-12, Vol.38 (12), p.1803-1818
• Main Authors: Demeulemeester, Erik, Herroelen, Willy
• Format: Article
• Language: English
• Subjects: Algorithms; applications; Applied sciences; branch-and-bound; Critical path; Economic resources; Exact sciences and technology; graphs; Heuristics; Mathematical models; Mathematical procedures; networks; networks/graphs; Operational research and scientific management; Operational research. Management science; Optimal solutions; Personal computers; PERT; programming; Project evaluation; Project management; Pruning; resource constraints; Resources conflict; Scheduling; Scheduling, sequencing; Standard deviation; Studies; Theory
• ISSN: 0025-1909; 1526-5501
• DOI: 10.1287/mnsc.38.12.1803

In this paper a branch-and-bound procedure is described for scheduling the activities of a project of the PERT/CPM variety subject to precedence and resource constraints where the objective is to minimize project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. Precedence and resource-based bounds described in the paper are combined with new dominance pruning rules to rapidly fathom major portions of the solution tree. The procedure is programmed in the C language for use on both a mainframe and a personal computer. The procedure has been validated using a standard set of test problems with between 7 and 50 activities requiring up to three resource types each. Computational experience on a personal computer indicates that the procedure is 11.6 times faster than the most rapid solution procedure reported in the literature while requiring less computer storage. Moreover, problems requiring large amounts of computer time using existing approaches for solving this problem type are rapidly solved with our procedure using the dominance rules described, resulting in a significant reduction in the variability in solution times as well.