OTIMIZAÇÃO COMBINATÓRIA: O PROBLEMA DE ALOCAÇÃO DE PROFESSORES FORMULADO COMO UM PROBLEMA BINÁRIO

  • Ríad Mattos Nassiffe IFC - Campus Blumenau
  • Amanda Cadore dos Santos
  • Milene Karine Gubetti
Palavras-chave: Escalonamento de horário, Instituição de ensino, Otimização, Computação, Matemática

Resumo

O escalonamento de horário acadêmico já é estudado há mais de 30 anos e ainda é um problema recorrente nas instituições de ensino, pois é algo complexo de ser solucionado manualmente. Grande parte da dificuldade em resolver esse tipo de problema ocorre devido às diferentes variáveis que estão envolvidas: número de professores, salas, turmas, disciplinas, dias e períodos. Quando alguma das variáveis é incrementada, o número de combinações cresce de forma exponencial e a complexidade do problema aumenta proporcionalmente. Computacionalmente, escolher o melhor escalonamento de horário é considerado um problema NP-Difícil, isso implica que não existe um algoritmo que o resolva de forma exata com complexidade polinomial. Sendo assim, um problema que envolva muitos professores, turmas, salas, disciplinas, dias e períodos pode não ser solucionado por um computador convencional. Atualmente, existem softwares disponíveis no mercado para realizar tal tarefa, eles podem ser acessados online, como o “URÂNIA” e o “PowerCubus”, ou estarem disponíveis para download, como o “aSc Timetables”. Contudo, ambas as formas disponíveis não são muito acessíveis, em consequência de seu custo, e as versões grátis possuem algumas limitações. Portanto, o objetivo principal do trabalho é pesquisar e desenvolver um programa capaz de gerar opções de escalonamento de horário de forma automatizada e acessível.  O programa, desenvolvido na linguagem Python, realizará a leitura de uma planilha em formato ods com as informações inseridas pelo usuário, as processará e retornará uma planilha em formato csv com a grade de horários. Para tornar isso possível, o primeiro passo foi a modelagem matemática do problema, a qual cria subgrupos das variáveis envolvidas para restringir o número de combinações possíveis e otimizar o processo. Desse modo, o presente trabalho também busca mostrar como a computação e matemática juntas podem resolver problemas do dia a dia das pessoas.

Publicado
2019-02-04
Seção
Poster