Agosto 2016 vol. 2 num. 1 - XVIII Simpósio de Pesquisa Operacional & Logística da Marinha

Artigo Completo - Open Access.

Idioma principal

SIMULATED ANNEALING APLICADO AO PROBLEMA DE PROGRAMAÇÃO DE HORÁRIOS DO CCA-UFES

Carvalho, André Soares ; Mariano, Gelinton Pablo ; Kampke, Edmar Hell ; Mauri, Geraldo Regis ;

Artigo Completo:

Atualmente, as instituições de ensino superior têm grande dificuldade em montar de maneira adequada os horários das disciplinas dos cursos, devido aos inúmeros requisitos pedagógicos, pessoais e institucionais envolvidos. Este trabalho tem como objetivo desenvolver e aplicar uma nova alternativa para resolver o Problema de Programação de Horários em Universidades (PPHU). O PPHU é um problema clássico na área de otimização combinatória e tem grande relevância prática e teórica. Para solucionar o problema, foi utilizada a meta-heurística Simulated Annealing (SA) que, além de ser de fácil implementação, tem apresentado bons resultados para outros problemas relacionados. Com o intuito de avaliar o desempenho da SA para resolução do PPHU, foram utilizados os dados referentes à oferta de disciplinas do Centro de Ciências Agrárias da Universidade Federal do Espírito Santo (CCA-UFES) realizada no período letivo 2013/2. Os resultados apresentam o bom desempenho do algoritmo proposto.

Artigo Completo:

Download (PDF)

Palavras-chave: Otimização Combinatória; Meta-heurísticas; Problema de Programação de Horários em Universidades; Simulated Annealing,

Palavras-chave: ,

DOI: 10.5151/marine-spolm2015-140476

Referências bibliográficas
  • [1] Barbosa, S. H. D e Souza, S. R. (2011), Resolução do problema de programação de Cursos universitários baseada em currículos via uma meta-heurística híbrida GRASPILS- relaxado. In: Simpósio Brasileiro de Pesquisa Operacional, 43, Ubatuba. Anais... SBPO.
  • [2] Cangalovié, M. e Schreuder, J. A. M. (1991), Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths. European Journal of Operational Research Society, v. 51, p. 248-258.
  • [3] Carvalho, R. (2011), Abordagem heurística para o problema de programação de horários de cursos. Dissertação (Mestrado em Engenharia Elétrica) – Universidade Federal de Minas Gerais (UFMG), Belo Horizonte-MG.
  • [4] Ceschia, S., Gaspero, L. D. e Schaerf, A. (2011), Design, engineering, and experimental analysis of a simulated annealing approach to the postenrolment course timetabling problem. Computers & Operations Research, v. 39, n. 7, p. 1615–162
  • [5] Csima, J. e Gotlieb, C. C. (1964), Tests on a computer method for construction of school timetables. Communications of the ACM, v. 7, p.160-163.
  • [6] Eiselt, H. A. e Laporte, G. (1987), Combinatorial optimization problems with soft and hard requirements. Journal of Operations Research, v. 38, n. 9, p. 785-795.
  • [7] Elloumi, A., Kamoun, H., Ferland, J. e Dammak, A. (2008), A tabu search procedure for course timetabling at a tunisian university. In Proceedings of the 7th PATAT Conference.
  • [8] Erben, W. e Keppler, J. (1995), A genetic algorithm solving a weekly coursetimetabling problem. In Proceedings of ICPTAT’95, 1st International Conference on the Practice and Theory of Automated Timetabling, Napier University, Edinburgh, UK, pp. 21-32.
  • [9] Ferland, J. A. e Roy, S. (1985), Timetabling problem for university as assignment of activity to resources. Computers & Operations Research, v. 12, p. 207-218.
  • [10] Fonseca, G. H. G, Ribeiro, R. G. e Martins, F. V. C. (2011), Uma abordagem híbrida de SAT e busca tabu para o problema da programação de horários escolares. In: Simpósio Brasileiro de Pesquisa Operacional, 43, Ubatuba. Anais... SBPO.
  • [11] Gotlieb, C. C. (1962), The construction of class-teacher timetables. In: Proceedings of IFIP Congress, Anais... North-Holland Pub. Co., Amsterdam.
  • [12] Kirkpatrick, S. (1984), Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, Kluwer Academic Publishers-Plenum Publishers.
  • [13] Mauri, G. R. (2005), Novas heurísticas para o problema de escalonamento de tripulações. Dissertação de mestrado - Instituto Nacional de Pesquisa Espacial (INPE), São José dos Campos-SP.
  • [14] Neufeld, G. A. e Tartar, J. (1974), Generalized graph colorations. SIAM Journal on Applied Mathemathics, v. 29, p. 91-98.
  • [15] Ostermann, R. e Werra, D. (1983), Some experiments with a timetabling system. OR Spektrum, v. 3, p.199-204.
  • [16] Santos, H. G. (2007), Formulações e algoritmos para o problema da programação de horários em escolas. Tese (Doutorado em Computação) – Universidade Federal Fluminense (UFF), Niterói-RJ.
  • [17] Santos, H. G. e Souza, M. J. F. (2007), Programação de horários em instituições educacionais: formulações e algoritmos. In: Simpósio Brasileiro de Pesquisa Operacional, 39, Fortaleza. Anais... SBPO.
  • [18] Schaerf, A. (1999), A survey of automated timetabling. Artificial Intelligence Review, v.13, p. 87-127.
  • [19] Schmidt, G. e Ströhlein, T. (1980), Timetable construction – an annotated bibliography. The Computer Jornal, v. 23, n. 4, p. 307-316.
  • [20] Souza, M. J. F. (2000), Programação de horários em escolas: uma aproximação por metaheurísticas. Tese (Doutorado em Engenharia de Sistemas e Computação) – Universidade Federal do Rio de Janeiro (UFRJ), Rio de Janeiro-RJ.
  • [21] Tripathy, A. (1984), School timetabling – a case in large binary integer linear programming. Management Science, v. 30, p. 1473-1489.
  • [22] Wood, D. C. (1969), A technique for colouring a graph applicable to large scale timetabling problems. The Computer Journal, v. 12, p. 317-319.
Como citar:

Carvalho, André Soares; Mariano, Gelinton Pablo; Kampke, Edmar Hell; Mauri, Geraldo Regis; "SIMULATED ANNEALING APLICADO AO PROBLEMA DE PROGRAMAÇÃO DE HORÁRIOS DO CCA-UFES", p. 341-352 . In: Anais do XVIII Simpósio de Pesquisa Operacinal & Logística da Marinha. São Paulo: Blucher, 2016.
ISSN 2175-6295, ISBN: 2358-5498
DOI 10.5151/marine-spolm2015-140476

últimos 30 dias | último ano | desde a publicação


downloads


visualizações


indexações