Construção de Calendários de Exames

Tese de mestrado, Estatística e Investigação Operacional (Investigação Operacional) Universidade de Lisboa, Faculdade de Ciências, 2022Todos os anos, os estabelecimentos de ensino tem de criar calendários de exames. Uma grande maioria destes estabelecimentos ainda opta pela sua criação manual, resultando numa tarefa demorada, e muitas vezes, pouco eficiente. A Faculdade de Ciências da Universidade de Lisboa não é uma exceção, utilizando um calendário de exames já criado em anos anteriores, e adaptando manualmente ao ano letivo corrente. O problema da calendarização de exames pertence a classe de problemas NP-Difícil e, como tal, para obter soluções de boa qualidade em tempos aceitáveis são necessários algoritmos heurísticos. Um dos tipos de algoritmos utilizados para este género de problemas são os algoritmos de coloração de grafos. Nesta dissertação são propostos três algoritmos, testados em dez instâncias diferentes, para a criação de um calendário de exames direcionado para a época especial, uma época de exames na qual apenas dias antes da sua realização se sabe ao certo o número de alunos para cada exame. Os primeiros algoritmos utilizados neste trabalho são de coloração de grafos e coloração equitativa, para a criação do calendário de exames, e tem como objetivo uma distribuição mais uniforme, e justa para os alunos, dos exames pelos dias da época especial. O terceiro algoritmo desenvolvido é baseado em algoritmos de caminho ótimo, para a reorganização dos dias do calendário criado para a melhoria de uma restrição soft, a garantia de que todos os alunos tenham pelo menos um dia de intervalo entre os dois exames. Os resultados obtidos foram favoráveis para todas instâncias, sendo possível concluir que a utilização de algoritmos de coloração de grafos permite atingir resultados promissores, principalmente se complementados com outro tipo de algoritmos direcionados para a melhoria das restrições soft.Every year, educational institutions have to create exam schedules. A large majority of this insti tutions still create them manually, resulting in a time-consuming and often not very efficient task. The Faculdade de Ciencias da Universidade de Lisboa is no exception, using an already existing exam schedule already created in previous years, and adapting it manually to the current academic year. The exam scheduling problem belongs to the class of NP-hard problems and, as such, to obtain good quality soluti ons in acceptable times heuristic algorithms are required. Graph coloring algorithms are one of the type of algoritmhs used for this kind of problems. In this dissertation three algorithms are proposed, tested in ten different instances, for the creation of an exam schedule aimed to the special examination period, an exam period in which only a few days before its realization it is known for sure the number of stu dents enrolled in each exam. The two first algorithms used in this work are graph coloring and equitable coloring, for the creation of the exam schedule, with the goal of a more uniform, and fairer distribution for students, of exams over the days of the special period. The third algorithm developed is based on optimal path algorithms, for the reorganization of the days of the created schedule for the improvement of the soft constraint, the guarantee that all students have at least one day between the two exams. The obtained results were favorable for all instances, and it is possible to bring to a conclusion that the use of graph coloring algorithms allows the achievement of promising results, especially if complemented with other types of algorithms, aimed at improving the soft constraints