Abordagens Exatas para o Problema de Escalonamento Robusto em Máquinas Paralelas

No Problema de Escalonamento de Máquinas Paralelas com minimização de makespan, existem um conjunto de tarefas com tempos de processamento e um conjunto de máquinas paralelas idênticas. Cada máquina pode processar no máximo uma tarefa por vez, e preempção não é permitida. O objetivo é escalonar todas as tarefas, minimizando o tempo máximo de conclusão. Em aplicações práticas, os tempos de processamento são frequentemente incertos. Este artigo aborda uma variante robusta do problema que considera tais incertezas. Adotamos o budget uncertainty set, limitando o número de tarefas que podem desviar de seus tempos de processamento nominais em cada máquina. Propomos duas abordagens exatas para resolver este Problema Robusto de Escalonamento de Máquinas Paralelas: uma formulação de fluxo em arcos e um procedimento de busca binária. Para avaliar o desempenho dos métodos propostos, os testamos em instâncias da literatura e comparamos os resultados com estudos anteriores, destacando as abordagens mais eficazes.