Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00684621
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Monday, April 2, 2012 - 4:18:52 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM

Links full text

Identifiers

Collections

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⟩

Share

Metrics

Record views

67