A multirecombinative evolutionary approach to solve the parallel task scheduling problem
Allocation of the components (tasks) of a parallel program to processors in a multiprocessor or a multicomputer system take full advantage of the computational power provided by the system. Evolutionary approaches has been used in the past to implement efficiently this type of scheduling. Those ap...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2000
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/23426 |
| Aporte de: |
| id |
I19-R120-10915-23426 |
|---|---|
| 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 parallel task allocation evolutionary algorithm multirecombination Scheduling Parallel programming Optimization |
| spellingShingle |
Ciencias Informáticas parallel task allocation evolutionary algorithm multirecombination Scheduling Parallel programming Optimization Esquivel, Susana Cecilia Gatica, Claudia R. Gallard, Raúl Hector A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| topic_facet |
Ciencias Informáticas parallel task allocation evolutionary algorithm multirecombination Scheduling Parallel programming Optimization |
| description |
Allocation of the components (tasks) of a parallel program to processors in a multiprocessor or a multicomputer system take full advantage of the computational power provided by the system.
Evolutionary approaches has been used in the past to implement efficiently this type of scheduling.
Those approaches showed their advantages when contrasted against conventional approaches and different chromosome representations were proposed. Latest improvements in evolutionary computation include multirecombinative variants allowing multiplicity of crossovers on the selected couple of parents. Multiple crossovers per couple (MCPC) exploits good parents' features in the creation of offspring. Performance enhancements were clearly demonstrated in single and multicriteria optimization under this approach.
This paper shows three 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. This involves the assignment of partially ordered tasks onto the system architecture processing components. Two evolutionary algorithms using a direct representation, are contrasted with the well-known Graham's [12] list scheduling algorithm (LSA).
The first one makes use of the conventional single crossover per couple (SCPC) approach while the second, following cunent trends in evolutionary computation, uses (MCPC) a multirecombinated approach. 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 |
A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| title_short |
A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| title_full |
A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| title_fullStr |
A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| title_full_unstemmed |
A multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| title_sort |
multirecombinative evolutionary approach to solve the parallel task scheduling problem |
| publishDate |
2000 |
| url |
http://sedici.unlp.edu.ar/handle/10915/23426 |
| work_keys_str_mv |
AT esquivelsusanacecilia amultirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem AT gaticaclaudiar amultirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem AT gallardraulhector amultirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem AT esquivelsusanacecilia multirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem AT gaticaclaudiar multirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem AT gallardraulhector multirecombinativeevolutionaryapproachtosolvetheparalleltaskschedulingproblem |
| bdutipo_str |
Repositorios |
| _version_ |
1764820465905303554 |