[en] A MIP-BASED APPROACH TO SOLVE A REAL-WORLD SCHOOL TIMETABLING PROBLEM

Detalhes bibliográficos
Ano de defesa: 2016
Autor(a) principal: NARA TORRES MOREIRA
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: MAXWELL
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=27073&idi=1
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=27073&idi=2
http://doi.org/10.17771/PUCRio.acad.27073
Resumo: [pt] Problemas de geração de grades horárias visam agendar eventos a fim de satisfazer demandas, ao mesmo tempo que satisfazem restrições adicionais. Uma solução é boa se todas as grades horárias resultantes são aceitáveis para todas as pessoas e recursos envolvidos. Para a geração de grades horárias escolares, um número conhecido de aulas, envolvendo estudantes, professores e salas de aula, deve ser agendado ao longo da semana, enquanto limitações operacionais, institucionais, pedagógicas e pessoais devem ser satisfeitas. A alta dificuldade do problema tem levado muitos pesquisadores a trabalhar em abordagens de resolução para o mesmo desde o início dos anos 60. Encontrar uma solução aplicável em um cenário do mundo real implica em satisfazer vários requisitos de qualidade e em não ignorar questões políticas, o que torna o problema clássico muito mais intrincado. Este trabalho descreve uma abordagem baseada em programação inteira mista (MIP) desenvolvida para resolver um problema real de geração de grades horárias escolares e discute ideias e desafios encarados durante a fase de implantação da solução em algumas escolas brasileiras. Em contraste com outros trabalhos na área, o compartilhamento de professores entre diferentes unidades de uma escola é considerado. Experimentos computacionais foram realizados para cenários cujo número de unidades varia de 2 a 15, o número de professores de 35 a 471, e o número de turmas de 16 a 295. Diferentes estratégias foram combinadas, visando a convergência da procura por boas soluções. Por fim, os resultados são avaliados e as melhores abordagens são destacadas.