Abordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafos

• Ano de defesa: 2007
• Autor(a) principal: Bello, Geraldo Simonetti
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Espírito Santo; BR; Mestrado em Informática; Centro Tecnológico; UFES; Programa de Pós-Graduação em Informática
• Palavras-chave em Português: Combinatorial optimization; Timetabling; Graph coloring; Tabu search; Coloração de grafos; Programação de grade horária; Busca tabu; Otimização combinatória; Ciência da Computação; 004
• Link de acesso: http://repositorio.ufes.br/handle/10/2046

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.