×

A survey of school timetabling research. (English) Zbl 1301.90040

Summary: Although there has been a fair amount of research in the area of school timetabling, this domain has not developed as well as other fields of educational timetabling such as university course and examination timetabling. This can possibly be attributed to the fact that the studies in this domain have generally been conducted in isolation of each other and have addressed different school timetabling problems. Furthermore, there have been no comparative studies on the success of different methodologies on a variety of school timetabling problems. As a way forward this paper provides an overview of the research conducted in this domain, details of problem sets which are publicly available and proposes areas for further research in school timetabling.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbas, A. M.; Tsang, E. P. K., Constraint-based timetabling—a case study, 67 (2001), Los Alamitos
[2] Abboud, N., Sakawa, M., & Inuiguchi, M. (1998). School scheduling using threshold accepting. Cybernetics and Systems, 29(6), 593-611. · Zbl 1012.90073
[3] Abramson, D. (1991). Constructing school timetables using simulated annealing: sequential and parallel algorithms. Management Science, 37(1), 98-113.
[4] Abramson, D.; Abela, J., A parallel genetic algorithm for the solving the school timetabling problem, 1-11 (1991)
[5] Abramson, D., Krishnamoorthy, M., & Dang, H. (1999). Simulated annealing cooling schedules for the school timetabling problem. Asia-Pacific Journal of Operational Research, 16(1), 1-22. · Zbl 1053.90508
[6] Alvarez-Valdes, R., Martin, G., & Tamarit, J. M. (1996). Constructing good solutions for the Spanish school timetabling problem. Journal of the Operational Research Society, 47(10), 1203-1215. · Zbl 0863.90081
[7] Alvarez-Valdes, R., Parreno, F., & Tamarit, J. M. (2002). A tabu search algorithm for assigning teachers to courses. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 10(2), 239-259. · Zbl 1038.90102
[8] Appleby, J. S., Blake, D. V., & Newman, E. A. (1961). Techniques for producing school timetables on computer and their application to other scheduling problems. The Computer Journal, 3(4), 237-245. · Zbl 0201.48903
[9] Aust, R. J. (1976). An improvement algorithm for school timetabling. Computer Journal, 19(4), 339-343. · Zbl 0339.68036
[10] Avella, P., D’Auria, B., Salerno, S., & Vasil’ev, I. (2007). A computational study of local search algorithms for Italian high school timetabling. Journal of Heuristics, 13(6), 543-556. · Zbl 1144.90451
[11] Beasley, J. (1990). OR library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069-1072.
[12] Beasley, J. F. (2010). OR library. http://people.brunel.ac.uk/mastjjb/jeb/orlib/tableinfo.html. Last accessed 1 February 2010.
[13] Bedoya, C. F., & Santos, M. (2003). A non-standard genetic algorithm approach to solve constrained school timetabling problems. Eurocast, 26-37.
[14] Beligiannis, G. N., Moschopoulos, C. N., Kaperonis, G. P., & Likothanassis, S. D. (2008). Applying evolutionary computation to the school timetabling problem: the Greek case. Computers and Operations Research, 35, 1265-1280. · Zbl 1179.90124
[15] Beligiannis, G. N., Moschopoulos, C. N., & Likothanassis, S. D. (2009). A genetic algorithm approach to school timetabling. Journal of the Operational Research Society, 60(1), 23-42. · Zbl 1168.90531
[16] Bello, G. S.; Rangel, M. C.; Boeres, M. C. S., An approach for the class/teacher timetabling problem (2008)
[17] Birbas, T., Daskalaki, S., & Housos, E. (1997). Timetabling for Greek high schools. Journal of the Operational Research Society, 48(2), 1191-1200. · Zbl 0895.90112
[18] Birbas, T., Daskalaki, S., & Housos, E. (2009). School timetabling for quality student and teacher schedules. Journal of Scheduling, 12(2), 177-197. · Zbl 1180.90113
[19] Boland, N., Hughes, B. D., Merlot, L. T. G., & Stuckey, P. J. (2008). New integer linear programming for course timetabling. Computers and Operations Research, 35, 2209-2233. · Zbl 1180.90197
[20] Bufe, M.; Fischer, T.; Gubbels, H.; Hacker, C.; Hasprich, O.; Scheibel, C.; Weicker, K.; Weicker, N.; Wenig, M.; Wolfangel, C., Automated solution of highly constrained school timetabling problem, 431-440 (2001) · Zbl 0982.90501
[21] Burke, E.; Hart, E.; Kendall, G.; Newall, J.; Ross, P.; Schulenburg, S., Hyper-heuristics: an emerging direction in modern research, 457-474 (2003), Dordrecht · Zbl 1102.90377
[22] Burke, E. K.; Wera, D.; Kingston, J. F., Applications of timetabling, 445-474 (2004), London
[23] Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research (EJOR), 176, 177-192. · Zbl 1137.90602
[24] Calderia, J. P.; Ross, A. C., School timetabling using genetic search, 115-122 (1997)
[25] Carrassco, M. P., & Pato, M. V. (2004). A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem. European Journal of Operational Research, 153, 65-79. · Zbl 1053.90137
[26] Carter, M. W., & Tovey, C. A. (1992). When is the classroom assignment problem hard? Operations Research, 40(S1), 28-29. · Zbl 0745.90049
[27] Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithmic strategies and applications. The Journal of the Operational Research Society, 47(3), 373-383.
[28] Carter, M. W.; Laporte, G.; Burke, E. (ed.); Carter, M. (ed.), Recent developments in the practical course timetabling, No. 1408, 3-19 (1997), Berlin
[29] Cedeira-Pena, A.; Carpente, L.; Farina, A.; Seco, D., New approaches for the school timetabling problem, 261-267 (2008)
[30] Ciscon, L. A.; Oliveira, H. C. B.; Andrade, M. C. A.; Alvarenga, G. B.; Esmin, A. A. A., The school timetabling problem: a focus on elimination of open periods and isolated classes, 70 (2006), New York
[31] Colorni, A., Dorigo, M., & Maniezzo, V. (1990). Genetic algorithms: a new approach to the timetable problem. NATO ASI Series, F82, 235-239. · Zbl 0825.90549
[32] Colorni, A., Dorigo, M., & Maniezzo, V. (1998). Metaheuristics for high school timetabling. Computational Optimization and Applications, 9, 275-298. · Zbl 0897.90124
[33] Cooper, T. B., & Kingston, J. H. (1993). The solution of real instances of the timetabling problem. The Computer Journal, 36(7), 645-653.
[34] Cooper, T. B.; Kingston, J. H., A program for constructing high school timetables (1995)
[35] Cooper, T. B.; Kingston, J. H., The complexity of timetable construction problems, 283-295 (1996)
[36] Cumming, A.; Paetcher, B., Post-publication timetabling, 107-108 (2000)
[37] de Gans, O. B. (1981). A computer timetabling system for secondary schools in the Netherlands. European Journal of Operational Research, 7(2), 175-182.
[38] de Haan (2004). Timetabling in dutch secondary schools. Masters Thesis, University of Twente.
[39] de Haan, P., Landman, R., Post, G., & Ruizenaar, H. (2007a). A case study for timetabling in Dutch high schools. Practice and Theory of Automated Timetabling, IV, 267-279.
[40] Haan, P.; Landman, R.; Post, G.; Ruizenaar, H.; Burke, E. K. (ed.); Rudova, H. (ed.), A four-phase approach to a timetabling problem for secondary schools, No. 3867, 267-279 (2007), Berlin
[41] de Werra, D. (1971). Construction of school timetables by flow methods. Information Systems and Operational Research, 9(1), 12-22.
[42] Stephano, C.; Tettamanzi, A. G. B., An evolutionary algorithm for solving the school timetabling problem, 659-672 (2001), Berlin
[43] Drexl, A., & Salewski, F. (1997). Distribution requirements and compactness constraints in school timetabling. European Journal of Operational Research, 102(1), 193-214. · Zbl 0948.90157
[44] Eikelder, H. M. M.; Willemen, R. J., Some complexity aspects of secondary school timetabling problems, No. 2079/2001, 18-27 (2001) · Zbl 0982.68769
[45] Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691-703. · Zbl 0358.90021
[46] Fernandes, C.; Caldeira, J. P.; Melicio, F.; Rosa, A., High school weekly timetabling by evolutionary algorithms, 344-350 (1999)
[47] Fernandes, C.; Caldeira, J. P.; Melicio, F.; Rosa, A.; Banzhaf, W. (ed.); Daida, J. (ed.); Eiben, A. E. (ed.); Garzon, M. H. (ed.); Honavar, V. (ed.); Jakiela, M. (ed.); Smith, R. D. (ed.), Evolutionary algorithm for school timetabling, 1777 (1999)
[48] Filho, G. R.; Lorena, L. A. N., A constructive evolutionary approach to school timetabling, No. 2037, 130-139 (2001), Berlin · Zbl 0978.68564
[49] Grobner, M.; Wilke, P.; Buttcher, S.; Burke, E. K. (ed.); Causmaecker, P. (ed.), A standard framework for timetabling problems, No. 2740, 24-38 (2003), Berlin
[50] Hertz, A., & Robert, V. (1998). Constructing a course schedule by solving a series of assignment type problems. European Journal of Operational Research, 108, 585-603. · Zbl 0936.90025
[51] Jacobsen, F.; Bortfeldt, A.; Gehring, H.; Burke, E. K. (ed.); Rudova, H. (ed.), Timetabling at German secondary schools: tabu search versus constraint programming, 439-442 (2006)
[52] Junginger, W. (1986). Timetabling in Germany—a survey. Interfaces, 16(4), 66-74.
[53] Kingston, J. H.; Burke, E. (ed.); Erben, W. (ed.), Modelling timetable problems with STTL, 309-321 (2000), Berlin
[54] Kingston, J. H., A tiling algorithm for high school timetabling, No. 3616/2005, 208-225 (2004), Berlin
[55] Kingston, J. H.; Burke, E. K. (ed.); Rudova, H. (ed.), The KTS high school timetabling systems, 181-195 (2006)
[56] Kingston, J. H.; Burke, E. (ed.); Rudova, H. (ed.), Hierarchical timetable construction, No. 3867, 294-307 (2007)
[57] Kingston, J. H., Resource assignment in high school timetabling (2008) · Zbl 1251.90241
[58] Kingston, J. H., Solving the general high school timetabling problem, 517-518 (2010)
[59] Kwan, A. C. M.; Chung, K. C. K.; Yip, K. K. K.; Tam, V., An automated school timetabling system using hybrid intelligent techniques, No. 2871, 124-134 (2003) · Zbl 1070.68607
[60] Kwok, L., Kong, S., & Kam, Y. (1997). Timetabling in Hong Kong secondary schools. Computer Education, 28(3), 173-183.
[61] Landman, R. (2005). Creating good-quality timetables for Dutch high schools. Masters Thesis, University of Twente, the Netherlands. · Zbl 0358.90021
[62] Lara, C.; Flores, J. J.; Calderon, F., Solving a school timetabling problem using a bee algorithm, No. 5317, 664-674 (2008)
[63] Lawrie, N. L. (1969). An integer linear programming model of a school timetabling problem. The Computer Journal, 12(4), 307-316.
[64] Lion, J. (1966). Matrix reduction using the Hungarian method for the generation of school timetables. Communications of the ACM, 9(5), 349-354. · Zbl 0171.15307
[65] Lion, J. (1967). The Ontario school timetabling problem. The Computer Journal, 10(1), 14-21.
[66] Liu, Y.; Zhang, D.; Leung, S. C. H., A simulated annealing algorithm with a new neighbourhood structure for the timetabling problem, 381-386 (2009)
[67] Lohnertz, M., A timetabling system for the German gymnasium (2002)
[68] Marte, M. (2002). Models and algorithms for school timetabling—a constraint-programming approach. Phd Thesis, University of Munchen. · Zbl 1120.90361
[69] Marte, M. (2006). Towards constraint-based grammar school timetabling. http://www3.deis.unibo.it/Events/Deis/Workshops/PapersCPAIOR99/21final.ps. Last accessed 12 February 2010. · Zbl 1145.90390
[70] McCollum, B., McMullan, P., Paechter, B., Lewis, R., Schaerf, A., Di Gaspero, L., Parkes, A. J., Qu, R., & Burke, E. K. (2009). Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS Journal on Computing. doi:10.1287/ijoc.1090.0320. · Zbl 1243.90007 · doi:10.1287/ijoc.1090.0320
[71] Melicio, F.; Calderia, J. P.; Rosa, A.; Burke, E. K. (ed.); Rudova, H. (ed.), THOR: a tool for school timetabling, 532-535 (2006)
[72] Meisels, A., Ell-sana, J., & Gudes, E. (1997). Decomposing and solving timetabling constraint networks. Computational Intelligence, 13(4), 486-505.
[73] Minh, K. N. T. T., Thanh, N. D. T., Trang, K. T., & Hue, N. T. T. (2010). Using tabu search for solving a high school timetabling problem. Studies in Computational Intelligence, 283, 305-313.
[74] Mohammadi, M. S.; Lucas, C., Cooperative co-evolution for school timetabling problem, 1-7 (2008)
[75] Monfroglio, A. (1996). Timetabling through constrained heuristic search and genetic algorithms. Software—Practice and Experience, 26(3), 251-279.
[76] Moschopoulos, C. N., Alexakos, C. E., Dosi, C., Beligiannis, G. N., & Likothanassis, S. D. (2009). A user-friendly evolutionary tool for high-school timetabling. Studies in Computational Intelligence, 166, 149-162.
[77] Moura, A. V., & Scaraficci, R. A. (2010). A GRASP strategy for a more constrained school timetabling problem. International Journal of Operational Research, 7(2), 152-170. · Zbl 1183.90185
[78] Nurmi, K.; Kyngas, J., A framework for school timetabling problem (2007)
[79] Nurmi, K.; Kyngas, J., A conversion scheme for turning a curriculum-based timetabling problem into a school timetabling problem, Montreal
[80] Ohtsubo, M., Kurashige, K., & Kameyama, Y. (2006). Approach to the timetabling problems for junior high schools. Journal of Japan Industrial Management Association, 57(3), 231-242.
[81] Ostler, J.; Wilke, P., The Erlangen advanced timetabling system (EATTS) unified XML file format for the specification of timetabling systems, 447-464 (2010)
[82] Papoutsis, K., Valouxis, C., & Housos, E. (2003). A column generation approach for the timetabling problem of Greek high schools. Journal of Operational Research Society, 54(3), 230-238. · Zbl 1171.90406
[83] Pillay, N., & Banzhaf, W. (2009). A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem. European Journal of Operational Research (EJOR), 197, 482-491. · Zbl 1159.90528
[84] Pillay, N., A study into hyper-heuristics for the school timetabling problem, 258-264 (2010)
[85] Post, G. F., & Ruizenaar, H. W. A. (2004). Clusterschemes in dutch secondary schools (Memorandum No. 1707). University of Twente, the Netherlands. · Zbl 1180.90113
[86] Post, G.; Ahmadi, S.; Daskalaki, S.; Kingston, J. H.; Kyngas, J.; Nurmi, C.; Ranson, D.; Ruizenaar, H., An XML format for benchmarks in high school timetabling, Montreal
[87] Post, G., Ahmadi, S., & Geertsema, F. (2010a). Cyclic transfers in school timetabling. OR Spectrum. doi:10.1007/s00291-010-0227-y. · Zbl 1238.90086 · doi:10.1007/s00291-010-0227-y
[88] Post, G.; Kingston, J. H.; Ahmadi, S.; Daskalaki, S.; Gogos, C.; Kyngas, G.; Nurmi, C.; Santos, H.; Rorije, B.; Schaerf, A., An XML format for benchmarks in high school timetabling, 347-352 (2010)
[89] Raghavjee, R.; Pillay, N.; Cilliers, C. (ed.); Barnard, L. (ed.); Botha, R. A. (ed.), An application of genetic algorithms to the school timetabling problem, 193-199 (2008), New York
[90] Raghavjee, R.; Pillay, N., Evolving solutions to the school timetabling problem, 1524-1527 (2009), New York
[91] Raghavjee, R.; Pillay, N., An informed genetic algorithm for the high school timetabling problem, 408-412 (2010), New York
[92] Raghavjee, R.; Pillay, N., Using genetic algorithms to solve the South African school timetabling problem (2010), New York
[93] Reis, L. P.; Oliveira, E., A language for specifying complete timetabling problems, 322-341 (2000) · Zbl 0982.68517
[94] Ribic, S.; Konjicija, S., A two phase integer programming approach to solving the school timetabling problem, No. 5546473, 651-656 (2010)
[95] Santos, H. G.; Ochi, L. S.; Souza, M. J. F., An efficient tabu search heuristic for the school timetabling problem, No. 3059, 468-481 (2004)
[96] Santos, H. G., Ochi, L. S., & Souza, M. J. F. (2005). A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. Journal of Experimental Algorithms, 10, 2.9. doi:10.1145/1064546.1180621. · Zbl 1189.90065 · doi:10.1145/1064546.1180621
[97] Santos, H. G.; Uchoa, E.; Ochi, L. S.; Maculan, N., Strong bounds with cut and column generation for class-teacher timetabling, Montreal
[98] Schaerf, A. (1996). Tabu search techniques for large high-school timetabling problems (Technical Report CS-R9611 1996). Computer Science/Department of Interactive Systems, Centrum Voor Wiskunder en Informatica (CWI). ISSN 0169-118X.
[99] Schaerf, A. (1999a). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127.
[100] Schaerf, A. (1999b). Local search methods for high school timetabling problems. IEEE Transactions on Systems, Man and Cybernetics, 29(4), 377-386.
[101] Slechta, P.; Burke, E. (ed.); Trick, M. (ed.), Decomposition and parallelization of multi-resource timetabling problem, No. 3616, 177-189 (2005)
[102] Smith, K. A., Abramson, D., & Duke, D. (2003). Hopfield neural networks for timetabling: formulations, methods, and comparative results. Computers and Industrial Engineering, 44, 283-305.
[103] Srndic, N.; Dervisevic, M.; Pandzo, E.; Konjicija, S., The application of a parallel genetic algorithm to timetabling of elementary school classes: a coarse grained approach, 1-5 (2009), New York
[104] Souza, M. J. F. (2004). A GRASP-tabu search algorithm for solving school timetabling problems. Metaheuristics: Computer Decision-Making, 659-672.
[105] Valouxis, C., & Housos, E. (2003). Constraint programming approach for school timetabling. Computers and Operations Research, 30, 1555-1572. · Zbl 1039.90039
[106] Wilke, P.; Grobner, M.; Oster, N., A hybrid genetic algorithm for school timetabling, No. 2557/2002, 455-464 (2002), Berlin · Zbl 1032.68755
[107] Wilke, P.; Ostler, J., Solving the school timetabling problem using tabu search, simulated annealing, genetic and branch & bound algorithms, Montreal
[108] Wilke, P.; Killer, H., A comparison of algorithms for solving school and course timetabling problems using the Erlangen advanced timetabling system, 427-439 (2010)
[109] Wilke, P.; Killer, H., Walk down jump up algorithm—a new hybrid algorithm for timetabling problems, 440-446 (2010)
[110] Willemen, R. J. (2002). School timetabling construction: algorithms and complexity. Phd Thesis, Technische Universiteit Eindhoven, The Netherlands.
[111] Wood, J., & Whitaker, D. (1998). Student central school timetabling. Journal of the Operational Research Society, 49(11), 1146-1152. · Zbl 1140.90414
[112] Wright, M. (1996). School timetabling using heuristic search. Journal of the Operational Research Society, 47, 347-357.
[113] Yigit, T., Constraint-based school timetabling using hybrid genetic algorithms, No. 4733, 848-855 (2007)
[114] Yongkai, L.; Defu, Z.; Leung, S. C. H., A simulated annealing algorithm with a new neighborhood structure for the timetabling problem, 381-386 (2009)
[115] Yoshikawa, M.; Kaneko, K.; Nomura, Y.; Watanabe, M., A constraint-based approach to high-school timetabling problems: a case study, 1111-1116 (1994), Menlo Park
[116] Yoshikawa, M.; Kaneko, K.; Yamanouchi, T.; Watanabe, M., A constraint-based high school scheduling system, 63-72 (1996)
[117] Zuters, J., Neural networks to enrich fitness function in a GA-based school timetabling model, No. 4(2), 346-353 (2007)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.