Top

Published in:

2021 | OriginalPaper | Chapter

11. A Fast Threshold Acceptance Algorithm for the Examination Timetabling Problem

Authors : Nuno Leite, Fernando Melício, Agostinho C. Rosa

Published in: Handbook of Operations Research and Management Science in Higher Education

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this chapter, an accelerated variant of the threshold acceptance (TA) metaheuristic, named FastTA, is proposed for solving the examination timetabling problem. FastTA executes a lower number of evaluations compared to TA while not worsening the solution cost in a significant way. Each exam selected for scheduling is only moved if that exam had any accepted moves in the immediately preceding threshold bin; otherwise, the exam is fixed and is not evaluated anymore. If an exam had zero accepted movements in the preceding threshold bin, it is likely to have few or zero accepted movements in the future, as it is becoming crystallised. The FastTA and TA were tested on the Toronto and Second International Timetabling Competition benchmark (ITC 2007) sets. Compared to TA, the FastTA uses 38% and 22% less evaluations, on average, on the Toronto and ITC 2007 sets, respectively. On the ITC 2007 set, the FastTA is competitive with TA attaining the best average solution cost value in four out of twelve instances while requiring less time to execute. Compared with the state-of-the-art approaches, the FastTA is able to achieve competitive results. The main contribution/value of this chapter is the proposal of a new acceptance criterion for the TA metaheuristic, which leads to a significantly faster variant (FastTA), and its application to solve public examination timetabling benchmark sets.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Funding Research in Higher Education Institutions: The Game Theory Approach

next chapter Robust Efficiency via Average Correlation: The Case of Academic Departments

Available only for authorised users

Abdullah, S., Turabieh, H., & McCollum, B. (2009). A hybridization of electromagnetic-like mechanism and great deluge for examination timetabling problems. In M. J. Blesa, C. Blum, L. D. Gaspero, A. Roli, M. Sampels, A. Schaerf (Eds.) Hybrid metaheuristics. Lecture Notes in Computer Science (vol. 5818, pp. 60–72). Springer.

Abramson, D. (1991). Constructing school timetables using simulated annealing: Sequential and parallel algorithms. Management Science, 37(1), 98–113. https://doi.org/10.1287/mnsc.37.1.98.CrossRef

Alzaqebah, M., & Abdullah, S. (2014). An adaptive artificial bee colony and late-acceptance hill-climbing algorithm for examination timetabling. Journal of Scheduling, 17(3), 249–262. https://doi.org/10.1007/s10951-013-0352-y.CrossRef

Alzaqebah, M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers & Operations Research, 54(0), 142–154. https://doi.org/10.1016/j.cor.2014.09.005.CrossRef

Battistutta, M., Schaerf, A., & Urli, T. (2017). Feature-based tuning of single-stage simulated annealing for examination timetabling. Annals of Operations Research, 252(2), 239–254. https://doi.org/10.1007/s10479-015-2061-8.CrossRef

Bellio, R., Ceschia, S., Gaspero, L. D., Schaerf, A., & Urli, T. (2016). Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Computers & Operations Research, 65(Supplement C), 83–92. https://doi.org/10.1016/j.cor.2015.07.002.

Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. TOP, 23(2), 313–349. https://doi.org/10.1007/s11750-015-0366-z.CrossRef

Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256. https://doi.org/10.1145/359094.359101.CrossRef

Broder, S. (1964). Final examination scheduling. Communications of the ACM, 7, 494–498. https://doi.org/10.1145/355586.364824.CrossRef

Burke, E., Bykov, Y., Newall, J., & Petrovic, S. (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6), 509–528.CrossRef

Burke, E. K., & Bykov, Y. (2008). A late acceptance strategy in hill-climbing for exam timetabling problems. In Proceedings of the PATAT ’08.

Burke, E. K., Qu, R., & Soghier, A. (2014). Adaptive selection of heuristics for improving exam timetables. Annals of Operations Research, 218(1), 129–145. https://doi.org/10.1007/s10479-012-1140-3.CrossRef

Bykov, Y., & Petrovic, S. (2013). An initial study of a novel step counting hill climbing heuristic applied to timetabling problems. In Proceedings of the MISTA’13 (pp. 691–693).

Bykov, Y., & Petrovic, S. (2016). A step counting hill climbing algorithm applied to university examination timetabling. Journal of Scheduling, 19(4), 479–492. https://doi.org/10.1007/s10951-016-0469-x.CrossRef

Carter, M., & Laporte, G. (1996). Recent developments in practical examination timetabling. In E. Burke, P. Ross (Eds.) Practice and theory of automated timetabling. Lecture Notes in Computer Science (vol. 1153, pp 1–21). Berlin/Heidelberg: Springer. https://doi.org/10.1007/3-540-61794-9_49.

Carter, M., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society, 47(3), 373–383. https://doi.org/10.2307/3010580.CrossRef

Carter, M. W. (1986) A survey of practical applications of examination timetabling algorithms. Operation Research, 34(2), 193–202. https://doi.org/10.1287/opre.34.2.193.CrossRef

