Resumo
A cada semestre, as universidades ao redor do mundo enfrentam um desafio ao planejar a oferta de disciplinas, considerando as restrições relacionadas ao espaço físico e ao corpo docente. Como resultado, foram desenvolvidos diversos softwares especializados para automatizar esse processo e chegar a uma solução dentro de um prazo razoável. Este trabalho propõe a criação de um software desse tipo para uma instituição de ensino brasileira, uma vez que a solução atualmente utilizada, além de ser paga e consumir um tempo excessivo para ser concluída, nem sempre é viável, dependendo de vários ajustes manuais. Utilizando a linguagem de programação Python 3.8 em conjunto com o CPLEX 20.1.0 da IBM, foi possível implementar um modelo de programação linear inteira. Uma interface simples e intuitiva foi desenvolvida para permitir o uso da ferramenta pela secretaria da instituição. O programa foi testado com dados do primeiro semestre de 2023, resultando em não somente a obtenção de uma solução viável como também em uma redução no tempo de processamento de 95%.
Palavras-chave: USTP. Programação Linear. Pesquisa Operacional.
Abstract
Utilising linear programming as a means of scheduling classes of a college in Minas Gerais
Each semester, universities around the world face the challenge of planning course offerings while considering constraints related to physical space and faculty availability. As a result, various specialized software solutions have been developed to automate this process and provide a solution within a reasonable timeframe. This study proposes the development of such software for a Brazilian educational institution, as the currently used solution, besides being paid and taking an excessive amount of time to complete, does not always find a feasible solution, requiring multiple manual adjustments. Using the Python 3.8 programming language in conjunction with IBM's CPLEX 20.1.0, we implemented an integer linear programming model. A simple and intuitive interface was developed to allow the institution's administrative office to use the tool. The program was tested with data from the first semester of 2023, resulting not only in a feasible solution but also in a 95% reduction in processing time.
Keywords: UTSP. Linear Programming. Operations Research.
Referências
ARENALES, M. et al. Pesquisa Operacional. Rio de Janeiro: ABEPRO, 2011.
BABAEI, Hamed; KARIMPOUR, Jaber; HADIDI, Amin. A survey of approaches for
University course timetabling problem. Computers & Industrial Engineering, v. 86,
p. 43-59, 2015.
ANDRADE, P. R. L.; SCARPIN, C. T.; STEINER, M. T. A. Geração da grade horária do curso de engenharia de produção da ufpr através de Programação linear binária. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 2012. Anais [...] Rio de Janeiro: SBPO, 2012
EVEN, S.; ITAI, A.; SHAMIR, A. On the complexity of timetable and multicommodity flow problems. Siam Jounal of Computing, 5(4), 691–703, 1976.
GERHARDT, T. E.; SILVEIRA, D. T. Métodos de Pesquisa. 1. ed. Porto Alegre: Editora da UFRGS, 2009.
MOREIRA, J. P.; COLNAGO, G. Otimização de grade de horários de professores e disciplinas: refinamento das soluções por penalizações na função objetivo. Disponível em: https://proceedings.science/sbpo/sbpo-2019/trabalhos/otimizacao-de-grade-de-horarios-de- professores-e-disciplinas-refinamento-das-sol?lang=pt-br. Acesso em: 31 abr. 2023.
POULSEN, C. J. B.; BUCCO, G. B.; BANDEIRA, D. L. Uma proposta de programação matemática para o university course timetabling problem. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL,. XLV, 2020. Anais [...] Salvador: SBPO, set. 2014, p. 979– 990
QUEIROZ, R. S; MESQUITA, L. M. O.; LIMA, V. G.; MARQUES, C. A. N.; FRUTUOSO, R. L. Proposta de um modelo para o school timetabling problem em um instituto federal de educação, ciência e tecnologia. In: Simpóso Brasileiro de Pesquisa Operacional, LII, 2020. Anais [...] João Pessoa: SBPO, set. 2020.
SCHAERF, Andrea. A survey of automated timetabling. Artificial intelligence review, v. 13, n. 2, p. 87- 127, 1999.
SOUZA FILHO, E. M.; GOMES, Carla Regina. Programação do quadro de horários de disciplinas de uma universidade via programação inteira. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, XLI, 2009. Anais [...] Porto Seguro: SBPO, p. 357-368, 2009.
TAN, Joo Siang et al.. A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications, v. 165, p. 113943, 2021.