Algoritmos heurísticos para problemas de definição de horários escolares

• Processo: 13/13563-3
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de novembro de 2013
• Data de Término da vigência: 07 de outubro de 2017
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Maristela Oliveira dos Santos
• Beneficiário: Landir Saviniec
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Bolsa(s) vinculada(s): 15/10032-2 - Algoritmos heurísticos para problemas de definição de horários escolares, BE.EP.DR
• Assunto(s): Otimização combinatória Métodos heurísticos Heurística
• Palavra(s)-Chave do Pesquisador: heuristicas | horários escolares | Otimização Combinatória | Métodos heurísticos

Resumo

Este projeto visa o desenvolvimento de algoritmos heurísticos eficientes e eficazes para resolver problemas de escalonamento de horários escolares, uma vez que a aplicabilidade de algoritmos exatos para tal finalidade é limitada. Inicialmente, pretende-se abordar o problema de horários em escolas de ensino médio devido a sua importância teórica e prática. Em um projeto de mestrado foram desenvolvidos dois novos operadores de vizinhança em larga escala, baseados em modelos de grafo, para algoritmos de busca local aplicados ao problema. Também foi construída uma base de dados com 102 instâncias de testes. Seis algoritmos baseados em ILS (Iterated Local Search) e três versões em VNS (Variable Neighborhood Search) incorporando os operadores desenvolvidos, foram implementados e testados na base de dados proposta e em uma segunda base de dados da literatura. Os resultados obtidos foram compatíveis com os melhores resultados conhecidos na literatura. Neste projeto pretende-se estender os métodos desenvolvidos de modo a aumentar a eficácia, flexibilidade e eficiência das abordagens. De maneira pragmática, pretende-se estudar operadores de vizinhança em larga escala baseados em modelos de programação inteira. Tais operadores serão combinados com metaheurísticas de busca local para desenvolver novos algoritmos para o problema. Também se pretende incorporar novos estudos de casos (instâncias) à base de dados existente, de modo que esta seja uma compilação ainda mais representativa de situações reais.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

SAYINIEC, LANDIR; SANTOS, MARISTELA O.; COSTA, ALYSSON M.. Parallel local search algorithms for high school timetabling problems. European Journal of Operational Research, v. 265, n. 1, p. 81-98, FEB 16 2018. (15/10032-2, 13/13563-3)

SAVINIEC, LANDIR; CONSTANTINO, ADEMIR APARECIDO. Effective local search algorithms for high school timetabling problems. APPLIED SOFT COMPUTING, v. 60, p. 363-373, NOV 2017. (13/13563-3)

SAVINIEC, LANDIR; SANTOS, MARISTELA O.; COSTA, ALYSSON M.; DOS SANTOS, LANA M. R.. Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems. European Journal of Operational Research, v. 280, n. 3, p. 1064-1081, FEB 1 2019. (15/10032-2, 13/13563-3)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SAVINIEC, Landir. Modelos e algoritmos para problemas de horários escolares. 2017. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.