Use of Metaheuristics in the Problem Solving of Classroom Schedules in Elementary School

• Fábio Santana de Oliveira UFG
• Wanderley de Souza Alencar UFG
• Hugo Alexandre Dantas do Nascimento UFG

Abstract

This article reports the use of metaheuristic techniques for the resolution of the so-called Teacher-Classroom Timetabling Problem, one of subcategories of the Educational Timetabling Problem. The three metaheuristic techniques employed are: In Vitro Fertilization Genetic Algorithm, Tabu Search and Greedy Ramdomized Adaptive Search Procedure. The experimentation was carried out with one real instance of the problem coming from a Brazilian school dedicated to elementary education and, in addition, with instances from widely known datasets. It turns out that the methods are able to produce solutions suitable for practical use in their contexts, being that method In Vitro has overcome the others for the established optimization goal.

Keywords: Metaheuristics, Educational Timetabling Problem, Vitro Fertilization, Genetic Algorithm.

References

Appleby, J. S. (1961). Techniques for producing school timetables on a computer and their application to other scheduling problems. The Computer Journal, 3(4):237–245.

Berghuis, J., van der Heiden, A. J., and Bakker, R. (1964). The preparation of school timetables by eletronic computer. BIT Numerical Mathematics, 4(2):106–114.Camilo-Junior, C. G. and Yamanaka, K. (2011). In vitro fertilization genetic algorithm. In Kita, E., editor, Evolutionary Algorithms, pages 1–14. InTech Open Access Publisher.Carter, M. W. and Tovey, C. A. (1992). When is the classroom assignment problem hard? Operations Research, 40(S1):28–29.

Colorni, A., Dorigo, M., and Maniezzo, V. (1992). Genetic algorithms: a new approach to the timetable problem. Combinatorial Optimization, pages 235–239.

Colorni, A., Dorigo, M., and Maniezzo, V. (1998). Metaheuristics for high school time-tabling. Computational Optimization and Applications, 9(3):275–298.

Csima, J. and Gotlieb, C. C. (1964). Test on a computer method for constructing school timetables. Communications of the ACM, 7:160.

de Haan, P., Landman, R., Post, G., and Ruizenaar, H. (2007). A case study for timetabling in a dutch secondary school. In Practice and Theory of Automated Timetabling VI, volume 3867, pages 267–279.

de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2):151–162.

de Werra, D. (1997). The combinatorics of timetabling. European Journal of Operational Research, 96:504–513.

dos Santos, C. N. and Santos, R. J. d. S. (2004). Implementação de um algoritmo genetico´ para a construção automatica´ de horarios´ em uma escola de ensino fundamental e medio´. In Anais do VIII Simposio´ Brasileiro de Pesquisa Operacional e Log´ıstica da Marinha, pages 1–8, Rio de Janeiro, Brasil.

Feo, T. A. and Resende, M. G. C. (1995). Greedy Randomized Adaptive Search Proce-dures. Journal of Global Optimization, 6:109–133.

Ferland, J. A. and Lavoie, A. (1992). Exchanges procedures for timetabling problems. Discrete Applied Mathematics, 35:237–253.

Fonseca, G. H. G. and Santos, H. G. (2014). Variable neighborhood search based algo-rithms for high school timetabling. Computers & Operations Research, 52:203–208.

Fonseca, G. H. G., Santos, H. G., and Carrano, E. G. (2016). Integrating matheuristics and metaheuristics for timetabling. Computers & Operations Research, 74:108–117.

Friedman, J. S. (2016). Automated timetabling for small colleges and high schools using huge integer programs. CoRR, abs/1612.08777.

Geske, U. and Goltz, H.-J. (2004). Automatische und interaktive Stundenplanung. Infor-matik Forsch. Entw., 19:65–73.

Glover, F. W. (1989). Tabu search (Part I). ORSA Journal on Computing, 1:190–206.

Glover, F. W. (1990). Tabu search (Part II). ORSA Journal on Computing, 2:4–32.

Gotlieb, C. C. (1962). The construction of class-teacher timetabling. In October, vo-lume 13, pages 73–77.

Hertz, A. (1991). Tabu search for large scale timetabling problems. European Journal of Operational Research, 54:39–47.

Hertz, A. (1992). Finding a feasible course schedule using tabu search. Discrete Applied Mathematics, 35:255–270.

J. Hirsch, M., Pardalos, P., and Resende, M. (2010). Speeding up continuous GRASP. European Journal of Operational Research, 205:507–521.

Kirkpatrick, S., Gelatt, C. D., and Vechi, M. P. (1983). Optimization by simulated annea-ling. Science, 220:671–680.

Lions, J. (1966). Matrix reduction using the Hungarian method for the generation of school timetables. Communications of the ACM, 9(5):349–354.

Lions, J. (1967). The Ontario school timetabling problem. The Computer Journal, 10(1):14–21.

Metropolis, N., Rosenbluth, A., Resenbluth, N., Teller, A., and Teller, E. (1953). Equa-tion of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087–1092.

Moura, A. V. and Scaraficci, R. A. (2010). A GRASP strategy for a more constrai-ned School Timetabling Problem. International Journal of Operational Research, 7(2):152.

Muller,¨ T. and Bartak,´ R. (2001). Interactive timetabling: concepts, techniques and prac-tical results. Technical report, Charles University, Prague, Czech Republic.

Santos, H. G., Ochi, L. S., and Souza, M. J. F. (2004). An Efficient Tabu Search Heuristic for the School Timetabling Problem. In Ribeiro, C. C. and Martins, S. L., editors, Experimental and Efficient Algorithms (WEA 2004), volume 3059 of Lecture Notes in Computer Science (LNCS), pages 468–481, Berlin. Springer.

Teoh, C. H., Wibowo, A., and Ngadiman, M. S. (2015). Review of state of art for me-teheuristic techniques in academic scheduling problems. Artificial Intelligence Review, 44:1–21.

van Staereling, I. v. H. (2012). School timetabling in theory and practice. Technical report, VU University, Amsterdam, Holland.

Veenstra, M. and Vis, I. F. A. (2016). School timetabling problem under disturbances. Computers & Industrial Engineering, 65:175–186.