Alocação de Horários Acadêmicos com Coloração de Grafos

Resumo

A organização de horários acadêmicos em instituições de ensino superior representa um desafio recorrente e complexo, sobretudo na ausência de ferramentas automatizadas que apoiem o processo de distribuição de disciplinas e docentes. A elaboração dessas alocações envolvem múltiplas variáveis, como disponibilidade de professores, adequação de salas, carga horária das disciplinas e restrições impostas pelos cursos, fatores que tornam a tarefa de alocação trabalhosa e sujeita a falhas. No campus Bagé da Universidade Federal do Pampa (UNIPAMPA), essa atividade ainda é realizada manualmente com interações entre os coordenadores de curso, juntamente com a coordenação acadêmica, o que demanda grande esforço administrativo, comprometendo a agilidade da gestão acadêmica. Nesse contexto, o presente trabalho apresenta uma proposta de sistema computacional desenvolvido com o objetivo de automatizar e otimizar o processo de alocação de horários, por meio de uma solução baseada em grafos. Assim, espera-se que o método reduza o esforço administrativo e aumente a confiabilidade das soluções obtidas. Grafos são estruturas matemáticas amplamente utilizadas para representar relações entre elementos de um sistema. Em termos gerais, um grafo é formado por nós (ou vértices), que representam entidades, e arestas, que indicam conexões ou conflitos entre esses nós. Ao modelar o problema de alocação de disciplinas como um grafo, é possível aplicar algoritmos bem estabelecidos da teoria dos grafos, como os de coloração, para garantir que disciplinas com restrições em comum não sejam alocadas em horários conflitantes. O protótipo foi implementado em linguagem Python, utilizando a biblioteca NetworkX, que é amplamente empregada em aplicações de análise e manipulação de grafos. Essa biblioteca possibilita representar formalmente problemas complexos em estruturas matemáticas de fácil interpretação, além de oferecer algoritmos eficientes para encontrar soluções em tempo reduzido. No caso específico da alocação de horários, o método de grafos é aplicado para modelar a representação de cada disciplina como um nó e cada conflito de alocação como uma aresta, o que inclui, por exemplo, professores com sobreposição de horários. Essa representação permitiu a proposta da aplicação de algoritmos de coloração de grafos para encontrar uma solução possível. A técnica de coloração de grafos busca atribuir cores (blocos de horários) a cada nó de modo que vértices vizinhos não recebam a mesma cor, assegurando que não ocorram conflitos. O procedimento utilizado baseou-se, portanto, na adaptação de algoritmos de coloração balanceada de grafos, preparados para lidar com restrições adicionais, como horários fixos e agrupamento de disciplinas que devem ocorrer simultaneamente. Para avaliar a viabilidade da proposta e a qualidade da solução gerada foi realizado um estudo de caso com o curso de Engenharia de Computação do campus Bagé. Neste caso, com base na proposta de alocação de disciplinas de semestres anteriores, foram previstos dez blocos de horários distintos, conforme a necessidade, distribuídos de segunda a sexta-feira, possibilitando a validação prática da proposta em cenários simulados que se aproximam da realidade institucional. Os dados obtidos até o momento demonstram que o sistema é capaz de realizar a alocação automática das disciplinas de maneira rápida e eficiente, apresentando desempenho promissor mesmo em situações de alta complexidade, como turmas compartilhadas por diferentes professores ou múltiplas restrições simultâneas. Outro diferencial da solução é a geração automática de arquivos de saída, que facilitam a visualização e a análise pelos coordenadores sem necessidade de conhecimentos técnicos avançados, aumentando a usabilidade da ferramenta no cotidiano acadêmico. Além disso, a arquitetura da aplicação foi projetada de forma extensível, possibilitando a inclusão futura de novas regras e restrições, como critérios de prioridade de docentes, indisponibilidade de salas ou necessidades específicas de determinados cursos, ampliando o potencial de aplicação. O impacto esperado é significativo: a ferramenta contribui para reduzir de dias para minutos o tempo gasto na elaboração dos horários, mitiga conflitos comuns como sobreposição de aulas obrigatórias. Do ponto de vista institucional, a proposta representa um passo importante para a modernização da gestão acadêmica, alinhando-se às demandas contemporâneas de inovação tecnológica no ensino superior. Constata-se que, portanto, a abordagem aqui proposta apresentou observações promissoras, podendo se tornar um importante instrumento de gestão acadêmica. Como próximas etapas, espera-se avaliar a qualidade das soluções geradas com a coordenação do curso de EC, assim como expandir a proposta para outros cursos do campus Bagé. Além disso, espera-se ampliar o estudo para o problema de alocação de salas do campus Bagé.