The Multi-Mode Resource-Constrained Project Scheduling Problem
Coelho, José Vanhoucke, Mario
Coelho, José
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Book Chapter
Supervisor
Publication Year
2015
Journal
Book
Handbook on Project Management and Scheduling Vol.1
Publication Volume
Publication Issue
Publication Begin page
491
Publication End page
511
Publication Number of pages
Collections
Abstract
This chapter reports on a new solution approach for the multi-mode resource-constrained project scheduling problem (MRCPSP, MPS | prec | Cmax). 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 nonrenewable) resource-feasible project schedule with a minimal makespan. The problem type is known to be 𝒩𝒫$$\mathcal{N}\mathcal{P}$$-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 nonrenewable 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
4005 Civil Engineering, 40 Engineering, 33 Built Environment and Design, 3302 Building