Aplicação de emparelhamento em grafos bipartidos no problema de alocação de salas

Abstract

O Problema de Alocação de Salas ocorre em várias instituições ao redor do mundo, e nocampus do Gama da Universidade de Brasília não é diferente. O problema consiste emalocar turmas à determinadas salas seguindo um conjunto de requisitos. Antes do início deum novo período letivo, a instituição é encarregada de disponibilizar a relação das turmasque serão ofertadas juntamente com seus respectivos locais e horários. Visando aprimoraresse processo, o trabalho tem por objetivo desenvolver uma solução automatizada queresolva o problema por inteiro ou em partes respeitando as demandas do campus. Asolução consistiu em modelar o problema de alocação de salas como um problema deemparelhamento em grafos bipartidos, de forma com que o grafo modelado atendessetodas as restrições impostas pela formulação do problema. O emparelhamento foi geradoatravés do algoritmo de Hopcroft-Karp que obteve um alto índice de turmas e salasemparelhadas. Foram utilizados dados reais da instituição para a validação da propostae, a partir dos resultados, foram levantadas discussões acerca da viabilidade da solução ecomo a mesma poderia ser aprimorada.