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

*(English)*Zbl 1279.90071Summary: 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.

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.

Full Text:
DOI

##### References:

[1] | Aarts, E. H. L., & Korst, J. (1989). Simulated annealing and Boltzmann machines. New York: Wiley. · Zbl 0674.90059 |

[2] | 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. · Zbl 1129.90061 |

[3] | 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. · Zbl 1170.90383 · doi:10.1007/s00291-006-0034-7 |

[4] | 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. · Zbl 1177.90139 · doi:10.1057/palgrave.jors.2602258 |

[5] | 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. |

[6] | 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. · Zbl 1051.90019 |

[7] | 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. |

[8] | 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. |

[9] | 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. |

[10] | 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. |

[11] | 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. |

[12] | 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. |

[13] | Boizumault, P., Delon, Y., & Peridy, L. (1996). Constraint logic programming for examination timetabling. Journal of Logic Programming, 26(2), 217–233. · Zbl 0871.68056 · doi:10.1016/0743-1066(95)00100-X |

[14] | Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119, 557–581. · Zbl 0938.90055 · doi:10.1016/S0377-2217(98)00364-6 |

[15] | Brelaz, D. (1979). New methods to colour the vertices of a graph. Communication of the ACM, 22(4), 251–256. · Zbl 0394.05022 · doi:10.1145/359094.359101 |

[16] | Broder, S. (1964). Final examination scheduling. Communications of the ACM, 7, 494–498. · Zbl 0221.68079 · doi:10.1145/355586.364824 |

[17] | 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. |

[18] | 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. |

[19] | 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. |

[20] | 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. · Zbl 0968.68560 |

[21] | Burke, E. K., & Kendall, G. (Eds.). (2005). Search methodologies: introductory tutorials in optimisation and decision support techniques. Berlin: Springer. ISBN: 0387234608. · Zbl 1140.90015 |

[22] | 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. |

[23] | 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. · Zbl 05451925 · doi:10.1109/4235.752921 |

[24] | 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. |

[25] | Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaptation of heuristic orderings. Annals of Operational Research, 129, 107–134. · Zbl 1056.90141 · doi:10.1023/B:ANOR.0000030684.30824.08 |

[26] | Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280. · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3 |

[27] | 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. |

[28] | 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. |

[29] | 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. |

[30] | 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. |

[31] | 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. |

[32] | 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. |

[33] | 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. · Zbl 05471035 · doi:10.1093/comjnl/40.9.565 |

[34] | 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. |

[35] | Burke, E. K., Newall, J. P., & Weare, R. F. (1998b). Initialisation strategies and diversity in evolutionary timetabling. Evolutionary Computation, 6(1), 81–103. · Zbl 05412731 · doi:10.1162/evco.1998.6.1.81 |

[36] | 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). |

[37] | 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. · doi:10.1016/S0950-7051(00)00057-5 |

[38] | 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. · Zbl 0982.68522 |

[39] | 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. · Zbl 1102.90377 |

[40] | Burke, E. K., Kendall, G., & Soubeiga, E. (2003b). A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics, 9, 451–470. · doi:10.1023/B:HEUR.0000012446.94732.b6 |

[41] | 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. · doi:10.1080/07408170490438410 |

[42] | 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. · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b |

[43] | 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. |

[44] | 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. |

[45] | 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. |

[46] | 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. · Zbl 1188.90090 |

[47] | Burke, E. K., Petrovic, S., & Qu, R. (2006b). Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9, 115–132. · Zbl 1154.90423 · doi:10.1007/s10951-006-6775-y |

[48] | 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. · Zbl 1137.90602 · doi:10.1016/j.ejor.2005.08.012 |

[49] | 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. |

[50] | 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. · Zbl 1243.90222 · doi:10.1287/ijoc.1070.0220 |

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

[52] | Carter, M. W. (1986). A survey of practical applications of examination timetabling algorithms. Operations Research, 34(2), 193–202. · doi:10.1287/opre.34.2.193 |

[53] | Carter, M. W., & Johnson, D. G. (2001). Extended clique initialisation in examination timetabling. Journal of Operational Research Society, 52, 538–544. · Zbl 1114.90378 · doi:10.1057/palgrave.jors.2601115 |

