Skip to main content
SpringerLink
Log in

Solving Examination Timetabling Problems through Adaption of Heuristic Orderings

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance “on the fly.” This method provides an alternative to existing forms of ‘backtracking,’ which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.

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

Similar content being viewed by others

References

  • Asmuni, M., E.K. Burke, and J.M. Garibaldi. (2004). “Fuzzy Multiple Ordering Criteria for Examination Timetabling.” University of Nottingham School of Computer Science and IT Technical Report NOTTCS-TR-2004–4.

  • Bardadym, V.A. (1996). “Computer-Aided School and University Timetabling: A New Wave.” In E. Burke (ed.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 22–45. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Boizumault, P., Y. Delon, and L. Peridy. (1996). “Constraint Logic Programming for Examination Timetabling.” Journal of Logic Programming 26(2), 217–233.

    Google Scholar 

  • Boufflet, J.P. and S. Negre. (1996). “Three Methods Used to Solve an Examination Timetable Problem.” In E. Burke and P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 327–344. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Brelaz, D. (1979). “New Methods to Colour the Vertices of a Graph.” Communications of the Association for Computing Machinery 22, 251–256.

    Google Scholar 

  • Bullnheimer, B. (1998). “An Examination Scheduling Model to Maximize Students' Study Time.” In E.K. Burke (ed.), pp. 78–91. Lecture Notes in Computer Science, Vol. 1408. Berlin: Springer.

    Google Scholar 

  • Burke, E.K., Y. Bykov, and S. Petrovic. (2001). “A Multicriteria Approach to Timetabling.” In E.K. Burke and W. Erben (eds.), Practice and Theory of Automated Timetabling III, pp. 118–131. Lecture Notes in Computer Science, Vol. 2079. Berlin: Springer.

    Google Scholar 

  • Burke, E.K., D. de Werra, and J.M. Kingston. (2004). “Applications to Timetabling.” In J. Gross and J. Yeller (eds.), Handbook of Graph Theory, section 5.6, pp. 445–474. CRC Press.

  • Burke, E.K. and S. Petrovic. (2002). “Recent Research Directions in Automated Timetabling.” European Journal of Operations Research, to appear.

  • Burke, E.K., D.G. Elliman, P.H. Ford, and R.F. Weare. (1996). “Examination Timetabling in British Universities-A Survey.” In E. Burke and P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 76–90. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Burke, E.K., D.G. Elliman, and R.F. Weare. (1994). “A University Timetabling System Based on Graph Colouring and Constraint Manipulation.” Journal of Research on Computing in Education 27(1), 1–18.

    Google Scholar 

  • Burke, E.K., D.G. Elliman, and R.F.Weare. (1995a). “A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems.” In L.J. Eshelman (ed.), Genetic Algorithms: Proceedings of the 6th International Conference, pp. 605–610. San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Burke, E.K., D.G. Elliman, and R.F. Weare. (1995b). “Specialised Recombinative Operators for Timetabling Problems.” In T.C. Fogarty (ed.), AISB Workshop on Evolutionary Computing, pp. 75–85. Lecture Notes in Computer Science, Vol. 993. Berlin: Springer.

    Google Scholar 

  • Burke, E.K., K. Jackson, J.H. Kingston, and R.F. Weare. (1997). “Automated University Timetabling: The State of the Art.” The Computer Journal 40(9), 565–571.

    Google Scholar 

  • Burke, E.K., G. Kendall, J.P. Newall, E. Hart, P. Ross, and Schulenburg. (2003). “Hyper-heuristics: An Emerging Direction inModern Search Technology.” In F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, chapter 16, pp. 457–474. Kluwer.

  • Burke, E.K. and J.P. Newall. (1999). “A Multi-Stage Evolutionary Algorithm for the Timetable Problem.” IEEE Transactions on Evolutionary Computation 3(1), 63–74.

    Google Scholar 

  • Burke, E.K., J.P. Newall, and R.F. Weare. (1996). “A Memetic Algorithmfor University Exam Timetabling.” In E. Burke and P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 241–250. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Burke, E.K., J.P. Newall, and R.F. Weare. (1998a). “Initialization Strategies and Diversity in Evolutionary Timetabling.” Evolutionary Computation 6(1), 81–103.

    Google Scholar 

  • Burke, E.K., J.P. Newall, and R.F. Weare. (1998b). “A Simple Heuristically Guided Search for the Timetable Problem.” In International ICSC Symposium on Engineering of Intelligent Systems (EIS '98), pp. 574–579. Canada/Switzerland: ICSC/Academic Press.

    Google Scholar 

  • Burke, E.K., P.M. Ross, P.I. Cowling, S. Petrovic, and G. Kendall. (2000). “An Investigation of Hyper-Heuristic Methods.” Research Project Funded by the Engineering and Physical Sciences Research Council (EPSRC), Grant Ref. GR/N36837/01.

  • Carter, M.W. (1986). “A Survey of Practical Applications of Examination Timetabling.” Operations Research 34, 193–202.

    Google Scholar 

  • Carter, M.W. and D.G. Johnson. (2001). “Extended Clique Initialization in Examination Timetabling.” Journal of the Operational Research Society 52(5), 538–544.

    Google Scholar 

  • Carter, M.W. and G. Laporte. (1996). “Recent Developments in Practical Examination Timetabling.” In E. Burke and P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 3–21. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Carter, M.W., G. Laporte, and J.W. Chinneck. (1994). “A General Examination Scheduling System.” Interfaces 11, 109–120.

    Google Scholar 

  • Carter, M.W., G. Laporte, and S. Lee. (1996). “Examination Timetabling: Algorithmic Strategies and Applications.” Journal of the Operational Research Society 47(3), 373–383.

    Google Scholar 

  • Corne, D., H.L. Fang, and C. Mellish. (1993). “Solving the Modular Exam Scheduling Problem with Genetic Algorithms.” In Proceedings of the 6th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, pp. 370–373.

  • Corne, D. and P. Ross. (1996). “Peckish Initialisation Strategies for Evolutionary Timetabling.” In E. Burke (ed.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 227–240. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Corne, D., P. Ross, and H. Fang. (1994). “Fast Practical Evolutionary Timetabling.” In T.C. Fogarty (ed.), pp. 250–263. Lecture Notes in Computer Science, Vol. 865. Berlin: Springer.

    Google Scholar 

  • David, P. (1998). “A Constraint-Based Approach for Examination Timetabling Using Local Repair Techniques.” In E.K. Burke and M.W. Carter (eds.), pp. 169–186. Lecture Notes in Computer Science, Vol. 1408. Berlin: Springer.

    Google Scholar 

  • de Werra, D. (1985). “An Introduction to Timetabling.” European Journal of Operations Research 19, 151–162.

    Google Scholar 

  • de Werra, D. (1997). “Restricted Coloring Models for Timetabling.” DMATH: Discrete Mathematics 165.

  • Di Gaspero, L. and A. Schaerf. (2001). “Tabu Search Techniques for Examination Timetabling.” In E.K. Burke and W. Erben (eds.), Practice and Theory of Automated Timetabling III, pp. 104–117. Lecture Notes in Computer Science, Vol. 2079. Berlin: Springer.

    Google Scholar 

  • Dowsland, K.A. (1996). “Simulated Annealing Solutions forMulti-Objective Scheduling and Timetabling.” In Modern Heuristic Search Methods, pp. 155–166. Chichester: Wiley.

    Google Scholar 

  • Dowsland, K.A. (1998). “Off-the-Peg or Made-to-Measure Timetabling and Scheduling with SA and TS.” In E.K. Burke and M.W. Carter (eds.), Practice and Theory of Automated Timetabling II, pp. 37–52.Lecture Notes in Computer Science, Vol. 1408. Berlin: Springer.

    Google Scholar 

  • Erben, W. (2001). “A Grouping Genetic Algorithm for Graph Colouring and Exam Timetabling.” In E.K. Burke and W. Erben (eds.), Practice and Theory of Automated Timetabling III, pp. 132–156. Lecture Notes in Computer Science, Vol. 2079. Berlin: Springer.

    Google Scholar 

  • Ergul, A. (1996). “GA-Based Examination Scheduling Experience at a Middle East Technical University.” In E. Burke (ed.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 198–211. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Falkenauer, E. (1998). Genetic Algorithms and Grouping Problems. Chichester: Wiley.

    Google Scholar 

  • Foxley, E. and K. Lockyer. (1968). “The Construction of Examination Timetables by Computer.” The Computer Journal 11, 264–268.

    Google Scholar 

  • Hertz, A. (1991). “Tabu Search for Large Scale Timetabling Problems.” European Journal of Operations Research 54, 39–47.

    Google Scholar 

  • Joslin, D.E. and D.P. Clements. (1999). “Squeaky Wheel Optimization.” Journal of Artificial Intelligence Research 10, 353–373.

    Google Scholar 

  • Mehta, N.K. (1981). “The Application of a Graph Coloring Method to an Examination Scheduling Problem.” Interfaces 11, 57–64.

    Google Scholar 

  • Nuijten, W.P.M., G.M. Kunnen, E.H.L. Aarts, and F.P.M. Dignum (1994). “Examination Timetabling: A Case Study for Constraint Satisfaction.” In ECAI '94 Workshop on Constraint Satisfaction Issues Raised by Practical Applications, pp. 11–19.

  • Pettoric, S. and E.K. Burke. (2004). “University of Timetabling.” In J. Leung (ed.), Handbook of Scheduling: Algorithms, Models and Performance Analysis, chapter 45. CRC Press, to appear.

  • Ross, P. and D. Corne. (1995). “Comparing Genetic Algorithms, Simulated Annealing and Stochastic Hillclimbing on Timetable Problems.” In T.C. Fogarty (ed.), AISB Workshop on Evolutionary Computing, pp. 94–102. Lecture Notes in Computer Science, Vol. 993. Berlin: Springer.

    Google Scholar 

  • Ross, P., D. Corne, and H.-L. Fang. (1994). “Improving Evolutionary Timetabling with Delta Evaluation and Directed Mutation.” In Y. Davidor, H.-P. Schwefel, and R. Manner (eds.), Parallel Problem Solving in Nature, Vol. III, pp. 565–566. Berlin: Springer.

    Google Scholar 

  • Ross, P., E. Hart, and D. Corne. (1998). “Some Observations about GA-Based Exam Timetabling.” In E.K. Burke (ed.), p. 115–130. Lecture Notes in Computer Science, Vol. 1408. Berlin: Springer.

    Google Scholar 

  • Schaerf, A. (1999). “A Survey of Automated Timetabling.” Artificial Intelligence Review 13(2), 87–127.

    Google Scholar 

  • Selman, B. and H. Kautz. (1993). “Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems.” In Proceedings of the 13th Int'l Joint Conf. on Artificial Intelligence, pp. 290–295.

  • Terashima-Marin, H., P. Ross, and M. Valenzuela-Rendon. (1999). “Evolution of Constraint Satisfaction Strategies in Examination Timetabling.” In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 635–642. San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Thompson, J.M. and K.A. Dowsland. (1996a). “General Cooling Schedules for a Simulated Annealing Based Timetabling System.” In E. Burke (ed.), The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pp. 345–364. Lecture Notes in Computer Science, Vol. 1153. Berlin: Springer.

    Google Scholar 

  • Thompson, J.M. and K.A. Dowsland. (1996b). “Variants of Simulated Annealing for the Examination Timetabling Problem.” Annals of Operations Research 63, 105–128.

    Google Scholar 

  • Thompson, J.M. and K.A. Dowsland. (1998). “A Robust Simulated Annealing Based Examination Timetabling System.” Computers and Operations Research 25(7–8), 637–648.

    Google Scholar 

  • Welsh, D.J.A. and M.B. Powell. (1967). “An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetable Problems.” The Computer Journal 10, 85–86.

    Google Scholar 

  • White, G.M. and B.S. Xie. (2001). “Examination Timetables and Tabu Search with Longer-Term Memory.” In E.K. Burke and W. Erben (eds.), Practice and Theory of Automated Timetabling III, pp. 85–103. Lecture Notes in Computer Science, Vol. 2079. Berlin: Springer.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Automated Scheduling, Optimisation and Planning Group, School of Computer Science & IT, University of Nottingham, Nottingham, NG8 1BB, UK

    E.K. Burke

  2. eventMAP Limited, 21 Stranmillis Road, Belfast, BT9 5AF, Northern Ireland, UK

    J.P. Newall

Authors
  1. E.K. Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J.P. Newall
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Burke, E., Newall, J. Solving Examination Timetabling Problems through Adaption of Heuristic Orderings. Annals of Operations Research 129, 107–134 (2004). https://doi.org/10.1023/B:ANOR.0000030684.30824.08

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:ANOR.0000030684.30824.08

Search

Navigation