Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers
Coelho, José Vanhoucke, Mario
Coelho, José
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2011
Journal
European Journal of Operational Research
Book
Publication Volume
213
Publication Issue
Publication Begin page
73
Publication End page
82
Publication Number of pages
Collections
Abstract
This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP-hard and has been solved using various exact as well as (meta-)heuristic procedures. The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time.
Research Projects
Organizational Units
Journal Issue
Keywords
Project Management