[54] | 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. |

[55] | Carter, M. W., Laporte, G., & Chinneck, J. W. (1994). A general examination scheduling system. Interfaces, 24, 109–120. · doi:10.1287/inte.24.3.109 |

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

[57] | 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. |

[58] | 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. |

[59] | 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. |

[60] | 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. |

[61] | 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. |

[62] | 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. |

[63] | 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. |

[64] | Costa, D., & Hertz, A. (1997). Ant can colour graphs. Journal of Operational Research Society, 48, 295–305. · Zbl 0890.90174 |

[65] | 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. |

[66] | 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. |

[67] | 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. |

[68] | de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19, 151–162. · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5 |

[69] | de Werra, D. (1997). Restricted colouring models for timetabling. Discrete Mathematics, 165/166, 161–170. · Zbl 0876.90060 · doi:10.1016/S0012-365X(96)00208-7 |

[70] | de Werra, D., Asratian, A. S., & Durand, S. (2002). Complexity of some special types of timetabling problems. Journal of Scheduling, 5, 171–183. · Zbl 0996.90039 · doi:10.1002/jos.97 |

[71] | 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. |

[72] | 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. · Zbl 0982.68784 |

[73] | 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. · Zbl 01963260 · doi:10.1002/spe.524 |

[74] | Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130, 202–213. · Zbl 0985.90046 · doi:10.1016/S0377-2217(00)00052-7 |

[75] | Dorigo, M., & Blum, C. (2005). Ant colony optimisation theory: a survey. Theoretical Computer Science, 344(2–3), 243–278. · Zbl 1154.90626 · doi:10.1016/j.tcs.2005.05.020 |

[76] | 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. |

[77] | Dowsland, K. A., & Thompson, J. (2005). Ant colony optimisation for the examination scheduling problem. Journal of Operational Research Society, 56, 426–438. · Zbl 1104.90019 · doi:10.1057/palgrave.jors.2601830 |

[78] | Dueck, G. (1993). New optimization heuristics: the great deluge and the record-to-record travel. Journal of Computational Physics, 104, 86–92. · Zbl 0773.65042 · doi:10.1006/jcph.1993.1010 |

[79] | 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. |

[80] | 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. · Zbl 1183.90451 |

[81] | 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. |

[82] | 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. · Zbl 0982.68512 |

[83] | 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. |

[84] | 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. |

[85] | 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. · Zbl 1137.90725 |

[86] | Glover, F., & Kochenberger, G. A. (2003). Handbook of meta-heuristics. Dordrecht: Kluwer. · Zbl 1058.90002 |

[87] | Glover, F., & Laguna, M. (1993). Tabu search. In C. R. Reeves (Ed.), Modern heuristic techniques for combinatorial problems. Oxford: Scientific Publications. · Zbl 0774.90033 |

[88] | 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. |

[89] | Hansen, P., & Mladenović, N. (2001). Variable neighbourhood search: principles and applications. European Journal of Operational Research, 130, 449–467. · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4 |

[90] | Hansen, M. P., & Vidal, R. V. V. (1995). Planning of high school examinations in Denmark. European Journal of Operational Research, 87, 519–534. · Zbl 0915.90149 · doi:10.1016/0377-2217(95)00227-8 |

[91] | 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. |

[92] | 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). |

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

[94] | 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. |

[95] | 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). |

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

[97] | 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. · Zbl 0987.68975 |

[98] | 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. · Zbl 05452085 · doi:10.1109/TEVC.2005.850260 |

[99] | 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. |

[100] | 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. · Zbl 1139.90420 |

[101] | 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. · Zbl 1188.90241 · doi:10.1007/s10479-006-0064-1 |

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

[103] | Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167–190. · Zbl 1133.90341 · doi:10.1007/s00291-007-0097-0 |

[104] | 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). |

[105] | 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. |

[106] | 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. · Zbl 1116.90412 |

[107] | 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. |

[108] | 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. |

[109] | 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. · Zbl 1243.90007 |

[110] | Mehta, N. K. (1981). The application of a graph colouring method to an examination scheduling problem. Interfaces, 11, 57–64. · doi:10.1287/inte.11.5.57 |

