Abstract
In this paper we propose a neighbourhood structure based on sequential/cyclic moves and a cyclic transfer algorithm for the high school timetabling problem. This method enables execution of complex moves for improving an existing solution, while dealing with the challenge of exploring the neighbourhood efficiently. An improvement graph is used in which certain negative cycles correspond to the neighbours; these cycles are explored using a recursive method. We address the problem of applying large neighbourhood structure methods on problems where the cost function is not exactly the sum of independent cost functions, as it is in the set partitioning problem. For computational experiments we use four real world data sets for high school timetabling in the Netherlands and England. We present results of the cyclic transfer algorithm with different settings on these data sets. The costs decrease by 8–28% if we use the cyclic transfers for local optimization compared to our initial solutions. The quality of the best initial solutions are comparable to the solutions found in practice by timetablers.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdullah S, Ahmadi S, Burke EK, Dror M (2007) Investigating Ahuja–Orlin’s large neighbourhood search approach for examination timetabling. OR Spectr 29: 351–372
Abdullah S, Ahmadi S, Burke EK, Dror M, McCollum B (2007) A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem. J Oper Res Soc 58: 1494–1502
Abramson D (1991) Constructing school timetables using simulated annealing: sequential and parallel algorithms. Manag Sci 37: 98–113
Agarwal R, Ahuja R, Laporte G, Shen Z (2003) A composite very large-scale neighborhood search algorithm for the vehicle routing problem. In: Handbook of scheduling: algorithms, models and performance analysis, Chap 49. Chapman & Hall/CRC, Boca Raton
Agarwal R, Ergun O, Orlin J, Potts C (2004) Solving parallel machine scheduling problems with variable depth local search. Working paper, Operations Research Center, MIT, Cambridge, MA
Ahmadi S, Barone R, Burke E, Cheng P, Cowling P, McCollum B (2002) Integrating human abilities and automated systems for timetabling: a competition using STARK and HuSSH representations at the PATAT 2002 conference. In: Proceedings of the 4th international conference on the practice and theory of automated timetabling (PATAT 2002), KaHo St.-Lieven, Gent, pp 265–273
Ahuja R, Orlin J, Sharma D (2001) Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem. Math Program 91: 71–97
Ahuja RK, Ergun O, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123: 75–102
Ahuja R, Jha K, Orlin J, Sharma D (2002) Very large-scale neighborhood search for the quadratic assignment problem. Working Paper, Operations Research Center, MIT, Cambridge, MA
Alvarez-Valdes R, Martin G, Tamarit JM (1996) Constructing good solutions for the Spanish school timetabling problem. J Oper Res Soc 47: 1203–1215
Birbis T, Daskalali S, Housos E (1997) Timetabling for Greek high schools. J Oper Res Soci 48: 1191–1200
Birbis T, Daskalali S, Housos E (2008) School timetabling for quality student and teacher schedules. J Sched. doi:10.1007/s10951-008-0088-2
Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper Res Lett 34: 58–68
Burke EK, Petrovic S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140: 266–280
Carter MW, Laporte G (1998) Recent developments in practical course timetabling. In: Burke E, Carter M (eds) Practice and theory of automated timetabling II. Lecture notes in computer science, vol 1408. Springer, Berlin, pp 3–19
Cheng P, Barone R, Cowling P, Ahmadi S (2002) Opening the information bottleneck in complex scheduling problems with a novel representation: STARK diagrams. Diagrammatic representations and inference: second international conference, Diagrams 2002, pp 264–278
Cheng P, Barone R, Ahmadi S, S, Cowling P (2003) Integrating human abilities with the power of automated scheduling systems: representational epistemological interface design. In: AAAI spring symposium on human interaction with autonomous systems in complex environments
Colorni A, Dorigo M, Maniezzo V (1998) Metaheuristics for high school timetabling. Comput Optim Appl 9: 275–298
Cooper TB, Kingston J (1993) The solution of real instances of the timetabling problem. Comput J 36: 645–653
Cowling P, Ahmadi S, Cheng P, Barone R (2002) Combining human and machine intelligence to produce effective examination timetables. In: Proceedings of the 4th Asia-Pacific conference on simulated evolution and learning (SEAL2002), pp 662–666
de Gans OB (1981) A computer timetabling system for secondary schools in the Netherlands. Eur J Oper Res 7: 175–182
de Haan P, Landman R, Post G, Ruizenaar H (2007) A case study for timetabling in a Dutch secondary school. In: Burke E, Rudová H (eds) Practice and theory of automated timetabling VI. Lecture Notes in Computer Science, vol 3867. Springer, Berlin, pp 267–279
de Werra D (1985) An introduction to timetabling. Eur J Oper Res 19: 151–162
de Werra D (1999) On a multiconstrained model for chromatic scheduling. Discret Appl Math 94
Deineko V, Woeginger G (2000) A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math Programm 87: 255–279
Drexl A, Salewski F (1997) Distribution requirements and compactness constraints in school timetabling. Eur J Oper Res 102: 193–214
Ergun O (2001) New neighborhood search algorithms based on exponentially large neighborhoods. PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA
Hertz A (1991) Tabu search for large scale timetabling problems. Eur J Oper Res 54: 39–47
Jha K (2004) Very large-scale neighborhood search heuristics for combination optimization problems. PhD dissertation, University of Florida
Kingston JH (2001) Modelling timetabling problems with STTL. In: Burke EK, Erben W (eds) Practice and theory of automated timetabling III. Lecture notes in computer science, vol 2079. Springer, Berlin, pp 309–321
Kingston JH (2005) A tiling algorithm for high school timetabling. In: Burke E, Trick M (eds) Practice and theory of automated timetabling V. Lecture notes in computer science, vol 3616. Springer, Berlin, pp 208–225
Lawrie NH (1969) An integer linear programming model of a school timetabling problem. Comput J 12: 307–316
Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21: 498–516
Meyers C, Orlin JB (2007) Very large-scale neighborhood search techniques in timetabling problems. In: Burke E, Rudová H (eds) Practice and theory of automated timetabling VI. Lecture notes in computer science, vol 3867, pp 24–39
Post G, Ahmadi S, Daskalaki S, Kingston JH, Kyngas J, Nurmi C, Ranson D, Ruizenaar H (2008) An XML format for Benchmarks in high School Timetabling. In: Proceeding of the 7th international conference on the practice and theory of automated timetabling (PATAT 2008)
Punnen A, Kabadi S (2002) Domination analysis of some heuristics for the traveling salesman problem. Discret Appl Math 119: 117–128
Ribeiro Filho G, Nogueira Lorena LA et al (2001) A constructive approach to school timetabling. In: Boers EJW (eds) EvoWorkshop 2001. Lecture notes in computer scienLawr69ce, vol 2037. Springer, Berlin, pp 130–139
Santos HG, Ochi LS, Souza MJF (2004) An efficient tabu search heuristic for the school timetabling problem. In: Ribeiro CC, Martins SL (eds) WEA 2004. Lecture notes in computer science, vol 3059. Springer Verlag, pp 468–481
Santos HG, Uchoa E, Ochi LS, Maculan N (2008) Strong bounds with cut and column generation for class-teacher timetabling. In: Proceedings of the 7th international conference on the practice and theory of automated timetabling PATAT 2008
Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13: 87–127
Schaerf A (1999) Local search techniques for large high school timetabling problems. IEEE Trans Syst Man Cybern Part A Syst Hum 29: 368–377
Smith KA, Abramson D, Duke D (2003) Hopfield neural networks for timetabling: formulations, methods and comparative results. Comput Indus Eng 44: 283–305
Thompson PM, Orlin JB (1989) The theory of cyclic transfer. Working paper OR200-89, Operation Research Center, MIT, Cambridge, MA
Thompson PM, Psaraftis HN (1993) Cyclic transfer algorithm for multivehicle routing and scheduling problems. Oper Res 41: 935–946
Valouxis C, Housos E (2003) Constraint programming approach for school timetabling. Comput Oper Res 30: 1555–1572
Willemen RJ (2002) School timetable construction; algorithms and complexity. PhD-thesis, Technical University Eindhoven, The Netherlands
Wright M (1996) School timetabling using heuristic search. J Oper Res Soc 47: 347–357
Yagiura M, Ibaraki T (2004) Recent metaheuristic algorithms for the generalized assignment problem. In: Proceedings of the twelfth international conference on informatics research for development of knowledge society infrastructure, pp 229–237, Kyoto, Japan
Yagiura M, Iwasaki S, Ibaraki T, Glover F (2004) A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem. Discret Optim 1: 87–98
Acknowledgments
We thank Dr. Maria Kavanagh for proof reading of the manuscript.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been supported by BSIK grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Post, G., Ahmadi, S. & Geertsema, F. Cyclic transfers in school timetabling. OR Spectrum 34, 133–154 (2012). https://doi.org/10.1007/s00291-010-0227-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-010-0227-y