Full text
| |
| Author(s): |
Landir Saviniec
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | São Carlos. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2017-12-18 |
| Examining board members: |
Maristela Oliveira dos Santos;
Alexandre Cláudio Botazzo Delbem;
Mariá Cristina Vasconcelos Nascimento;
Haroldo Gambini Santos;
Lana Mara Rodrigues dos Santos
|
| Advisor: | Maristela Oliveira dos Santos; Alysson Machado Costa |
| Abstract | |
High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. (AU) | |
| FAPESP's process: | 13/13563-3 - Heuristic methods for school timetabling problems |
| Grantee: | Landir Saviniec |
| Support Opportunities: | Scholarships in Brazil - Doctorate |