New Benchmark Results for the Resource-Constrained Project Scheduling Problem

TLDR

The resource‑constrained project scheduling problem is addressed using a branch‑and‑bound procedure. This paper reports new insights from computational results of an updated branch‑and‑bound procedure and studies how memory, search strategy, and a stronger lower bound affect RCPSP computation time. The study employs a 32‑bit implementation of a truncated branch‑and‑bound algorithm on Windows NT/OS/2, varying memory, search strategy, and lower bound, and compares it to a minimum slack time heuristic. The truncated branch‑and‑bound procedure’s solution quality improves with increased CPU time, outperforming the minimum slack time heuristic. Published in Management Science, 1992, vol.

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.