Use este identificador para citar ou linkar para este item: https://repositorio.ufu.br/handle/123456789/28884
ORCID:  http://orcid.org/0000-0001-9042-2562
Tipo do documento: Dissertação
Tipo de acesso: Acesso Aberto
Término do embargo: 2022-01-20
Título: Representações de Algoritmos Genéticos para o Problema de Escalonamento Estático de Tarefas em Multiprocessadores
Título(s) alternativo(s): Representations of Genetic Algorithms for the Static Multiprocessor Task Scheduling Problem
Autor(es): Silva, Eduardo Cassiano da
Primeiro orientador: Gabriel, Paulo Henrique Ribeiro
Primeiro membro da banca: Carneiro, Murillo Guimarães
Segundo membro da banca: Soares, Telma Woerle de Lima
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
Área(s) do CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editora: Universidade Federal de Uberlândia
Programa: Programa de Pós-graduação em Ciência da Computação
Referência: 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>.
Identificador do documento: http://doi.org/10.14393/ufu.di.2020.104
URI: https://repositorio.ufu.br/handle/123456789/28884
Data de defesa: 20-Jan-2020
Aparece nas coleções:DISSERTAÇÃO - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
RepresentacoesAlgoritmosGeneticos.pdfPrimeira submissão efetuada.2.89 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.