| |
| Acadêmico(a): Thomás Augusto Preis |
| Título: Protótipo gerador de grades horárias para instituições de ensino |
| |
| Introdução: |
| A construção de grades horárias é um problema enfrentado corriqueiramente por pequenas e principalmente por grandes instituições de ensino. Problema que ocorre devido a alguns fatores, dentre os quais podem ser citados a disponibilidade de horários de cada professor, salas de aula e número de disciplinas. Freqüentemente é uma tarefa difícil juntar todos esses elementos sem que haja conflitos nos horários. Esta tarefa pode tornar-se ainda mais árdua conforme o aumento do número de disciplinas e restrições dos professores. O problema é potencializado quando o sistema permite que os professores informem suas disponibilidades para ministrarem aulas, pois se torna ainda mais complexo efetuar uma boa distribuição dos horários, de forma que seja interessante a todos, respeitando as restrições de cada um. Observam-se muitos estudos voltados à análise dessa questão e à busca de soluções no meio computacional. Conforme Alvarenga et al. (2005), problemas na construção de horários acadêmicos são conhecidos na literatura como timetabling. Para essa questão, não existe uma solução genérica, a qual sempre possa ser aplicada para alcançar o resultado esperado: cada situação requer uma solução específica. Michalewicz (1996 apud COSTA; BRUNA, 2003, p. 1) afirma que o timetabling pode ser considerado como um dos problemas mais interessantes da pesquisa operacional. A questão tem sido profundamente estudada e vem sendo considerada de difícil solução sob o ponto de vista computacional, isto devido ao grande número de restrições e variáveis de diferentes tipos a serem levadas em consideração e atendidas para obter-se uma solução ótima. O problema de alocação de horários há tempos é amplamente discutido e estudado, principalmente para instituições de ensino, onde conciliar, manualmente, disponibilidade entre professores e classes (turmas) é tarefa difícil, que demanda tempo e nem sempre se consegue resolver sem conflitos de disponibilidades das partes envolvidas. Também conhecido como \\\'timetabling\\\', o problema de alocação de horários escolar é assunto abordado por muitos autores que propõem uma variedade de soluções e de restrições. (SCHAEFER, 1999 apud ALVARENGA et al., 2005). Inúmeros algoritmos podem auxiliar a solucionar problemas de timetabling. Conforme Sorroche (2002, p. 84-85), é possível citar: algoritmos genéticos, algoritmo guloso, algoritmo de Bron e Kerbosh, Simulated Anneling e Tabu Search. Estudando-se de forma mais aprofundada alguns algoritmos que se propõem a solucionar problemas de timetabling, observou-se que não há um algoritmo mais ou menos apropriado para se chegar ao resultado esperado. Cada algoritmo, em cada caso, apresenta particularidades, dentre as quais: desempenho, complexidade, capacidade de exploração de seu espaço de busca e outros. O presente trabalho explora a aplicação de busca com Algoritmos Genéticos (AG) aplicados na resolução de problemas de timetabling. |
| |
|
