Abordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafos
Nenhuma Miniatura disponível
Data
2007-11-12
Autores
Bello, Geraldo Simonetti
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
Resumo
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.
Descrição
Palavras-chave
Combinatorial optimization , Timetabling , Graph coloring , Tabu search , Coloração de grafos , Programação de grade horária , Busca tabu
Citação
BELLO, Geraldo Simonetti. Abordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafos. 2007. 136 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2007.