Simpósio de Pesquisa Operacional e Logística da Marinha - Publicação Online

Agosto 2016, vol.2, num.1 - XVIII Simpósio de Pesquisa Operacional & Logística da Marinha
Artigo Completo - Open Access Idioma principal | Segundo principal

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

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.

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.

Download (PDF)

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–1624.
  • [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 21756295, DOI 10.5151/marine-spolm2015-140476

últimos 30 dias

139
downloads

369
visualizações

1090
indexações