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

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.