Abordagem do Problema de Programação de Grade Horária sujeito a Restrições utilizando Coloração de Grafos

Nome: Geraldo Simonetti Bello
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 12/11/2007
Orientador:

Nome Papelordem decrescente
Maria Cristina Rangel Co-orientador
Maria Claudia Silva Boeres Orientador

Banca:

Nome Papelordem decrescente
Maria Cristina Rangel Coorientador
Luiz Satoru Ochi Examinador Externo
Elias Silva de Oliveira Examinador Interno
Maria Claudia Silva Boeres Orientador

Resumo: Este trabalho aborda os problemas de Programação de Grade Horária Escolar e de Coloração de Grafos. Apresenta suas características e descreve as principais abordagens propostas na literatura para solução destes dois problemas, incluindo a que reformula a versão básica do problema de Programação de Grade Horária Escolar como um problema de Coloração de Grafos e utiliza os algoritmos correspondentes a esta abordagem para a sua resolução. Escolhe na literatura um problema de Programação de Grade Horária Escolar com restrições adicionais àquelas encontradas na versão básica. Desenvolve um modelo que estende a correspondência entre os dois problemas, contemplando também restrições adicionais. Implanta adaptações em um algoritmo Busca Tabu para Coloração de Grafos descrito na literatura e em uma implementação existente deste algoritmo em linguagem C, de forma a permitir a resolução do problema com restrições adicionais considerado. Reformula o problema escolhido como problema de Coloração de Grafos e utiliza o algoritmo modificado para a sua resolução. Apresenta os resultados computacionais para um conjunto de instâncias associado ao problema. Verifica o efeito desta reformulação nos resultados, comparando-os com os existentes na literatura, que não empregam esta reformulação.

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