Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/2046
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorBoeres, Maria Cláudia Silva-
dc.date.accessioned2016-08-15T18:52:40Z-
dc.date.available2016-08-17T06:00:04Z-
dc.identifier.urihttp://repositorio.ufes.br/handle/10/2046-
dc.rightsopen accesseng
dc.subjectCombinatorial optimizationeng
dc.subjectTimetablingeng
dc.subjectGraph coloringeng
dc.subjectTabu searcheng
dc.titleAbordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafospor
dc.typemasterThesiseng
dc.subject.udc004por
dc.subject.br-rjbnOtimização combinatóriapor
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.eng
dcterms.creatorBello, Geraldo Simonetti-
dcterms.dateSubmitted2007-11-12-
dcterms.formatTexteng
dcterms.issued2007-11-12-
dcterms.languageporpor
dcterms.subjectOtimização combinatóriapor
dcterms.subjectProgramação de grade horáriapor
dcterms.subjectColoração de grafospor
dcterms.subjectBusca tabupor
dc.publisher.programPrograma de Pós-Graduação em Informáticapor
dc.subject.cnpqCiência da Computaçãopor
dc.publisher.courseMestrado em Informáticapor
dc.contributor.refereeOliveira, Elias Silva de-
dc.contributor.refereeOchi, Luiz Satoru-
dc.contributor.advisor-coRangel, Maria Cristina-
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