A matheuristic approach to the multi-mode resource constrained project scheduling problem. (December 2021) - Fernandes, Gustavo Alves; de Souza, Sérgio Ricardo
Highlights: Local Branching (LB) matheuristic for solvingMulti-mode Resource-Constrained Project Scheduling Problem. Analysis of the parameters influence on the local search based method was verified. Two characterization of neighborhood structures that define a subproblem during the enumeration of the LB matheuristic. The used matheuristic leads the exact methods hybridized with heuristics to state-of-the-art. Abstract: This article addresses the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP). It is an NP-Hard problem and consists of scheduling all activities of a project, respecting the precedence order of these activities, which, once initiated, cannot be interrupted. Jobs have combinations of execution modes, in the form of different combinations of processing time and resource consumption. The objective is to minimize the duration of the project, finding start times for each project activity. This article proposes a Local Branching matheuristic strategy for solving MRCPSP. The influence of the parameters of the based local search method is verified, as well as the characterization of neighborhood structures that define a subproblem during the enumeration of the LB matheuristic. Two characterizations to define the subproblems are proposed, and one of them surpasses the characterization discussed in the literature. Computational tests were performed using sets of instances from the PSPLIB and MMLIB libraries. The best-known results for these instances in relation to the state-of-the-art are presented as a reference to validate the results obtained by the approach proposed in this article.