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:

Nomeordem decrescente Papel
Geraldo Regis Mauri Orientador
Maria Claudia Silva Boeres Co-orientador

Banca:

Nomeordem decrescente 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.

Acesso ao documento

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910