Fonseca, George Henrique Godim daOliveira, Paganini Barcellos deSantos, Paulo Sérvulo2022-03-032022-03-032022SANTOS, Paulo Sérvulo. Problema de programação de horários de cursos universitários da ITC2019: modelos e algoritmos. 2022. 75 f. Dissertação (Mestrado em Engenharia de Produção) – Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2022.http://www.repositorio.ufop.br/jspui/handle/123456789/14600Programa de Pós-Graduação em Engenharia de Produção. Departamento de Engenharia de Produção, Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto.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.pt-BRabertoProgramação de horáriosProgramação linear inteira mistaHeurísticaDissertacaoAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 23/02/2022 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.