Um estudo de caso sobre a geração de quadros de horários nos cursos de Ciência da Computação e Engenharia da Computação da UFRGS

Abstract

A geração de quadros de horários para universidades é um problema clássico de otimização combinatória que leva em consideração um grande número de variáveis e requisitos. Este tipo de problema, em geral, contém restrições específicas da aplicação, gerando diversas variações do problema. Apesar do problema ser classificado como NP-Difícil, o mesmo é resolvido manualmente na maior parte das instituições, devido à dificuldade de formalizar todas as restrições que cada aplicação requer em um sistema informatizado. Este trabalho apresenta um estudo da geração de quadros de horários no curso de Ciência da Computação e Engenharia da Computação da Universidade Federal do Rio Grande do Sul onde o problema é formalizado através de um modelo matemático e um estudo experimental é realizado em instâncias reais do problema. Para auxiliar tais experimentos, também foi desenvolvida uma ferramenta web para facilitar a criação de instâncias. Os resultados obtidos demonstram que as instâncias consideradas podem ser resolvidas de maneira eficiente com o modelo proposto através de um resolvedor comercial de programação inteira mista, em comparação com as soluções manuais.

University timetabling is a classic combinatorial optimization problem that considers a large number of variables and requirements. That type of problem in general has specific application constraints generating a large quantity of variations of the problem. Despite the fact the problem belongs to the NP-Hard class of complexity, it is usually manually solved in most institutions, due to the difficult to formalize all the required constrains in a computerized system. This work presents a study about timetabling at the course of Computer Science and Computer Engineering at UFRGS where the problem is formalized by a mathematical model and an experimental study is realized using real instances of the problem. In order to assist the experiments, a web based tool was also developed to help the creation of the instances. The results show that the instances can be efficiently solved with the proposed model using a general purpose mixed integer programming solver, in comparison to the manual solutions.