Use este identificador para citar ou linkar para este item: http://ri.ufs.br/jspui/handle/riufs/6839
Tipo de Documento: Monografia
Título: Formulações exata e heurística para o problema de programação de horários da Universidade Federal de Sergipe
Autor(es): Menezes, Dimitri Carvalho
Data do documento: 28-Set-2017
Orientador: Gusmão, René Pereira de
Resumo: O 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.
Abstract: Curriculum 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 and
Palavras-chave: Ciência da computação
Ensino de computação
Otimização combinatória
Programação de horários
Método heurístico
Programação linear
Combinatorial optimization
Timetabling problem
Heuristic method
Linear programming
área CNPQ: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO
Idioma: por
Sigla da Instituição: Universidade Federal de Sergipe
Departamento: DCOMP - Departamento de Computação – Ciência da Computação – São Cristóvão - Presencial
Citação: MENEZES, 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.
URI: https://ri.ufs.br/handle/riufs/6839
Aparece nas coleções:Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Dimitri Carvalho Menezes.pdf375,14 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.