[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. / [en] Timetabling Problems have been widely studied, given its practical and
theorical relevance. Most of its variations belong to the NP-Hard class of
problems. In general, it is about allocation of material and human resources
in time and space, aiming to optimize some set of defined objetives. In
University Course Timetabling, for example, the objective might be the
satisfaction of professors and the academic performance of students. In the
last years, the formulations for timetabling problems proposed by the In-
ternational Timetabling Competition (ITC) have been widely adopted. The
predominance of meta-heuristics and local search-based methods is remark-
able among the recently proposed approaches. The objetive of this thesis
is to propose algorithms for the Post Enrolment-based Course Timetabling
Problem of the ITC, focusing on Mathematical Programming-based heuris-
tic methods. Among the Mixed Integer Linear Programming models that
we propose for this problem, we highlight the one based on the Asymetric
Representatives Formulation for the Graph Coloring Problem. We explore
the application of the Local Branching heuristic and we propose a Column
Generation solution procedure, as an attempt to handle the proposed models,
given that the complexity of such models poses a challenge for currently
available Mixed Integer Linear Programming solvers.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:13807 |
| Date | 24 June 2009 |
| Creators | VITOR CAVALCANTI DANTAS |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0018 seconds