Cheong, C., Tan, K., & Veeravalli, B. (2009). A multi-objective evolutionary algorithm for examination timetabling. Journal of Scheduling, 12, 121–146. https://doi.org/10.1007/s10951-008-0085-5.CrossRef

Cole, A. J. (1964). The preparation of examination time-tables using a small-store computer. The Computer Journal, 7(2), 117–121. https://doi.org/10.1093/comjnl/7.2.117.CrossRef

Demeester, P., Bilgin, B., Causmaecker, P. D., & Berghe, G. V. (2012). A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice. Journal of Scheduling, 15(1), 83–103. https://doi.org/10.1007/s10951-011-0258-5.CrossRef

Derrac, J., García, S., Molina, D., & Herrera, F. (2011). A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 1(1), 3–18. https://doi.org/10.1016/j.swevo.2011.02.002.CrossRef

de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2), 151–162. https://doi.org/10.1016/0377-2217(85)90167-5.CrossRef

de Werra, D. (1997), The combinatorics of timetabling. European Journal of Operational Research, 96(3), 504–513. https://doi.org/10.1016/S0377-2217(96)00111-7.CrossRef

Dowsland, K. A. (1990). A timetabling problem in which clashes are inevitable. Journal of the Operational Research Society, 41(10), 907–918. https://doi.org/10.1057/jors.1990.143.CrossRef

Dowsland, K. A., & Thompson, J. M. (2012). Simulated annealing. In G. Rozenberg, T. Bäck, & J. N. Kok (Eds.) Handbook of natural computing (pp. 1623–1655). Berlin,Heidelberg: Springer. https://doi.org/10.1007/978-3-540-92910-9_49.

Dueck, G., & Scheuer, T. (1990). Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90(1), 161–175. https://doi.org/10.1016/0021-9991(90)90201-B.CrossRef

Eley, M. (2006). Ant algorithms for the exam timetabling problem. In E. K. Burke, & H. Rudová (Eds.) PATAT. Lecture Notes in Computer Science (vol. 3867, pp. 364–382). Springer.

Fong, C. W., Asmuni, H., & McCollum, B. (2015). A hybrid swarm-based approach to university timetabling. IEEE Trans Evolutionary Computation, 19(6), 870–884. https://doi.org/10.1109/TEVC.2015.2411741.CrossRef

García, S., & Herrera, F. (2008). An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. Journal of Machine Learning Research, 9, 2677–2694.

Gashgari, R., Alhashimi, L., Obaid, R., Palaniswamy, T., Aljawi, L., Alamoudi, A. (2018). A survey on exam scheduling techniques. In 2018 1st International Conference on Computer Applications Information Security (ICCAIS) (pp. 1–5). https://doi.org/10.1109/CAIS.2018.8441950.

Gogos, C., Alefragis, P., & Housos, E. (2008). A multi-staged algorithmic process for the solution of the examination timetabling problem. In Proceedings of the 7th PATAT, University of Montreal, Canada.

Gogos, C., Alefragis, P., & Housos, E. (2012). An improved multi-staged algorithmic process for the solution of the examination timetabling problem. Annals OR, 194(1), 203–221. https://doi.org/10.1007/s10479-010-0712-3.CrossRef

Hamilton-Bryce, R., McMullan, P., & McCollum, B. (2013). Directing selection within an extended great deluge optimization algorithm. In Proceedings of the MISTA’13 (pp. 499–508).

International Timetabling Competition, (2007). ITC 2007 website. http://www.cs.qub.ac.uk/itc2007/, accessed on May 2020.

Johnes, J. (2015). Operational research in education. European Journal of Operational Research, 243(3), 683–696. https://doi.org/10.1016/j.ejor.2014.10.043.CrossRef

June, T. L., Obit, J. H., Leau, Y. B., & Bolongkikit, J. (2019). Implementation of constraint programming and simulated annealing for examination timetabling problem. In R. Alfred, Y. Lim, A. A. A. Ibrahim, & P. Anthony (Eds.) Computational science and technology (pp. 175–184). Singapore: Springer Singapore. https://doi.org/10.1007/978-981-13-2622-6_18.CrossRef

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671–680. https://doi.org/10.1126/science.220.4598.671.CrossRef

Kristiansen, S., & Stidsen, T. R. (2013). A comprehensive study of educational timetabling, a survey. Tech. Rep. DTU Management Engineering Report, No. 8.2013 (Accessed on 21.05.2020), Department of Management Engineering, Technical University of Denmark. http://orbit.dtu.dk/files/60366101/A_Comprehensive_Study.pdf.

Leite, N., Melício, F., & Rosa, A. C. (2016). A shuffled complex evolution algorithm for the examination timetabling problem. In J. J. Merelo, A. Rosa, M. J. Cadenas, A. Dourado, K. Madani, & J. Filipe (Eds.) Computational intelligence: International joint conference, IJCCI 2014 Rome, Italy, October 22–24, pp. 151–168. 2014 Revised Selected Papers. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-26393-9_10.

