Informações:

Publicações do PESC

Título
Programação de Horários em Escolas: Uma Aproximação por Metaheurísticas
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
15/12/2000
Resumo

Este trabalho trata do problema de programação de horários em escolas. Suas características e propriedades básicas são presentadas. Alguns dos principais algoritmos da literatura são descritos. É desenvolvida uma heurística de busca local, baseada em caminhos mínimos, para melhorar um quadro de horário, ainda que com um certo tipo de inviabilidade. Essa heurística age primeiramente tentando recuperar a viabilidade e, em um segundo momento, se bem sucedida, tentando melhorar os requisitos de qualidade exigidos para o quadro de horário. Várias metaheurísticas conduzindo essa técnica em determinadas fases são desenvolvidas e testadas. É proposta, também, uma modelagem de programação matemática para o problema.
Resultados computacionais são apresentados para um conjunto de problemas-teste reais.

Abstract

The focus of this work is the school timetabling problem. Its basic characteristics and properties are presented. Some of the main algorithms from the literature are described. An heuristic approach, based on shortest paths, to improve the timetable, even infeasible, is proposed. First, this heuristic try to retrieve the feasibility.
If it is successful it will be activated again, now in order to try to improve the compactness of the timetable, as well as other quality requirements. Several metaheuristics using this technique in some phases are developed and tested. A mathematical programming model is proposed too. Computational results are presented for a set of real problems.

Topo