Alocação de salas usando fluxo máximo de custo mínimo em grafos bipartidos
Resumo
Este artigo apresenta uma solução para o problema de alocação de salas no âmbito da UFG. O problema consiste em, dado um conjunto de pedidos para uso de salas e um conjunto de salas disponíveis, otimizar a ocupação das salas garantindo que cada sala tenha capacidade suficiente para que as pessoas fiquem sentadas. Com o aumento de cursos de graduação e pós-graduação e por conseguinte de disciplinas nos campus da UFG, alocar as disciplinas em salas tem se tornando um desafio e consumindo muito tempo pois é feito de forma manual. Este artigo oferece uma solução para o problema usando fluxo máximo de custo mínimo em grafos bipartidos e analisa a alocação atual versus a alocação feita pelo algoritmo, provendo uma alternativa para a alocação manual.
Referências
Burke, E. e Newall, J. (1999). A multistage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, 3(1):63–74.
Even, S., Itai, A., e Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. Em 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), páginas 184–193.
Foxley, E. e Lockyer, K. (1968). The construction of examination timetables by computer. The Computer Journal, 11(3):264–268.
Kogler, J. (2018). Minimum-cost flow - successive shortest path algorithm. https://cp-algorithms.com/graph/min_cost_flow.html, Acesso em Julho de 2020.
Lemos, A., Melo, F. S., Monteiro, P. T., e Lynce, I. (2019). Room usage optimization in ti-metabling: A case study at Universidade de Lisboa. Operations Research Perspectives, 6:100092.
Netto, J. (2020). TCC em ciência da computação no INF/UFG: Implementação do problema de alocação de salas na UFG em Python. https://github.com/joaobnetto/ICPython, Acesso em Agosto 2020.
Sales, E. S., Müller, F. M., e Simonetto, E. O. (2015). Solução do problema de alocação de salas utilizando um modelo matemático multi-ı́ndice. Porto de Galinhas, Pernambuco - PE. Simpósio Brasileiro de Pesquisa Operacional.
Smith, O. P. (2020). Sistema de distribuição de Salas. https://files.cercomp.ufg.br/weby/up/90/o/Tutorial_SiDS_v3.14.pdf, Acesso em Julho 2020.
van Rossum, G., Warsaw, B., e Coghlan, N. (2001). Style guide for python code. https://www.python.org/dev/peps/pep-0008/, Acesso em Agosto 2020.
