Modelo lineal de programación entera mixta para la programación óptima de clases y aulas

Rafael Roque Alejandro Vargas; Carlos Onofre Ponce; Walter Fernando Bogorni

doi:10.56487/9emjsv45

Autores

Rafael Roque Alejandro Vargas Universidad Adventista del Plata https://orcid.org/0009-0000-9340-2735
Carlos Onofre Ponce Universidad Adventista del Plata https://orcid.org/0009-0002-8543-7836
Walter Fernando Bogorni Universidad Adventista del Plata https://orcid.org/0009-0006-3015-0271

DOI:

https://doi.org/10.56487/9emjsv45

Palavras-chave:

UCTP — Planejamento — Otimização

Resumo

A tarefa de agendar aulas em ambientes universitários exige um esforço organizacional significativo devido à sua
natureza combinatória. Essa complexidade foi ampliada com a adoção de diversas modalidades de ensino, à medida
que os programas online ganham popularidade.
Embora seja possível encontrar na literatura uma ampla gama de trabalhos acadêmicos voltados à resolução desse
tipo de problema, comumente conhecido como Problema de Programação Horária de Cursos Universitários
(UCTP, na sigla em inglês), existem poucas referências àqueles que consideram simultaneamente as diferentes modalidades
de oferta de aulas atualmente em uso. Além disso, entre os trabalhos publicados para resolver problemas
UCTP, destacam-se os modelos baseados em Programação Linear Inteira Mista (MILP) devido à sua versatilidade e
capacidade de adaptação a diferentes situações. No entanto, resolver esses modelos é computacionalmente intenso.
No presente trabalho, desenvolve-se um modelo MILP adaptado ao agendamento de aulas sob a abordagem de
planejamento curricular. Ao considerar o corpo discente de forma agregada, o modelo melhora a tratabilidade
computacional, permitindo o planejamento simultâneo de aulas presenciais e virtuais síncronas. Paralelamente, implementa-se um algoritmo híbrido, alcançando pelo menos uma aceleração computacional de 100 vezes e garantindo
a viabilidade do modelo dentro de prazos adequados para uso prático.

Downloads

Os dados de download ainda não estão disponíveis.

Referências

Arratia-Martinez, N. M., Maya-Padron, C., & Avila-Torres, P. A. (2021). University course timetabling problem with professor assignment. Mathematical Problems in Engineering, 2021. https://doi.org/10.1155/2021/6617177

Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers and Industrial Engineering, 86, 43–59. https://doi.org/10.1016/j.cie.2014.11.010

Barnhart, C., Bertsimas, D., Delarue, A., & Yan, J. (2022). Course scheduling under sudden scarcity: Applications to pandemic planning. Manufacturing and Service Operations Management, 24(2), 727–745. https://doi.org/10.1287/msom.2021.0996

Borchani, R., Elloumi, A., & Masmoudi, M. (2017). Variable neighborhood descent search based algorithms for course timetabling problem: Application to a Tunisian University. Electronic Notes in Discrete Mathematics, 58, 119–126. https://doi.org/10.1016/j.endm.2017.03.016

Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557–581. https://doi.org/10.1016/S0377-2217(98)00364-6

Burke, E. K., De Causmaecker, P., Berghe, G. Vanden, & Van Landeghem, H. (2004). The state of the art of nurse scheduling. Journal of Scheduling, 7(6), 441–499.

Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., & Woodward, J. R. (2010). A classification of hyper-heuristic approaches. In Handbook of Metaheuristics (Issue May). https://doi.org/10.1007/978-1-4419-1665-5

Corne, D., Ross, P., & Fang, H. (1994). Fast practical evolutionary timetabling. Proceedings of the AISB Workshop on Evolution- Ary Computation, 708.

Daskalaki, S., & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160(1), 106–120. https://doi.org/10.1016/j.ejor.2003.06.023

Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117–135. https://doi.org/10.1016/S0377-2217(03)00103-6

Davison, M., Kheiri, A., & Zografos, K. G. (2025). Modelling and solving the university course timetabling problem with hybrid teaching considerations. Journal of Scheduling, 28(2), 195–215. https://doi.org/10.1007/s10951-024-00817-w

Di Gaspero, L., & Schaerf, A. (2001). Tabu search techniques for examination timetabling. In E., Burke, & W. Erben (Eds.), Practice and theory of automated timetabling III (pp. 104–117). Springer. https://doi.org/10.1007/3-540-44629-X_7

Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2–3), 243–278. https://doi.org/10.1016/j.tcs.2005.05.020

