Métodos de Otimização Aplicados à Programação de Horários da ENCE

O problema de programação de horários configura um desafio clássico de otimização combinatória, frequentemente tratado de forma manual, o que limita a qualidade das soluções obtidas. Este trabalho analisa um estudo de caso real da ENCE, reinterpretando-o como um problema de matching com restrições. São exploradas três abordagens: Programação Linear Inteira, um algoritmo de Backtracking e uma heurística baseada em VNS. As formulações produzem ótimos globais em poucos segundos, com destaque para a redução da dispersão da carga docente (de 51 para 47 dias). A heurística VNS combina rápida obtenção de soluções viáveis com refinamento progressivo, enquanto o Backtracking permite a enumeração eficiente de múltiplas soluções ótimas globais. Os resultados evidenciam ganhos relevantes na qualidade das soluções e no suporte à decisão, com validação em dados reais.