Doutorado em Ciência da Computação

URI Permanente para esta coleção

http://repositorio.ufes.br/handle/10/17626

Nível: Doutorado
Ano de início:
Conceito atual na CAPES:
Ato normativo:
Periodicidade de seleção:
Área(s) de concentração:
Url do curso:

Navegar

Navegando Doutorado em Ciência da Computação por Autor "Amaral, Andre Renato Sales"

Agora exibindo 1 - 1 de 1
  • Nenhuma Miniatura disponível
    Item
    Novas estratégias para obtenção de limitantes inferiores para o problema de tabela-horário de universidades
    (Universidade Federal do Espírito Santo, 2020-08-07) Kampke, Edmar Hell; Mauri, Geraldo Regis; https://orcid.org/0000-0002-8393-7741; http://lattes.cnpq.br/7870111209439581; https://orcid.org/0000-0001-5276-1483; http://lattes.cnpq.br/7599323771219296; Santos, Haroldo Gambini; https://orcid.org/0000-0002-4759-0680; http://lattes.cnpq.br/6320646681995247; Catabriga, Lucia; https://orcid.org/0000-0001-8763-5188; http://lattes.cnpq.br/4364303980383808; Amaral, Andre Renato Sales; https://orcid.org/0000-0001-7344-3994; http://lattes.cnpq.br/4695002674556067
    The University Timetabling Problem (UTP) is one of the most researched topics in the field of combinatorial optimization. This problem consists of allocating a set of lectures to available rooms and periods (timetable) considering students and teachers requests and constraints. Several mathematical formulations for the UTP can be found in the literature once specificities of this problem can vary for each institution. The formulation considered in this work is based on courses curricula of an university, proposed in the second International Timetabling Competition (ITC-2007). So far, several methods based on integer linear programming have been proposed in the literature to obtain lower bounds for this minimization problem. Here, new strategies based on the divide and conquer principle are presented in order to obtain lower bounds for the problem. In this way, the original problem is partitioned with METIS library into sub-problems, each one solved by CPLEX solver. Computational experiments were performed on the ITC-2007 benchmark instances and the results were compared to the best lower bounds found in the literature. These results show the strategies proposed are able to improve the best known lower bounds for two of 21 instances tested and prove the optimality for another 15 instances.