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/as

Rafael 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

Palabras clave:

UCTP — Planificación — Optimización

Resumen

La tarea de programar clases en entornos universitarios exige un esfuerzo organizativo debido a su naturaleza combinatoria.
Esta complejidad se ha visto amplificada con la adopción de diversas modalidades de enseñanza, a medida que los programas en línea ganan popularidad.
Aunque en la literatura se pueden encontrar numerosos trabajos académicos dirigidos a resolver este tipo de problema, comúnmente conocido como el problema de programación horaria de cursos universitarios (UCTP, por sus siglas en inglés), existen pocas referencias a aquellos que consideren simultáneamente las distintas modalidades de impartición de clases actualmente en uso. Además, entre los trabajos publicados para resolver problemas UCTP, destacan los modelos basados en programación lineal entera mixta (MILP) debido a su versatilidad y capacidad de adaptación a diferentes situaciones. No obstante, resolver estos modelos requiere un alto poder computacional.
En el presente trabajo se desarrolla un modelo MILP adaptado a la programación de clases bajo un enfoque de planificación curricular. Al considerar el alumnado de manera agregada, el modelo mejora la tratabilidad computacional, permitiendo la planificación simultánea de clases presenciales y virtuales sincrónicas. Paralelamente, se implementa un algoritmo híbrido, logrando al menos una aceleración computaciones de 100 veces y asegurando la viabilidad del modelo dentro de plazos adecuados para su uso práctico.

Descargas

Los datos de descarga aún no están disponibles.

Referencias

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