[en] ALGORITHMS FOR POST ENROLLMENT-BASED COURSE TIMETABLING

• Ano de defesa: 2009
• Autor(a) principal: VITOR CAVALCANTI DANTAS
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO LINEAR; [pt] PROGRAMACAO DE HORARIO; [pt] OTIMIZACAO COMBINATORIA; [pt] METAHEURISTICAS; [en] LINEAR PROGRAMMING; [en] COMBINATORIAL OPTIMIZATION; [en] METAHEURISTICS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13807&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13807&idi=2; http://doi.org/10.17771/PUCRio.acad.13807

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis.