Generalized Benders decomposition-based matheuristics for the multi-mode resource-constrained project scheduling problem
Journal
Optimization and Engineering
ISSN
1389-4420
Publisher
Springer Science and Business Media LLC
Date Issued
2025-03-13
Author(s)
Pablo A. Miranda-Gonzalez
Type
text::journal::journal article
Abstract
The multi-mode resource-constrained project scheduling problem is an NP-hard optimization problem with practical applications in construction, software development, manufacturing, and other industrial and business situations. It involves a set of activities that need to be sequenced while considering precedence and resource constraints as well as different alternative execution modes, which determine each activity’s duration and resource consumption. This research proposes three matheuristic strategies based on a reformulation and partial relaxation of the problem, including a generalized Benders decomposition (GBD)-based algorithm to solve the relaxed problem and three different procedures to find a solution to the original problem. The strategies were tested using benchmark instances of various sizes obtained from published libraries. These strategies showed a significant improvement in speed, achieving up to 92.77% faster performance than the exact method for finding high-quality sub-optimal solutions. This offers a valuable trade-off between computation time and solution quality. Additionally, the GBD-based algorithm generated tighter lower bounds than other existing methods in the literature for a substantial number of the tested instances, all within a very short computing time.
License
Acceso Restringido
URL License
How to cite
Ramos, A.S., Miranda-Gonzalez, P.A., Olivares-Benitez, E. et al. Generalized Benders decomposition-based matheuristics for the multi-mode resource-constrained project scheduling problem. Optim Eng (2025). https://doi.org/10.1007/s11081-025-09964-1
Table of contents
1 Introduction -- 2 Literature review -- 3 Problem description and formulations -- 4 Generalized Benders decomposition-based solution strategies -- 5 Computational implementation and results -- 6 Discussion -- 7 Conclusions.