Please use this identifier to cite or link to this item: https://app.uff.br/riuff/handle/1/12489
Title: Algoritmos para o Problema de Programação de Horários: Um Estudo de Caso
Authors: Jardim, Arydiane Magalhães
metadata.dc.contributor.advisor: Semaan, Gustavo Silva
metadata.dc.contributor.advisorco: Penna, Puca Huachi Vaz
Issue Date: 2016
Abstract: Este trabalho propõe o desenvolvimento de algoritmos para resolver um Problema de Programação de Horários (PPH). Mais especificamente o Problema de Programação de Horários de Cursos Universitários (PPHU) baseados em currículos, aplicado a um departamento da Universidade Federal Fluminense (UFF). O problema consiste em definir os quadros de horários dos cursos do departamento, alocando professores às disciplinas, de acordo com suas preferências quanto a horários e disciplinas. As restrições e conflitos são definidos pelos currículos dos cursos, como também na alocação de professores e nos tipos e números de salas disponíveis no instituto. Devido à complexidade do problema que é considerado NP-Difícil é proposto um algoritmo utilizando a meta-heurística Iterated Local Search (ILS) para geração automática de quadros de horários. O algoritmo ILS proposto utiliza movimentos intra e inter períodos que são baseados em movimentos simples e bem conhecidos na literatura, como de reinserção e troca, na busca local e também no procedimento de perturbação. A fim de testar e calibrar o algoritmo desenvolvido foram utilizadas instâncias artificiais criadas com base nas características e demandas do departamento estudado. Os experimentos computacionais, utilizando as instâncias artificiais, mostram que o algoritmo proposto foi capaz de encontrar soluções de alta qualidade para todos os grupos e melhores soluções para todas as instâncias dos grupos com nível de dificuldade fácil e médio. Agora, utilizando um exemplo real, baseado no quadro de horário adotado pelo departamento em 2014. A instância com dados reais envolve cinco cursos e até quarenta professores. Os resultados obtidos com o algoritmo proposto foram comparados com a solução gerada por um software de código aberto, chamado FET, utilizado pelo departamento. O algoritmo proposto foi capaz de encontrar uma solução melhor do que a obtida pelo FET. Portanto, os resultados dos experimentos indicam que o algoritmo proposto é uma eficiente alternativa para resolver o PPHU.
metadata.dc.description.abstractother: This work proposes an algorithm to solve Timetabling Problems (TP). More specifically, the University Timetabling Problems (UTP), applied to a department of the Fluminense Federal University. The problem consists in defining the timetabling of the department's courses, allocating professors to courses according to their preferences, related to schedules and disciplines. The restrictions and conflicts are defined by the curricula of the courses, as well as, the types and numbers of available rooms at the teaching building. Due to the complexity of the problem, it is considered NP-Hard, we propose an algorithm based on the Iterated Local Search (ILS) meta-heuristic for automatic courses timetabling generation. The proposed ILS algorithm uses intra and inter period moves based on simple and well-know moves, like reinsertion and swap, in the local search and also in the perturbation mechanism. In order to test and calibrate the proposed algorithm a set of artificial benchmark problems were created based on the characteristics and demands of the department in our case study. Computational experiments, using our artificial benchmark problems, show that the proposed algorithm was able to find high quality solutions for all groups and optimal solutions for all instances in groups with easy and medium difficulty level. Now, using a real instance, based on the department timetabling of 2014. The real case instance involves five courses and up to forty professors. The obtained results of the proposed algorithm were compared to the solution generated by an open source software, named FET, and used by the department. Our approach was able to find a better solution than the one obtained using FET. In conclusion, the experiments results indicate that the proposed algorithm is an effective alternative to solve the UTP.
URI: https://app.uff.br/riuff/handle/1/12489
Appears in Collections:PCL - Trabalhos de Conclusão de Curso - Santo Antônio de Pádua

Files in This Item:
File Description SizeFormat 
TFC_Arydiane.pdf1.44 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons