Abstract
University course timetabling is one of the most important administrative activities that take place in all academic institutions. In this work, we go over the main points of recent papers on the timetabling problem. We concentrate on university timetabling and introduce hard and soft constraints as well as most currently used objective functions. We also discuss some solution methods that have been applied by researchers. Finally, we raise more questions to be explored in future studies. We hope the directions lead to new researches that cover all aspects of the problem and result in high-quality timetables.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdennadher S, Marte M (2000) University course timetabling using constraint handling rules. J Appl Artif Intell 143: 311–326
Aladag CH, Hocaoglu G (2007) A tabu search algorithm to solve course timetabling problem. Hacettepe J Math Stat 36(1): 53–64
Aladag CH, Hocaoglu G, Basaran MA (2009) The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Syst Appl 36: 12349–12356
Alvarez R, Crespo E, Tamarit JM (2002) Design and implementation of a course scheduling system using tabu search. Eur J Oper Res 137: 512–523
Al-Yakoob SM, Salem M, Sherali Hanif D (2007) A mixed-integer programming approach to a class timetabling problem: a case study with gender policies and traffic considerations. Eur J Oper Res 180: 1028–1044
Al-Yakoob SM, Salem M, Sherali Hanif D (2006) Mathematical programming models and algorithms for a class–faculty assignment problem. Eur J Oper Res 173: 488–507
Asratian AS, Werra D (2002) A generalized class teacher model for some timetabling problems. Eur J Oper Res 143: 531–542
Azimi Z (2005) Hybrid heuristics for examination timetabling problem. Appl Math Comput 163: 705–733
Beligiannis GN, Moschopoulos C, Likothanas SD (2007) A genetic algorithm approach to school timetabling. Journal of the Operational Research Society 1: 1–20
Birbas T, Daskalaki S, Housos E (1977) Timetabling for Greek high schools. Journal of the Operational Research Society 48: 1191–1200
Boland N, Hughes BD, Merlot LT, Stuckey PJ (1977) Timetabling for Greek high schools. Journal of the Operational Research Society 48: 1191–1200
Broek JVD, Hurkens C, Woeginger G (2009) Timetabling problems at TU Eindhoven. European Journal of Operation Research 192: 877–885
Brown EC, Vroblefski M (2004) A grouping genetic algorithm for the microcell sectorization problem. Engineering Applications of Artificial Intelligence 17(6): 589–598
Burke Ek, Kingston J, de Werra D (2004) Applications to timetabling. In: Gross J, Yellen J (eds) Handbook of graph theory. Chapman Hall/CRC Press, London, pp 445–474
Burke EK, Kingston J, Jackson K, Weare R (1997) Automated university timetabling. The state of the art. Comput J 40(9): 565–571
Burke EK, Elliman DG, Weare RF (1994a) A genetic algorithm for university timetabling. AISB Workshop on Evolutionary Computing, University of Leeds, UK, Society for the Study of Artificial Intelligence and Simulation of Behaviour, pp 35–40
Burke EK, Elliman DG, Weare RF (1994) A university timetabling system based on graph colouring and constraint manipulation. J Res Comput Educ 27(1): 1–18
Burke EK, Ross P (1996) The practice and theory of automated timetabling. Selected papers from the 1st international conference on the practice and theory of automated timetabling, Napier University, August/September, Springer Lecture Notes in Computer Science Series, pp 309–324
Burke EK, Kendall G, Soubeiga E (2003) A tabu search hyper heuristic for timetabling and rostering. J Heuristics 9(6): 51–70
Burke EK, McCollum b, Meisels C, Petrovic A, Rong Q (2007) A graph-based hyper-heuristic for educational timetabling problems. Eur J Oper Res 176: 177–192
Burke EK, Mrecek j, Andrew J, parkes AJ, Rudova H (2010) Decomposition, reformulation, and divingin university course time tabling. Comput Oper Res 37: 582–597
Burke EK, Petrovice S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140: 266–280
Carrasco MP, Pato MV (2001) A multiobjective genetic algorithm for the class/teacher timetabling problem. Lect Notes Comput Sci 2079: 3–17
Carter M (1986) A lagrangian relaxation approach to the classroom assignment. INFOR 27(2): 230–246
Carter M (1968) A survey of practical applications of examination timetabling algorithms. Oper Res 34: 193–202
Carter MW, Laporte G (1998) Recent developments in practical course timetabling. In: Selected and revised papers of the second international conference on practice and theory of automated timetabling (PATAT 1997), LNCS. Springer, Toronto, vol 1408, pp 3–19
Carter M, Burke EK (1998) The practice and theory of automated timetabling II, selected papers from the 2nd international conference on the practice and theory of automated timetabling. University of Toronto o, August 278 Burke EK and Petrovic S J Oper Res 140, pp 266–280
Carter MW, Laporte G (1996a) Recent developments in practical examination timetabling. In: Burke EK, Ross P (eds), the practice and theory of automated timetabling. Springer, Berlin, Selected papers from the 1st international conference. LNCS 1153. Springer, Berlin, Heidelberg, pp 3–21
Carter MW, Laporte G, Lee SY (1996) Examination timetabling: algorithmic strategies and applications. J Oper Res 74: 373–383
Causmaecker DBB, Demeester PA, Berghe GV (2009) A decomposed metaheuristic approach for a real-world university timetabling problem. Eur J Oper Res 195: 307–318
Cordeau JF, Jaumard, Morales R (2003) Efficient timetabling solution with tabu search. International timetabling competition results, http://www.idsia.ch/Files/ttcomp2002/jaumard.pdf
Daskalaki S, Birbas T (2005) Efficient solutions for a university timetabling problem through integer programming. Eur J Oper Res 160: 106–120
Daskalaki S, Birbas T, Housos E (2004) An integer programming formulation for a case study in university timetabling. Eur J Oper Res 153(1): 117–135
Deris S, Omatu S, Ohta Hiroshi (2000) Timetable planning using the constraint-based reasoning. Comput Oper Res 27: 819–840
Dimopoulou M, Miliotis P (2001) Implementation of a university course and examination timetabling system. Eur J Oper Res 130: 202–213
Falkenauer E (1992) The grouping genetic algorithm–widening the scope of the GAs. In: Proceedings of the Belgian journal of operations research, statistics and computer science, vol 33, pp 79–102
Fisher JG, Shier DR (1983) A heuristic procedure for largescale examination scheduling problems. Technical Report, Department of Mathematical Sciences, Clemson University 417
Grigorios N et al (2008) Likothanassisa applying evolutionary computation to the school timetabling problem. Greek Case Comput Oper Res 35: 1265–1280
Haan pd, Landman r, Post G, Ruizena H (2007) A four-phase approach to a timetabling problem in secondary schools. 7500 AE Enschede, The Netherlands Department of applied Matematics, University Twente, P.O. Box 217
Hung C, Sumichrast RT, Brown EC (2003) A grouping genetic algorithm for material cutting plan generation. Comput Ind Eng 44(4): 651–667
Ismayilova NA, Sagir M, Rafail N (2005) A multiobjective faculty–course–time slot assignment pr with preferences. Math Comput Modell 46: 1017–1029
James T, Vroblefski M, Nottingham Q (2007) A hybrid grouping genetic algorithm for the registration area planning problem. Comput Commun 30(10): 2180–2190
James TL, Brown EC, Keeling KB (2007) A hybrid grouping genetic algorithm for the cell formation problem. Comput Oper Res 34: 2059–2079
Jaumard J, Cordeau R, Morales (2002) Efficient timetabling solution with tabu search, Working Paper, Available from Metaheuristics Network. International Timetabling Competition
Kustoch PA (2003) Timetabling competition SA-based heuristics. International timetabling competition results
Luis E, Blas A, Salcedo-Sanz S, Emilio G, Portilla A (2009) A hybrid grouping genetic algorithm for assigning students to preferred. Expert Syst Appl 36: 7234–7241
MirHassani SA (2006) A computational approach to enhancing course timetabling with integer programming. Appl Math Comput 175: 814–822
MirHassani SA (2006) Improving paper spread in examination timetables. Appl Math Comput 179: 702–706
Newall JP, Weara RF, Burke E (1996b) A memetic algorithm for university exam timetabling Practice and theory of automated timetabling. Lecture notes in computer science. Springer, Berlin, pp 241–250
Ozdemir MS, Gasimov RN (2004) The analytic hierarchy process and multiobjective 0–1 faculty course assignment problem. Eur J Oper Res 157(2): 398–408
Paker RG, Rardin RL, Diego S (1988) Discrete optimization. Academic Press Inc, USA
Papoutsis K, Valouxis C, Housos CE (2003) A column generation approach for the timetabling problem of Greek high schools. J Oper Res Soc 54: 230–238
Pongcharoena P, Promtetb W, Yenradeec P, Hicksd C (2008) Stochastic optimization timetabling tool for university course scheduling. Int J Prod Econ 112: 903–918
Ross P, Hart E, Corne D, Chosd, Tsutsui S (2003) Genetic algorithms and timetabling. Advances in evolutionary computation, theory and applications, pp 755–771
Rossi-Doria O, Paechter B (2004) A memetic algorithm for university course timetabling, in Combinatorial Optimisation. Book of Abstracts
Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13(2): 87–127
Valouxis C, Housos E (2003) Constraint programming approach for school timetabling. Comput Oper Res 30: 1555–1572
Werra D (1985) An introduction to timetabling. Eur J Oper Res 19(2): 151–162
Zhipeng Lu AB, Jin-Kao Hao A (2009) Adaptive Tabu Search for course timetabling. Eur J Oper Res 200(1): 235–244
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
MirHassani, S.A., Habibi, F. Solution approaches to the course timetabling problem. Artif Intell Rev 39, 133–149 (2013). https://doi.org/10.1007/s10462-011-9262-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10462-011-9262-6