Resumo |
Este estudo aborda a variante de um clássico problema combinatório: o Problema de Alocação de Salas da Universidade Federal de Viçosa – Campus Rio Paranaíba. A complexidade do problema de alocação de horários é largamente conhecida devido a necessidade de conciliar diversas variáveis e é também determinada pelas exigências técnicas e administrativas de cada instituição. Desta forma, faz-se necessário automatizar o processo de alocação e recorrer a estratégias computacionais que conformem soluções de qualidade e baixo custo. Em função de situações como essa, uma atenção especial vem sendo dada à automação deste problema. Sendo o problema considerado NP-difícil, ele é normalmente abordado através de técnicas heurísticas. Dentre essas técnicas, destacam-se as chamadas metaheurísticas, as quais são providas de mecanismos para escapar de ótimos locais, contrariando as heurísticas convencionais. Dentre as metaheurísticas que vêm sendo aplicadas com relativo sucesso em problemas desta natureza, utiliza-se: Simulated Annealing, Busca Tabu e Programação Genética. Para tanto, neste caso, o método de busca local que aceita movimentos de piora para escapar de ótimos locais, Simulated Annealing, foi utilizado, uma vez que é de fácil implementação e apresenta um bom desempenho na resolução de problemas de otimização. O estudo contou ainda com análises baseadas na Busca Tabu, técnica considerada adequada para a resolução de problemas desta natureza. Ao se buscar a solução automatizada para esta abordagem, confeccionou-se um modelo de otimização, com o intuito de minimizar a distância percorrida pelos alunos e uma melhor distribuição das salas de aula, respeitando suas respectivas capacidades. Foi possível se atentar à fatores pedagógicos e questões logísticas consideradas pela instituição de ensino. Acredita-se que a formulação matemática apresentada poderá sanar problemas de outras Instituições de ensino, além de ser capaz de gerar soluções de alta qualidade, quando comparada ao método manual. |