Construção de um modelo de programação linear para o University Timetabling Problem

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula.The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization