Models and algorithms for high school timetabling problems

• Ano de defesa: 2017
• Autor(a) principal: Saviniec, Landir
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Column generation; Geração de colunas; High school timetabling problem; Metaheurísticas paralelas; Mixed-integer programming; Parallel metaheuristics; Problema de horários escolares; Programação linear inteira mista
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/

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.