Please use this identifier to cite or link to this item: http://ri.ufs.br/jspui/handle/riufs/6839
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMenezes, Dimitri Carvalho-
dc.date.accessioned2017-11-03T16:00:48Z-
dc.date.available2017-11-03T16:00:48Z-
dc.date.issued2017-09-28-
dc.identifier.citationMENEZES, Dimitri Carvalho. Formulações exata e heurística para o problema de programação de horários da Universidade Federal de Sergipe. 2017. CD-ROM Monografia (Graduação em Ciência da Computação) - Departamento de Computação, Centro de Ciências Exatas e Tecnológica, Universidade Federal de Sergipe, São Cristóvão, SE, 2017.pt_BR
dc.identifier.urihttps://ri.ufs.br/handle/riufs/6839-
dc.description.abstractCurriculum based timetabling problem is a combinatorial optimization problem and considered as a NP-Hard problem. The biggest difficulty of this problem is to allocate classes for teachers, classrooms and schedules without conflicts of time and space. Relying on curriculum or curriculum matrix means that curriculum schedules should not be in conflict. This is a usual problem in universities and a general formulation is not a good deal to all universities, as institutional rules and restrictions change from one university to another. The construction of a mathematical model can be the basis for new studies or even the construction of a tool that simplifies the organization of teachers schedules of a university.Therefore, this study aimed to build a specific model for the Federal University of Sergipe with the idea of maximizing teachers’ preferences to teach classes at specific time. In addition, to verify how difficult it is to solve this problem increased with the specific restrictions of the university, it was used branch and bound exact method and Iterated Local search heuristic method. The results show that the exact method can obtain solutions after using a lot of time and computational resources. However, it was not possible to prove the optimality of the solutions within the given time limit. While the heuristic method can obtain solutions close to or better than the exact method, using less time andeng
dc.languageporpt_BR
dc.subjectCiência da computaçãopor
dc.subjectEnsino de computaçãopor
dc.subjectOtimização combinatóriapor
dc.subjectProgramação de horáriospor
dc.subjectMétodo heurísticopor
dc.subjectProgramação linearpor
dc.subjectCombinatorial optimizationeng
dc.subjectTimetabling problemeng
dc.subjectHeuristic methodeng
dc.subjectLinear programmingpor
dc.titleFormulações exata e heurística para o problema de programação de horários da Universidade Federal de Sergipept_BR
dc.typeMonografiapt_BR
dc.contributor.advisor1Gusmão, René Pereira de-
dc.description.resumoO problema de programação de horários baseado em currículos é um problema de otimização combinatória e considerado como um problema NP difícil. A grande dificuldade desse problema é alocar aulas para professores, salas e horários sem que haja conflitos de tempo e espaço. Basear-se em currículos ou matriz curricular significa que os horários das aulas de um currículo não devem estar em conflitos. Esse problema é comum em universidades e uma formulação geral do problema acaba não sendo útil para todas as universidades, pois as regras e restrições institucionais mudam de uma universidade para outra. A construção de um modelo matemático pode servir como base para novos estudos ou até mesmo a construção de uma ferramenta que facilite a organização dos horários dos professores de uma universidade. Logo este trabalho teve como objetivo construir um modelo de programação linear inteira para a Universidade Federal de Sergipe com a ideia de maximizar a preferência dos professores em lecionar aulas em horários específicos. E para verificar o quão difícil é solucionar o problema complementado com as restrições específica da universidade, foi utilizado o método exato de branch and bound e a metaheurística Iterated Local Search. Os resultados mostram que o método exato consegue obter soluções após utilizar muito tempo e recursos computacionais. Porém, não foi possível provar a otimalidade das soluções dentro do limite de tempo determinado. Enquanto que o método heurístico consegue obter soluções próximas ou melhores do que o método exato, utilizando menos tempo e recursos computacionais.pt_BR
dc.publisher.departmentDCOMP - Departamento de Computação – Ciência da Computação – São Cristóvão - Presencialpt_BR
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAOpt_BR
dc.publisher.initialsUniversidade Federal de Sergipept_BR
dc.description.localSão Cristóvão, SEpt_BR
Appears in Collections:Computação

Files in This Item:
File Description SizeFormat 
Dimitri Carvalho Menezes.pdf375,14 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.