Combining metaheuristics and exact methods for solving exactly multi-objective problems on the grid

Combining metaheuristics and exact methods for solving exactly multi-objective problems on the grid

0.00 Avg rating0 Votes
Article ID: iaor20083369
Country: United Kingdom
Volume: 6
Issue: 3
Start Page Number: 393
End Page Number: 409
Publication Date: Sep 2007
Journal: Journal of Mathematical Modelling and Algorithms
Authors: , ,
Keywords: scheduling, computational analysis: parallel computers, heuristics: genetic algorithms, programming: branch and bound, programming: multiple criteria
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 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.

Reviews

Required fields are marked *. Your email address will not be published.