Modelos e algoritmos para problemas de horários escolares

Autor(es)

Landir Saviniec

• Tipo de documento: Tese de Doutorado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2017-12-18

Membros da banca

Maristela Oliveira dos Santos; Alexandre Cláudio Botazzo Delbem; Mariá Cristina Vasconcelos Nascimento; Haroldo Gambini Santos; Lana Mara Rodrigues dos Santos

• Orientador: Maristela Oliveira dos Santos; Alysson Machado Costa

Resumo

Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte. (AU)

• Processo FAPESP: 13/13563-3 - Algoritmos heurísticos para problemas de definição de horários escolares
• Beneficiário: Landir Saviniec
• Modalidade de apoio: Bolsas no Brasil - Doutorado