Heurísticas de pesquisa local para problemas de máquina única

O escalonamento é uma das decisões mais importantes no funcionamento de uma linha de produção. No âmbito desta dissertação foi realizada uma descrição do problema do escalonamento, identificando alguns métodos para a optimização dos problemas de escalonamento. Foi realizado um estudo ao caso do problema de máquina única através do teste de várias instâncias com o objectivo de minimizar o atraso pesado, aplicando uma Meta-Heurística baseada na Pesquisa Local e dois algoritmos baseados no SB. Os resultados obtidos reflectem que os algoritmos baseados no SB apresentaram resultados mais próximos do óptimo, em relação ao algoritmo baseado na PL. Os resultados obtidos permitem sustentar a hipótese de não existirem algoritmos específicos para os problemas de escalonamento. A melhor forma de encontrar uma solução de boa qualidade em tempo útil é experimentar diferentes algoritmos e comparar o desempenho das soluções obtidas.

Scheduling is one of the most important decisions to be made in the operation of a production line. In this dissertation the scheduling problem is explored, identifying optimization methods used to solve scheduling problems. It was conducted a study to the single machine problem, in which minimizing the weighted tardiness was the objective. It was tested by solving different instances of the problem. The results were obtained applying a Local-Search Meta-Heuristic and two algorithms based on the Shifting Bottleneck procedure. The results obtained with the SB based algorithms present solutions closer to the optimum, when compared with the results obtained with the LS Meta-Heuristic. The results obtained support the hypothesis that there are no specific algorithms for scheduling. The best way to achieve a quality result in a time limited situation is to implement different algorithms and evaluate the performance of each solution.