Experiências com Ssimulated Annealing e Busca Tabu na resolução do problema de alocação de salas.
Data
2002
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Este trabalho trata do problema de alocação de salas. Uma vez que este problema é NP-difícil, muitos métodos heurísticos têm sido propostos para resolvê-lo. Simulated Annealing (SA) e Busca Tabu (BT) são exemplos de tais métodos que têm sido aplicados com sucesso na resolução deste problema. Esta classe de heurísticas encontra uma boa solução melhorando uma alocação inicial através de técnicas de pesquisa em vizinhança. Contrariamente às heurísticas convencionais, SA e BT permitem movimentos de piora como forma de escapar de ótimos locais. Neste artigo relata-se uma experiência com a utilização destas técnicas e propõe-se uma técnica híbrida SA+TS, a qual combina as características mais apropriadas de SA e BT de forma a obter um procedimento mais eficaz. A eficiência dessa combinação é avaliada comparando-a com as versões puras dos métodos envolvidos.
Descrição
Palavras-chave
Metaheurística, Otimização combinatória, Classroom assignment problem, Metaheuristics, Combinatorial optimization
Citação
SOUZA, M. J. F.; MARTINS, A. X.; ARAÚJO, C. R. Experiências com Simulated Annealing e Busca Tabu na resolução do problema de alocação de salas. In. XXXIV Simpósio Brasileiro de Pesquisa Operacional, 34., 2002. Rio de Janeiro. Anais... Rio de Janeiro: SOBRAPO, 2002. p. 1100-1110. Disponível em: <http://www.iceb.ufop.br/decom/prof/marcone/Disciplinas/InteligenciaComputacional/SBPO-2002-PAS-TC0106.pdf>. Acesso em: 11 out. 2012