Representações de Algoritmos Genéticos para o Problema de Escalonamento Estático de Tarefas em Multiprocessadores

• Ano de defesa: 2020
• Autor(a) principal: Silva, Eduardo Cassiano da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Uberlândia; Brasil; Programa de Pós-graduação em Ciência da Computação
• Palavras-chave em Português: Algoritmos Genéticos; Escalonamento de Tarefas; Sistemas Multiprocessados; Representações; Função Objetivo; DAG; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufu.br/handle/123456789/28884; http://doi.org/10.14393/ufu.di.2020.104

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.