Algorithms for the RCPSP
The resource-constrained project scheduling problem (RCPSP) has been solved by various algorithms at the Operations Research and Scheduling group, and a short overview is given on this page. An overview of other research projects for this problem can be found at the RCPSP webpage.
Priority rules
The use of priority rules for the RCPSP has been investigated in a paper in which a genetic programming approach designs new quick and efficient rules to solve the challenging problem
References:
- Luo, J., Vanhoucke, M., Coelho, J., & Guo, W. (2022). An efficient genetic programming approach to design priority rules for resource-constrained project scheduling problem. Expert Systems with Applications, 198, 116753. https://doi.org/10.1016/j.eswa.2022.116753
Meta-heuristic algorithms
OR&S has presented various meta-heuristic algorithms to solve the RCPSP. A non-exhaustive list is given below. The Debels and Vanhoucke (2007) algorithm still belongs to one of the best-performing algorithms in the literature, and has been used in many of our other RCPSP studies.
References:
- Debels, D., & Vanhoucke, M. (2007). A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Research, 55(3), 457–469. https://doi.org/10.1287/opre.1060.0358
- Debels, D., De Reyck, B., Leus, R., & Vanhoucke, M. (2006). A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research, 169(2), 638–653. https://doi.org/10.1016/j.ejor.2004.08.020
- Debels, D., & Vanhoucke, M. (2005). A bi-population based genetic algorithm for the resource-constrained project scheduling problem. Lecture Notes in Computer Science, 3483, 378–387. https://doi.org/10.1007/11424925_41
Branch-and-bound procedures
OR&S has programmed most of the branch-and-bound procedures available in the literature into a so-called composite lower bound strategy approach. The procedure is used in various studies to analyse project data, to classify the procedures and automatically select the best performing one and to present new data instances. OR&S also investigated the complexity of the problem in a study of 2022.
References:
- 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. https://doi.org/10.1016/j.cor.2018.01.017
- Van Eynde, R., & Vanhoucke, M. (2022). A theoretical framework for instance complexity of the resource-constrained project scheduling problem. Mathematics of Operations Research, To Appear. https://doi.org/10.1287/moor.2021.1237
- Coelho, J., & Vanhoucke, M. (2020). Going to the core of hard resource-constrained project scheduling instances. Computers and Operations Research, 121, 104976. https://doi.org/10.1016/j.cor.2020.104976
- Vanhoucke, M., & Coelho, J. (2021). An analysis of network and resource indicators for resource-constrained project scheduling problem instances. Computers and Operations Research, 132, 105260. https://doi.org/10.1016/j.cor.2021.105260
Machine learning algorithms
Given the overwhelming amount of procedures, OR&S has proposed some ways to classify, select and rank the best performing procedures to solve the problem using classification algorithms.
References:
- Guo, W., Vanhoucke, M., Coelho, J., & Luo, J. (2021). Automatic detection of the best performing priority rule for the resource-constrained project scheduling problem. Expert Systems with Applications, 167, 114116. https://doi.org/10.1016/j.eswa.2020.114116 (download code)
- Guo, W., Vanhoucke, M., & Coelho, J. (2022). A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem, under submission (download the technical appendix (A, B and C) and the source code).
Many extensions
Satisfiability problem: A number of challenging extensions to the classic RCPSP have been proposed and solved using a combination of two algorithms. The meta-heuristic solution procedure by Debels and Vanhoucke (2007) has been combined with a satisfiability solution approach to solve the problem. Visit the SAT page.
Other extensions: The RCPSP can be extended with many other features such as the incorporation of alternative branches (RCPSP-AS), discounted cash-flows (RCPSP-DC), multiple modes (MMRCPSP), multi-skilled resources (MSRCPSP) and multi-projects (RCMPSP). Each of these problem types has a separate webpage (go to Research > Project Scheduling and click on the abbreviations for each problem type).