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

Alekseeva, Ekaterina; Mezmaz, Mohand; Tuyttens, Daniel; Melab, Nouredine

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1002/cpe.3835

Titre :

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

Auteur(s) :

Alekseeva, Ekaterina [Collaborateur]
Institut de Mathématiques [Mons]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Titre de la revue :

Concurrency and Computation: Practice and Experience

Pagination :

Éditeur :

Wiley

Date de publication :

2017-05-10

ISSN :

1532-0626

Mot(s)-clé(s) en anglais :

Parallel computing
Metaheuristics
Scheduling problems
Combinatorial optimization

Discipline(s) HAL :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Parallel multi-core hyper-heuristic GRASP ... BibTeX CSV Excel RIS

Parallel multi-core hyper-heuristic GRASP ...

BibTeX

CSV

Excel

RIS