A mathematical programming model for high school timetabling problem

Main Article Content

Juan Camilo Marin Ángel
Pablo Andrés Maya Duque https://orcid.org/0000-0002-5348-8615

Keywords

Educational timetabling, Mathematical programming

Abstract

This paper presents a mathematical programing model that supports the design of timetables of classes in primary and secondary educational institutions, allowing the decision maker to take into account the constraints and variables that are commonly associated to this problem. Our model diers from most of those in the literature as the objective function aims at maximizing the number of blocks, two consecutive hours of lecture devoted to the same subject, which favors the learning process, optimizes teachers' agendas by reducing idle times and reduces cost and contractual diculties.  The model is validated using a real instance of a middle size institution for which the current timetable is considerably improved. Additionally, computational experiments with larger instances were carried on in order to test the capacity of the model for which promising results were obtained. 

Downloads

Download data is not yet available.
Abstract 825 | PDF (Español) Downloads 560 HTML (Español) Downloads 306

References

[1] M. G. C. y Erwin Pardo Quiroga y Roberto Salas Ruiz, “Problema del school timetabling y algoritmos genéticos: una revisión,” Vínculos, vol. 10,no. 2, pp. 259–276, 2014. [Online]. Available:http://revistas.udistrital.edu.co/ojs/index.php/vinculos/article/view/6478 48, 53, 54

[2] G. M. Bejarano Nicho, “Planificación de horarios del personal de cirugía de un hospital del estado aplicando algoritmos genéticos (time tabling problem),”Pontificia Universidad Católica del Perú, Lima, Tech. Rep., 2010. 48

[3] P. A. Maya Duque, V. Gutiérrez Gutiérrez, K. J. Pinto Bohorquez, J. I.Arango Rúa, and T. Rúa, “Diseño y validación de un modelo matemáticode apoyo a la toma de decisiones en el proceso de asignación de aulas,”Universidad de Antioquia, Medellín, Tech. Rep., 2008. 49

[4] G. H. Fonseca and H. G. Santos, “Variable neighborhood search based algorithms for high school timetabling,” Computers & Operations Research,vol. 52, Part B, pp. 203 – 208, 2014, recent advances in Variable neighborhood search. [Online].
Available:http://dx.doi.org/10.1016/j.cor.2013.11.012 49

[5] S. Kristiansen, M. Sørensen, and T. R. Stidsen, “Integer programming for the generalized high school timetabling problem,” Journal of Scheduling, vol. 18, no. 4, pp. 377–392, 2014. [Online]. Available:http://dx.doi.org/10.1007/s10951-014-0405-x 53, 55

[6] Z. Lü and J.-K. Hao, “Adaptive tabu search for course timetabling,”European Journal of Operational Research, vol. 200, no. 1, pp. 235 – 244,2010. [Online]. Available: http://dx.doi.org/10.1016/j.ejor.2008.12.007 53


[7] I. V. Katsaragakis, I. X. Tassopoulos, and G. N. Beligiannis, “Acomparative study of modern heuristics on the school timetabling problem,” Algorithms, vol. 8, no. 3, pp. 723–742, 2015. [Online]. Available:http://dx.doi.org/10.3390/a8030723 53

[8] R. Leone, P. Festa, and E. Marchitto, “A bus driver scheduling problem:a new mathematical model and a grasp approximate solution,” Journal of Heuristics, vol. 17, no. 4, pp. 441–466, 2010. [Online]. Available:http://dx.doi.org/10.1007/s10732-010-9141-353

[9] E. Burke and M. Carter, Practice and Theory of Automated Timetabling II: Second International Conference, PATAT’97, Toronto, Canada, August 20 - 22, 1997, Selected Papers, ser. Lecture Notes in Computer Science.Springer, 1998, no. 2. [Online]. Available: https://books.google.com.co/booksid=IONmzsoRTQUC 54

[10] M. Sørensen, S. Kristiansen, and T. R. Stidsen, “International timetabling competition 2011: An adaptive large neighborhood search algorithm,” in 9th International Conference on the Practice and Theory of Automated Timetabling(PATAT 2012), 2012, pp. 489–492. 54

[11] ——, “International timetabling competition 2011: An adaptive large neighborhood search algorithm,” Technical University of Denmark, Denmark,
Tech. Rep., 2012. 54

[12] M. Sørensen and T. Stidsen, High School Timetabling: Modeling and solving a large number of cases in Denmark. Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), 2012, pp. 359–364. 54

[13] S. Kristiansen, M. Sørensen, M. B. Herold, and T. R. Stidsen, “The consultation timetabling problem at danish high schools,” Journal of Heuristics, vol. 19, no. 3, pp. 465–495, 2013. [Online]. Available:http://dx.doi.org/10.1007/s10732-013-9219-9 55