Publicação: Representações de Algoritmos Genéticos para o Problema de Escalonamento Estático de Tarefas em Multiprocessadores
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Este trabalho apresenta uma revisão sistemática da literatura sobre as características dos algoritmos genéticos aplicado ao problema do escalonamento de tarefas em sistemas multiprocessados. A revisão foi aplicada sobre trabalhos publicados entre 1990 e 2018. Sendo assim, um protocolo de pesquisa foi elaborado para definir as fases de execução da revisão, assim como as regras para incluir e excluir estudos. Após a execução da revisão, 13 representações de cromossomos foram identificadas. Dadas as particularidades de cada representação, 78 operadores genéticos foram encontrados. As funções objetivo empregadas nesses algoritmos também foram sumarizadas. Por fim, as quatro codificações (Codificação de Listas Topológicas (TLE), Codificação de Alocação e Escalonamento (MSE), Codificação por Lista Ordenada (OLE) e Codificação por Lista de Processadores (PLE)) foram comparadas através de uma análise de dispersão. Desse modo, ao aplicar as métricas de makespan, flowtime e load balance, foi possível observar um melhor desempenho na representação OLE e uma equivalência entre TLE, MSE e PLE. Por fim, a síntese elaborada nesta dissertação pode ser significativa na tomada de decisão e na realização de novas pesquisas.
Abstract
This dissertation presents a systematic review of the literature on the characteristics of genetic algorithms applied to the multiprocessor task scheduling problem. The review was applied on works published between 1990 and 2018. A research protocol was developed to define the stages of the review as well as the rules for including and excluding studies. In the review, 13 representations of chromosomes were identified. Given the particularities of each representation, 78 genetic operators were found. The objective functions employed in these algorithms have also been summarized. Finally, the four encodings (Topological List Encoding (TLE), Matching Scheduling Encoding (MSE), Ordered List Encoding (OLE) and Processor List Encoding (PLE)) were compared by dispersion analysis. Thus, when applying the metrics of makespan, flowtime and load balance, it was possible to observe a better performance in the OLE representation and an equivalence between TLE, MSE and PLE. Lastly, the synthesis developed in this dissertation can be significant in decision making and in conducting new research.
Palavras-chave
Algoritmos Genéticos, Escalonamento de Tarefas, Sistemas Multiprocessados, Representações, Função Objetivo, DAG
Citação
SILVA, Eduardo Cassiano da. Representações de Algoritmos Genéticos para o Problema de Escalonamento Estático de Tarefas em Multiprocessadores. 2020. 231 f. Dissertação (Mestrado) - Curso de Mestrado em Ciência da Computação, Faculdade de Computação, Universidade Federal de Uberlândia, Uberlândia, 2020. Disponível em: <http://doi.org/10.14393/ufu.di.2020.104>.