Utilização de métodos meta-heurísticos para a resolução do problema de máquinas paralelas com restrição de recursos

Abstract

O problema de máquinas paralelas idênticas com restrição de recursos consiste em determinar a alocação e o sequenciamento de tarefas em máquinas paralelas, considerando que tarefas que compartilham um mesmo recurso não podem ser processadas simultaneamente. Trata-se de um problema NP-difícil, cuja elevada complexidade computacional dificulta a obtenção de soluções ótimas por métodos exatos em instâncias de maior porte. Nesse contexto, este trabalho teve como objetivo implementar, calibrar e comparar as meta-heurísticas Greedy Randomized Adaptive Search Procedure (GRASP), Iterated Local Search (ILS), Variable Neighborhood Search (VNS) e Simulated Annealing (SA) para a resolução desse problema, considerando a minimização do makespan. Inicialmente, foi realizada a calibração dos parâmetros por meio de planejamento de experimentos. Em seguida, os algoritmos foram avaliados utilizando instâncias da literatura e um conjunto de instâncias geradas especificamente para este trabalho, contemplando diferentes quantidades de tarefas, máquinas e recursos compartilhados. Os resultados demonstraram que todas as meta-heurísticas produziram soluções de elevada qualidade, alcançando o limite inferior em diversas instâncias e apresentando baixos desvios em relação a esse limite nos demais casos. Na comparação com um modelo de Programação Linear Inteira Mista resolvido pelo Gurobi, as meta-heurísticas encontraram soluções equivalentes para as instâncias de pequeno porte em tempos computacionais significativamente inferiores. Entre os métodos avaliados, o Simulated Annealing apresentou o melhor desempenho global, destacando-se pelos menores desvios percentuais médios em relação ao limite inferior, pelos menores tempos computacionais e pela menor variabilidade dos resultados entre as 30 execuções, especialmente nas instâncias de médio e grande porte.