Evolutionary approaches for the parallel task scheduling problem : the representation issue

The problem of how to find a schedule on m > 2 processors of equal capacity that minimises the whole processing time of independent tasks has been shown as belonging to the NP-complete class (Horowitz and Sahni [12]). Evolutionary Algorithms (EAs) have been used in the past to implement the alloc...

Descripción completa

Detalles Bibliográficos
Autores principales: Esquivel, Susana Cecilia, Gatica, Claudia R., Gallard, Raúl Hector
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2001
Materias:
Ciencias Informáticas
Algorithms
Scheduling
Optimization
Parallel
Concurrent Programming
Parallel task allocation
Evolutionary algorithm
multirecombination
indirect-decode representation
List Scheduling Algorithm
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/23332
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-23332
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Algorithms
Scheduling
Optimization
Parallel
Concurrent Programming
Parallel task allocation
Evolutionary algorithm
multirecombination
indirect-decode representation
List Scheduling Algorithm
spellingShingle Ciencias Informáticas
Algorithms
Scheduling
Optimization
Parallel
Concurrent Programming
Parallel task allocation
Evolutionary algorithm
multirecombination
indirect-decode representation
List Scheduling Algorithm
Esquivel, Susana Cecilia
Gatica, Claudia R.
Gallard, Raúl Hector
Evolutionary approaches for the parallel task scheduling problem : the representation issue
topic_facet Ciencias Informáticas
Algorithms
Scheduling
Optimization
Parallel
Concurrent Programming
Parallel task allocation
Evolutionary algorithm
multirecombination
indirect-decode representation
List Scheduling Algorithm
description The problem of how to find a schedule on m > 2 processors of equal capacity that minimises the whole processing time of independent tasks has been shown as belonging to the NP-complete class (Horowitz and Sahni [12]). Evolutionary Algorithms (EAs) have been used in the past to implement the allocation of the components (tasks) of a parallel program to processors [12], [13], [14], [16], [17]. Those approaches showed their advantages when contrasted against conventional approaches and different chromosome representations were proposed. This paper shows four algorithms to solve the problem of allocating a number of non-identical related tasks in a multiprocessor or multicomputer system. The model assumes that the system consists of a number of identical processors and only one task may execute on a processor at a time. All schedules and tasks are non-preemptive. Three evolutionary algorithms, using an indirect-decode representation, are contrasted with the well-known Graham’s [11] list scheduling algorithm (LSA). All of them use the conventional Single Crossover Per Couple (SCPC) approach and indirectdecode representation but they differ in what is represented by the decoders. In the first representation scheme, decoders represent processor dispatching priorities, in the second decoders represent tasks priority lists, and in the third decoders represent both processor dispatching priorities and tasks priority lists in a bipartite chromosome. Chromosome structure, genetic operators, experiments and results are discussed.
format Objeto de conferencia
Objeto de conferencia
author Esquivel, Susana Cecilia
Gatica, Claudia R.
Gallard, Raúl Hector
author_facet Esquivel, Susana Cecilia
Gatica, Claudia R.
Gallard, Raúl Hector
author_sort Esquivel, Susana Cecilia
title Evolutionary approaches for the parallel task scheduling problem : the representation issue
title_short Evolutionary approaches for the parallel task scheduling problem : the representation issue
title_full Evolutionary approaches for the parallel task scheduling problem : the representation issue
title_fullStr Evolutionary approaches for the parallel task scheduling problem : the representation issue
title_full_unstemmed Evolutionary approaches for the parallel task scheduling problem : the representation issue
title_sort evolutionary approaches for the parallel task scheduling problem : the representation issue
publishDate 2001
url http://sedici.unlp.edu.ar/handle/10915/23332
work_keys_str_mv AT esquivelsusanacecilia evolutionaryapproachesfortheparalleltaskschedulingproblemtherepresentationissue
AT gaticaclaudiar evolutionaryapproachesfortheparalleltaskschedulingproblemtherepresentationissue
AT gallardraulhector evolutionaryapproachesfortheparalleltaskschedulingproblemtherepresentationissue
bdutipo_str Repositorios
_version_ 1764820465694539778

Ejemplares similares