Reactive GRASP with path relinking for solving parallel machines scheduling problem with resource-assignable sequence dependent setup times

摘要

This paper addresses an unrelated parallel machine problem with machine and job sequence dependent setup times. The objective function considered is a linear combination of the total completion time and the total number of resources assigned. Due to the combinatorial complexity of this problem, we propose an algorithm based on the GRASP metaheuristic, in which the basic parameter that defines the restrictiveness of the candidate list during the construction phase is self-adjusted according to the quality of the solutions previously found (reactive GRASP). The algorithm uses an intensification strategy based on the path relinking technique which consists in exploring paths between elite solutions found by GRASP. The results obtained by the proposed algorithm are compared with the best results available in the literature.