Article ID: | iaor20083047 |
Country: | Netherlands |
Volume: | 6 |
Issue: | 3 |
Start Page Number: | 393 |
End Page Number: | 409 |
Publication Date: | Sep 2007 |
Journal: | Journal of Mathematical Modelling and Algorithms |
Authors: | Talbi El-Ghazali, Mezmaz Mohand, Melab Nouredine |
Keywords: | programming: multiple criteria, programming: branch and bound, heuristics: genetic algorithms |
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 bi-objective 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.