PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Filtros

20191

Configurações

Autor: search.filters.author.Araujo, Janniele Aparecida SoaresAssunto: search.filters.subject.Programação linear

Resultados da Pesquisa

Agora exibindo 1 - 1 de 1
  • Nenhuma Miniatura Disponível
    Item
    Mixed-integer linear programming based approaches for the resource constrained project scheduling problem.
    (2019) Araujo, Janniele Aparecida Soares; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Barboza, Eduardo Uchoa; Souza, Marcone Jamilson Freitas; Jena, Sanjay Dominik; Toffolo, Túlio Ângelo Machado
    Resource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known NP-hard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. First, in this thesis, we provide improved upper bounds for many hard instances from the literature by using methods based on Stochastic Local Search (SLS). As the most contribution part of this work, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chvátal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-the-art mixed-integer linear programming solver to nd provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.