Uma Heurística GRASP+VND para o Problema de Programação de Horário Escolar

Janio Gloria De Oliveira, Dalessandro Soares Vianna, Marcilene de Fátima Dianin Vianna

Resumo


Este trabalho propõe uma heurística GRASP que utiliza, na etapa de busca local, a técnica VND para solucionar o Problema de Horário Escolar. Consideraram-se, para programação de dois turnos do ensino médio, os dados da Escola Agrotécnica Federal de Alegre (ES, Brasil) nos anos de 2006 e 2007 e outras instâncias geradas neste trabalho para testes. O método proposto tem como objetivo satisfazer as restrições de formação do horário da instituição, tais como: satisfazer aos professores quanto à quantidade de dias em que suas aulas são distribuídas e respeitar seus horários de indisponibilidade; minimizar o número de aulas consecutivas da mesma disciplina; evitar a ocorrência de aulas vagas; evitar a sobreposição de aulas de um mesmo professor; minimizar a ocorrência de “janelas” no horário do professor; evitar que uma turma esteja com aula no mesmo horário com mais de um professor e outras restrições que trazem qualidade ao horário definido. Os resultados computacionais obtidos demonstraram a viabilidade de sua utilização gerando horários que atendem a todas as restrições de viabilidade e um percentual acima de 85% para as restrições de qualidade da solução.

Palavras-chave


Metaheurística; GRASP; VND; Problema de Horário Escolar

Texto completo:

PDF


DOI: https://doi.org/10.7177/sg.2012.V7.N3.A3

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN: 1980-5160

Rua Passo da Pátria 156, bloco E, sala Sistemas & Gestão, Escola de Engenharia, São Domingos, Niterói, RJ, CEP: 24210-240

Tel.: (21) 2629-5616

Correspondência: Caixa Postal LATEC: 100175, CEP 24.020-971, Niterói, RJ