Repositório Institucional da UFPB

Tipo:	Dissertação
Título:	Metaheurística Híbrida GRASP e Busca Tabu Aplicada ao Problema de Escalonamento de Tarefas
Autor(es):	Cunha, Cláudia Rossana
Primeiro Orientador:	Cabral, Lucídio dos Anjos Formiga
Resumo:	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.
Abstract:	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.
Palavras-chave:	Escalonamento de processos GRASP Busca Tabu Job Shop Scheduling GRASP Tabu Search
CNPq:	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	BR
Editor:	Universidade Federal da Paraí­ba
Sigla da Instituição:	UFPB
Departamento:	Informática
Programa:	Programa de Pós Graduação em Informática
Citação:	CUNHA, Cláudia Rossana. Metaheurística Híbrida GRASP e Busca Tabu Aplicada ao Problema de Escalonamento de Tarefas. 2010. 67 f. Dissertação (Mestrado em Informática) - Universidade Federal da Paraí­ba, João Pessoa, 2010.
Tipo de Acesso:	Acesso aberto
URI:	https://repositorio.ufpb.br/jspui/handle/tede/6055
Data do documento:	16-Jul-2010
Aparece nas coleções:	Centro de Informática (CI) - Programa de Pós-Graduação em Informática

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.