Artículos de revistas
Programação Da Grade De Horário Em Escolas De Ensino Fundamental E Médio
Registro en:
Pesquisa Operacional. , v. 28, n. 3, p. 399 - 421, 2008.
1017438
2-s2.0-59449095930
Autor
De Sousa V.N.
Moretti A.C.
De Podesta V.A.
Institución
Resumen
The school timetabling problem (STP) consists in fixing a sequence of meetings between teachers and students in a prefixed period of time (typically a week), satisfying organizational, pedagogical and personal constraints. STP is a NP-complete problem and is usually tackled using heuristic methods. In this work we considered typical characteristics of Brazilian public schools. We presented a Tabu Search procedure associated with a Randomized Local Search to solve this problem and two mathematical formulations. The implementation of the procedure has been successfully experimented in some Brazilian public schools. 28 3 399 421 Abramson, D., Constructing schools timetables using simulated annealing: Sequential and parallel algorithms (1991) Management Science, 37 (1), pp. 98-113 Colorni, A., Dorigo, M., Maniezzo, V., Metaheuristics for high school timetabling (1998) Computational Optimization Applications, 9, pp. 275-298 Costa, D., A tabu search algorithm for computing an operational timetable (1994) European Journal of Operational Research, 76, pp. 98-110 de Werra, D., The combinatorics of timetabling (1997) European Journal of Operational Research, 96, pp. 504-513 Even, S., Itai, A., Shamir, A., On the complexity of timetabling and multicommodity flow problems (1976) SIAM Journal of Computation, 5, pp. 691-703 Filho, G.R., Lorena, L.A.N., A constructive evolutionary approach to school timetabling (2001) Springer Lecture Notes in Computer Science, 2037, pp. 130-139. , Applications of Evolutionary Computing [edited by EJ.W. Boers, J. Gottlieb, P.L. Lanzi, R.E. Smith, S. Cagnoni, E. Hart, G.R. Raidl and H. Tijink Glover, F., Laguna, M., (1997) Tabu Search, , Kluver Academic Publishers, Boston Dordrecht London Gotlieb, C.C., The construction of a class-teacher timetables (1963) IFIP Congress, 62, pp. 73-77. , edited by C.M. Poplewell, North-Holland. Springer Lecture Notesin Computer Science Junginger, W., Timetabling in Germany - a survey (1986) Interfaces, 16, pp. 66-74 Neufeld, G.A., Tartar, J., Graph coloring conditions of the existence of solutions to the timetable problem (1974) Communications of the ACM, 17 (8), pp. 450-433 Ostermann, R., de Werra, D., Some experiments with a timetabling system (1983) OR Spektrum, 3, pp. 199-204 Shaerf, A., Tabu search techniques for large high-school timetabling problems (1996) 13 th National Conference of the American Association for Artificial Intelligence (AAAI-96) Sousa, V.N., (2006), Programação da grade de horário em escolas de ensino fundamental e médio. Dissertação de Mestrado, Instituto de Matemática Estatística e Computação Científica, Universidade Estadual de Campinas, BrasilSouza, M.J.F., (2000) School Timetabling: An approximation by metaheuristcs, , PhD. Dissertation, Computing and Systems Engineering Program, Federal University of Rio de Janeiro, Brazil