New Benchmark Results for the Resource-Constrained Project Scheduling Problem

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.

• 저널Management Science · 43(11) · 1485–1492
• 토픽Resource-Constrained Project Scheduling · Management Science and Operations Research
• DOI10.1287/mnsc.43.11.1485
• 저자Erik Demeulemeester, Willy Herroelen