Leite, N., Fernandes, C. M., Melício, F., & Rosa, A. C. (2018). A cellular memetic algorithm for the examination timetabling problem. Computers & OR, 94, 118–138. https://doi.org/10.1016/j.cor.2018.02.009.CrossRef

Leite, N., Melício, F., & Rosa, A. C. (2019). A fast simulated annealing algorithm for the examination timetabling problem. Expert Systems with Applications, 122, 137–151. https://doi.org/10.1016/j.eswa.2018.12.048.CrossRef

Li, J., Bai, R., Shen, Y., & Qu, R. (2015). Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling. European Journal of Operational Research, 242(3), 798–806. https://doi.org/10.1016/j.ejor.2014.11.002.CrossRef

McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K., & Abdullah, S. (2009). An extended great deluge approach to the examination timetabling problem. In Proceedings of the 4th Multidisciplinary International Scheduling: Theory and Applications 2009 (MISTA 2009) (pp. 424–434).

McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., Gaspero, L. D., Qu, R., & Burke, E. K. (2010). Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing, 22(1), 120–130. https://doi.org/10.1287/ijoc.1090.0320.CrossRef

McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K., & Qu, R. (2012). A new model for automated examination timetabling. Annals of Operations Research, 194, 291–315. https://doi.org/10.1007/s10479-011-0997-x.CrossRef

Melício, F., Caldeira, P., & Rosa, A. (2000). Solving the timetabling problem with simulated annealing. In J. Filipe (Ed.) Enterprise information systems (pp. 171–178). Dordrecht: Springer Netherlands. https://doi.org/10.1007/978-94-015-9518-6_18.CrossRef

Melício, F., Caldeira, J. P., & Rosa, A. (2004). Two neighbourhood approaches to the timetabling problem. In Proceedings of the Practice and Theory of Automated Timetabling (PATAT) (pp. 267–282).

Müller, T. (2009). ITC2007 solver description: a hybrid approach. Annals of Operations Research, 172(1), 429–446. https://doi.org/10.1007/s10479-009-0644-y.CrossRef

Özcan, E., Elhag, A., & Shah, V. (2012). A study of hyper-heuristics for examination timetabling. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2012) (pp. 410–414).

Pillay, N. (2016). A review of hyper-heuristics for educational timetabling. Annals OR, 239(1), 3–38. https://doi.org/10.1007/s10479-014-1688-1.CrossRef

Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2), 457–467. https://doi.org/10.1016/j.asoc.2009.08.011.CrossRef

Qu, R., Burke, E., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12, 55–89. https://doi.org/10.1007/s10951-008-0077-5.CrossRef

Sabar, N. R., Ayob, M., Kendall, G., & Qu, R. (2015). A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems. IEEE Transactions on Cybernetics, 45(2), 217–228. https://doi.org/10.1109/TCYB.2014.2323936.CrossRef

Santini, A., Ropke, S., & Hvattum, L. M. (2018). A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics, 24(5), 783–815. https://doi.org/10.1007/s10732-018-9377-x.CrossRef

Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. https://doi.org/10.1023/A:1006576209967.CrossRef

Talbi, E. G. (2009). Metaheuristics - From design to implementation. Wiley.

Teoh, C. K., Wibowo, A., & Ngadiman, M. S. (2015). Review of state of the art for metaheuristic techniques in academic scheduling problems. Artificial Intelligence Review, 44(1), 1–21. https://doi.org/10.1007/s10462-013-9399-6.CrossRef

Thompson, J. M., & Dowsland, K. A. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operations Research, 63(1), 105–128. https://doi.org/10.1007/BF02601641.CrossRef

Thompson, J. M., & Dowsland, K. A. (1998). A robust simulated annealing based examination timetabling system. Computers & OR, 25(7–8), 637–648. https://doi.org/10.1016/s0305-0548(97)00101-9.CrossRef

Welsh, D. J. A., & Powell, M. B. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86. https://doi.org/10.1093/comjnl/10.1.85.CrossRef

Winker, P. (2001). Optimization heuristics in econometrics: Applications of threshold accepting. Chichester, UK: John Wiley and Sons Ltd.

Woumans, G., Boeck, L. D., Beliën, J., & Creemers, S. (2016). A column generation approach for solving the examination-timetabling problem. European Journal of Operational Research, 253(1), 178–194. https://doi.org/10.1016/j.ejor.2016.01.046.CrossRef

Zhang, D., Liu, Y., M’Hallah, R., & Leung, S. C. (2010). A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 203(3), 550–558. https://doi.org/10.1016/j.ejor.2009.09.014.CrossRef

Title: A Fast Threshold Acceptance Algorithm for the Examination Timetabling Problem
Authors: Nuno Leite
Fernando Melício
Agostinho C. Rosa
Publisher: Springer International Publishing
Book: Handbook of Operations Research and Management Science in Higher Education
Print ISBN: 978-3-030-74049-8

Electronic ISBN: 978-3-030-74051-1

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-74051-1_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Premium Partner