A new parallel asynchronous cellular genetic algorithm for scheduling in grids

Author

Pinel, Frédéric ; Dorronsoro, Bernabeé ; Bouvry, Pascal

Author_Institution

Fac. of Sci., Technol., & Commun., Univ. of Luxembourg, Luxembourg, Luxembourg

fYear

2010

fDate

19-23 April 2010

Firstpage

1

Lastpage

8

Abstract

We propose a new parallel asynchronous cellular genetic algorithm for multi-core processors. The algorithm is applied to the scheduling of independent tasks in a grid. Finding such optimal schedules is in general an NP-hard problem, to which evolutionary algorithms can find near-optimal solutions. We analyze the parallelism of the algorithm, as well as different recombination and new local search operators. The proposed algorithm improves previous schedules on benchmark problems. The parallelism of this algorithm suits it to bigger problem instances.

Keywords

genetic algorithms; grid computing; microprocessor chips; parallel processing; processor scheduling; NP-hard problem; grid scheduling; multicore processors; optimal schedules; parallel asynchronous cellular genetic algorithm; Algorithm design and analysis; Concurrent computing; Genetic algorithms; Iterative algorithms; Multicore processing; Optimal scheduling; Parallel processing; Processor scheduling; Scheduling algorithm; Space exploration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on

Conference_Location

Atlanta, GA

Print_ISBN

978-1-4244-6533-0

Type

conf

DOI

10.1109/IPDPSW.2010.5470698

Filename

5470698