Problema de programação de horários de cursos universitários da ITC2019 : modelos e algoritmos.

Abstract

Este trabalho aborda o Problema de Agendamento de Horários de Cursos Universitários apresentado na Competição Internacional de Horários 2019 (ITC2019). O problema é composto por um conjunto de cursos, salas e estudantes, onde cada curso possui uma estrutura hierárquica que define em quais turmas o aluno pode se matricular. O objetivo é alocar uma sala e um horário para cada turma e alocar os alunos às turmas de forma a não violar as restrições de distribuição rígidas e minimizar os custos associados aos tempos, salas, penalidades das restrições fracas e conflitos de alunos. Para solucionar a problemática, uma heurística matemática multi-vizinhança do tipo Fixa-e-Otimiza, que utiliza um modelo já disponível na literatura, foi proposta. Além da heurística matemática, foram propostas diferentes técnicas de pré-processamento para a redução da dimensão das instâncias, o que contribui para compactação dos modelos. Também foi desenvolvida uma heurística construtiva capaz de gerar soluções válidas que são usadas como entrada para o algoritmo Fixa-e-Otimiza. Os resultados computacionais indicam que, para algumas das instâncias, as estratégias de pré-processamento auxiliam na geração de um modelo mais compacto. Obteve-se uma redução média de 22,03% e 7,65% na quantidade de variáveis e restrições, respectivamente, quando comparados com trabalhos da literatura. O algoritmo Fixa-e-Otimiza também se mostrou eficiente na medida em que obteve alguns resultados melhores que o segundo e terceiro colocados da ITC2019. Mesmo com o grande esforço no pré-processamento para reduzir a dimensão das instâncias, algumas delas não puderam ser carregadas em memória para serem resolvidas pelo modelo matemático.