Heurísticas eficientes para o problema de geração de grade escolar automatizada

Resumo

As instituições de ensino têm grande dificuldade no momento da geração da grade escolar. A programação de horários torna-se tarefa difícil devido ao grande número de possibilidades e à necessidade de se respeitar uma série de restrições, muitas vezes conflitantes entre si. Podem-se levar semanas ou, até mesmo, meses para se conseguir uma solução satisfatória. Além disso, os resultados normalmente causam insatisfação tanto dos professores quanto dos alunos. Uma solução que seja capaz de propor uma grade com qualidade e que não viole as restrições é muito necessária, uma vez que é crescente o número de novos estabelecimentos de ensino e o problema estar presente em todos eles. O uso de heurísticas para geração automática da grade visa facilitar o trabalho e, ao mesmo tempo, buscar uma solução que melhor atenda às expectativas da instituição. Foi feito um comparativo entre a qualidade das soluções encontradas utilizando um algoritmo GRASP e um ILS para determinar o melhor algoritmo a ser usado na busca de solução. Os resultados indicaram que, dependendo do conjunto de disponibilidades dos professores a ser utilizado, um algoritmo pode convergir para melhores soluções mais rápidas que o outro algoritmo.