Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas

Abstract

Heuristics and meta-heuristics are approximate methods that have been shown to be very promising in solving combinatorial optimization problems. Are applied to problems complex or difficult to solve, even for a computer, in general NP-difficult problems. In this context, this work aims to identify the heuristics and meta-heuristics that can be applied to task scheduling with dates suggested termination dates. The method adopted consisted of a secondary study called Mapping Systematic (MS) to identify the algorithmic strategies applied to the problem investigated, along with experimentation and empirical analysis of the execution of an Algorithm Genetics with Local Search and Path Reconnection (GLS + PR). As a result of the MS, 13 types of algorithmic strategies were identified, among the 30 publications raised in the MS, most of which apply the local search algorithm. The MS allowed to raise the literature testing instances for different variations of scheduling problems based on on suggested end dates. As for the results of computational experiments with GLS + PR, it was identified that this approach provides competitive solutions in relation to the literature, for the test batteries performed with 40, 50 and 100 tasks in 2, 4 and 10 identical parallel machines.