An exact composite lower bound strategy for the resource-constrained project scheduling problem

Abstract

This paper reports on results for the well-known resource-constrained project scheduling problem. A branch-and-bound procedure is developed that takes into account all best performing components from literature, varying branching schemes and search strategies, using the best performing dominance rules and assembling these components into a unified search algorithm. A composite lower bound strategy that statically and dynamically selects the best performing bounds from literature is used to find optimal solutions within reasonable times. An extensive computational experiment is set up to determine the best combination of the various components used in the procedure, in order to benchmark the current existing knowledge on four different datasets from the literature. By varying the network topology, resource scarceness and the size of the projects, the computational experiments are carried out on a diverse set of projects. The procedure was able to find some new lower bounds and optimal solutions for the PSPLIB instances. Moreover, new best known results are reported for other, more diverse datasets that can be used in future research studies. The experiments revealed that even project instances with 30 activities cannot be solved to optimality when the topological structure is varied.