Solving the Sequencing Problem in Resource-Constrained Projects with Multiple Execution Modes Using a GRASP Hybrid Algorithm with Path-Relinking

This article addresses the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP). This problem consists of sequencing project activities with limited resources and multiple execution modes. Each mode has specific time and resource demands, generating planning alternatives. The objective is to minimize the makespan by defining the completion time and execution mode for each activity. As MRCPSP is an NP-hard problem, this article proposes the implementation of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic integrated with the Path Relinking (PR) procedure as a post-optimization step for its solution, evaluating two PR variants: (i) interior PR, focused on intensification, and (ii) exterior PR, focused on diversification. Computational experiments, performed on instances of the PSLIB and MMLIB libraries, were compared to the best known solutions. The results show competitive performance of the proposed approach.