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

Ekaterina Alekseeva 1 Mohand Mezmaz 1 Daniel Tuyttens 1 Nouredine Melab 2
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2017, 29 (9), pp.15. 〈10.1002/cpe.3835〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01419060
Contributeur : Nouredine Melab <>
Soumis le : dimanche 18 décembre 2016 - 14:50:21
Dernière modification le : vendredi 13 avril 2018 - 01:28:05

Identifiants

Collections

Citation

Ekaterina Alekseeva, Mohand Mezmaz, Daniel Tuyttens, Nouredine Melab. Parallel multi-core hyper-heuristic GRASP to solve permutation flow-shop problem. Concurrency and Computation: Practice and Experience, Wiley, 2017, 29 (9), pp.15. 〈10.1002/cpe.3835〉. 〈hal-01419060〉

Partager

Métriques

Consultations de la notice

351