The resource-constrained project scheduling problem (RCPSP) is the basic problem in project scheduling, and has been investigated widely in the academic literature. OR&S has developed various algorithms to solve this challenging problem, and a summary can be found here. On this page, you find the theoretical work we have done on this challenging problem consisting of three phases. First, we have benchmarked the best performing procedures from the literature (branching-and-bound). Secondly, we have used these procedure to change the network structure of project instances (going to the core) and finally we have changed the resource parameters of the project instances (solution equivalence). The papers are published in the flagship journal Computers and Operations Research.
Benchmarking procedures --> Changing network structure --> Changing resource scarceness
Benchmarking exact procedures: Branch-and-bound
The best components of various branch-and-bound procedures from the literature have been assembled into a unified branch-and-bound procedure. This procedure relies on the most widely used branching schemes and branching orders and makes use of the best performing dominance rules and lower bounds from the literature. The new procedures is called a composite lower bound strategy and is tested on four benchmark datasets with 4,860 instances. The results have shown that - contrary to what many believe - instances with only 30 activities are not always solvable. The inherent complexity of the problem, even for small to medium sized instances, and the observation that they cannot be solved to optimality probably means that fundamentally different research is necessary to optimally solve these and larger project instances.
- Publication: Coelho, J., & Vanhoucke, M. (2018). An exact composite lower bound strategy for the resource-constrained project scheduling problem. Computers and Operations Research, 93, 135–150.
Changing network indicators: Going to the core
In this study, we have changed the network structure of 8,370 project instances using a three-phased approach into smaller but very hard instances that can - with the current state-of-the-art algorithms - not be solved to optimality. To that purpose, we have used the best performing meta-heuristic and exact solution procedures in the academic literature. Four computational experiments have been set up that took in total almost 45 years of computational time (when using a single core processor), which have finally resulted in a small set of 623 hard instances 'which we refer to as the CV set), all of them with at most 30 activities.
- Publication: Coelho, J., & Vanhoucke, M. (2020). Going to the core of hard resource-constrained project scheduling instances. Computers and Operations Research, 121, 104976.
- Dataset: Download the CV set(for more data downloads, go to bottom of this page)
Changing resource parameters: Solution equivalence
In our latest research, we have investigated well-known network and resource indicators, and proposed a new heuristic algorithm that changes project instances into equivalent changes by changing the resource demand and availabilities. The algorithm is based on concept called "solution equivalence" to show that instances might have very different values for their resource indicators without changing any possible solution for this instance.
- Publication: Vanhoucke, M. & Coelho, J. (2020). An analysis of network and resource indicators for resource-constrained project scheduling problem instances, Computers and Operations Research, 132, 105260.
- Technical appendix: Download the technical appendix of this paper with an illustrative example and detailed calculations
- Dataset: Each instance has now two equivalent instances, labelled "lowRU" and "highRD" instances.
Project data: Download, use and benchmark projects
At OR&S, we have generated a lot of artificial project data and collected a significant number of empirical project data that is freely available for researchers and professionals. Moreover, we have also created a new website to share data and solutions. For a summary visit the following website:
On this website, you will find access to:
- 10 artificial datasets and 1 empirical dataset for the RCPSP
- 2 datasets for the multi-project RCPSP
- Several datasets for the RCPSP with alternative network structures
- A new website to download all data and best known solutions, and upload new solutions