Artigo6 AlessandraMartinsCoelho

SPOLM 2006

ISSN 1806-3632

Rio de Janeiro, Brasil, 15 e 16 de agosto de 2006

UM ALGORITMO HÍBRIDO BASEADO EM ALGORITMOS
MEMÉTICOS E RECONEXÃO POR CAMINHOS PARA
RESOLUÇÃO DO PROBLEMA DE HORÁRIO ESCOLAR
Alessandra Martins Coelho
Centro Federal de Educação Tecnológica de Rio Pomba
Av. Dr. José Sebastião da Paixão, s/n, Lindo Vale, Rio Pomba-MG [e-mail] Sérgio Ricardo de Souza
Centro Federal de Educação Tecnológica de Minas Gerais
Av. Amazonas, 7675, Nova Gameleira, Belo Horizonte-MG [e-mail] Resumo
Este trabalho propõe uma metodologia híbrida entre algoritmos meméticos e a técnica de reconexão por caminhos, para solucionar o Problema de Horário Escolar. Considerou-se, para análise, os dados referentes aos professores do Centro Federal de Educação Tecnológica de Rio Pomba-MG nos anos de 2005 e 2006, para a programação de dois turnos em simultâneo. A metodologia proposta tem como objetivo satisfazer o maior número de professores quanto à quantidade de dias em que suas aulas são distribuídas; minimizar o número de janelas e quebras de aula; além de atender a um certo número de aulas duplas. Os resultados encontrados pelo algoritmo híbrido são comparados com os do método iterated local search.
Palavras-Chaves: Metaheurísticas; Problema de Horário Escolar; Algoritmo Memético.

Abstract
This work provides a hybrid methodology between the memetics algorithms and the
Path Relinking technique for solving an School Timetabling Problem. The analyzed source data came from the teachers staff of Centro Federal de Educação Tecnológica de Rio PombaMG from years 2005 and 2006, to the simultaneous scheduling two turns. The methodology objective is to satisfy the higher number of teachers requests, by reducing the number of days which its lessons are distributed; minimizing the number of empty windows and same classes being apart from each other, besides of reducing the number of double classes. The results found for the hybrid algorithm are compared with