Estudo de Coloração de Grafos Aplicado ao Problema de Alocação de Horários: Uma Solução Focada no Aluno
Resumo
A pesquisa explora a aplicação da Teoria dos Grafos no problema de alocação de horários, focando nos alunos em ano de conclusão de curso. Utilizando a coloração de grafos, as disciplinas foram representadas como vértices e os alunos como arestas. Foram comparadas duas abordagens principais: o algoritmo de Força Bruta e a heurística Degree of Saturation (DSATUR). Os resultados mostraram que, embora o algoritmo de Força Bruta forneça uma solução ótima, ele é computacionalmente caro. Em contrapartida, a heurística DSATUR demonstrou ser extremamente eficiente em termos de tempo de execução, embora não garanta sempre a solução ótima. O código da aplicação proposta está disponível no Google Colab.
Referências
Bagheri, E., Noia, T. D., Gasevic, D., and Ragone, A. (2012). Formalizing interactive staged feature model configuration. Journal of Software: Evolution and Process, 24(4):375–400.
Blum, A. (1994). New approximation algorithms for graph coloring. J. ACM, 41(3):470–516.
de Werra, D. (1990). Heuristics for Graph Coloring, pages 191–208. Springer Vienna, Vienna.
Duarte, I., Cancela, L., and Rebola, J. (2021). Graph coloring heuristics for optical networks planning. In 2021 Telecoms Conference (ConfTELE), pages 1–6.
Egwuche, O. S. (2020). Examination timetabling with graph coloring for emerging institutions. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS), pages 1–6.
Hussin, B., Basari, A. S. H., Shibghatullah, A. S., Asmai, S. A., and Othman, N. S. (2011). Exam timetabling using graph colouring approach. In 2011 IEEE Conference on Open Systems, pages 133–138.
Jensen, T. and Toft, B. (2011). Graph Coloring Problems. Wiley Series in Discrete Mathematics and Optimization. Wiley.
LABED, S., KOUT, A., and CHIKHI, S. (2018). A fast heuristic for graph b-coloring problem. In 2018 JCCO Joint International Conference on ICT in Education and Training, International Conference on Computing in Arabic, and International Conference on Geocomputing (JCCO: TICET-ICCA-GECO), pages 1–6.
Pillay, N. (2013). A comparative study of hyper-heuristics for solving the school timetabling problem. In Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, SAICSIT ’13, page 278–285, New York, NY, USA. Association for Computing Machinery.
Streicher, S. and du Preez, J. (2017). Graph coloring: Comparing cluster graphs to factor graphs. In Proceedings of the ACM Multimedia 2017 Workshop on South African Academic Participation, SAWACMMM ’17, page 35–42, New York, NY, USA. Association for Computing Machinery.
Tuza, Z. (1997). Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17(2):161–228.
Blum, A. (1994). New approximation algorithms for graph coloring. J. ACM, 41(3):470–516.
de Werra, D. (1990). Heuristics for Graph Coloring, pages 191–208. Springer Vienna, Vienna.
Duarte, I., Cancela, L., and Rebola, J. (2021). Graph coloring heuristics for optical networks planning. In 2021 Telecoms Conference (ConfTELE), pages 1–6.
Egwuche, O. S. (2020). Examination timetabling with graph coloring for emerging institutions. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS), pages 1–6.
Hussin, B., Basari, A. S. H., Shibghatullah, A. S., Asmai, S. A., and Othman, N. S. (2011). Exam timetabling using graph colouring approach. In 2011 IEEE Conference on Open Systems, pages 133–138.
Jensen, T. and Toft, B. (2011). Graph Coloring Problems. Wiley Series in Discrete Mathematics and Optimization. Wiley.
LABED, S., KOUT, A., and CHIKHI, S. (2018). A fast heuristic for graph b-coloring problem. In 2018 JCCO Joint International Conference on ICT in Education and Training, International Conference on Computing in Arabic, and International Conference on Geocomputing (JCCO: TICET-ICCA-GECO), pages 1–6.
Pillay, N. (2013). A comparative study of hyper-heuristics for solving the school timetabling problem. In Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, SAICSIT ’13, page 278–285, New York, NY, USA. Association for Computing Machinery.
Streicher, S. and du Preez, J. (2017). Graph coloring: Comparing cluster graphs to factor graphs. In Proceedings of the ACM Multimedia 2017 Workshop on South African Academic Participation, SAWACMMM ’17, page 35–42, New York, NY, USA. Association for Computing Machinery.
Tuza, Z. (1997). Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17(2):161–228.
Publicado
11/09/2024
Como Citar
BARBOSA, François; JEOVANE, José; AVELINO, Guilherme; MAGALHÃES, Arlino.
Estudo de Coloração de Grafos Aplicado ao Problema de Alocação de Horários: Uma Solução Focada no Aluno. In: ESCOLA REGIONAL DE COMPUTAÇÃO DO CEARÁ, MARANHÃO E PIAUÍ (ERCEMAPI), 12. , 2024, Parnaíba/PI.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 139-148.
DOI: https://doi.org/10.5753/ercemapi.2024.243698.
