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:

Nomeordem decrescente Papel
Maria Claudia Silva Boeres Orientador
Maria Cristina Rangel Co-orientador

Banca:

Nomeordem decrescente 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.

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910