Loading...
An exact composite lower bound strategy for the resource-constrained project scheduling problem
Coelho, José Vanhoucke, Mario
Coelho, José
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2018
Journal
Computers & Operations Research
Book
Publication Volume
93
Publication Issue
May
Publication Begin page
135
Publication End page
150
Publication NUmber of pages
Collections
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.
Research Projects
Organizational Units
Journal Issue
Keywords
Resource-constrained Project Scheduling, Branch-and-Bound, Lower Bounds