PROGRAMAÇÃO DE HORÁRIOS DE EXAMES ATRAVÉS DA COLORAÇÃO DE GRAFOS

Vanessa Scheeren, Elizangela Dias Pereira, Francieli Aparecida Vaz

Resumo


Este trabalho apresenta uma solução para o Problema de Horários de Exames de cursos universitários. O propósito é desenvolver um cronograma de exames finais viável que aplique todos os exames no período de cinco dias, atendendo às condições impostas pelo problema. Esta abordagem justifica-se pelo fato de que a elaboração do calendário de exames de forma manual consiste em uma atividade exaustiva, que exige a dedicação de muitos funcionários por um longo período de tempo e ainda assim, na maioria das vezes, o resultado final não atende as expectativas. Nesta proposta a técnica de solução fundamenta-se na Teoria dos Grafos, mais precisamente no método de Coloração de Grafos realizado por meio do algoritmo de Welsh-Powell adaptado. Com este propósito, para desenvolver a solução para o problema de programação de horários de exames finais foram utilizados dados reais referentes aos componentes curriculares ofertados aos alunos do Curso de Matemática – Licenciatura da Universidade Federal do Pampa. Os resultados alcançados mostraram que o algoritmo de Welsh-Powell adaptado, alicerçado na técnica de Coloração de Grafos conseguiu atender aos objetivos do problema. Com base neste trabalho foi possível desenvolver um Calendário de Exames Finais viável, dentro do prazo estabelecido, satisfazendo a todas as condições impostas.

Palavras-chave


Coloração de Grafos; Algoritmo de Welsh-Powell; Exames.

Texto completo:

PDF

Referências


BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos, Algoritmos. 4. ed. São Paulo: Edgard Blucher, 2006.

BURKE, E. K. et al. A graph based hyper-heuristic for exam timetabling problems. European Journal of Operational Research, 176, 2007, p. 177-192.

BURKE, E.K., ELLIMAN, D.G. e WEARE, R. F. A hybrid genetic algorithm for highly constrained timetabling problems. Proceedings of the 6th International Conference on Genetic Algorithms (ICGA'95, Pittsburgh, USA, 15th-19th July 1995). Morgan Kaufmann, San Francisco, CA, USA, 1995, p. 605-610.

CARVALHO, R. Abordagem Heurística para o Problema de Programação de Horários de Cursos. Dissertação de Mestrado em Engenharia Elétrica. Escola de Engenharia da Universidade Federal de Minas Gerais. Belo Horizonte, 2011.

CÔTÉ, P., WONG, T. e SABOURIN, R. Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem. Lecture Notes in Computer Science. 2005, v. 3616, p. 151-168.

DAVID, P. A constraint-based approach for examination timetabling using local repair techniques. In: E.K. Burke and M.W. Carter (eds). Practice and Theory of Automated Timetabling: Selected Papers from the 2nd International Conference. Lecture Notes in Computer Science, 1998, v. 1408, p. 169-186.

DUONG, T. A.; LAM, K. H. Combining constraint programming and simulated

annealing on university exam timetabling. In: Proceedings of the 2nd International

Conference in Computer Sciences, Research, Innovation & Vision for the Future (RIVF2004), Hanoi, Vietnam, February 2-5, 2004, p. 205-210.

GASPERO, L. DI; SCHAERF, A. Tabu Search Techniques for Examination Timetabling. Conferência Internacional sobre a Prática e Teoria do Ajuste Automatizado PATAT 2000: Prática e Teoria do Timetabling Automatizado III, 2000, v. 2079, p. 104-117.

LIPSCHUTZ, S.; LIPSON, M. Matemática Discreta, coleção Schaum. 2. ed. São Paulo: Bookman, 2004.

MACHADO, A. M.; BOERES, M. C. S. Uma proposta de formulação do problema de programação de tabela-horário de exames de Toronto via coloração de grafos e sua resolução pelo algoritmo de busca tabu. XLI SBPO - Pesquisa Operacional na Gestão do Conhecimento, 2009.

MUJUNI, E.; MUSHI, A. Solving the Examination Timetabling Problem Using a Two-Phase Heuristic: The case of Sokoine University of Agriculture. Journal of Information and Computing Science, 2015, v. 10, n. 3, p. 220-227. England, UK, 2015.

SCHAERF, A. A Survey of Automated Timetabling. Artificial Intelligence Review, 1999. p. 87-127. v. 13, n. 2.

WERRA, D. An introduction to timetabling. European Journal of Operational Research, 1985, p. 151-162.

WOUMANS, G. et al. A column generation approach for solving the examination-timetabling problem. European Journal of Operational Research 253, 2016, p. 178-194.




DOI: https://doi.org/10.30945/ccei-v23i38.295

Apontamentos

  • Não há apontamentos.