A Path-Relinking algorithm for the multi-mode resource-constrained project scheduling problem

This paper proposes a Path-Relinking (PR) algorithm for the well-known and NP-hard Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP). This problem generalizes the Resource-Constrained Project Scheduling Problem (RCPSP) where the project activities have a set of execution modes. For each execution mode, the processing time, the renewable and nonrenewable resource demands are given. The MRCPSP goal is to minimize the total makespan of the project. The PR algorithm works by travelling through the solution space between two solutions, it performs local search around the intermediate solutions. This work also presents computational tests using benchmark instances to compare our implementation with the most competitive methods from the literature. The PR's computational results improve the earlier results reported for the benchmark instance sets.