Published May 29, 2014



PLUMX
Almetrics
 
Dimensions
 

Google Scholar
 
Search GoogleScholar


Camilo Torres-Ovalle, MSc

Jairo Rafael Montoya-Torres, PhD

Carlos Quintero-Araujo, MSc

Angelica Sarmiento-Lepesqueur, MSc

Monica Castilla-Luna, MSc

##plugins.themes.bootstrap3.article.details##

Abstract

This paper studies a real-life course timetabling andclassroom assignment problem found at Universidad deLa Sabana, Colombia. The problem is characterized andmodeled using integer linear programming. Because ofits complexity in the number of decision variables andconstraints, a hierarchical two-phase solution approachis proposed: course timetabling firstly, and classroom assignment,secondly. The approach is validated using realdata from the first semester of year 2012. Results showthat the proposed approach obtains a better utilizationof classrooms satisfying both hard and soft constraints ofthe original problem. A sensitivity analysis is finally carriedout, in which it was possible to verify the possibility ofreducing both the number of classrooms to be assignedand the number of course groups. Both analyses allow anincrease in teaching resource availability and a reductionof total cost.

Keywords

Course timetabling, classroom assignment, integer linear programming., Class periods, classrooms – programmingProgramación de clases, asignación de salones, programación entera, Periodos lectivos – programación, salones de clase – programación

References
ABDULLAH, S.; BURKE, E.K. and MCCOLLUM, B. An investigation of variable neighbourhood search for the course timetabling problem. Proceedings of the 2nd Multidisciplinary Conference on Scheduling: Theory and Applications (MISTA), New York, 2005, pp. 413-427.
ARNTZEN, H. and LOKKETANGEN, A. A tabu search heuristic for a university timetabling problem. In Ikabaki, T.; NONOBE, K.; YAGIURA, M. (eds.). Metaheuristics: progress as real problem solvers. Vol. 32. Berling: Springer-Verlag, 2005, pp. 65-86.
BURKE, E.K. and PIETROVIC, S. Recent research directions in automated timetabling. European Journal of Operational Research. 2002, vol. 140, pp. 266-280.
CARTER, M.W. A comprehensive course timetabling and student scheduling system at the University of Waterloo. In BURKE, E.K. and ERBEN, W. (eds.). Lecture notes in computer science. Vol. 2079. Heidelberg: Springer-Verlag, 2001, pp. 64-84.
CARTER, M.W. and LAPORTE G. Recent developments in practical course timetabling. In BURKE, E.K. and CARTER, M.W. (eds.). Lecture notes in computer science. Vol. 1408. Heidelberg: Springer-Verlag, 1998, pp. 3-19.
DE WERRA, D. An introduction to timetabling. European Journal of Operational Research. 1985, vol. 19, pp. 151-162.
HERNÁNDEZ, R.; MIRANDA, J. and REY, P. Programación de horarios de clases y asignación de salas para la Facultad de Ingeniería de la Universidad Diego Portales mediante un enfoque de programación entera. Revista de Ingeniería de Sistemas. 2008, vol. XXII, pp. 121-141.
KONSTANTINOW, G. and COAKLEY, C. Use of genetic algorithms in reactive scheduling for course timetabling adjustments. In BURKE, E.K. and TRICK, M.A. (eds.). Lecture Notes in Computer Science. Vol. 3616. Heidelberg: Springer-Verlag, 2005, pp. 521-522.
LEWIS, R. A survey of metaheuristics-based techniques for university timetabling problems. OR Spectrum. 2008, vol. 30, pp. 167-190.
MCCULLOM, B. A perspective on bridging the gap between theory and practice in university timetabling. In BURKE, E.K. and RUDOVÁ, H. (eds.). Lecture notes in computer science. Vol. 3867. Berlin: Springer-Verlag, 2007, pp. 3-23.
PILLAY, N. A survey of school timetabling research. Annals of Operations Research. 2013. DOI: 10.1007/s10479-013-1321-8.
ROSSI-DORIA, O.; SAMPLES, M.; BIRATTARI, M.; CHIARANDINI, M.; DORIGO, M.; GAMBARDELLA, L.M.; KNOWLES, J.; MANFRIN, M.; MASTROLILLI, M.; PAECHTER, B.; PAQUETE, L.; STUTZLE, Y. A comparison of the performance of different metaheuristics on the timetabling problem. In BURKE, E.K. and DE CAUSMAECKER, P. (eds.). Lecture notes in computer science. Vol. 2740. Heidelberg: Springer-Verlag, 2003, pp. 329-351.
SARMIENTO-LEPESQUEUR, A.; TORRES-OVALLE, C.; QUINTERO-ARAÚJO, C.L.; MONTOYA-TORRES, J.R. Programación y asignación de horarios de clases universitarias: un enfoque de programación entera. Proceedings of the Tenth LACCEI Latin American and Caribbean Conference (LACCEI’2012), Panama City, Panama, July 23-27, 2012. Latin American and Caribbean Consortium of Engineering Institutions (LACCEI Inc), Boca Raton, Florida, USA, 2012. (ISBN: 13 978-0-9822896-5-5). CD-ROM, paper 027.
SCHAERF, A. A survey of automated timetabling. Artificial Intelligence Review. 1999, vol. 13, pp. 87-127.
SOCHA, K.; KNOWLES, J. and SAMPLES, M. A max-min ant system for the university course timetabling problem. In DORIGO, M.; DI CARO, G.A.; SAMPLES, M. (eds.). Lecture notes in computer science. Vol. 2463. Heidelberg: Springer-Verlag, 2002, pp. 1-13.
TORRES OVALLE, C. Programación de horarios y asignación de aulas de clases universitarias [trabajo de grado]. Maestría en Gerencia de Operaciones, Universidad de La Sabana, Chía, Colombia, 2013.
How to Cite
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.ucsc
Section
Articles