×

zbMATH — the first resource for mathematics

Investigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. (English) Zbl 1170.90383
Summary: Since the 1960s, automated approaches to examination timetabling have been explored and a wide variety of approaches have been investigated and developed. In this paper we build upon a recently presented, sequential solution improvement technique which searches efficiently over a very large set of “adjacent” (neighbourhood) solutions. This solution search methodology, originally developed by Ahuja and Orlin, has been applied successfully in the past to a number of difficult combinatorial optimisation problems. It is based on an improvement graph representation of solution adjacency and identifies improvement moves by finding cycle exchange operations using a modified shortest path label-correcting algorithm. We have drawn upon Ahuja-Orlin’s basic methodology to develop an effective automated exam timetabling technique. We have evaluated our approach against the latest methodologies in the literature on standard benchmark problems. We demonstrate that our approach produces some of the best known results on these problems.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
Hyperheuristics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja RK, Magnanti LT, Orlin JB (1993) Network flows: theory, algorithms, and applications. ISBN 1000499012. Prentice Hall, Englewood Cliffs, pp 133–165
[2] Ahuja RK, Orlin JB, Sharma D (2000) Very large scale neighbourhood search. Int Trans Oper Res 7:301–317 · doi:10.1111/j.1475-3995.2000.tb00201.x
[3] Ahuja RK, Orlin JB, Sharma D (2001) Multiexchange neighbourhood search algorithm for capacitated minimum spanning tree problem. Math Program 91:71–97
[4] Ahuja RK, Ozlem E, Orlin JB, Abraham OP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl Math 123:75–102 · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[5] Ahuja RK, Orlin JB, Sharma D (2003) A composite neighbourhood search algorithm for capacitated spanning tree problem. Oper Res Lett 31:185–194 · Zbl 1064.90039 · doi:10.1016/S0167-6377(02)00236-5
[6] Asmuni H, Burke EK, Garibaldi JM (2005) Fuzzy multiple ordering criteria for examination timetabling. In: Burke E, Trick M (eds) The practice and theory of automated timetabling V: selected papers from the 5th International Conference, lecture notes in computer science 3616. Springer, Berlin Heidelberg New York, pp 334–353
[7] Ayob M, Kendall G (2003) A Monte Carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. In: Proceedings of the International Conference on Intelligent Technologies, InTech’03, Chiang Mai, pp 132–141
[8] Balakrishnan N, Lucena A, Wong RT (1992) Scheduling examinations to reduce second order conflicts. Comput Oper Res 19:353–361 · Zbl 0825.90530 · doi:10.1016/0305-0548(92)90066-E
[9] Bardadym VA (1996) Computer-aided school and university timetabling: the new wave. In: Burke E, Ross P (eds) The practice and theory of automated timetabling I: selected papers from the 1st International Conference Lecture Notes in Computer Science 1153. Springer, Berlin Heidelberg New York, pp 22–45
[10] Boizumault P, DelonY, Peridy L (1996) Constraint logic programming for examination timetabling. J Log Program 29(2):217–233 · Zbl 0871.68056 · doi:10.1016/0743-1066(95)00100-X
[11] Brelaz D (1979) New methods to color the vertices of a graph. Commun ACM 22(4):251–256 · Zbl 0394.05022 · doi:10.1145/359094.359101
[12] Burke EK, Ross P (eds) (1996) Practice and theory of automated timetabling I, vol 1153 of lecture notes in computer science. Springer, Berlin Heidelberg New York
[13] Burke EK, Carter MW (eds) (1998) Practice and theory of automated timetabling II, vol 1408 of lecture notes in computer science. Springer, Berlin Heidelberg New York
[14] Burke EK, Newall JP (1999) A multi-stage evolutionary algorithm for the timetable problem. IEEE Trans Evol Comput 3.1:63–74 · Zbl 05451925 · doi:10.1109/4235.752921
[15] Burke EK, Erben W (eds) (2001) Practice and theory of automated timetabling III, vol 2079 of lecture notes in computer science. Springer, Berlin Heidelberg New York
[16] Burke EK, Petrovic S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140:266–280 · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3
[17] Burke EK, De Causmaecker P (eds) (2003) Practice and theory of automated timetabling IV, vol 2740 of lecture notes in computer science. Springer, Berlin Heidelberg New York
[18] Burke EK, Newall JP (2003) Enhancing timetable solutions with local search methods. In: Burke E, De Causmaecker P (eds) The practice and theory of automated timetabling IV: selected papers from the 4th International Conference, lecture notes in computer science 2740. Springer, Berlin Heidelberg New York, pp 195–206
[19] Burke EK, Newall JP (2004) Solving examination timetabling problems through adaptation of heuristic orderings. Ann Oper Res 129:107–134 · Zbl 1056.90141 · doi:10.1023/B:ANOR.0000030684.30824.08
[20] Burke EK, Trick M (eds) (2005) Practice and theory of automated timetabling V, vol 3616 of lecture notes in computer science. Springer, Berlin Heidelberg New York
[21] Burke EK, Newall JP, Weare RF (1996a) A memetic algorithm for university exam timetabling. In: Burke E, Ross P (eds) The practice and theory of automated timetabling I: selected papers from the 1st International Conference, lecture notes in computer science 1153. Springer, Berlin Heidelberg New York, pp 3–21
[22] Burke EK, Elliman D, Ford PH, Weare D (1996b) Examination timetabling in British universities–a survey. In: Burke E, Ross P (eds) The practice and theory of automated timetabling I: selected papers from the 1st International Conference, lecture notes in computer science 1153. Springer, Berlin Heidelberg New York, pp 76–90
[23] Burke EK, Jackson KS, Kingston JH, Weare RF (1997) Automated timetabling: the state of the art. Comput J 40(9):565–571 · Zbl 05471035 · doi:10.1093/comjnl/40.9.565
[24] Burke EK, Newall JP, Weare RF (1998) Initialisation strategies and diversity in evolutionary timetabling. Evol Comput J 6.1:81–103 (special issue on Scheduling) · Zbl 05412731 · doi:10.1162/evco.1998.6.1.81
[25] Burke EK, Petrovic S, Bykov Y (2000a) A multicriteria approach to examination timetabling. In: Burke E, Ross P (eds) The practice and theory of automated timetabling III: selected papers from the 3rd International Conference, lecture notes in computer science 2079. Springer, Berlin Heidelberg New York, pp 118–131
[26] Burke EK, MacCarthy B, Petrovic S, Qu R (2000b) Structured cases in CBR–re-using and adapting cases for timetabling problems. Knowl Based Syst 13(2–3):159–165 · doi:10.1016/S0950-7051(00)00057-5
[27] Burke EK, Kendall G, Soubiega E (2003a) A Tabu-search hyper-heuristic for timetabling and rostering. J Heuristics 9:451–470 · doi:10.1023/B:HEUR.0000012446.94732.b6
[28] Burke EK, Hart E, Kendall G, Newall JP, Ross P, Schulenburg S (2003b) Hyper-heuristics: an emerging direction in modern search technology. In: Glover F, Kochenberger G (eds) Handbook of meta-heuristics. Kluwer, Norwell, pp 457–474 · Zbl 1102.90377
[29] Burke EK, Kingston J, de Werra D (2004a) Applications to timetabling. In: Gross J, Yellen J (eds) Handbook of graph theory. Chapman Hall/CRC Press, pp 445–474
[30] Burke EK, Bykov Y, Newall JP, Petrovic S (2004b) A time-predefined local search approach to exam timetabling problem. IIE Trans 36(6):509–528 · doi:10.1080/07408170490438410
[31] Burke EK, Petrovic S, Qu R (2006) Case based heuristic selection for timetabling problems. J Sched 36(6):509–528 · Zbl 1154.90423
[32] Caramia M, Dell’Olmo P, Italiano GF (2001) New algorithms for examinations timetabling. In: Naher S, Wagner D (eds) Algorithm engineering 4th International Workshop, Proceedings WAE 2000 Saarbrucken, Germany, September. Lecture notes in computer science, vol 1982. Springer, Berlin Heidelberg New York, pp 230–241
[33] Carter MW (1986) A survey of practical applications of examination timetabling. Oper Res 34:193–202 · doi:10.1287/opre.34.2.193
[34] Carter MW, Laporte G (1996) Recent developments in practical examination timetabling. In: Burke E, Ross P (eds) The practice and theory of automated timetabling I: selected papers from the 1st International Conference lecture notes in computer science 1153. Springer, Berlin Heidelberg New York, pp 3–21
[35] Carter MW, Johnson DG (2001) Extended partition initialization in examination timetabling. J Oper Res Soc 52:538–544 · Zbl 1114.90378 · doi:10.1057/palgrave.jors.2601115
[36] Carter MW, Laporte G, Lee SY (1996) Examination timetabling: algorithmic strategies and applications. J Oper Res Soc 47:373–383
[37] Casey S, Thompson J (2003) GRASPing the examination scheduling problem. In: Burke E, De Causmaecker P (eds) The practice and theory of automated timetabling IV: selected papers from the 4th International Conference, lecture notes in computer science 2740. Springer, Berlin Heidelberg New York, pp 232–244
[38] David P (1997) A constraint-based approach for examination timetabling using local repair techniques. In: Burke E, Carter M (eds) The practice and theory of automated timetabling II: selected papers from the 2nd International Conference, lecture notes in computer science 1408. Springer, Berlin Heidelberg New York, pp 169–186
[39] de Werra D (1985) An introduction to timetabling. Eur J Oper Res 19:151–162 · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5
[40] Di Gaspero L, Schaerf A (2001) Tabu search techniques for examination timetabling. In: Burke E, Erbens W (eds) The practice and theory of automated timetabling III: selected papers from the 3rd International Conference, lecture notes in computer science 2079. Springer, Berlin Heidelberg New York, pp 104–117 · Zbl 0982.68784
[41] Fahrion R, Wrede M (1990) On a principle of chain exchange for vehicle routing problems (I-VRP). J Oper Res Soc 41:821–827 · Zbl 0711.90043
[42] Gendreau M, Guertin F, Potvin JY, Seguin R (1998) Neighbourhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. CRT-98-10
[43] Han L, Kendall G (2003a) Guided operators for a hyper-heuristic genetic algorithm. In: Gedeon TD, Chun Che Fung L (eds) Proceedings of AI-2003: advances in artificial intelligence. The 16th Australian Conference on Artificial Intelligence (AI’03), Perth, pp 807–820
[44] Han L, Kendall G (2003b) Investigation of a tabu assisted hyper-heuristic genetic algorithm. In: Proceedings of Congress on Evolutionary Computation (CEC2003), vol 3, Canberra, Australia, pp 2230–2237, IEEE Catalog Number: 03TH8674, ISBN: 0-7803-7804-0
[45] Joslin DE, Clements DP (1999) Squeaky wheel optimisation. J Artif Intell Res 10:353–373 · Zbl 0918.90120
[46] Kendall G, Hussin MN (2004) An investigation of a tabu search based hyper-heuristic for examination timetabling. In: Kendall G, Burke E, Petrovic S (eds) Proceedings of the 1st Multidisciplinary International Conference on Scheduling: theory and applications (MISTA2003). Kluwer, Boston, pp 226–233
[47] Merlot TGL, Boland N, Hughes DB, Stuckey JP (2003) A hybrid algorithm for the examination timetabling problem. In: Burke E, De Causmaecker P (eds) The practice and theory of automated timetabling IV: selected papers from the 4th International Conference, lecture notes in computer science 2740. Springer, Berlin Heidelberg New York, pp 207–231
[48] Petrovic S, Bykov Y (2002) A multi-objective optimisation technique for exam timetabling based on trajectories. In: Burke E, De Causmaecker P (eds) The practice and theory of automated timetabling IV: selected papers from the 4th International Conference, lecture notes in computer science 2740. Springer, Berlin Heidelberg New York, pp 181–206
[49] Petrovic S, Burke EK (2004) University timetabling. In: Leung J (ed) The handbook of scheduling: algorithms, models, and performance analysis. Chapman Hall/CRC Press, Boca Raton
[50] Romero BP (1982) Examination scheduling in a large engineering school: a computer assisted participative procedure. Interfaces 12:17–23 · doi:10.1287/inte.12.2.17
[51] Ross P, Hart E, Corne D (1997) Some observations about GA-based exam timetabling. In: Burke E, Carter M (eds) The practice and theory of automated timetabling II: selected papers from the 2nd International Conference, lecture notes in computer science 1408. Springer, Berlin Heidelberg New York, pp 115–129
[52] Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13(2):87–127 · Zbl 05467698 · doi:10.1023/A:1006576209967
[53] Terashima-Marín H, Ross P, Valenzuela-Rendón M (1999) Evolution of constraint satisfaction strategies in examination timetabling. Proceedings of the Genetic and Evolutionary Conference, Orlando, pp 635–642
[54] Thompsom PM, Orlin JB (1989) The theory of cyclic transfer. Working paper OR200-89, Operation Research Center, MIT, Cambridge
[55] Thompsom PM, Psaraftis HN (1993) Cyclic transfer algorithm for multi-vehicle routing and scheduling problems. Oper Res 41:935–946 · Zbl 0797.90021 · doi:10.1287/opre.41.5.935
[56] Thompson JM, Dowsland KA (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648 · Zbl 1042.90568 · doi:10.1016/S0305-0548(97)00101-9
[57] White MG, Chan PW (1979) Towards the construction of optimal examination timetables. Infor 17:219–229
[58] White MG, Xie SB (2000) Examination timetables and tabu search with longer-term memory. In: Burke E, Erbens W (eds) The practice and theory of automated timetabling III: selected papers from the 3rd International Conference, lecture notes in computer science 2079. Springer, Berlin Heidelberg New York, pp 85–103
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.