A new parallel asynchronous cellular genetic algorithm for scheduling in grids

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. W...

Full description

Saved in:
Bibliographic Details
Main Authors: Pinel, Frederic, Dorronsoro, Bernabe, Bouvry, Pascal
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Concurrent computing
Genetic algorithms
Iterative algorithms
Multicore processing
Optimal scheduling
Parallel processing
Processor scheduling
Scheduling algorithm
Space exploration
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/IPDPSW.2010.5470698