An Adaptive Large Neighborhood Search Algorithm for the Multi-mode RCPSP

We present an Adaptive Large Neighborhood Search algorithm for the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP). We incorporate techniques for deriving additional precedence relations and propose a new method, so-called mode-diminution, for removing modes during execution. These techniques make use of bound arguments, and we propose and experiment with three new bounds for the MRCPSP, in addition to bounds found in the literature. We propose a simple technique, so-called opportunistic mode-flipping, which can be applied whenever a schedule is generated,and which significantly improves the results of the algorithm. Computational experiments are performed on a set of standard benchmark instances from the PSPLIB, and a comparison is made with other algorithms found in the literature. The experiments show that the algorithm is competitive, but can not beat the best algorithms. Even so, some of the elements of the algorithm perform well, that is the bound arguments, the mode-removal procedure, and in particular opportunistic mode-flipping, and these elements may perhaps be used to improve the results of other algorithms for this problem.