Desenvolvimento de um modelo para o School Timetabling Problem baseado na Meta-Heurística Simulated Annealing

Abstract

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível.

Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.