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 |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| ELIAS SILVA DE OLIVEIRA | Examinador Interno |
| LUIZ SATORU OCHI | Examinador Externo |
| MARIA CLAUDIA SILVA BOERES | Orientador |
| MARIA CRISTINA RANGEL | Coorientador |
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.
