[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A survey of search methodologies and automated system development for examination timetabling

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

Examination timetabling is one of the most important administrative activities that takes place in all academic institutions. In this paper, we present a critical discussion of the research on exam timetabling which has taken place in the last decade or so. This last ten years has seen a significantly increased level of research attention for this important area. There has been a range of insightful contributions to the scientific literature both in terms of theoretical issues and practical aspects. The main aim of this survey is to highlight the new trends and key research achievements that have been carried out in the last decade. We also aim to outline a range of relevant important research issues and challenges that have been generated by this body of work.

We first define the problem and discuss previous survey papers. Within our presentation of the state-of-the-art methodologies, we highlight recent research trends including hybridisations of search methodologies and the development of techniques which are motivated by raising the level of generality at which search methodologies can operate. Summarising tables are presented to provide an overall view of these techniques. We also present and discuss some important issues which have come to light concerning the public benchmark exam timetabling data. Different versions of problem datasets with the same name have been circulating in the scientific community for the last ten years and this has generated a significant amount of confusion. We clarify the situation and present a re-naming of the widely studied datasets to avoid future confusion. We also highlight which research papers have dealt with which dataset. Finally, we draw upon our discussion of the literature to present a (non-exhaustive) range of potential future research directions and open issues in exam timetabling research.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aarts, E. H. L., & Korst, J. (1989). Simulated annealing and Boltzmann machines. New York: Wiley.

    Google Scholar 

  • Aarts, E. H. L., Korst, J., & Michiels, W. (2005). Simulated annealing. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 187–211). Berlin: Springer. ISBN: 0387234608.

    Google Scholar 

  • Abdullah, S., Ahmadi, S., Burke, E. K., & Dror, M. (2007a). Investigating Ahuja–Orlins large neighbourhood search for examination timetabling. OR Spectrum, 29(2), 351–372.

    Google Scholar 

  • Abdullah, S., Ahmadi, S., Burke, E. K., Dror, M., & McCollum, B. (2007b). A tabu based large neighbourhood search methodology for the capacitated examination timetabling problem. Journal of Operational Research, 58, 1494–1502.

    Google Scholar 

  • Ahmadi, S., Barone, R., Cheng, P., Cowling, P., & McCollum, B. (2003). Perturbation based variable neighbourhood search in heuristic space for examination timetabling problem. In Proceedings of multidisciplinary international scheduling: theory and applications (MISTA 2003) (pp. 155–171), Nottingham, 13–16 August, 2003. ISBN: 0-9545821-2-8.

  • Ahuja, R. K., Orlin, J. B., & Sharma, D. (2001). Multi-exchange neighbourhood search algorithm for capacitated minimum spanning tree problem. Mathematical Programming, 91, 71–97.

    Google Scholar 

  • Ajili, F., & Wallace, M. W. (2003). Hybrid problem solving in ECLiPSe. In M. Milano (Ed.), Constraint and integer programming: toward a unified methodology (pp. 169–201). Dordrecht: Kluwer Academic.

    Google Scholar 

  • Asmuni, H., Burke, E. K., Garibaldi, J., & McCollum, B. (2005). Fuzzy multiple ordering criteria for examination timetabling. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: selected papers from the 5th international conference (pp. 334–353). Berlin: Springer.

    Google Scholar 

  • Asmuni, H., Burke, E. K., Garibaldi, J., & McCollum, B. (2007a). A novel fuzzy approach to evaluate the quality of examination timetabling. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 327–346). Berlin: Springer.

    Google Scholar 

  • Asmuni, H., Burke, E. K., Garibaldi, J., & McCollum, B. (2007b). Determining rules in fuzzy multiple heuristic orderings for construction examination timetables. In Proceedings of the 3rd multidisciplinary international conference on scheduling: theory and application (pp. 59–66), Paris, France, August 2007.

  • Bardadym, V. A. (1996). Computer-aided school and university timetabling: The new wave. In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 22–45). Berlin: Springer.

    Google Scholar 

  • Bilgin, B., Özcan, E., & Korkmaz, E. E. (2007). An experimental study on hyper-heuristics and exam timetabling. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 394–412). Berlin: Springer.

    Google Scholar 

  • Boizumault, P., Delon, Y., & Peridy, L. (1996). Constraint logic programming for examination timetabling. Journal of Logic Programming, 26(2), 217–233.

    Google Scholar 

  • Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119, 557–581.

    Google Scholar 

  • Brelaz, D. (1979). New methods to colour the vertices of a graph. Communication of the ACM, 22(4), 251–256.

    Google Scholar 

  • Broder, S. (1964). Final examination scheduling. Communications of the ACM, 7, 494–498.

    Google Scholar 

  • Bullnheimer, B. (1998). An examination scheduling model to maximise students study time. In E. K. Burke & M. W. Carter (Eds.), Lecture notes in computer science : Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference (pp. 78–91). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., & Carter, M. W. (Eds.). (1998). Lecture notes in computer science : Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference. Berlin: Springer. ISBN: 3-540-64979-4.

    Google Scholar 

  • Burke, E. K., & De Causmaecker, P. (Eds.). (2003). Lecture notes in computer science : Vol. 2740. Practice and theory of automated timetabling IV: selected papers from the 4th international conference. Berlin: Springer. ISBN: 3-540-40699-9.

    Google Scholar 

  • Burke, E. K., & Erben, W. (Eds.). (2001). Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference. Berlin: Springer. ISBN: 3-540-42421-0.

    Google Scholar 

  • Burke, E. K., & Kendall, G. (Eds.). (2005). Search methodologies: introductory tutorials in optimisation and decision support techniques. Berlin: Springer. ISBN: 0387234608.

    Google Scholar 

  • Burke, E. K., & Landa Silva, J. D. (2004). The design of memetic algorithms for scheduling and timetabling problems. In W. E. Hart, N. Krasnogor, & J. E. Smith (Eds.), Studies in fuzziness and soft computing : Vol. 166. Recent advances in memetic algorithms and related search technologies (pp. 289–312). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., & Newall, J. P. (1999). A multi-stage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, 3(1), 63–74.

    Google Scholar 

  • Burke, E. K., & Newall, J. P. (2003). Enhancing timetable solutions with local search methods. In E. K. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science : Vol. 2740. Practice and theory of automated timetabling IV: selected papers from the 4th international conference (pp. 195–206). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaptation of heuristic orderings. Annals of Operational Research, 129, 107–134.

    Google Scholar 

  • Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.

    Google Scholar 

  • Burke, E. K., & Ross, P. (Eds.). (1996). Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference. Berlin: Springer. ISBN: 3-540-61794-9.

    Google Scholar 

  • Burke, E. K., & Rudova, H. (Eds.). (2007). Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference. Berlin: Springer. ISBN: 978-3-540-77344-3.

    Google Scholar 

  • Burke, E. K., & Trick, M. (Eds.). (2005). Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: selected papers from the 5th international conference. Berlin: Springer. ISBN: 3-540-30705-2.

    Google Scholar 

  • Burke, E. K., Elliman, D. G., & Weare, R. F. (1994). A genetic algorithm for university timetabling. In Proceedings of the AISB workshop on evolutionary computing, University of Leeds, UK, 11–13 April 1994.

  • Burke, E. K., Elliman, D. G., Ford, P. H., & Weare, R. F. (1996a). Examination timetabling in British universities: a survey. In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 76–90). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., Newall, J. P., & Weare, R. F. (1996b). A memetic algorithm for university exam timetabling. In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 241–250). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., Jackson, K., Kingston, J. H., & Weare, R. (1997). Automated university timetabling: the state of the art. The Computer Journal, 40(9), 565–571.

    Google Scholar 

  • Burke, E. K., Kingston, J., & Pepper, P. A. (1998a). A standard data format for timetabling instances. In E. K. Burke & M. W. Carter (Eds.), Lecture notes in computer science : Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference (pp. 215–224). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., Newall, J. P., & Weare, R. F. (1998b). Initialisation strategies and diversity in evolutionary timetabling. Evolutionary Computation, 6(1), 81–103.

    Google Scholar 

  • Burke, E. K., Newall, J. P., & Weare, R. F. (1998c). A simple heuristically guided search for the timetable problem. In Proceedings of the international ICSC symposium on engineering of intelligent systems (EIS98) (pp. 574–579).

  • Burke, E. K., MacCarthy, B., Petrovic, S., & Qu, R. (2000). Structured cases in CBR—Re-using and adapting cases for timetabling problems. Knowledge-Based Systems, 13(2–3), 159–165.

    Google Scholar 

  • Burke, E. K., Bykov, Y., & Petrovic, S. (2001). A multi-criteria approach to examination timetabling. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 118–131). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., Hart, E., Kendall, G., Newall, J., Ross, P., & Schulenburg, S. (2003a). Hyper-heuristics: an emerging direction in modern search technology. In F. Glover & G. Kochenberger (Eds.), Handbook of meta-heuristics (pp. 457–474). Dordrecht: Kluwer.

    Google Scholar 

  • Burke, E. K., Kendall, G., & Soubeiga, E. (2003b). A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics, 9, 451–470.

    Google Scholar 

  • Burke, E. K., Bykov, Y., Newall, J. P., & Petrovic, S. (2004a). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6), 509–528.

    Google Scholar 

  • Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004b). The state of the art of nurse rostering. Journal of Scheduling, 7(6), 441–499.

    Google Scholar 

  • Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. (2004c). Analysing similarity in examination timetabling. In: E. K. Burke, M. Trick (Eds.), Proceedings of the 5th international conference on the practice and theory of automated timetabling (pp. 89–106), Pittsburgh, PA, USA, August 2004.

  • Burke, E. K., Kingston, J. H., & de Werra, D. (2004d). Applications to timetabling. In J. Gross & J. Yellen (Eds.), The handbook of graph theory (pp. 445–474). London: Chapman Hall/CRC.

    Google Scholar 

  • Burke, E. K., Dror, M., Petrovic, S., & Qu, R. (2005). Hybrid graph heuristics in hyper-heuristics applied to exam timetabling problems. In B. L. Golden, S. Raghavan, & E. A. Wasil (Eds.), The next wave in computing, optimisation, and decision technologies (pp. 79–91). Maryland: Springer.

    Google Scholar 

  • Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. (2006a). Hybrid variable neighbourhood approaches to university exam timetabling (Technical Report NOTTCS-TR-2006-2). School of Computer Science, University of Nottingham.

  • Burke, E. K., Petrovic, S., & Qu, R. (2006b). Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9, 115–132.

    Google Scholar 

  • Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph based hyper-heuristic for exam timetabling problems. European Journal of Operational Research, 176, 177–192.

    Google Scholar 

  • Caramia, M., Dell’Olmo, P., & Italiano, G. F. (2001). New algorithms for examination timetabling. In S. Naher & D. Wagner (Eds.), Lecture notes in computer science : Vol. 1982. Algorithm engineering 4th international workshop, proceedings WAE 2000 (pp. 230–241). Berlin: Springer.

    Google Scholar 

  • Caramia, M., Dell’Olmo, P., & Italiano, G. F. (2008). Novel local-search-based approaches to university examination timetabling. INFORMS Journal of Computing, 20(1), 86–99.

    Google Scholar 

  • Carter, M. W. (1983). A decomposition algorithm for practical timetabling problems (Technical Paper 83-06). Department of Industrial Engineering, University of Toronto.

  • Carter, M. W. (1986). A survey of practical applications of examination timetabling algorithms. Operations Research, 34(2), 193–202.

    Google Scholar 

  • Carter, M. W., & Johnson, D. G. (2001). Extended clique initialisation in examination timetabling. Journal of Operational Research Society, 52, 538–544.

    Google Scholar 

  • Carter, M. W., & Laporte, G. (1996). Recent developments in practical examination timetabling. In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 3–21). Berlin: Springer.

    Google Scholar 

  • Carter, M. W., Laporte, G., & Chinneck, J. W. (1994). A general examination scheduling system. Interfaces, 24, 109–120.

    Google Scholar 

  • Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithmic strategies and applications. Journal of Operational Research Society, 47(3), 373–383.

    Google Scholar 

  • Casey, S., & Thompson, J. (2003). GRASPing the examination scheduling problem. In E. K. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science : Vol. 2740. Practice and theory of automated timetabling IV: selected papers from the 4th international conference (pp. 232–244). Berlin: Springer.

    Google Scholar 

  • Chand, A. (2005). A constraint based genetic model for representing complete University timetabling data. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Proceedings of the 5th international conference on the practice and theory of automated timetabling (pp. 125–150). Berlin: Springer.

    Google Scholar 

  • Colijn, A. W., & Layfield, C. (1995a). Conflict reduction in examination schedules. In E. K. Burke & P. Ross (Eds.), Proceedings of the 1st international conference on the practice and theory of automated timetabling. (pp. 297–307), 30 August–1 September 1995. Edinburgh: Napier University.

    Google Scholar 

  • Colijn, A. W., & Layfield, C. (1995b). Interactive improvement of examination schedules. In E. K. Burke & P. Ross (Eds.), Proceedings of the 1st international conference on the practice and theory of automated timetabling (pp. 112–121), 30 August–1 September 1995. Edinburgh: Napier University.

    Google Scholar 

  • Cooper, T. B., & Kingston, J. H. (1996). The complexity of timetable construction problems. In E. K. Burke (Ed.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 283–295). Berlin: Springer.

    Google Scholar 

  • Corne, D., Ross, P., & Fang, H. (1994). Evolutionary timetabling: Practice, prospects and work in progress. In P. Prosser (Ed.), Proceedings of UK planning and scheduling SIG workshop.

  • Corr, P. H., McCollum, B., McGreevy, M. A. J., & McMullan, P. (2006). A new neural network based construction heuristic for the examination timetabling problem. In The international conference on parallel problem solving from nature (PPSN 2006) (pp. 392–401), Reykjavik, Iceland, September 2006.

  • Costa, D., & Hertz, A. (1997). Ant can colour graphs. Journal of Operational Research Society, 48, 295–305.

    Google Scholar 

  • Côté, P., Wong, T., & Sabouri, R. (2005). Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: selected papers from the 5th international conference (pp. 151–168). Berlin: Springer.

    Google Scholar 

  • David, P. (1998). A constraint-based approach for examination timetabling using local repair techniques. In E. K. Burke & M. W. Carter (Eds.), Lecture notes in computer science : Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference (pp. 169–186). Berlin: Springer.

    Google Scholar 

  • De Causmaecker, P., Lu, Y., Demeester, P., & Vanden Berghe, G. (2002). Using web standards for timetabling. In E. K. Burke & P. De Causmaecker (Eds.), Proceedings of the 4th international conference on practice and theory of automated timetabling (pp. 238–257), KaHo St.-Lieven, Gent, Belgium, 21–23 August 2002.

  • de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19, 151–162.

    Google Scholar 

  • de Werra, D. (1997). Restricted colouring models for timetabling. Discrete Mathematics, 165/166, 161–170.

    Google Scholar 

  • de Werra, D., Asratian, A. S., & Durand, S. (2002). Complexity of some special types of timetabling problems. Journal of Scheduling, 5, 171–183.

    Google Scholar 

  • Di Gaspero, L. (2002). Recolour, shake and kick: A recipe for the examination timetabling problem. In: E. K. Burke & P. De Causmaecker (Eds.), Proceedings of the 4th international conference on practice and theory of automated timetabling (pp. 404–407), KaHo St.-Lieven, Gent, Belgium, 21–23 August 2002.

  • Di Gaspero, L., & Schaerf, A. (2001). Tabu search techniques for examination timetabling. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 104–117). Berlin: Springer.

    Google Scholar 

  • Di Gaspero, L., & Schaerf, A. (2003). EasyLocal++: an object-oriented framework for flexible design of local search algorithms. Software, Practice & Experience, 33(8), 733–765.

    Google Scholar 

  • Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130, 202–213.

    Google Scholar 

  • Dorigo, M., & Blum, C. (2005). Ant colony optimisation theory: a survey. Theoretical Computer Science, 344(2–3), 243–278.

    Google Scholar 

  • Dowsland, K. A. (1996). Simulated annealing solutions for multi-objective scheduling and timetabling. In V. J. R. Smith, I. H. Osman, C. R. Reeves, & G. D. Smith (Eds.), Modern heuristic search methods (pp. 155–166). New York: Wiley.

    Google Scholar 

  • Dowsland, K. A., & Thompson, J. (2005). Ant colony optimisation for the examination scheduling problem. Journal of Operational Research Society, 56, 426–438.

    Google Scholar 

  • Dueck, G. (1993). New optimization heuristics: the great deluge and the record-to-record travel. Journal of Computational Physics, 104, 86–92.

    Google Scholar 

  • Duong, T. A., & Lam, K. H. (2004). Combining constraint programming and simulated annealing on university exam timetabling. In Proceedings of the 2nd international conference in computer sciences, research, innovation & vision for the future (RIVF2004) (pp. 205–210), Hanoi, Vietnam, 2–5 February, 2004.

  • Easton, K., Nemhauser, G., & Trick, M. (2004). Sports scheduling. In J. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis. Boca Raton: CRC Press, Chap. 52.

    Google Scholar 

  • Eley, M. (2007). Ant algorithms for the exam timetabling problem. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 364–382). Berlin: Springer.

    Google Scholar 

  • Erben, W. (2001). A grouping genetic algorithm for graph colouring and exam timetabling. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 132–156). Berlin: Springer.

    Google Scholar 

  • Ersoy, E., Özcan, E., & Etaner, A. S. (2007). Memetic algorithms and hyperhill-climbers. In Proceedings of the 3rd multidisciplinary international conference on scheduling: theory and applications (pp. 159–166), Paris, France, August 2007.

  • Freuder, E. C., & Wallace, M. (2005). Constraint programming. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 239–272). Berlin: Springer.

    Google Scholar 

  • Gendreau, M., & Potvin, J. Y. (2005). Tabu search. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 165–186). Berlin: Springer. ISBN: 0387234608.

    Google Scholar 

  • Glover, F., & Kochenberger, G. A. (2003). Handbook of meta-heuristics. Dordrecht: Kluwer.

    Google Scholar 

  • Glover, F., & Laguna, M. (1993). Tabu search. In C. R. Reeves (Ed.), Modern heuristic techniques for combinatorial problems. Oxford: Scientific Publications.

    Google Scholar 

  • Goltz, H. J., & Matzke, D. (1999). University timetabling using constraint logic programming. In Lecture notes in computer science : Vol. 1551. Practical aspects of declarative languages (pp. 320–334). Berlin: Springer.

    Google Scholar 

  • Hansen, P., & Mladenović, N. (2001). Variable neighbourhood search: principles and applications. European Journal of Operational Research, 130, 449–467.

    Google Scholar 

  • Hansen, M. P., & Vidal, R. V. V. (1995). Planning of high school examinations in Denmark. European Journal of Operational Research, 87, 519–534.

    Google Scholar 

  • Hansen, M. P., Lauersen, V., & Vidal, R. V. V. (1995). Nationwide scheduling of examinations: lessons from experience. In E. K. Burke & P. Ross (Eds.), Proceedings of the 1st international conference on the practice and theory of automated timetabling (pp. 468–473), 30 August–1 September 1995. Edinburgh: Napier University.

    Google Scholar 

  • Ho, W. K., Lim, A., & Oon, W. C. (2001). Maximising paper spread in examination timetabling using a vehicle routing method. In Proceedings of 13th IEEE international conference on tools with artificial intelligence (ICTAI01) (pp. 359–366).

  • Hussin, N. (2005). Tabu search based hyper-heuristic approaches for examination timetabling. PhD thesis, Department of Computer Science, University of Nottingham, UK, November 2005.

  • Kendall, G., & Hussin, N. M. (2005a). A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA university of technology. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: selected papers from the 5th international conference (pp. 199–218). Berlin: Springer.

    Google Scholar 

  • Kendall, G., & Hussin, N. M. (2005b). An investigation of a tabu search based hyper-heuristic for examination timetabling. In G. Kendall, E. Burke, & S. Petrovic (Eds.), Selected papers from multidisciplinary scheduling; theory and applications (pp. 309–328).

  • Kingston, J. H. (1995). Bibliography on practice and theory of automated timetabling. http://liinwww.ira.uka.de/bibliography/Misc/timetabling.html.

  • Kingston, J. H. (2001). Modelling timetabling problems with STTL. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 309–321). Berlin: Springer.

    Google Scholar 

  • Krasnogor, N., & Smith, J. E. (2005). A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Transactions on Evolutionary Computation, 9(5), 474–488.

    Google Scholar 

  • Kwan, R. (2004). Bus and train driver scheduling. In J. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance. Boca Ratom: CRC Press, Chap. 51.

    Google Scholar 

  • Landa Silva, J. D., Burke, E. K., & Petrovic, S. (2004). An introduction to multi-objective meta-heuristics for scheduling and timetabling. In X. Gandibleux, M. Sevaux, K. Sorensen, & V. Tkindt (Eds.), Lecture notes in economics and mathematical systems : Vol. 535. Multiple objective meta-heuristics (pp. 91–129). Berlin: Springer.

    Google Scholar 

  • Le Huédé, F., Grabisch, M., Labreuche, C., & Savéant, P. (2006). MCS—a new algorithm for multicriteria optimisation in constraint programming. Annals of Operational Research, 147, 143–174.

    Google Scholar 

  • Leake, D. B. (1996). Case based reasoning: experiences, lessons, and future directions. Menlo Park: AAAI Press/MIT Press.

    Google Scholar 

  • Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167–190.

    Google Scholar 

  • Lim, A., Chin, A. J., Kit, H. W., & Oon, W. C. (2000). A campus-wide university examination timetabling application. In Proceedings of the 17th national conference on artificial intelligence and 12th conference on innovative applications of artificial intelligence (pp. 1020–1025).

  • Lin, S. L. M. (2002). A broker algorithm for timetabling problem. In E. K. Burke & P. De Causmaecker (Eds.), Proceedings of the 4th international conference on practice and theory of automated timetabling, (pp. 372–386), KaHo St.-Lieven, Gent, Belgium, 21–23 August 2002.

  • Lourenço, H. R., Martin, O., & Stützle, T. (2003). Iterated local search. In F. Glover & G. A. Kochenberher (Eds.), Handbook of meta-heuristics (pp. 321–354). Boston: Kluwer Academic.

    Google Scholar 

  • Malim, M. R., Khader, A. T., & Mustafa, A. (2006). Artificial immune algorithms for university timetabling. In E. K. Burke & H. Rudova (Eds.). Proceedings of the 6th international conference on practice and theory of automated timetabling (pp. 234–245), Brno, Czech Republic, August 2006.

  • McCollum, B. G. C. (2007). A perspective on bridging the gap between theory and practice in university timetabling. In E. K. Burke & H. Rudova (Eds.), Lecture Notes in Computer Science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 3–23). Berlin: Springer.

    Google Scholar 

  • McCollum, B., McMullan, P., Burke, E. K., Parkes, A. J., & Qu, R. (2008). The second international timetabling competition: examination timetabling track (Technical Report QUB/IEEE/Tech/ITC2007/Exam/v1.0/1). Queen’s Belfast University, N. Ireland.

  • Mehta, N. K. (1981). The application of a graph colouring method to an examination scheduling problem. Interfaces, 11, 57–64.

    Google Scholar 

  • Mehta, N. K. (1982). A computer-based examination management system. Journal of Educational Technology Systems, 11, 185–198.

    Google Scholar 

  • Merkle, D., & Middendorf, M. (2005). Swarm intelligence. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 401–436). Berlin: Springer.

    Google Scholar 

  • Merlot, L. T. G., Boland, N., Hughes, B. D., & Stuckey, P. J. (2003). A hybrid algorithm for the examination timetabling problem. In E. K. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science : Vol. 2740. Practice and theory of automated timetabling IV: selected papers from the 4th international conference (pp. 207–231). Berlin: Springer.

    Google Scholar 

  • Miles, R. (1975). Computer timetabling: a bibliography. British Journal of Educational Technology, 6(3), 16–20.

    Google Scholar 

  • Mladenović, N., & Hansen, P. (1997). Variable neighbourhood search. Computers and Operations Research, 24(11), 1097–1100.

    Google Scholar 

  • Moscato, P., & Norman, M. G. (1992). A “memetic” approach for the travelling salesman problem—implementation of a computational ecology for combinatorial optimisation on message passing systems. In Proceedings of the international conference on parallel computing and transputer applications (pp. 177–186). Amsterdam: IOS Press.

    Google Scholar 

  • Naji Azimi, Z. (2004). Comparison of metaheuristic algorithms for examination timetabling problem. Applied Mathematics and Computation, 16(1–2), 337–354.

    Google Scholar 

  • Naji Azimi, Z. (2005). Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, 163(2), 705–733.

    Google Scholar 

  • Osman, I. H., & Laporte, G. (1996). Metaheuristics: a bibliography. Annals of Operational Research, 63, 513–628.

    Google Scholar 

  • Paquete, L., & Stützle, T. (2002). An experimental investigation of iterated local search for colouring graphs. In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, & G. Raidl (Eds.), Lecture notes in computer science : Vol. 2279. Applications of evolutionary computing, EvoWorkshops 2002 (pp. 122–131). Berlin: Springer.

    Google Scholar 

  • Paquete, L., & Stützle, T. (2002). Empirical analysis of tabu search for the lexicographic optimisation of the examination timetabling problem. In E. K. Burke & P. De Causmaecker (Eds.), Proceedings of the 4th international conference on practice and theory of automated timetabling (pp. 413–420), KaHo St.-Lieven, Gent, Belgium 21–23 August 2002.

  • Petrovic, S., & Burke, E. K. (2004). University timetabling. In J. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis. Boca Raton: CRC Press. Chap. 45.

    Google Scholar 

  • Petrovic, S., & Bykov, Y. (2003). A multi-objective optimisation technique for exam timetabling based on trajectories. In E. K. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science : Vol. 2740. Practice and theory of automated timetabling IV: selected papers from the 4th international conference (pp. 179–192). Berlin: Springer.

    Google Scholar 

  • Pirlot, M. (1996). General local search methods. European Journal of Operational Research, 92, 493–511.

    Google Scholar 

  • Qu, R., & Burke, E. K. (2007). Adaptive decomposition and construction for examination timetabling problems. In Multidisciplinary international scheduling: theory and applications (MISTA’07) (pp. 418–425), Paris, France, August 2007.

  • Qu, R., & Burke, E. K. (2008, accepted). Hybridisations within a graph based hyper-heuristic framework for university timetabling problems. Journal of Operational Research Society.

  • Ranson, D., & Ahmadi, S. (2007). An extensible modelling framework for timetabling problems. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 383–393). Berlin: Springer.

    Google Scholar 

  • Reeves, C. R. (Ed.). (1993). Modern heuristic techniques for combinatorial problems. Oxford: Scientific Publications.

    Google Scholar 

  • Reeves, C. R. (2005). Fitness landscapes. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 587–610). Berlin: Springer.

    Google Scholar 

  • Reis, L. P., & Oliveira, E. (1999). Constraint logic programming using set variables for solving timetabling problems. In 12th international conference on applications of Prolog.

  • Reis, L. P., & Oliveira, E. (2001). A language for specifying complete timetabling problems. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 322–341). Berlin: Springer.

    Google Scholar 

  • Resende, M. G. C., & Ribeiro, C. C. (2003). Greedy randomised adaptive search procedures. In F. Glover & G. A. Kochenberher (Eds.), Handbook of meta-heuristics (pp. 219–249). Dordrecht: Kluwer.

    Google Scholar 

  • Romero, B. P. (1982). Examination scheduling in a large engineering school: a computer assisted participative procedure. Interfaces, 12, 17–23.

    Google Scholar 

  • Ross, P. (2005). Hyper-heuristics. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 529–556). Berlin: Springer. Chap. 17.

    Google Scholar 

  • Ross, P., Corne, D., & Terashima-Marin, H. (1996). The phase transition niche for evolutionary algorithms in timetabling. In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 309–324). Berlin: Springer.

    Google Scholar 

  • Ross, P., Hart, E., & Corne, D. (1998). Some observations about GA-based exam timetabling. In E. K. Burke & M. W. Carter (Eds.), Lecture notes in computer science : Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference (pp. 115–129). Berlin: Springer.

    Google Scholar 

  • Ross, P., Hart, E., & Corne, D. (2003). Genetic algorithms and timetabling. In A. Ghosh & S. Tsutsui (Eds.), Advances in evolutionary computing: theory and applications (pp. 755–771). New York: Springer.

    Google Scholar 

  • Ross, P., Marin-Blazquez, J. G., & Hart, E. (2004). Hyper-heuristics applied to class and exam timetabling problems. In Proceedings of the 2004 congress on evolutionary computation (CEC2004) (pp. 1691–1698). Washington: IEEE Press.

    Google Scholar 

  • Sabin, G. C. W., & Winter, G. K. (1986). The impact of automated timetabling on universities—a case study. Journal of Operational Research Society, 37, 689–693.

    Google Scholar 

  • Sastry, K., Goldberg, D., & Kendall, G. (2005). Genetic algorithms. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support techniques (pp. 97–125). Berlin: Springer. ISBN: 0387234608.

    Google Scholar 

  • Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127.

    Google Scholar 

  • Schaerf, A., & Di Gaspero, L. (2007). Measurability and reproducibility in university timetabling research: discussion and proposals. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 40–49). Berlin: Springer.

    Google Scholar 

  • Schmidt, E. A., & Strohlein, T. (1979). Timetable construction—an annotated bibliography. The Computer Journal, 23, 307–316.

    Google Scholar 

  • Sheibani, K. (2002). An evolutionary approach for the examination timetabling problems. In E. K. Burke & P. De Causmaecker (Eds.), Proceedings of the 4th international conference on practice and theory of automated timetabling (pp. 387–396), KaHo St.-Lieven, Gent, Belgium, 21–23 August 2002.

  • Simonis, H. (1995). The CHIP system and its applications. In Lecture notes in computer science : Vol. 976. First international conference on principles and practice of constraint programming (pp. 643–646). Berlin: Springer.

    Google Scholar 

  • Socha, K., Sampels, M., & Manfrin, M. (2003). Ant algorithms for the university course timetabling problem with regard to state-of-the-art. In Proceedings of the 3rd European workshop on evolutionary computation in combinatorial optimisation (pp. 334–345), Essex, UK, April 2003.

  • Terashima-Marin, H., Ross, P., & Valenzuela-Rendon, M. (1999a). Evolution of constraint satisfaction strategies in examination timetabling. In Proceedings of the genetic and evolutionary conference (pp. 635–642), Orlando, FL.

  • Terashima-Marin, H., Ross, P., & Valenzuela-Rendon, M. (1999b). Clique-based crossover for solving the timetabling problem with GAs. In Proceedings of 1999 IEEE congress on evolutionary computation (pp. 1200–1206). Washington: IEEE Press.

    Google Scholar 

  • Terashima-Marin, H., Ross, P., & Valenzuela-Rendon, M. (1999c). Application of the hardness theory when solving the timetabling problem with GAs. In Proceedings of the congress on evolutionary computation 1999 (pp. 604–611). Washington: IEEE Press.

    Google Scholar 

  • Thompson, J., & Dowsland, K. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operational Research, 63, 105–128.

    Google Scholar 

  • Thompson, J., & Dowsland, K. (1998). A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25, 637–648.

    Google Scholar 

  • Tsang, E., Mills, P., & Williams, R. (1999). A computer aided constraint programming system. In The 1st international conference on the practical application of constraint technologies and logic programming (PACLP) (pp. 81–93).

  • Ulker, O., Özcan, E., & Korkmaz, E. E. (2007). Linear linkage encoding in grouping problems: applications on graph colouring and timetabling. In E. K. Burke & H. Rudova (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI: selected papers from the 6th international conference (pp. 347–363). Berlin: Springer.

    Google Scholar 

  • Van Hentenryck, P. (1989). Logic programming series. Constraint satisfaction in logic programming. Cambridge: MIT Press.

    Google Scholar 

  • Van Hentenryck, P. (1999). The OPL optimisation programming language. Cambridge: MIT Press.

    Google Scholar 

  • Welsh, D. J. A., & Powell, M. B. (1967). The upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 11, 41–47.

    Google Scholar 

  • White, G. M. (2000). Constrained satisfaction, not so constrained satisfaction and the timetabling problem. In E. K. Burke & W. Erben (Eds.) , Proceedings of the 3rd international conference on the practice and theory of automated timetabling (pp. 32–47), Constance, Germany, 16–18 August 2000.

  • White, G. M., & Xie, B. S. (2001). Examination timetables and tabu search with longer-term memory. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 85–103). Berlin: Springer.

    Google Scholar 

  • White, G. M., Xie, B. S., & Zonjic, S. (2004). Using tabu search with longer-term memory and relaxation to create examination timetables. European Journal of Operational Research, 153(16), 80–91.

    Google Scholar 

  • Wong, T., Côté, P., & Gely, P. (2002). Final exam timetabling: a practical approach. In IEEE Canadian conference on electrical and computer engineering (CCECE 2002) (Vol. 2, pp. 726–731).

  • Wood, D. C. (1968). A system for computing university examination timetables. The Computer Journal, 11(1), 41–47.

    Google Scholar 

  • Wren, A. (1996). Scheduling, timetabling and rostering—a special relationship? In E. K. Burke & P. Ross (Eds.), Lecture notes in computer science : Vol. 1153. Practice and theory of automated timetabling I: selected papers from the 1st international conference (pp. 46–75). Berlin: Springer.

    Google Scholar 

  • Yang, Y., & Petrovic, S. (2005). A novel similarity measure for heuristic selection in examination timetabling. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: selected papers from the 5th international conference (pp. 377–396). Berlin: Springer.

    Google Scholar 

  • Zeleny, M. (1974). A concept of compromise solutions and method of displaced ideal. Computers & Operations Research, 1(4), 479–496.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, UK

    R. Qu & E. K. Burke

  2. School of Computer Science, Queens University, Belfast University Road, N. Ireland, BT7 1NN, UK

    B. McCollum

  3. Quantm Ltd, 4/333 Flinders Lane, Melbourne, 3000, Australia

    L. T. G. Merlot

  4. Mechanical and Industrial Engineering, University of Toronto, 5 King’s College Road, Toronto, ON, M5S 3G8, Canada

    S. Y. Lee

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

  3. B. McCollum
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. L. T. G. Merlot
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. S. Y. Lee
    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.K., McCollum, B. et al. A survey of search methodologies and automated system development for examination timetabling. J Sched 12, 55–89 (2009). https://doi.org/10.1007/s10951-008-0077-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-008-0077-5

Keywords

Search

Navigation