[111] | Mehta, N. K. (1982). A computer-based examination management system. Journal of Educational Technology Systems, 11, 185–198. · doi:10.2190/T2A4-GVQW-M5DN-EKCT |

[112] | 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. |

[113] | 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. |

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

[115] | Mladenović, N., & Hansen, P. (1997). Variable neighbourhood search. Computers and Operations Research, 24(11), 1097–1100. · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2 |

[116] | 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. |

[117] | Naji Azimi, Z. (2004). Comparison of metaheuristic algorithms for examination timetabling problem. Applied Mathematics and Computation, 16(1–2), 337–354. · Zbl 1129.90318 |

[118] | Naji Azimi, Z. (2005). Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, 163(2), 705–733. · Zbl 1116.90413 · doi:10.1016/j.amc.2003.10.061 |

[119] | Osman, I. H., & Laporte, G. (1996). Metaheuristics: a bibliography. Annals of Operational Research, 63, 513–628. · Zbl 0849.90097 · doi:10.1007/BF02125421 |

[120] | 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. · Zbl 1044.68788 |

[121] | 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. |

[122] | 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. |

[123] | 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. |

[124] | Pirlot, M. (1996). General local search methods. European Journal of Operational Research, 92, 493–511. · Zbl 0914.90227 · doi:10.1016/0377-2217(96)00007-0 |

[125] | 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. |

[126] | Qu, R., & Burke, E. K. (2008, accepted). Hybridisations within a graph based hyper-heuristic framework for university timetabling problems. Journal of Operational Research Society. · Zbl 1196.90071 |

[127] | 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. |

[128] | Reeves, C. R. (Ed.). (1993). Modern heuristic techniques for combinatorial problems. Oxford: Scientific Publications. · Zbl 0942.90500 |

[129] | 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. |

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

[131] | 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. · Zbl 0982.68517 |

[132] | 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. · Zbl 1102.90384 |

[133] | Romero, B. P. (1982). Examination scheduling in a large engineering school: a computer assisted participative procedure. Interfaces, 12, 17–23. · doi:10.1287/inte.12.2.17 |

[134] | 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. |

[135] | 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. |

[136] | 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. |

[137] | 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. |

[138] | 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. |

[139] | 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. |

[140] | 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. |

[141] | Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. · Zbl 05467698 · doi:10.1023/A:1006576209967 |

[142] | 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. |

[143] | Schmidt, E. A., & Strohlein, T. (1979). Timetable construction–an annotated bibliography. The Computer Journal, 23, 307–316. · doi:10.1093/comjnl/23.4.307 |

[144] | 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. |

[145] | 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. |

[146] | 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. · Zbl 1033.90508 |

[147] | 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. |

[148] | 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. |

[149] | 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. |

[150] | Thompson, J., & Dowsland, K. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operational Research, 63, 105–128. · Zbl 0851.90069 · doi:10.1007/BF02601641 |

[151] | Thompson, J., & Dowsland, K. (1998). A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25, 637–648. · Zbl 1042.90568 · doi:10.1016/S0305-0548(97)00101-9 |

[152] | 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). |

[153] | 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. |

[154] | Van Hentenryck, P. (1989). Logic programming series. Constraint satisfaction in logic programming. Cambridge: MIT Press. · Zbl 0707.68101 |

[155] | Van Hentenryck, P. (1999). The OPL optimisation programming language. Cambridge: MIT Press. |

[156] | 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. · Zbl 0147.15206 |

[157] | 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. |

[158] | 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. · Zbl 0982.68630 |

[159] | 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. · Zbl 1053.90047 · doi:10.1016/S0377-2217(03)00100-0 |

[160] | 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). |

[161] | Wood, D. C. (1968). A system for computing university examination timetables. The Computer Journal, 11(1), 41–47. · Zbl 0157.24004 · doi:10.1093/comjnl/11.1.41 |

[162] | 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. |

[163] | 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. |

[164] | Zeleny, M. (1974). A concept of compromise solutions and method of displaced ideal. Computers & Operations Research, 1(4), 479–496. · doi:10.1016/0305-0548(74)90064-1 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.