New Benchmark Results for the Resource-Constrained Project Scheduling Problem
Erik L. Demeulemeester, Willy S. Herroelen
Management Science · 1997 · Volume 43 · Issue 11
Abstract
This paper reports on new insights derived from computational results obtained with an updated version of the branch-and-bound procedure previously developed by Demeulemeester and Herroelen (Demeulemeester, E., W. Herroelen. 1992. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Sci. 38 1803–1818.) for solving the resource-constrained project scheduling problem (RCPSP). The new code fully exploits the advantages of 32-bit programming provided by recent compilers running on platforms such as Windows NT ® and OS/2 ® : flat memory, increased addressable memory, and fast program execution. We study the impact of three important variables on the computation time for the RCPSP: addressable computer memory, the search strategy (depth-first, best-first, or hybrid), and the introduction of a stronger lower bound. We compare the results obtained by a truncated branch-and-bound procedure with the results generated by the minimum slack time heuristic and report on the dependency of its solution quality on the allotted CPU time.
Keywords
project scheduling–resource constraints, branch-and-bound, 32-bit programming, computational results
Enable JavaScript for citation tools and additional paper interactions.