Formulações e algoritmos para o problema de programação de horários em escolas

• Ano de defesa: 2007
• Autor(a) principal: Santos, Haroldo Gambini
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Programação de horários em escolas; Programação linear inteira; Metaheurística; Algoritmo; Otimização combinatória; School Timetabling; Mixed Integer Programming; Metaheuristic; Algorithm; Combinatorial optimization; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/18770

This thesis considers an variation of a classical combinatorial NP-Complete problem: The Class-Teacher Timetabling Problem. In this variant, important practical considerations are incorporated, specifically, teachers preferences and distribution of lessons. The proposals of this work are divided in three parts. In the first part a new hybrid heuristic is presented, based on Tabu Search. Computational experiments demonstrated that the proposed heuristic improves upon existing methods presenting a consistently better performance in all test problems. In the second part, proposals for producing optimal timetables are presented, considering Mixed Integer Linear Programming Techniques. In this sense, a formulation with an exponential number of rows and columns is developed, as well an algorithm to manage this formulation by cut and column generation. Computational experiments demonstrated that the proposed formulation provides stronger bounds, which allowed the proof of optimality for 3 open instances from literature. Finally, in the third part, the synergy of heuristics and exact methods is explored, by the optimal resolution of sub-problems from timetables heuristically generated. These hybrid algorithms offered the best upper bounds available.