Hart, W. E., Watson, J. P., & Woodruff, D. L. (2011). Pyomo: Modeling and solving mathematical programs in Python. Mathematical Programming Computation, 3(3), 219–260. https://doi.org/10.1007/s12532-011-0026-8

Hmer, A., & Mouhoub, M. (2010). Teaching assignment problem solver. In N. García-Pedrajas, F. Herrera, C. Fyfe, J. M. Benítez, & M. Ali (Eds.), Trends in applied intelligent systems (Lectures Notes in Computer Science, Vol. 6097, pp. 298–307). Springer. https://doi.org/10.1007/978-3-642-13025-0_32

Lemos, A., Melo, F. S., Monteiro, P. T., & Lynce, I. (2019). Room usage optimization in timetabling: A case study at Universidade de Lisboa. Operations Research Perspectives, 6(December 2018), 100092. https://doi.org/10.1016/j.orp.2018.100092

Lemos, A., Monteiro, P. T., & Lynce, I. (2020). Minimal perturbation in university timetabling with maximum satisfiability. In E. Hebrard, & N. Musliu (Eds.), Integration of constraint programming, artificial intelligence, and operations research (Lecture Notes in Computer Science, Vol. 12296, pp. 317–333). Springer. https://doi.org/10.1007/978-3-030-58942-4_21

Lewis, R., Paechter, B., & McCollum, B. (2007). Post enrollment based course timetabling: A description of the problem model used for track two of the second international timetabling competition (Cardiff Working Papers in Accounting and Finance No. A2007/3). Cardiff Business School, Cardiff University.

Méndez-Díaz, I., Zabala, P., & Miranda-Bront, J. J. (2016). An ILP based heuristic for a generalization of the post-enrollment course timetabling problem. Computers & Operations Research, 76, 195–207. https://doi.org/10.1016/j.cor.2016.06.018.

Meyers, C., & Orlin, J. B. (2006). Very large-scale neighborhood search techniques in timetabling problems. In E. K. Burke, & H. Rudová (Eds.), Practice and theory of automated timetabling VI (Lecture Notes in Computer Science, Vol. 3867, pp. 24–39). Springer. https://doi.org/10.1007/978-3-540-77345-0_2

Mirhassani, S. A. (2006). A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175(1), 814–822. https://doi.org/10.1016/j.amc.2005.07.039

Müller, T., Rudová, H., & Müllerová, Z. (2018, August 28–31). University course timetabling and international timetabling competition 2019. In Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2018) (pp. 5–31).

National Center for Education Statistics (NCES). (2023). Student enrollment: What is the percent ofstudents enrolled in distance education courses in postsecondary institutions in the fall? NCES. https://nces.ed.gov/ipeds/TrendGenerator/app/build-table/2/42?cid=85&rid=6

Oladejo, N. K., Abolarinwa, A., Salawu, S. O., Bamiro, M. O., Lukman, A. F., & Bukari, H. I. (2019). Application of optimization principles in classroom allocation using linear programming. International Journal of Mechanical Engineering and Technology, 10(1), 874–885.

Petrovic, S., & Bykov, Y. (2003). A multiobjective optimisation technique for exam timetabling based on trajectories. In E. Burke, & P. De Causmaecker (Eds.), Practice and theory of automated timetabling IV (Lecture Notes in Computer Science, Vol. 2740, pp. 181–194). https://doi.org/10.1007/978-3-540-45157-0_12

Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M. (2015). Integer programming methods for largescale practical classroom assignment problems. Computers and Operations Research, 53, 42–53. https://doi.org/10.1016/j.cor.2014.07.012

Prabodanie, R. A. R. (2017). An integer programming model for a complex university timetabling problem: A case study. Industrial Engineering and Management Systems, 16(1), 141–153. https://doi.org/10.7232/iems.2017.16.1.141

Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1), 55–89. https://doi.org/10.1007/s10951-008-0077-5

Raman, R., & Grossmann, I. E. (1991). Relation between MILP modelling and logical inference for chemical process synthesis. Computers and Chemical Engineering, 15(2), 73–84. https://doi.org/10.1016/0098-1354(91)87007-V

Thompson, J. M., & Dowsland, K. A. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operations Research, 63, 105–128. https://doi.org/10.1007/BF02601641

Wren, A. (1996). Scheduling, timetabling and rostering – A special relationship? In E. Burke, & P. Ross (Eds.), Practice and theory of automated timetabling (Lecture Notes in Computer Science, Vol. 1153, pp. 46–75). https://doi.org/10.1007/3-540-61794-9_51