Programação de Horários em Escolas: Uma Aproximação por Metaheurísticas
Autores
|
1961 |
44,836
|
|
|
1962 |
44,836
|
Informações:
Publicações do PESC
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.
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.