Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2592
Type: Relatório
Title: Scheduling multiprocessor tasks with genetic algorithms
Author(s)/Inventor(s): Corrêa, Ricardo Cordeiro
Ferreira, Afonso
Rebreyend, Pascal
Abstract: In the multíprocessor schedulíng problem a given program is to be scheduled in a given multiprocessor system such that the program 's execution time is minimized. This problem being very hard to solve exactly, many heuristic methods for finding a suboptimal schedule exist. We propose a new combined approach, where a genetic algorithm is improved with the introduction of some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutatíon genetic operations. This knowledge-augmented genetic approach is empirically compared with a "pure" genetic algorithm and with a "pure" list heuristic, both from the literature. Results of the experiments carried out with synthetic instances of the scheduling problem show that our knowledge-augmented algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time.
Keywords: Multiprocessadores
Escalonamento multidimensional
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0296
Issue Date: 31-Dec-1996
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: CORRÊA, R. C.; FERREIRA, A.; REBREYEND, P. Scheduling multiprocessor tasks with genetic algorithms. Rio de Janeiro: NCE, UFRJ, 1996. 27 p. (Relatório Técnico, 02/96)
URI: http://hdl.handle.net/11422/2592
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
02_96.pdf1,4 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.