Problema de alocação de sala de aula

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 Busca Tabu, é um método de busca local, com uma estrutura de memória que armazena as soluções geradas. Ela explora o espaço de solução, movendo-se de uma solução para outra que seja seu melhor vizinho, aceitando movimentos de piora (quando não há possibilidades de melhora) para escapar de ótimos locais.

A cada iteração, a solução atual s muda para outra que seja sua vizinha no espaço de busca, isto é, para uma solução s’ que difere de s por uma modificação. Partindo de uma solução inicial s0, um