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

Erik Demeulemeester and Willy Herroelen
Additional contact information
Erik Demeulemeester: Department of Applied Economic Sciences, Katholieke Universiteit Leuven, Dekenstraat 2, B-3000 Leuven, Belgium
Willy Herroelen: Department of Applied Economic Sciences, Katholieke Universiteit Leuven, Dekenstraat 2, B-3000 Leuven, Belgium

Management Science, 1992, vol. 38, issue 12, 1803-1818

Abstract: 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.

Keywords: project management; resource constraints; programming; branch-and-bound; networks/graphs; applications (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (114)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.38.12.1803 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:38:y:1992:i:12:p:1803-1818

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().