Exploration of a Generalized Benders Decomposition Method for Solving Project Scheduling Problems with Resource Constraints
Journal
Proceedings of the 14th International Conference on Operations Research and Enterprise Systems
Publisher
SCITEPRESS - Science and Technology Publications
Date Issued
2025
Author(s)
Pablo Miranda-Gonzalez
Type
text::conference output::conference proceedings
Abstract
This research introduces a new Generalized Benders Decomposition-based Algorithm (GBDA) to solve the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP). The MRCPSP is a scheduling problem that besides precedence constraints, includes renewable and non-renewable resource constraints, as well as the selection of execution modes for the project activities. This mode selection determines the resource usage and duration of each activity. The GBDA splits the problem into a Master Problem (MP) and a Sub- Problem (SP) with a relaxation. Both problems are solved alternately, each one incorporating information from the other at each iteration, until a stopping criterion is met. Additionally, at each iteration, a non-relaxed SP is solved to obtain a solution for the original problem, and the best solution from all iterations is reported. The GBDA was tested, with three different stopping criteria, on benchmark instances from a public library and compared against solving the traditional formulation of the problem with an exact Mixed Integer Linear Programming (MILP) method. The GBDA found solutions of good quality in less than half the computing time than the exact method, with one of the stopping criteria. The analysis of the results provides valuable insights for future research.
Table of contents
1 Introduction and literature review -- 2 Problem formulation -- 3 Methodology -- 4 Experimentation -- 5 Results and discussion -- 6 Conclusions.