NOVAS ESTRATÉGIAS PARA OBTENÇÃO DE LIMITANTES INFERIORES PARA O PROBLEMA DE TABELA-HORÁRIO DE UNIVERSIDADES
Nome: EDMAR HELL KAMPKE
Tipo: Tese de doutorado
Data de publicação: 07/08/2020
Orientador:
Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Co-orientador |
Banca:
| Nome |
Papel |
|---|---|
| ANDRÉ RENATO SALES AMARAL | Examinador Interno |
| GERALDO REGIS MAURI | Orientador |
| HAROLDO GAMBINI SANTOS | Examinador Externo |
| LUCIA CATABRIGA | Examinador Interno |
| LUCIANO LESSA LORENZONI | Examinador Externo |
Resumo: O Problema de Tabela-Horário de Universidades (PTHU) é um dos mais pesquisados dentre os problemas de Otimização Combinatória (OC). Este problema consiste em alocar uma sequência de aulas nas salas disponíveis para um período de tempo predeterminado (tabela-horário) considerando necessidades de alunos, professores e satisfazendo algumas restrições. Várias formulações para o PTHU podem ser encontradas na literatura pois as necessidades que devem ser atendidas na construção da tabela-horário variam para cada instituição. Neste trabalho é considerado o PTHU baseado na formulação de currículos de cursos (CB-CTT) proposta na segunda edição do campeonato internacional de tabela-horário (ITC-2007). Até o momento, diversos métodos baseados em Programação Linear Inteira (PLI) foram propostos na literatura para obter valores de limitantes inferiores desse problema de minimização. Neste trabalho são apresentadas novas estratégias baseadas no princípio dividir para conquistar com o intuito de obter valores de limitantes inferiores. As estratégias apresentadas usam a biblioteca METIS para particionar o problema original em subproblemas que são resolvidos com o otimizador CPLEX. Experimentos computacionais foram executados nas instâncias de referência usadas no ITC-2007 e os resultados foram comparados com os melhores limitantes inferiores encontrados na literatura. Esses resultados mostram que as estratégias propostas são capazes de melhorar o valor do melhor limitante inferior atualmente conhecido em duas das 21 instâncias e provar a otimalidade em outras 15 instâncias.
Palavras-chaves: Tabela-Horário de Universidades. Limitantes Inferiores. Particionamento. Relaxações.
