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.
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.
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.
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.
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.
Brucker P and Knust S (2006). Complex Scheduling . Springer: Berlin.
Burke EK and Newall J (1999). A multi-stage evolutionary algorithm for the timetabling problem . IEEE Trans Evol Comput 3: 63–74.
Burke EK and Petrovic S (2002). Recent research directions in automated timetabling . Eur J Opl Res 140: 266–280.
Burke EK and Newall J (2004). Solving examination timetabling problems through adaptation of heuristic orderings . Ann Opns Res 129: 107–134.
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.
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.
Burke EK, Kendall G and Soubeiga E (2003b). A tabu search hyperheuristic for timetabling and rostering . J Heuristics 9: 451–470.
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.
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.
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.
Burke EK, Petrovic S and Qu R (2006). Case based heuristic selection for examination timetabling . J Scheduling 9: 115–132.
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.
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.
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.
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.
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.
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.
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.
Hansen P and Mladenovic N (2001). Variable neighbourhood search: principles and applications . Eur J Opl Res 130: 449–467.
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.
Krasnogor N and Smith JE (2005). A tutorial for competent memetic algorithms: Model taxonomy and design issues . IEEE Trans Evol Comput 9: 474–488.
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.
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.
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.
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.
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.
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.
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.
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.
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.
de Werra D (1985). An introduction to timetabling . Eur J Opl Res 19: 151–162.
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.
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2008.102