Algoritmos evolutivos multiobjetivo baseados em tabelas para escalonamento de tarefas em ambientes multiprocessados

Abstract

Task scheduling is an important activity to ensure the efficiency of computer systems. This problem is defined as a series of tasks executed by several processors, subject to different optimization criteria. Some problems involve multiple measures, which may conflict, making resolution more complex. There are several solutions based on heuristics and meta-heuristics, with evolutionary algorithms being one of the most common tools. In this work, we implemented three multiobjective evolutionary algorithms: NSGA-II (Non-Dominated Sorting Genetic Algorithm II), MEAMT (Multiobjective Evolutionary Algorithm with Many Tables), and MEAMD (Multiobjective Evolutionary Algorithm with Multiple Dominances), these last two being representatives of the new class of algorithms proposed to solve problems with many objectives. We adjust all these algorithms for the presented problem and had their performance evaluated comparatively on a set of problems with different numbers of tasks, processors and objectives. Based on the experimental results, it is possible to verify that MEAMT produced the best results, followed by MEAMD and, finally, by NSGA-II.