Título: | ALGORITHMS FOR POST ENROLLMENT-BASED COURSE TIMETABLING | |||||||
Autor: |
VITOR CAVALCANTI DANTAS |
|||||||
Colaborador(es): |
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO - Orientador |
|||||||
Catalogação: | 24/JUN/2009 | Língua(s): | PORTUGUESE - BRAZIL |
|||||
Tipo: | TEXT | Subtipo: | THESIS | |||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
|||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=13807&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=13807&idi=2 |
|||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.13807 | |||||||
Resumo: | ||||||||
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.
|
||||||||