A mathematical programming model for high school timetabling problem

Main Article Content

Juan Camilo Marin Ángel
Universidad de Antioquia

Pablo Andrés Maya Duque
Universidad de Antioquia
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 1418 | PDF (Español) Downloads 972 HTML (Español) Downloads 513

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

Article Sidebar

PDF (Español) HTML (Español)
Published
Feb 22, 2016
DOI https://doi.org/10.17230/ingciencia.12.23.3

Article Details

How to Cite
Marin Ángel, J. C., & Maya Duque, P. A. (2016). A mathematical programming model for high school timetabling problem. Ingeniería Y Ciencia, 12(23), 47–71. https://doi.org/10.17230/ingciencia.12.23.3
Issue
Vol. 12 No. 23 (2016)
Section
Articles
Supporting Agencies

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).