Artigo

UMA ABORDAGEM HÍBRIDA PARA O PROBLEMA DA PROGRAMAÇÃO DE HORÁRIOS

Karine Gomes dos Santos Souza [e-mail] RESUMO O trabalho desenvolvido propõe uma abordagem híbrida para o problema da programação de horários de escolas. Esta abordagem é um algoritmo GRASP que utiliza uma fase de construção parcialmente gulosa para construir uma solução inicial e utiliza o algoritmo de Busca Tabu para melhorar a solução inicial. Resultados computacionais mostram que este procedimento produz soluções viáveis e de boa qualidade mais rapidamente.
PALAVRAS CHAVE. GRASP, Busca Tabu, Grade Escolar

1. Introdução O problema da programação de horários de escolas diz respeito à grade escolar semanal. O problema consiste em alocar aulas em períodos, respeitando um conjunto de restrições. Resolver este problema de forma manual é muito difícil e geralmente requer vários dias de trabalho, devido ao grande espaço de busca e por possuir muitas restrições. Além disso, a solução obtida pode ser não ser satisfatória.
O problema da programação de horários é um problema NP-difícil (Even et al. (1976)), ou seja, é um problema de elevada complexidade, e devido a isso, é abordado utilizando-se metaheurísticas, que, diferentemente das técnicas heurísticas, são providas de mecanismos para escapar de soluções ótimas locais.
Algumas metaheurísticas que dão boas soluções para o problema são: Busca Tabu (Glover (1986)), Simulated Annealing (Kirkpatrick et al. (1983)), Algoritmos Genéticos (Carrasco & Pato (2001), Colorni et al. (1998)), entre outros.
Geralmente, as metaheurísticas dependem muito das soluções iniciais, ou seja, boas soluções iniciais geram soluções finais melhores em menos tempo. Atualmente utiliza-se bastante a fase de construção da metaheurística GRASP para alcançar boas soluções iniciais.
O objetivo deste trabalho é desenvolver um algoritmo capaz de gerar soluções de boa qualidade em um tempo computacional razoável, através de uma abordagem híbrida utilizando GRASP e