Formulações e algoritmos para o problema de programação de horários em escolas

• Ano de defesa: 2025
• Autor(a) principal: Santos, Haroldo Gambini
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Programação de horários em escolas; Programação linear inteira; Metaheurísticas; Programação linear; Programação inteira; Horário escolar; Metaheurística; Algoritmo; School timetabling; Mixed integer programming; Metaheuristics
• Link de acesso: https://app.uff.br/riuff/handle/1/37287

Esta tese trata de uma variante de um clássico problema combinatório NP-Completo: o Problema de Programação de Horários Professor-Turma. Nessa variante, importantes considerações práticas são incorporadas, especificamente tratando de preferências de professores e distribuição das aulas. As propostas apresentadas nesta tese dividem-se em 3 partes. Na primeira parte é apresentada uma nova heurística híbrida, baseada em Busca Tabu. Experimentos computacionais demonstraram que a heurística proposta melhora os resultados da literatura, apresentando um desempenho consistentemente superior em todos os problemas teste. Na segunda parte, propostas foram apresentadas para a obtenção de quadros de horários provadamente ótimos, considerando técnicas de Programação Linear Inteira Mista. Nesse sentido é desenvolvida uma formulação com um número exponencial de linhas e colunas, bem como um algoritmo que utiliza as técnicas de geração de colunas e cortes para o tratamento dessa formulação. Experimentos computacionais demonstraram que a formulação apresentada permite a obtenção de limites inferiores bastante fortes, os quais permitiram a prova da otimalidade para 3 instâncias em aberto da literatura. Finalmente, na terceira parte, é explorada a sinergia entre heurísticas e métodos exatos, através da resolução ótima de sub-problemas em quadros de horários construídos heuristicamente, esses algoritmos híbridos ofereceram os melhores limites superiores disponíveis.