Combining Metaheuristics and Exact Methods for Solving Exactly Multi-Objective Problems on the Grid

Mohand Mezmaz 1 Nouredine Melab 1 El-Ghazali Talbi 1
1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics - a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method - a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models - the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a biobjective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem - 50 jobs on 5 machines. More than 400 processors belonging to 4 different administrative domains have contributed to the resolution process during more than 6 days.
Type de document :
Article dans une revue
Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2007, 6 (3), pp.393-409. 〈10.1007/s10852-007-9063-8〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00684621
Contributeur : Ist Rennes <>
Soumis le : lundi 2 avril 2012 - 16:18:52
Dernière modification le : mardi 24 avril 2018 - 13:53:10

Lien texte intégral

istex

Identifiants

Collections

INRIA | GRID5000 | LIFL | UNIV-LILLE3

Citation

Mohand Mezmaz, Nouredine Melab, El-Ghazali Talbi. Combining Metaheuristics and Exact Methods for Solving Exactly Multi-Objective Problems on the Grid. Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2007, 6 (3), pp.393-409. 〈10.1007/s10852-007-9063-8〉. 〈hal-00684621〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

173

Contact


archive-ouverte@inria.fr