Top

Published in:

2019 | OriginalPaper | Chapter

An Adaptive VNS and Skewed GVNS Approaches for School Timetabling Problems

Authors : Ulisses Rezende Teixeira, Marcone Jamilson Freitas Souza, Sérgio Ricardo de Souza, Vitor Nazário Coelho

Published in: Variable Neighborhood Search

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

The School Timetabling Problem is widely known and it appears at the beginning of the school term of the institutions. Due to its complexity, it is usually solved by heuristic methods. In this work, we developed two algorithms based on the Variable Neighborhood Search (VNS) metaheuristic. The first one, named Skewed General Variable Neighborhood Search (SGVNS), uses Variable Neighborhood Descent (VND) as local search method. The second one, so-called Adaptive VNS, is based on VNS and probabilistically chooses the neighborhoods to do local searches, with the probability being higher for the more successful neighborhoods. The computational experiments show a good adherence of these algorithms for solving the problem, especially comparing them with previous works using the same metaheuristic, as well as with previous published results of the winning algorithm of the International Timetabling Competition of 2011.

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 "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

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 New VNS Variants for the Online Order Batching Problem

next chapter Finding Balanced Bicliques in Bipartite Graphs Using Variable Neighborhood Search

Aziz, R.A., Ayob, M., Othman, Z., Ahmad, Z., Sabar, N.R.: An adaptive guided variable neighborhood search based on honey-bee mating optimization algorithm for the course timetabling problem. Soft Comput. 21(22), 6755–6765 (2017)CrossRef

Bardadym, V.A.: Computer-aided school and university timetabling: the new wave. In: Burke, E., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 22–45. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61794-9_50CrossRef

Benjamini, Y., Hochberg, Y.: Controlling the false discovery rate: a practical and powerful approach to multiple testing. J. R. Stat. Soc. Ser. B (Methodol.) 57, 289–300 (1995)MathSciNetMATH

Birattari, M., Balaprakash, P., Dorigo, M.: The ACO/F-Race algorithm for combinatorial optimization under uncertainty. In: Doerner, K.F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R.F., Reimann, M. (eds.) Metaheuristics. ORSIS, vol. 39, pp. 189–203. Springer, Boston, MA (2007). https://doi.org/10.1007/978-0-387-71921-4_10CrossRefMATH

da Fonseca, G.H.G., Santos, H.G., Toffolo, T.Â.M., Brito, S.S., Souza, M.J.F.: GOAL solver: a hybrid local search based solver for high school timetabling. Ann. Oper. Res. 239(1), 77–97 (2016)MathSciNetCrossRef

de Haan, P., Landman, R., Post, G., Ruizenaar, H.: A case study for timetabling in a dutch secondary school. In: Burke, E.K., Rudová, H. (eds.) PATAT 2006. LNCS, vol. 3867, pp. 267–279. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77345-0_17CrossRef

Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 184–193 (1975)

Gotlieb, C.C.: The construction of class-teacher timetables. In: Proceedings of IFIP Congress, pp. 73–77 (1963)

Hansen, P., Mladenovic, N., Pérez, J.A.M.: Variable neighborhood search: methods and applications. 4OR: Q. J. Belg. Fr. Ital. Oper. Res. Soc. 6, 319–360 (2008)CrossRef

10.

Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Oper. Res. 39(3), 378–406 (1991)CrossRef

11.

Kingston, J.H.: Hierarchical timetable construction. In: Burke, E.K., Rudová, H. (eds.) PATAT 2006. LNCS, vol. 3867, pp. 294–307. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77345-0_19CrossRef

12.

Lopez-Ibanez, M., Dubois-Lacoste, J., Stutzle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. IRIDIA, Universite Libre de Bruxelles, Belgium, Technical report, TR/IRIDIA/2011-004 (2011)

13.

Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)MathSciNetCrossRef

14.

Mladenović, N., Dražić, M., Kovačevic-Vujčić, V., Čangalović, M.: General variable neighborhood search for the continuous optimization. Eur. J. Oper. Res. 191, 753–770 (2008)MathSciNetCrossRef

15.

Montgomery, D.C.: Design and Analysis of Experiments. Wiley, Boco Raton (2017)

16.

Nurmi, K., Kyngas, J.: A framework for school timetabling problem. In: Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications, Paris, pp. 386–393 (2007)

17.

Post, G., et al.: XHSTT: an XML archive for high school timetabling problems in different countries. Ann. Oper. Res. 218, 295–301 (2014)MathSciNetCrossRef

18.

R Core Team: R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2014). http://www.R-project.org/

19.

Schaerf, A.: A survey of automated timetabling. Artif. Intell. Rev. 13(2), 87–127 (1999)CrossRef

20.

Santos, H.G., Ochi, L.S., Souza, M.J.F.: A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. J. Exp. Algorithmics (JEA) 10, 2–9 (2005)MATH

21.

Santos, H.G., Souza, M.J.F.: Timetabling in educational institutions: formulations and algorithms (in Portuguese). In: Proceedings of the XXXIX Brazilian Symposium of Operations Research, Fortaleza, Brazil, pp. 2827–2882 (2007)

22.

Souza, M.J.F.: School timetabling: an approximation by metaheuristics (in Portuguese). Ph.D. thesis, Programa de Pós-graduação em Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Brazil (2000)

23.

Souza, M.J.F., Maculan, N., Ochi, L.S.: A GRASP-Tabu search algorithm for solving school timetabling problems. In: METAHEURISTICS: Computer Decision-Making. Kluwer Academic Publishers, Dordrech, vol. 86, pp. 659–672 (2004)

24.

Teixeira, U.R., Souza, M.J.F., de Souza, S.R.: A local search approach using GVNS for solving school timetabling problems (in Portuguese). In: Proceedings of the XXXVIII Ibero Latin American Congress on Computational Methods in Engineering (CILAMCE), Florianópolis, Brazil (2017). https://doi.org/10.20906/CPS/CILAMCE2017-1240

25.

Valouxis, C., Housos, E.: Constraint programming approach for school timetabling. Comput. Oper. Res. 30(10), 1555–1572 (2003)CrossRef

26.

Wright, M.: School timetabling using heuristic search. J. Oper. Res. Soc. 47(3), 347–357 (1996)CrossRef

Title: An Adaptive VNS and Skewed GVNS Approaches for School Timetabling Problems
Authors: Ulisses Rezende Teixeira
Marcone Jamilson Freitas Souza
Sérgio Ricardo de Souza
Vitor Nazário Coelho
Publisher: Springer International Publishing
Book: Variable Neighborhood Search
Print ISBN: 978-3-030-15842-2

Electronic ISBN: 978-3-030-15843-9

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-15843-9_9

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner