Algoritmos para o problema de programação de horários: um estudo de caso

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSemaan, Gustavo Silva-
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.creatorJardim, Arydiane Magalhães-
Data de aceite: dc.date.accessioned2024-07-11T18:37:38Z-
Data de disponibilização: dc.date.available2024-07-11T18:37:38Z-
Data de envio: dc.date.issued2019-12-10-
Data de envio: dc.date.issued2019-12-10-
Data de envio: dc.date.issued2016-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/12489-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/774216-
Descrição: dc.descriptionEste 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.-
Descrição: dc.descriptionThis 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/br/-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectComputação-
Título: dc.titleAlgoritmos para o problema de programação de horários: um estudo de caso-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.