Algoritmo GRASP para o Problema de Tabela-horário de Universidades
Nome: WALACE DE SOUZA ROCHA
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 28/02/2013
Orientador:
Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| FLÁVIO MIGUEL VAREJÃO | Examinador Interno |
| HAROLDO GAMBINI SANTOS | Examinador Externo |
| MARIA CLAUDIA SILVA BOERES | Orientador |
| MARIA CRISTINA RANGEL | Coorientador |
Resumo: O problema de tabela-horário é de grande destaque na área de otimização combinatória. Dado um conjunto de disciplinas, alunos, professores e salas, o problema consiste em alocar aulas em um número limitado de horários e salas, respeitando algumas restrições. As formulações são variadas, o que às vezes dificulta a comparação de trabalhos. Apesar das diferenças, ele é classificado em três classes principais: tabela-horário de exames, de escolas e de universidades. Este trabalho trata especificamente de tabela-horário de universidades e é adotada a formulação três do campeonato internacional de tabela-horário ITC-2007. O problema é resolvido com a meta-heurística GRASP. Hill Climbing e Simulated Annealing são usados como fase de busca local do algoritmo e Path-relinking é implementado para melhorar a versão básica. Testes foram feitos simulando as mesmas regras do campeonato e os resultados obtidos estão competitivos com os obtidos pelos finalistas do ITC-2007.
