Name: EDMAR HELL KAMPKE

Publication date: 07/08/2020
Advisor:

Namesort descending Role
MARIA CLAUDIA SILVA BOERES Co-advisor *

Examining board:

Namesort descending Role
ANDRÉ RENATO SALES AMARAL Internal Examiner *
LUCIA CATABRIGA Internal Examiner *
LUCIANO LESSA LORENZONI External Examiner *

Summary: The University Timetabling Problem (UTP) is one of the most researched topics in the field of combinatorial optimization. This problem consists of allocating a set of lectures to available rooms and periods (timetable) considering students and teachers requests and constraints. Several mathematical formulations for the UTP can be found in the literature once specificities of this problem can vary for each institution. The formulation considered in this work is based on courses curricula of an university, proposed in the second International Timetabling Competition (ITC-2007). So far, several methods based on integer linear programming have been proposed in the literature to obtain lower bounds for this minimization problem. Here, new strategies based on the divide and conquer principle are presented in order to obtain lower bounds for the problem. In this way, the original problem is partitioned with METIS library into sub-problems, each one solved by CPLEX solver. Computational experiments were performed on the ITC-2007 benchmark instances and the results were compared to the best lower bounds found in the literature. These results show the strategies proposed are able to improve the best known lower bounds for two of 21 instances tested and prove the optimality for another 15 instances.
Keywords: University Timetabling. Lower Bounds. Partitioning. Relaxations.

Access to document

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910