Desenvolvimento e aplicação de algoritmos heurísticos ao problema de alocação de espaço físico em universidade

Abstract

Resumo: O Problema de Alocação de Salas em uma instituição acadêmica consiste em distribuir turmas para as devidas salas, respeitando uma série de restrições operacionais e preferências. Neste trabalho é proposta a aplicação de três algoritmos heurísticos. O primeiro consiste na resolução sucessiva de problemas de designação e o segundo na resolução sucessiva de problemas de designação com gargalo, ambos com três fases cada. O terceiro algoritmo é baseado na meta-heurística Busca em Vizinhança Variável. Os testes foram realizados com dados reais de uma universidade e os resultados alcançados pelos três algoritmos foram comparados entre si e com resultados utilizados pela instituição. O primeiro algoritmo, baseado no problema de designação, apresentou os melhores resultados em relação à qualidade da solução e eficiência

Abstract: The Classroom Assignment Problem in an academic institution consists in distributing classes for the due rooms, respecting a series of operational restrictions and preferences. In this work, the application of three heuristic algorithms is proposed. The first one consists in a successive resolution of assignment problem and the second in a successive resolution of bottleneck assignment problem, both with three phases each. The third algorithm is based on Variable Neighborhood Search metaheuristic. The tests were realized with real data of a public university and the results reached by the three algorithms were compared among themselves and with those used by the institution. The first algorithm, based on the assignment problem, presented the best results in relation to the quality of the solution and efficiency