Metaheurística Híbrida GRASP e Busca Tabu Aplicada ao Problema de Escalonamento de Tarefas

Este trabalho aborda o problema de escalonamento de tarefas (Job Shop Scheduling) através da combinação das metaheurísticas GRASP e Busca Tabu. O estudo consiste em utilizar o GRASP na fase de construção da solução inicial, sugerindo, para tanto, um procedimento específico baseado no algoritmo de Coffman Gramah. Tal procedimento foi o grande diferencial deste trabalho, visto que oferece uma solução inicial qualitativamente superior, permitindo a redução do tempo de busca local, onde foi utilizada a metaheurística Busca Tabu, a qual demonstrou proporcionar melhores resultados, comparando-se com outras metaheurísticas que seguem a mesma base estrutural. A combinação GRASP e Busca Tabu foi avaliada sob duas implementações diferenciadas, sendo uma com a Busca Tabu em sua forma mais simplificada e outra com a Busca Tabu desenvolvendo um processo de busca otimizada com o auxílio de um modelo matemático , a qual demonstrou grandes progressos quanto ao tempo de processamento e a obtenção de resultados. Os resultados computacionais obtidos, quando comparados com os existentes na literatura, mostraram que a combinação GRASP e Busca Tabu é capaz de produzir boas soluções.This work approaches the problem of the tasks scheduling (Job Shop Scheduling) through the combination of the GRASP and Tabu Search metaheuristics. The study consists of using the GRASP (Greedy Randomized Adaptive Search Procedure) in the construction phase of the initial solution, suggesting for that, a specific procedure based on Coffman Gramah algorithm. However, such procedure was the great differential in this study, since it offers an initial solution qualitatively better, what allows the reduction of the local search time, where it was utilized the Tabu Search metaheuristic in the local search phase, which provided best results when it was compared with other metaheuristics that have the same structural base. The combination GRASP and Tabu Search were evaluated under two differentiated implementations, being one with Tabu Search in its form more simplified and another one with Tabu Search developing a process of optimized search, using an aditional mathematical model, which demonstrated great advancements in relation at processing time and the obtained results. The computational results, when compared with the existing ones in literature, they had shown that GRASP and Tabu Search combination are capable to produce good solutions