GRASP with Exterior Path-Relinking applied to the solution of the Multi-mode Resource-Constrained Project Scheduling Problem

This paper proposes an implementation of the GRASP metaheuristic combined with the exterior Path Relinking (ePR) algorithm to solve the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP). This problem consists of sequencing all project activities, respecting their precedence relations. Each activity of the project has a set of execution modes, with particular processing time and demand for renewable and non-renewable resources, resulting in different combinations for the execution of the project. MRCPSP aims to minimize the total makespan of the project by providing the completion time for each activity. GRASP samples the best solutions found, while ePR explores promising regions adjacent to these solutions, applying local search in the intermediate solutions. The computational tests were performed using a set of instances from the literature of the PSLIB and MMLIB libraries and compared with the best found solutions.