Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/2046
Título: Abordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafos
Autor(es): Bello, Geraldo Simonetti
Orientador: Boeres, Maria Cláudia Silva
Coorientador: Rangel, Maria Cristina
Palavras-chave: Otimização combinatória
Programação de grade horária
Coloração de grafos
Busca tabu
Data do documento: 12-Nov-2007
Resumo: Este trabalho aborda os problemas de Programação de Grade Horária Escolar e de Coloração de Grafos, apresenta suas características, 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. Um problema de Programação de Grade Horária Escolar com restrições adicionais àquelas encontradas na versão básica é escolhido na literatura e é desenvolvido um modelo que estende a correspondência entre os dois problemas, contemplando também restrições adicionais. São propostas 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. O problema escolhido é reformulado como problema de Coloração de Grafos e o algoritmo modificado é utilizado para a sua resolução. São apresentados os resultados computacionais para um conjunto de instâncias associado ao problema e é verificado o efeito desta reformulação nos resultados, comparando-os com os existentes na literatura, que não empregam esta reformulação.
This work addresses the Class/Teacher Timetabling Problem and Graph Coloring Problem, presents features, describes the main approaches proposed in the literature for the solution of these two problems, including the reformulation of the basic version of the Class/Teacher Timetabling Problem as a Graph Coloring Problem, and uses the algorithms on this approach for their resolution. A Class/Teacher Timetabling Problem with additional constraints to those found in the basic version is chosen in the literature and a model that extends the correspondence between the two problems is developed, also contemplating additional constraints. Adaptations in a Tabu Search algorithm for Graph Coloring described in the literature and in the existing implementation in C language are proposed, in order to allow the resolution of the problem with the additional constraints considered. The chosen problem is reformulated as a Graph Coloring Problem and the modified algorithm is used for its resolution. The computational results for a set of instances related to the problem are presented and the effect of this reformulation in the results is verified, comparing them with those in the literature, which does not use this reformulation.
URI: http://repositorio.ufes.br/handle/10/2046
Aparece nas coleções:PPGI - Dissertações de mestrado

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTAÇÃO_GERALDO BELLO.pdf98.95 MBAdobe PDFVisualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons