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.advisor-co1Rangel, Maria Cristina
dc.contributor.advisor1Boeres, Maria Cláudia Silva
dc.contributor.authorBello, Geraldo Simonetti
dc.contributor.referee1Oliveira, Elias Silva de
dc.contributor.referee2Ochi, Luiz Satoru
dc.date.accessioned2016-08-15T18:52:40Z
dc.date.available2016-08-17T06:00:04Z
dc.date.issued2007-11-12
dc.date.submitted2007-11-12
dc.description.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
dc.description.resumoEste 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.
dc.formatText
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.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/2046
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectCombinatorial optimizationeng
dc.subjectTimetablingeng
dc.subjectGraph coloringeng
dc.subjectTabu searcheng
dc.subjectColoração de grafospor
dc.subjectProgramação de grade horáriapor
dc.subjectBusca tabupor
dc.subject.br-rjbnOtimização combinatória
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleAbordagem do problema de programação de grade horária sujeito a restrições utilizando coloração de grafos
dc.typemasterThesis
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
Mestrado em Informática