Models and algorithms for high school timetabling problems (2017)
- Authors:
- Autor USP: SAVINIEC, LANDIR - ICMC
- Unidade: ICMC
- Sigla do Departamento: SME
- Subjects: PROGRAMAÇÃO LINEAR; PROGRAMAÇÃO MISTA; PROGRAMAÇÃO PARALELA; HORÁRIO ESCOLAR; PROGRAMAÇÃO HEURÍSTICA
- Keywords: 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
- Language: Inglês
- Abstract: 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.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2017
- Data da defesa: 18.12.2017
-
ABNT
SAVINIEC, Landir. Models and algorithms for high school timetabling problems. 2017. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/. Acesso em: 19 abr. 2024. -
APA
Saviniec, L. (2017). Models and algorithms for high school timetabling problems (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/ -
NLM
Saviniec L. Models and algorithms for high school timetabling problems [Internet]. 2017 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/ -
Vancouver
Saviniec L. Models and algorithms for high school timetabling problems [Internet]. 2017 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas