Abstract
The university course timetabling problem deals with the task of scheduling lectures of a set of university courses into a given number of rooms and time periods, taking into account various hard and soft constraints. The goal of the International Timetabling Competitions ITC2002 and ITC2007 was to establish models for comparison that cover the most frequently found use cases. Our model, motivated by a project with University College London (UCL), builds on the standard model from track 3 of ITC2007. Compared to the standard model from the literature, we cover several new constraints and extra features. For example, we expand the ITC2007 framework to generate a timetable for several weeks of the term instead of only one and introduce the corresponding timetable regularity metric, which measures the consistency of time and room assignments for a course throughout the term. We suggest an Integer Linear Programming approach for solving this expanded timetabling problem and introduce a corresponding new benchmark library. Finally we conduct computational experiments and discuss the results obtained with respect to solution quality and practical suitability for UCL.
This research was supported by the third party project Satalia, funded by Satalia (NPComplete Ltd.) and conducted at the Alpen-Adria-Universität Klagenfurt.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Asín Achá, R., Nieuwenhuis, R.: Curriculum-based course timetabling with sat and maxsat. Ann. Oper. Res. 218(1), 71–91 (2014)
Lach, G., Lübbecke, M.E.: Curriculum based course timetabling: new solutions to udine benchmark instances. Ann. Oper. Res. 194(1), 255–272 (2012)
Lü, Z., Hao, J.-K.: Adaptive tabu search for course timetabling. Eur. J. Oper. Res. 200(1), 235–244 (2010)
Lewis, R.: A survey of metaheuristic-based techniques for university timetabling problems. OR Spectr. 30(1), 167–190 (2008)
McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A.J., Gaspero, L.D., Qu, R., Burke, E.K.: Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS J. Comput. 22(1), 120–130 (2010)
Zhang, L., Lau, S.: Constructing university timetable using constraint satisfaction programming approach. In: CIMCA-IAWTIC’06, vol. 02, pp. 55–60. IEEE Computer Society (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Aschinger, M., Applebee, S., Bucur, A., Edmonds, H., Hungerländer, P., Maier, K. (2018). New Constraints and Features for the University Course Timetabling Problem. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-55702-1_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55701-4
Online ISBN: 978-3-319-55702-1
eBook Packages: Business and ManagementBusiness and Management (R0)