Multi‐mode resource‐constrained project scheduling using RCPSP and SAT solvers

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.