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

Authors

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

Keywords:

UCTP, Planning, Optimization

Abstract

The task of class scheduling in university settings demands significant organizational effort due to its combinatorial nature. This complexity has been amplified with the adoption of various teaching modalities as online programs gain traction.

While a wide range of academic works aimed at solving this type of problem, commonly known as the University Course Timetabling Problem (UCTP), can be found in the literature, there are few references to any that simultaneously consider the different class delivery modalities currently in use. Moreover, among the published works to solve UCTP problems, models based on Mixed-Integer Linear Programming (MILP) stand out due to their versatility and adaptability to different situations. However, solving these models is computationally intensive.

In the present work, a MILP type model adapted to class scheduling under the curriculum planning approach, typically used in the Argentine university context, is developed, where simultaneous planning of face-to-face and synchronous virtual classes is required. Concurrently, a hybrid algorithm is implemented for solving this model within suitable time frames for its practical use.

Downloads

Download data is not yet available.

References

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