New Benchmark Results for the Resource-Constrained Project Scheduling Problem

This paper reports on 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 ® 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 an improved 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