Desenvolvimento de um modelo de programação linear para o Problema da Construção de Grades Horárias em Universidades

Abstract

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 importante tarefa administrativa. É 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. Neste artigo, propõe-se um modelo matemático para construir grades de horários, otimizando a utilização de salas de aula. Para resolver o modelo proposto, desenvolveu-se um algoritmo que divide o problema para viabilizar o uso de programação linear inteira mista. Experimentos computacionais aplicados a uma base de dados real de uma universidade pública brasileira confirmaram o bom desempenho da abordagem proposta, reduzindo consideravelmente a quantidade de salas de aulas alocadas.

Creating timetables for courses is a problem that universities face at the beginning of every semester. This activity represents an important administrative task because it consumes significant amount of resources. In terms of computational complexity, this is classified as NP-hard, as it demands a huge amount of processing capacity. Timetabling is modeled in a number of different ways, aiming to fit the country’s educational context, meet specific rules of institutions of higher education or specific goals of managers, among others. In this paper, we propose a mathematical model to solve the University Course Timetabling Problem and optimize classroom utilization. To solve the proposed model, an algorithm that divides the problem was developed, solving it with mixed integer linear programming tools. Computational experiments applied to a real database of a Brazilian public university confirmed the good performance of the proposed approach, which greatly reduces the amount of assigned classrooms.