Article ID: | iaor1999182 |
Country: | United States |
Volume: | 43 |
Issue: | 11 |
Start Page Number: | 1485 |
End Page Number: | 1492 |
Publication Date: | Nov 1997 |
Journal: | Management Science |
Authors: | Herroelen Willy S., Demeulemeester Erik L. |
Keywords: | computational analysis: personal computers, programming: branch and bound |
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 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.