Por favor, use este identificador para citar o enlazar este ítem: http://www.repositorio.ufop.br/jspui/handle/123456789/14600
Título : Problema de programação de horários de cursos universitários da ITC2019 : modelos e algoritmos.
Autor : Santos, Paulo Sérvulo
metadata.dc.contributor.advisor: Fonseca, George Henrique Godim da
Oliveira, Paganini Barcellos de
Palabras clave : Programação de horários
Programação linear inteira mista
Heurística
Fecha de publicación : 2022
metadata.dc.contributor.referee: Fonseca, George Henrique Godim da
Oliveira, Paganini Barcellos de
Santos, Haroldo Gambini
Toffolo, Túlio Ângelo Machado
Citación : SANTOS, Paulo Sérvulo. Problema de programação de horários de cursos universitários da ITC2019: modelos e algoritmos. 2022. 75 f. Dissertação (Mestrado em Engenharia de Produção) – Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2022.
Resumen : Este trabalho aborda o Problema de Agendamento de Horários de Cursos Universitários apresentado na Competição Internacional de Horários 2019 (ITC2019). O problema é composto por um conjunto de cursos, salas e estudantes, onde cada curso possui uma estrutura hierárquica que define em quais turmas o aluno pode se matricular. O objetivo é alocar uma sala e um horário para cada turma e alocar os alunos às turmas de forma a não violar as restrições de distribuição rígidas e minimizar os custos associados aos tempos, salas, penalidades das restrições fracas e conflitos de alunos. Para solucionar a problemática, uma heurística matemática multi-vizinhança do tipo Fixa-e-Otimiza, que utiliza um modelo já disponível na literatura, foi proposta. Além da heurística matemática, foram propostas diferentes técnicas de pré-processamento para a redução da dimensão das instâncias, o que contribui para compactação dos modelos. Também foi desenvolvida uma heurística construtiva capaz de gerar soluções válidas que são usadas como entrada para o algoritmo Fixa-e-Otimiza. Os resultados computacionais indicam que, para algumas das instâncias, as estratégias de pré-processamento auxiliam na geração de um modelo mais compacto. Obteve-se uma redução média de 22,03% e 7,65% na quantidade de variáveis e restrições, respectivamente, quando comparados com trabalhos da literatura. O algoritmo Fixa-e-Otimiza também se mostrou eficiente na medida em que obteve alguns resultados melhores que o segundo e terceiro colocados da ITC2019. Mesmo com o grande esforço no pré-processamento para reduzir a dimensão das instâncias, algumas delas não puderam ser carregadas em memória para serem resolvidas pelo modelo matemático.
metadata.dc.description.abstracten: This work addresses the Problem University Course Timetabling presented in the International Schedule Competition 2019 (ITC2019). The problem is composed of a set of courses, rooms and students, where each course has a hierarchical structure that define how the student should participate in classes. The objective is to allocate a room and time to each class and to allocate students to classes so as not to violate strict allocation restrictions and to minimize the costs associated with times, classrooms, penalties of soft constraints and student conflicts. To solve the problem, a Fix-and-Optimize multi-neighborhood mathematical heuristic that uses a model already available in the literature was proposed. In addition to the heuristic, different pre-processing techniques were proposed to reduce the instance size, which contributes to the compaction of the models. A constructive heuristic capable of generating valid solutions that are used as input to Fix-and-Optimize algorithm was also developed. The computational results indicate that, for some of the instances, the pre-processing strategies help in the generation of a more compact model, and on average it was possible to obtain a reduction of 22.03% and 7.65% in the number of variables and constraints, respectively, compared with the literature. Fix-and-Optimize algorithm also proved to be efficient as it obtained some better results than the second and third placed in the ITC2019. Even with the great effort in the pre-processing to reduce the dimension of the instances, some of them could not be loaded in memory to be solved by the mathematical model.
Descripción : Programa de Pós-Graduação em Engenharia de Produção. Departamento de Engenharia de Produção, Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto.
URI : http://www.repositorio.ufop.br/jspui/handle/123456789/14600
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 23/02/2022 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.
Aparece en las colecciones: PPGEP - Mestrado (Dissertações)

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
DISSERTAÇÃO_ProblemaProgramaçãoHorários.pdf1,51 MBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons