1.INTRODUÇÃO.

O Problema de Alocação de Salas de Aula consiste em alocar aulas, com horários de início e término previamente programados, a um número fixo de salas. Esse é um problema típico que surge nas instituições universitárias antes do início dos semestres letivos, sendo um problema clássico de otimização combinatória pertencente à classe NP-hard (não polinomial difícil) em que a determinação da solução ótima do problema, em período de tempo aceitável, não é uma tarefa simples.
Os métodos empregados na resolução destes problemas chegam a consumir tempos de ordem exponencial, portanto, a utilização exclusiva de algoritmos exatos se torna praticamente inviável, fazendo necessário recorrer a outras técnicas na tentativa de se obter uma solução próxima à solução ótima e em tempos computacionais baixos.

O presente trabalho propõe resolver o problema de alocação de salas de aula com um algoritmo heurístico, tendo como objetivo obter soluções com alto grau de satisfação e baixo custo computacional. O algoritmo desenvolvido é baseado na metaheurística Busca Tabu tendo em vista seu desempenho satisfatório na resolução de várias classes de problemas de programação de horários.

2. BUSCA TABU.

A busca Tabu foi proposta por Fred Glover em 1986 para problemas de programação inteira, porém a comprovação de sua eficiência só surgiu após alguns anos da definição de sua forma atual, sendo hoje utilizada em diferentes áreas e campos do conhecimento.

De forma simplificada, a