Integer Programming Model for the Timetabling Problem in University Courses
DOI:
https://doi.org/10.46661/rev.metodoscuant.econ.empresa.7354Keywords:
Timetabling, integer programming, classroom assignmentAbstract
Timetabling scheduling is classified as a combinatorial problem for which there are multiple solution alternatives, including the integer programming. However, the modeling of operational rules and the size of real problems makes its use not common compared to other techniques. This article proposes an integer programming model (IP) model, which addresses the scheduling problem made up of variables associated with time slots, subject and assigned teacher. Parameters such as the number of minimum and maximum time slots to be taught by the teacher, time slot time, teacher availability, available classrooms and estimated cost of dissatisfaction generated by the assigned schedule are also included. Seven hard and seventeen soft constraints are integrated into the model, which provide higher quality to the final schedule solution. The IP model is validated with a global objective function, in which experiments, and results obtained in real instances of the Universidad de la Salle (ULS) are reported. The new solution approach offers improvements in the final schedules, as well as the interaction with the users during its construction. Finally, in the conclusions of the work, the design and development of a system that provides support for decisions is discussed, referencing suggestions for future developments.
Downloads
References
Alnowaini, G. & Aljomai, A. A. (2021). Genetic Algorithm For Solving University Course Timetabling Problem Using Dynamic Chromosomes. 2021 International Conference of Technology, Science and Administration (ICTSA), 1-6. https://doi.org/10.1109/ICTSA52017.2021.9406539
Al-Yakoob, S. M. & Sherali, H. D. (2015). Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 61, 56-68. https://doi.org/10.1016/j.cor.2015.02.011
Asmuni, H. (2008). Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation [PhD Thesis]. University of Nottingham.
Assi, M., Halawi, B. & Haraty, R. A. (2018). Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem. Procedia Computer Science, 126, 899-906. https://doi.org/10.1016/j.procs.2018.08.024
Babaei, H., Karimpour, J. & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43-59. https://doi.org/10.1016/j.cie.2014.11.010
Barnhart, C., Lu, F. & Shenoi, R. (1998). Integrated Airline Schedule Planning. En G. Yu (Ed.), Operations Research in the Airline Industry (Vol. 9, pp. 384-403). Springer US. https://doi.org/10.1007/978-1-4615-5501-8_13
Battiti, R. & Tecchiolli, G. (1994). The Reactive Tabu Search. ORSA Journal on Computing, 6(2), 126-140. https://doi.org/10.1287/ijoc.6.2.126
Brucker, P., Drexl, A., Möhring, R., Neumann, K. & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3-41. https://doi.org/10.1016/S0377-2217(98)00204-5
Castillo-Salazar, J. A., Landa-Silva, D. & Qu, R. (2016). Workforce scheduling and routing problems: Literature survey and computational study. Annals of Operations Research, 239(1), 39-67. https://doi.org/10.1007/s10479-014-1687-2
Ceschia, S., Di Gaspero, L. & Schaerf, A. (2012). Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem. Computers & Operations Research, 39(7), 1615-1624. https://doi.org/10.1016/j.cor.2011.09.014
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
de Palma, A. & Lindsey, R. (2001). Optimal timetables for public transportation. Transportation Research Part B: Methodological, 35(8), 789-813. https://doi.org/10.1016/S0191-2615(00)00023-0
de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2), 151-162. https://doi.org/10.1016/0377-2217(85)90167-5
Dimopoulou, M. & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130(1), 202-213. https://doi.org/10.1016/S0377-2217(00)00052-7
Domenech, B. & Lusa, A. (2016). A MILP model for the teacher assignment problem considering teachers’ preferences. European Journal of Operational Research, 249(3), 1153-1160. https://doi.org/10.1016/j.ejor.2015.08.057
Feizi-Derakhshi, M.-R., Babaei, H. & Heidarzadeh, J. (2012, septiembre 27). A Survey of Approaches for University Course Timetabling Problem. Proceedings of 8th International Symposium on Intelligent and Manufacturing Systems (IMS 2012).
Feng, X., Lee, Y. & Moon, I. (2017). An integer program and a hybrid genetic algorithm for the university timetabling problem. Optimization Methods and Software, 32(3), 625-649. https://doi.org/10.1080/10556788.2016.1233970
Ghalia, M. B. (2008). Particle swarm optimization with an improved exploration-exploitation balance. 2008 51st Midwest Symposium on Circuits and Systems, 759-762. https://doi.org/10.1109/MWSCAS.2008.4616910
Goh, S. L., Kendall, G. & Sabar, N. R. (2019). Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. Journal of the Operational Research Society, 70(6), 873-888. https://doi.org/10.1080/01605682.2018.1468862
Gotlieb, C. C. (1962). The Construction of Class-Teacher Time-Tables. Information Processing, Proceedings of the 2nd IFIP Congress 1962, Munich, Germany, August 27 - September 1, 1962, 73-77.
Gülcü, A. & Akkan, C. (2020). Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research, 283(2), 630-646. https://doi.org/10.1016/j.ejor.2019.11.024
Hung, R. & Emmons, H. (1993). Multiple-shift Workforce Scheduling under the 3-4 compressed workweek with a Hierarchical Workforce. IIE Transactions, 25(5), 82-89. https://doi.org/10.1080/07408179308964318
Ismayilova, N. A., Sağir, M. & Gasimov, R. N. (2007). A multiobjective faculty–course–time slot assignment problem with preferences. Mathematical and Computer Modelling, 46(7-8), 1017-1029. https://doi.org/10.1016/j.mcm.2007.03.012
K. Alsmadi, M., M. Jaradat, G., Alzaqebah, M., ALmarashdeh, I., A. Alghamdi, F., Mustafa A. Mohammad, R., Aldhafferi, N. & Alqahtani, A. (2022). An Enhanced Particle Swarm Optimization for ITC2021 Sports Timetabling. Computers, Materials & Continua, 72(1), 1995-2014. https://doi.org/10.32604/cmc.2022.025077
LaGanga, L. R. & Lawrence, S. R. (2012). Appointment Overbooking in Health Care Clinics to Improve Patient Service and Clinic Performance. Production and Operations Management, 21(5), 874-888. https://doi.org/10.1111/j.1937-5956.2011.01308.x
Lewis, R. (2012). A time-dependent metaheuristic algorithm for post enrolment-based course timetabling. Annals of Operations Research, 194(1), 273-289. https://doi.org/10.1007/s10479-010-0696-z
McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K. & Qu, R. (2012). A new model for automated examination timetabling. Annals of Operations Research, 194(1), 291-315. https://doi.org/10.1007/s10479-011-0997-x
Nagata, Y. (2018). Random partial neighborhood search for the post-enrollment course timetabling problem. Computers & Operations Research, 90, 84-96. https://doi.org/10.1016/j.cor.2017.09.014
Nandhini, V. (2019). A Study on Course Timetable Scheduling and Exam Timetable Scheduling using Graph Coloring Approach. International Journal for Research in Applied Science and Engineering Technology, 7(3), 1999-2006. https://doi.org/10.22214/ijraset.2019.3368
Neumann, K., Schwindt, C. & Zimmermann, J. (2003). Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Functions. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-540-24800-2_3
Nothegger, C., Mayer, A., Chwatal, A. & Raidl, G. R. (2012). Solving the post enrolment course timetabling problem by ant colony optimization. Annals of Operations Research, 194(1), 325-339. https://doi.org/10.1007/s10479-012-1078-5
Ribić, S. & Konjicija, S. (2010, junio). A two phase integer linear programming approach to solving the school timetable problem | IEEE Conference Publication | IEEE Xplore. Proceedings of the ITI 2010, 32nd International Conference on Information Technology Interfaces. https://ieeexplore.ieee.org/abstract/document/5546473?casa_token=8NXEYLyhBJYAAAAA:DO9jDMq4-wyY2YxPPgfUUOGBO1n4ELugtWtLZzG3WTMrYB09TAvcnX6Nkr2N0KKYHvBoQ7CY0Ect7VU
Saldaña Crovo, A., Oliva San Martín, C. & Pradenas Rojas, L. (2007). Modelos de Programación Entera para un Problema de Programación de Horarios para Universidades. Ingeniare. Revista Chilena de Ingeniería, 15(3). https://doi.org/10.4067/S0718-33052007000300005
Scheepmaker, G. M., Goverde, R. M. P. & Kroon, L. G. (2017). Review of energy-efficient train control and timetabling. European Journal of Operational Research, 257(2), 355-376. https://doi.org/10.1016/j.ejor.2016.09.044
Selim, S. M. (1988). Split Vertices in Vertex Colouring and Their Application in Developing a Solution to the Faculty Timetable Problem. The Computer Journal, 31(1), 76-82. https://doi.org/10.1093/comjnl/31.1.76
Shakibaei, S., Alpkokin, P. & Black, J. A. (2021). A multi-objective optimisation model for train scheduling in an open-access railway market. Transportation Planning and Technology, 44(2), 176-193. https://doi.org/10.1080/03081060.2020.1868085
Sörensen, K. & Glover, F. W. (2013). Metaheuristics. En S. I. Gass & M. C. Fu (Eds.), Encyclopedia of Operations Research and Management Science (pp. 960-970). Springer US. https://doi.org/10.1007/978-1-4419-1153-7_1167
Tan, J. S., Goh, S. L., Kendall, G. & Sabar, N. R. (2021). A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications, 165, 113943. https://doi.org/10.1016/j.eswa.2020.113943
Torres-Ovalle, C., Montoya-Torres, J. R., Quintero-Araujo, C., Sarmiento Lepesqueur, A. & Castilla Luna, M. (2014). University Course Scheduling and Classroom Assignment. Ingenieria y Universidad, 18(1), 59-76. https://doi.org/10.11144/Javeriana.IYU18-1.phaa
Vermuyten, H., Lemmens, S., Marques, I. & Beliën, J. (2016). Developing compact course timetables with optimized student flows. European Journal of Operational Research, 251(2), 651-661. https://doi.org/10.1016/j.ejor.2015.11.028
Wang, P. & Goverde, R. M. P. (2019). Multi-train trajectory optimization for energy-efficient timetabling. European Journal of Operational Research, 272(2), 621-635. https://doi.org/10.1016/j.ejor.2018.06.034
Welsh, D. J. A. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85-86. https://doi.org/10.1093/comjnl/10.1.85
Wirasinghe, S. C. (2002). Initial Planning for Urban Transit Systems. En W. H. K. Lam & M. G. H. Bell (Eds.), Advanced Modeling for Transit Operations and Service Planning (pp. 1-29). Emerald Group Publishing Limited. https://doi.org/10.1108/9780585475226-001
Zacharias, C. & Pinedo, M. (2014). Appointment Scheduling with No-Shows and Overbooking. Production and Operations Management, 23(5), 788-801. https://doi.org/10.1111/poms.12065
Zhu, K., Li, L. D. & Li, M. (2021). School Timetabling Optimisation Using Artificial Bee Colony Algorithm Based on a Virtual Searching Space Method [Preprint]. Mathematics and Computer Science. https://doi.org/10.20944/preprints202111.0215.v1
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Carlos A. Arango, Msc, Heriberto Felizzola, Msc, Andrés Hualpa, Msc., Paula Gomez, Eng., Carlos Mora, Eng.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Submission of manuscripts implies that the work described has not been published before (except in the form of an abstract or as part of thesis), that it is not under consideration for publication elsewhere and that, in case of acceptance, the authors agree to automatic transfer of the copyright to the Journal for its publication and dissemination. Authors retain the authors' right to use and share the article according to a personal or instutional use or scholarly sharing purposes; in addition, they retain patent, trademark and other intellectual property rights (including research data).
All the articles are published in the Journal under the Creative Commons license CC-BY-SA (Attribution-ShareAlike). It is allowed a commercial use of the work (always including the author attribution) and other derivative works, which must be released under the same license as the original work.
Up to Volume 21, this Journal has been licensing the articles under the Creative Commons license CC-BY-SA 3.0 ES. Starting from Volume 22, the Creative Commons license CC-BY-SA 4.0 is used.