Heurística Híbrida para Sequenciamento de Tarefas em Máquinas Paralelas Heterogêneas

Abstract

Este trabalho considera o problema de sequenciamento de tarefas em máquinas paralelas heterogêneas com o objetivo de redução da multa total aplicada pelo atraso na execução das tarefas. O problema é considerado np-hard e por isso apresenta-se uma heurística híbrida que utiliza um modelo de programação linear inteira de designação e regras de despacho em máquina única. O modelo de designação é resolvido utilizando-se o otimizador LINGO®, e é responsável por definir em quais máquinas serão processadas as tarefas, considerando-se a minimização do tempo total de execução das tarefas. Para a obtenção do sequenciamento em cada máquina, visando a minimização da multa por atraso na data de entrega, é desenvolvido um algoritmo em Python que aplica regras de despacho. Ao se aplicar a heurística proposta para o cenário considerado em Barbosa et al. (2021) a solução ótima global não é alcançada, porém exige tempo computacional de processamento do algoritmo significativamente inferior quando se comparado com o modelo PLI proposto pela autora. Destaca-se que quando se considerou outros cenários de dados aleatórios, foi possível alcançar a solução ótima obtida pelo modelo de PLI em 100% dos casos em que foi possível também aplicar o PLI. Além disso, possibilitou resolver problemas com quantidades maiores de tarefas. O estudo traz como contribuição um método capaz de resolver problemas com grande quantidade de tarefas e de máquinas, que embora não garanta alcançar a solução ótima do problema, necessita de baixo tempo de processamento do algoritmo.

This work considers the scheduling problem on heterogeneous parallel machines aiming to reduce the total fine for the delay in the execution of tasks. The problem is considered np-hard and therefore we present a hybrid heuristic that uses an integer linear programming model of assignment and dispatch rules in a single machine. The assignment model is solved using the LINGO® optimizer, and is responsible for defining on which machines the tasks will be processed, considering the makespan minimization. To obtain the sequencing on each machine, aiming to minimize the fine for late delivery, a Python algorithm is developed, that applies dispatch rules. When applying the proposed heuristic to the scenario considered in Barbosa et al. (2021) the global optimal solution is not reached, but it requires significantly lower computational time for processing the algorithm when compared to the ILP model proposed by the author. It is noteworthy that when considering other random data scenarios, it was possible to reach the optimal solution obtained by the ILP model in 100% of the cases in which it was also possible to apply the ILP. In addition, was possible to solve problems with larger amounts of tasks. The study brings as a contribution a method capable of solving problems with a large number of tasks and machines, which, even does not guarantee reaching the optimal solution of the problem, requires low processing time of the algorithm.