Skip to main content
SpringerLink
Log in

Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

A significant body of recent literature has explored various research directions in hyper-heuristics (which can be thought as heuristics to choose heuristics). In this paper, we extend our previous work to construct a unified graph-based hyper-heuristic (GHH) framework, under which a number of local search-based algorithms (as the high level heuristics) are studied to search upon sequences of low-level graph colouring heuristics. To gain an in-depth understanding on this new framework, we address some fundamental issues concerning neighbourhood structures and characteristics of the two search spaces (namely, the search spaces of the heuristics and the actual solutions). Furthermore, we investigate efficient hybridizations in GHH with local search methods and address issues concerning the exploration of the high-level search and the exploitation ability of the local search. These, to our knowledge, represent entirely novel directions in hyper-heuristics. The efficient hybrid GHH obtained competitive results compared with the best published results for both benchmark course and exam timetabling problems, demonstrating its efficiency and generality across different problem domains. Possible extensions upon this simple, yet general, GHH framework are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Asmuni H, Burke EK and Garibaldi J (2005). Fuzzy multiple ordering criteria for examination timetabling. In: Burke EK and Trick M. (eds). Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3616. Springer: Berlin, pp 334–353.

  • Abdullah S, Ahmadi S, Burke E and Dror M (2007a). Investigating Ahuja-Orlin's large neighbourhood search for examination timetabling . OR Spectrum 29: 351–372.

    Article  Google Scholar 

  • Abdullah S, Ahmadi S, Burke EK, Dror M and McCollum B (2007b). A tabu based large neighbourhood search methodology for the capacitated examination timetabling problem . J Opl Res Soc 58: 1494–1502.

    Article  Google Scholar 

  • Abdullah S, Burke EK and McCollum B (2007c). Using a randomised iterative improvement algorithm with composite neighborhood structures for university course timetabling . In: Doerner K.F., Gendreau M., Greistorfer P., Gutjahr W.J., Hartl R.F. and Reimann M. (eds). Metaheuristics-Progress in Complex Systems Optimization :Computer Science Interfaces Book Series, Springer Operations Research. Springer: New York, pp. 153–172.

    Google Scholar 

  • Bardadym VA (1996). Computer-aided school and university timetabling: the new wave. In: Burke EK and Ross P (eds). Practice and Theory of Automated Timetabling, Selected Papers from the 1st International Conference, Springer Lecture Notes in Computer Science, Vol. 1153. Springer: Berlin, pp 22–45.

  • Bilgin B, Özcan E and Korkmaz EE (2007). An experimental study on hyper-heuristics and exam scheduling. In: Burke EK and Rudová H (eds). Selected Papers from the 6th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3867. Springer: Berlin, pp 394–412.

  • Brailsford SC, Potts CN and Smith BM (1999). Constraint satisfaction problems: algorithms and applications . Eur J Opns Res 119: 557–581.

    Article  Google Scholar 

  • Brucker P and Knust S (2006). Complex Scheduling . Springer: Berlin.

    Google Scholar 

  • Burke EK and Newall J (1999). A multi-stage evolutionary algorithm for the timetabling problem . IEEE Trans Evol Comput 3: 63–74.

    Article  Google Scholar 

  • Burke EK and Petrovic S (2002). Recent research directions in automated timetabling . Eur J Opl Res 140: 266–280.

    Article  Google Scholar 

  • Burke EK and Newall J (2004). Solving examination timetabling problems through adaptation of heuristic orderings . Ann Opns Res 129: 107–134.

    Article  Google Scholar 

  • Burke E.K. and Kendall G. (eds). Search Methodologies: Introductory Tutorials in Optimisation and Decision Support Techniques. Springer: Berlin.

  • Burke EK, Jackson K, Kingston JH and Weare R (1997). Automated university timetabling: the state of the art . Comput J 40: 565–571.

    Article  Google Scholar 

  • Burke EK, Hart E, Kendall G, Newall J, Ross P and Schulenburg S (2003a). Hyperheuristics: an emerging direction in modern search technology . In: Glover F. and Kochenberger G. (eds). Handbook of Meta-Heuristics. Kluwer: Dordrecht, pp. 457–474.

    Google Scholar 

  • Burke EK, Kendall G and Soubeiga E (2003b). A tabu search hyperheuristic for timetabling and rostering . J Heuristics 9: 451–470.

    Article  Google Scholar 

  • Burke E, Bykov Y, Newall J and Petrovic S (2004a). A time-predefined local search approach to exam timetabling problems . IIE Trans 36: 509–528.

    Article  Google Scholar 

  • Burke EK, De Causmaecker P, Vanden Berghe G and Van Landeghem H (2004b). The state of the art of nurse rostering . J Scheduling(6)441–499.

  • Burke EK, Kingston J and de Werra D (2004c). Applications to timetabling . In: Gross J. and Yellen J. (eds). Handbook of Graph Theory. Chapman Hall/CRC Press: FL, USA, pp. 445–474.

    Google Scholar 

  • Burke EK, Dror M, Petrovic S and Qu R (2005). Hybrid graph heuristics within a hyper-heuristic approach to exam timetabling problems . In: Golden B.L., Raghavan S. and Wasil E.A. (eds). The Next Wave in Computing, Optimization and Decision Technologies. Springer: Berlin, pp. 79–91.

    Chapter  Google Scholar 

  • Burke EK, Petrovic S and Qu R (2006). Case based heuristic selection for examination timetabling . J Scheduling 9: 115–132.

    Article  Google Scholar 

  • Burke EK, McCollum B, Meisels A, Petrovic S and Qu R (2007). A graph-based hyper heuristic for timetabling problems . Eur J Opl Res 176: 177–192.

    Article  Google Scholar 

  • Burke EK, Eckersley AJ, McCollum B, Petrovic S and Qu R (2008). Hybrid variable neighbourhood approaches to university exam timetabling. Euro J Opl Res, Forthcoming.

  • Caramia M, Dell'Olmo P and Italiano GF (2008). Novel local-search-based approaches to university examination timetabling . INFORMS J Comput 20: 86–99.

    Article  Google Scholar 

  • Carter M and Laporte G (1996). Recent developments in practical exam timetabling. In: Burke EK and Ross P (eds). Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 1153. Springer: Berlin, pp 3–21.

  • Carter M and Laporte G (1998). Recent developments in practical course timetabling. In: Burke EK, and Ross P (eds). Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 1408. Springer, Berlin, pp. 3–19.

  • Carter M, Laporte G and Lee S (1996). Examination timetabling: algorithmic strategies and applications . J Opl Res Soc 47: 373–383.

    Article  Google Scholar 

  • Casey S and Thompson J (2003). GRASPing the examination scheduling problem. In: Burke E, Causmaecker P (eds). Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 2740. Springer: Berlin, pp 232–246.

  • Cicirello VA and Smith SF (2004). Heuristic selection for stochastic search optimization: modeling solution quality by extreme value theory. In: Wallace M (ed). Principles and Practice of Constraint Programming CP 2004, Lecture Notes in Computer Science, Vol. 3258 Springer: Berlin, pp 197–211.

  • Crowston WB, Glover F, Thompson GL and Trawick JD (1963). Probabilistic and parameter learning combinations of local job shop scheduling rules. ONR Research Memorandum, GSIA, Carnegie Mellon University, Pittsburgh, 117.

  • Di Gaspero L, Schaerf A (2001). Tabu search techniques for examination timetabling. In: Burke EK and Erben W (eds). Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 2079. Springer: Berlin, pp 104–117.

  • Dowsland K, Soubeiga E and Burke EK (2007). A simulated annealing hyperheuristic for determining shipper sizes . Eur J Opl Res 179: 759–774.

    Article  Google Scholar 

  • Easton K, Nemhauser G and Trick M (2004). Sports scheduling . In: Leung J. (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press: Boca Raton: FL Chapter 52.

    Google Scholar 

  • Eley M (2007). Ant algorithms for the exam timetabling problem. In: Burke EK and Rudova H (eds). Selected Papers from the 6th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3867. Springer: Berlin, pp 364–382.

  • Fisher H and Thompson GL (1963). Probabilistic learning combinations of local job-shop scheduling rules . In: Muth J.F. and Thompson G.L. (eds). Industrial Scheduling. Prentice-Hall: New Jersey, pp. 225–251.

    Google Scholar 

  • Gaw A, Rattadilok P and Kwan RS (2005). Distributed choice function hyperheuristics for timetabling and scheduling. In: Burke EK and Trick M (eds). Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3616. Springer: Berlin, pp 51–67.

  • Gomes CP and Selman B (2001). Algorithm portfolios . Artif Intell 126(1–2): 43–62.

    Article  Google Scholar 

  • Hansen P and Mladenovic N (2001). Variable neighbourhood search: principles and applications . Eur J Opl Res 130: 449–467.

    Article  Google Scholar 

  • Hansen P and Mladenovic N (2005). Variable neighbourhood search . In: Burke E.K. and Kendall G. (eds). Search Methodologies: Introductory Tutorials in Optimisation and Decision Support Techniques. Springer: Berlin, pp. 211–238.

    Chapter  Google Scholar 

  • Krasnogor N and Smith JE (2005). A tutorial for competent memetic algorithms: Model taxonomy and design issues . IEEE Trans Evol Comput 9: 474–488.

    Article  Google Scholar 

  • Krasnogor N, Aragon A and Pacheco J (2006). Memetic algorithms . In: Marti R. and Alba E. (eds). Metaheuristics in Neural Networks Learning. Kluwer: Dordrecht, pp. 225–247.

    Google Scholar 

  • Kwan R (2004). Bus and train driver scheduling . In: Leung J. (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press: Boca Raton, FL, USA Chapter 51.

    Google Scholar 

  • Lourenco HR, Martin O and Stutzle T (2003). Iterated local search . In: Glover F. and Kochenberger G. (eds). Handbook of Metaheuristics. Kluwer Academic Publishers: Dordrecht, pp. 321–353.

    Google Scholar 

  • McCollum BGC (2007). A perspective on bridging the gap in university timetabling. In: Burke EK and Rudová H (eds). Selected Papers from the 6th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3867. Springer: Berlin, pp 3–23.

  • Merlot L, Boland N, Hughes B and Stuckey P (2002). A hybrid algorithm for the examination timetabling problem. In: Burke E and Causmaecker P (eds). Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 2740. Springer: Berlin, pp 207–231.

  • Meyers C and Orlin JB (2007). Very large-scale neighborhood search techniques. In: Burke EK and Rudova H (eds). Selected Papers from the 6th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Vol. 3867. Springer: Berlin, pp 24–39.

  • Nareyek A (2003). Choosing search heuristics by non-stationary reinforcement learning . In: Resende M.G.C. and deSousa J.P. (eds). Metaheuristics: Computer Decision-Making. Kluwer Academic Publishers: Dordrecht, pp. 523–544.

    Chapter  Google Scholar 

  • Nonobe K and Ibaraki T (1998). A tabu search approach to the constraint satisfaction problem as a general problem solver . Eur J Opl Res 106: 599–623.

    Article  Google Scholar 

  • Petrovic S and Burke EK (2004). University timetabling . In: Leung J. (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC: FL, USA Chapter 45.

    Google Scholar 

  • Qu R, Burke EK McCollum B, Merlot LTG and Lee SY (2008). A survey of search methodologies and automated system development for examination timetabling. Accepted by J Scheduling, DOI: 10.1007/s10951-008-10077-5, accepted for publication.

  • Reeves C.R. (ed). Modern Heuristic Techniques for Combinatorial Problems. Oxford: Scientific Publications.

  • Ross P (2005). Hyper-heuristics . In: Burke E.K. and Kendall G. (eds). Search Methodologies: Introductory Tutorials in Optimisation and Decision Support Techsiques. Springer: Berlin, pp. 529–556.

    Chapter  Google Scholar 

  • Ross P, Marin-Blazquez J and Hart E (2004). Hyper-heuristics applied to class and exam timetabling problems. Proceedings of the 2004 Congress on Evolutionary Computation (CEC 2004). IEEE Press, Portland, USA, pp 1691–1698.

  • Schaerf A (1999). A survey of automated timetabling . Artif Intell Rev 13: 87–127.

    Article  Google Scholar 

  • Socha K, Knowles J and Sampels M (2002). A max-min ant system for the university course timetabling problem. In: Proceedings of the 3rd International Workshop on Ant Algorithms, Lecture Notes in Computer Science, Vol. 2463. Springer: Berlin, pp 1–13.

  • Terashima-Marin H, Ross P, Valenzuela-Rendon M (1999). Evolution of constraint satisfaction strategies in examination timetabling. In: Banzhaf W, Daida JM, Eiben AE, Garzon MH, Horava V, Jakiela MJ and Smith RE (eds). Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida USA. Morgan Kaufmann: San Francisco, CA, pp 635–642.

  • Thompson J and Dowsland K (1998). A robust simulated annealing based examination timetabling system . Comput Opl Res 25: 637–648.

    Article  Google Scholar 

  • de Werra D (1985). An introduction to timetabling . Eur J Opl Res 19: 151–162.

    Article  Google Scholar 

  • White GM (2000). Constrained satisfaction, not so constrained satisfaction and the timetabling problem. In: Burke EK and Erben W (eds). Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, keynote. Fachhochschule Konstanz, Germany, pp 32–54.

  • White GM, Xie BS and Zonjic S (2004). Using tabu search with longer term memory and relaxation to create examination timetables . Eur J Opl Res 153: 80–91.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Nottingham, Nottingham, UK

    R Qu & E K Burke

Authors
  1. R Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E K Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R Qu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Qu, R., Burke, E. Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems. J Oper Res Soc 60, 1273–1285 (2009). https://doi.org/10.1057/jors.2008.102

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2008.102

Keywords

Search

Navigation