Parallel multi-core hyper-heuristic GRASP to solve permutationflow-shop problem

摘要

In this paper, we aim to propose a parallel multi-core hyper-heuristic based on greedy randomized adaptivesearch procedure (GRASP) for the permutation flow-shop problem with the makespan criterion. The GRASPis a well-known two-phase metaheuristic. First, a construction phase builds a complete solution iteratively,component by component, by a greedy randomized algorithm. After that, a local search phase improves thissolution. The choice of a component and the order in which it is added in a solution mostly depend on itsincremental cost. Thus, a basic GRASP configuration is defined by a cost function, a probabilistic parameterof greediness and a neighbourhood structure. We consider five cost functions and seven well-known neighbourhoodstructures. In this paper a cost function based on a bounding operator is integrated in GRASP forthe first time. Mechanisms that investigate automatically algorithm configurations refer to hyper-heuristics.Our hyper-heuristic investigates 315 GRASP configurations and reports which one produces better results.Parallel multi-core computing is used as a way to efficiently implement the hyper-heuristic. Taillard’s benchmarkinstances are used to test the hyper-heuristic for the permutation flow-shop problem. Copyright © 2016John Wiley & Sons, Ltd.