Parallel multi‐core hyper‐heuristic GRASP to solve permutation flow‐shop problem

Summary In this paper, we aim to propose a parallel multi‐core hyper‐heuristic based on greedy randomized adaptive search procedure (GRASP) for the permutation flow‐shop problem with the makespan criterion. The GRASP is 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 this solution. The choice of a component and the order in which it is added in a solution mostly depend on its incremental cost. Thus, a basic GRASP configuration is defined by a cost function, a probabilistic parameter of greediness and a neighbourhood structure. We consider five cost functions and seven well‐known neighbourhood structures. In this paper a cost function based on a bounding operator is integrated in GRASP for the 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 benchmark instances are used to test the hyper‐heuristic for the permutation flow‐shop problem.