Abstract
This chapter is an introduction to the problems of timetabling educational institutions such as high schools and universities. These are large problems with multiple sources of NP-completeness, for which robust solvers do not yet exist, although steady progress is being made. This chapter presents the three main problems found in the literature: high school timetabling, university examination timetabling, and university course timetabling. It also examines some major subproblems of these problems: student sectioning, single student timetabling, and room assignment. This chapter also shows how real-world instances of these problems, with their many constraints, can be modelled in full detail, using a case study in high school timetabling as an example.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Timetabling Problem
- Real Instance
- Nurse Rostering
- Examination Timetabling
- Adaptive Large Neighborhood Search
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Appleby, J.S., Blake, D.V., Newman, E.A.: Techniques for producing school timetables on a computer and their application to other scheduling problems. The Computer Journal 3, 237–245 (1960)
Aubin, J., Ferland, J.A.: A large scale timetabling problem. Computers and Operations Research 16, 67–77 (1989)
Carter, M.W.: A survey of practical applications of examination timetabling algorithms. Operations Research 34, 193–202 (1986)
Carter, M.W., Tovey, C.A.: When is the classroom assignment problem hard? Operations Research 40, S28–S39 (1992)
Carter, M.W., Laporte, G.: Recent developments in practical examination timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 3–21. Springer, Heidelberg (1996)
Carter, M.W., Laporte, G., Lee, S.Y.: Examination timetabling: algorithmic strategies and applications. Journal of Operational Research Society 47, 373–383 (1996)
Carter, M.W., Laporte, G.: Recent developments in practical course timetabling. In: Burke, E.K., Carter, M. (eds.) PATAT 1997. LNCS, vol. 1408, pp. 3–19. Springer, Heidelberg (1998)
Carter, M.W.: A comprehensive course timetabling and student scheduling system at the University of Waterloo. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 64–81. Springer, Heidelberg (2001)
Cooper, T.B., Kingston, J.H.: The complexity of timetable construction problems. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 283–295. Springer, Heidelberg (1996)
Cumming, A., Paechter, B.: Standard formats for timetabling data. In: Unpublished Discussion Session at the First International Conference on the Practice and Theory of Automated Timetabling, PATAT 1995, Edinburgh (August 1995)
Curtois, T.: Employee scheduling benchmark data sets, http://www.cs.nott.ac.uk/~tec/NRP/ (Cited September 15, 2012)
De Cesco, F., Di Gaspero, L., Schaerf, A.: Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, and results. In: Proceedings, 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2008, Montreal (August 2008)
de Haan, P., Landman, R., Post, G., Ruizenaar, H.: A case study for timetabling in a Dutch secondary school. In: Burke, E.K., Rudová, H. (eds.) PATAT 2007. LNCS, vol. 3867, pp. 267–279. Springer, Heidelberg (2007)
De Werra, D.: Construction of school timetables by flow methods. INFOR—Canadian Journal of Operational Research and Information Processing 9, 12–22 (1971)
Fonseca, G.H.G., Santos, H.G., Toffolo, T.A.M., Brito, S.S., Souza, M.J.F.: A SA-ILS approach for the high school timetabling problem. In: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), Son, Norway (August 2012)
Gotlieb, C.C.: The construction of class-teacher timetables. In: Popplewell, C.M. (ed.) Information Processing 1962 (Proceedings of the 1962 IFIP Congress), pp. 73–77 (1962)
Kingston, J.H.: The HSEval high school timetable evaluator (2009), http://www.it.usyd.edu/au/~jeff/hseval.cgi (Cited September 15, 2012 )
Kingston, J.H.: Timetable construction: the algorithms and complexity perspective. In: Proceedings of the Eighth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2010), Belfast, UK (August 2010)
Kingston, J.H.: Resource assignment in high school timetabling. Annals of Operations Research 194, 241 (2012)
Kjenstad, D., Riise, A., Nordlander, T.E., McCollum, B., Burke, E.: In: Proceedings, of the 9th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2012, Son, Norway (August 2012)
Kristiansen, S., Stidsen, T.R.: Adaptive large neighborhood search for student sectioning at Danish high schools. In: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), Son, Norway (August 2012)
Laporte, G., Desroches, S.: The problem of assigning students to course sections in a large engineering school. Computers and Operations Research 13, 387–394 (1986)
McCollum, B.: The Second International Timetabling Competition (ITC 2007), Track 3 (2007), http://www.cs.qub.ac.uk/itc2007 (Cited September 17, 2012)
McCollum, B., McMullan, P., Parkes, A.J., Burke, E.K., Qu, R.: A new model for automated examination timetabling. Annals of Operations Research 194, 291–315 (2012)
Müller, T., Rudová, H., Barták, R.: Minimal perturbation problem in course timetabling. In: Burke, E.K., Trick, M.A. (eds.) PATAT 2004. LNCS, vol. 3616, pp. 126–146. Springer, Heidelberg (2005)
Müller, T., Rudová, H.: Real-life curriculum-based timetabling. In: Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2012, Son, Norway (August 2012)
Murray, K., Rudová, H.: University course timetabling with soft constraints. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 310–328. Springer, Heidelberg (2003)
Murray, K., Müller, T., Rudová, H.: Modeling and solution of a complex university course timetabling problem. In: Burke, E.K., Rudová, H. (eds.) PATAT 2007. LNCS, vol. 3867, pp. 189–209. Springer, Heidelberg (2007)
Murray, K., Müller, T.: Comprehensive approach to student sectioning. Annals of Operations Research 181, 249–269 (2007)
Nurmi, K., Kyngäs, J.: A conversion scheme for turning a curriculum-based timetabling problem into a school timetabling problem. In: Proceedings, of the 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2008, Montreal (August 2008)
Pillay, N.: An overview of school timetabling. In: Proceedings, of the 8th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2010, Belfast, UK, pp. 321–335 (August 2010)
Pillay, N.: Classification of school timetabling research, http://titan.cs.unp.ac.za/~nelishiap/st/classification.htm (Cited September 15, 2012)
Post, G.: Benchmarking project for (high) school timetabling, http://www.utwente.nl/ctit/hstt/ (Cited September 15, 2012)
Post, G., Di Gaspero, L., Kingston, J.H., McCollum, B., Schaerf, A.: The third international timetabling competition. In: Proceedings, of the 9th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2012, Son, Norway (August 2012)
Qu, R., Burke, E.K., McCollum, B., Merlot, L.T.G., Lee, S.Y.: A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling 12, 55–89 (2009)
Qu, R.: Benchmark data sets in exam timetabling, http://www.cs.nott.ac.uk/~rxq/data.htm (Cited September 15, 2012)
Schaerf, S.: A survey of automated timetabling. Articifial Intelligence Review 13, 87–127 (1999)
Schmidt, G., Ströhlein, T.: Timetable construction–an annotated bibliography. The Computer Journal 23, 307–316 (1980)
UniTime: a comprehensive university timetabling system, http://www.unitime.org/ (Cited September 18, 2012)
Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to a timetabling problem. The Computer Journal 10, 85–86 (1967)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kingston, J.H. (2013). Educational Timetabling. In: Uyar, A., Ozcan, E., Urquhart, N. (eds) Automated Scheduling and Planning. Studies in Computational Intelligence, vol 505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39304-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-39304-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39303-7
Online ISBN: 978-3-642-39304-4
eBook Packages: EngineeringEngineering (R0)