Timetabling school : modelagem, solução e um estudo de caso na Escola de Minas da UFOP.

Abstract

A criação de grades horárias é uma tarefa que demanda muitos recursos, pois há diferentes variáveis que possuem ligações múltiplas. É considerada, em termos de grau de complexidade computacional como NP- hard, exigindo elevada capacidade de processamento.Na literatura este problema é denominado de STP (School Timetabling Problem) que consiste em agendar encontros entre professores e estudantes. No presente trabalho desenvolveu-se um modelo de programação linear inteira baseado nas restrições presentes em um outro modelo da literatura para otimizar a criação das referidas grades de horários de forma a minimizar o número de disciplinas alocadas em um mesmo horário de aula. A solução do modelo foi desenvolvida em C++ e para a solução do algoritmo foi realizada via o solver Gurobi que possui um algoritmo interno para resolução de problemas lineares baseada em Simplex, parallel barrier with crossover, concurrent and sifting. Utilizou-se uma base de dados real da Universidade Federal de Ouro Preto do curso de Engenharia de Produção e o algoritmo desenvolvido gerou a grade horária referente aos dez períodos do curso. Os experimentos realizados levaram 0,118 segundos para obter os resultados.