Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/28884
ORCID:  http://orcid.org/0000-0001-9042-2562
Document type: Dissertação
Access type: Acesso Embargado
Title: Representações de Algoritmos Genéticos para o Problema de Escalonamento Estático de Tarefas em Multiprocessadores
Alternate title (s): Representations of Genetic Algorithms for the Static Multiprocessor Task Scheduling Problem
Author: Silva, Eduardo Cassiano da
First Advisor: Gabriel, Paulo Henrique Ribeiro
First member of the Committee: Carneiro, Murillo Guimarães
Second member of the Committee: Soares, Telma Woerle de Lima
Summary: 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.
Keywords: Algoritmos Genéticos
Escalonamento de Tarefas
Sistemas Multiprocessados
Representações
Função Objetivo
DAG
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: 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>.
Document identifier: http://doi.org/10.14393/ufu.di.2020.104
URI: https://repositorio.ufu.br/handle/123456789/28884
Date of defense: 20-Jan-2020
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
RepresentacoesAlgoritmosGeneticos.pdf
  Until 2021-01-20
Primeira submissão efetuada.2.89 MBAdobe PDFView/Open    Request a copy


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