Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas

Abstract

This dissertation presents the results of the investigation carried out on parallel machine scheduling problems, with focus on minimizing the total weighted tardiness of the jobs, with arbitrary processing times and deadlines. This is a classic scheduling problem that is often found in industries, production environments, and scenarios where delayed completion of jobs can lead to penalties. The applied resolution strategy makes use of an exact-heuristic hybrid method, where the execution of a strongly Local Search-based Genetic Algorithm, called GLS, provides a set of optimal location solutions to be incorporated in a tri-indexed integer linear programming formulation, optimizing the implicit enumerative resolution process. How the parameterization is an inherent problem in genetic algorithms and meta-heuristics in general, the iRace tool was used for optimization and parameter definition. The IBM ILog CPLEX solver and UFFLP dynamic library was used to evaluate the solution set obtained through heuristics using the integer linear programming formulation. The computational experiments were performed for instances created similar of the OR-Library with 40, 50, 100, 150, 200, 300 and 500 tasks in 2, 4, 10 and 20 parallel machines, obtaining competitive results against the best strategies available in the literature, and presenting the robustness of the method in larger instances.