Publication:
University Course Scheduling and Classroom Assignment

Thumbnail Image
Files

Files

University Course Scheduling and.pdf (382.59 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Torres-Ovalle, Camilo
Montoya-Torres, Jairo R.
Quintero-Araújo, Carlos L.
Sarmiento-Lepesqueur, Angélica
Castilla-Luna, Mónica
Abstract (Spanish)
Este artículo considera el problema real de programación de horarios de clases universitarias y asignación de salones en la Universidad de La Sabana, Colombia. El problema es caracterizado y modelado empleando programación lineal entera. Debido a su alta complejidad en el número de variables de decisión y de restricciones, se propone un enfoque de solución secuencial de dos fases: primero, asignación de horarios a las materias, y segundo, asignación de salones. Este método de resolución es validado empleando datos reales del primer semestre académico de 2012. Los resultados muestran que el enfoque propuesto permite obtener una mejor utilización de los salones, al mismo tiempo que se satisfacen las restricciones duras y blandas del problema original. Se realiza también un análisis de sensibilidad con el cual fue posible verificar la posibilidad de reducir tanto el número de salones que se van a asignar como el número de grupos de cada materia. Ambos análisis incrementan la disponibilidad de los recursos docentes y reducen los costos de la programación.
Abstract (English)
This paper studies a real-life course timetabling and classroom assignment problem found at Universidad de La Sabana, Colombia. The problem is characterized and modeled using integer linear programming. Because of its complexity in the number of decision variables and constraints, a hierarchical two-phase solution approach is proposed: course timetabling firstly, and classroom assignment, secondly. The approach is validated using real data from the first semester of year 2012. Results show that the proposed approach obtains a better utilization of classrooms satisfying both hard and soft constraints of the original problem. A sensitivity analysis is finally carried out, in which it was possible to verify the possibility of reducing both the number of classrooms to be assigned and the number of course groups. Both analyses allow an increase in teaching resource availability and a reduction of total cost.
Extent
17 páginas.
URI: https://repositorio.escuelaing.edu.co/handle/001/1919
Collections

Collections

AI - Centro de Investigación en Manufactura y Servicios – CIMSER
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.