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 (1992) 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(R) and OS/2(R): 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.