Utilização de Metaheurísticas na Resolução do Problema de Agendamento de Horários de Aulas numa Escola de Ensino Fundamental
Resumo
O artigo relata o emprego de metaheurísticas na resolução do Problema do Agendamento de Horário de Aulas, um exemplar da classe Educational Timetabling Problem. As três técnicas metaheurísticas empregadas foram: (1a) In Vitro Fertilization Genetic Algorithm; (2a) Tabu Search; e (3a) Gre-edy Ramdomized Adaptative Search Procedure. A experimentação foi realizada com instâncias reais do problema advindas de uma escola brasileira dedicada à oferta do ensino fundamental e, adicionalmente, de datasets amplamente conhecidos. Verifica-se que os métodos são capazes de produzir soluções adequadas para utilização prática em seus contextos, sendo que o método In Vitro superou os demais para o objetivo de otimização estabelecido.
Palavras-chave:
Metaheurística, Educational Timetabling Problem, Vitro Fertilization, Genetic Algorithm.
Referências
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.
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.
Publicado
08/08/2018
Como Citar
OLIVEIRA, Fábio Santana de; ALENCAR, Wanderley de Souza; NASCIMENTO, Hugo Alexandre Dantas do.
Utilização de Metaheurísticas na Resolução do Problema de Agendamento de Horários de Aulas numa Escola de Ensino Fundamental. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 2018. , 2018, Goiânia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 121-134.
