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

Página do item simplificado
dc.contributor.advisorBoeres, Maria Cláudia Silva
dc.contributor.advisor-coRangel, Maria Cristina
dc.contributor.refereeOliveira, Elias Silva de
dc.contributor.refereeOchi, Luiz Satoru
dc.date.accessioned2016-08-15T18:52:40Z
dc.date.available2016-08-17T06:00:04Z
dc.identifier.citationBELLO, 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.por
dc.identifier.urihttp://repositorio.ufes.br/handle/10/2046
dc.publisher.courseMestrado em Informáticapor
dc.publisher.programPrograma de Pós-Graduação em Informáticapor
dc.rightsopen accessen
dc.subjectCombinatorial optimizationen
dc.subjectTimetablingen
dc.subjectGraph coloringen
dc.subjectTabu searchen
dc.subjectColoração de grafospor
dc.subjectProgramação de grade horáriapor
dc.subjectBusca tabupor
dc.subject.br-rjbnOtimização combinatóriapor
dc.subject.cnpqCiência da Computaçãopor
dc.subject.udc004por
dc.titleAbordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafospor
dc.typemasterThesisen
dcterms.abstractEste 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.por
dcterms.abstractThis 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.en
dcterms.creatorBello, Geraldo Simonetti
dcterms.dateSubmitted2007-11-12
dcterms.formatTexten
dcterms.issued2007-11-12
dcterms.languageporen
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
DISSERTAÇÃO_GERALDO BELLO.pdf
Tamanho:
96.63 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
PPGI - Dissertações de mestrado