Mixed-integer linear programming based approaches for the resource constrained project scheduling problem.

Simple item page
dc.contributor.advisorSantos, Haroldo Gambinipt_BR
dc.contributor.authorAraujo, Janniele Aparecida Soares
dc.contributor.refereeSantos, Haroldo Gambinipt_BR
dc.contributor.refereeBarboza, Eduardo Uchoapt_BR
dc.contributor.refereeSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.refereeJena, Sanjay Dominikpt_BR
dc.contributor.refereeToffolo, Túlio Ângelo Machadopt_BR
dc.date.accessioned2020-01-09T16:42:21Z
dc.date.available2020-01-09T16:42:21Z
dc.date.issued2019
dc.descriptionPrograma de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.pt_BR
dc.description.abstractResource 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.pt_BR
dc.identifier.citationARAUJO, Janniele Aparecida Soares. Mixed-integer linear programming based approaches for the resource constrained project scheduling problem. 2019. 96 f. Tese (Doutorado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2019.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/11879
dc.language.isoen_USpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 20/12/2019 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.pt_BR
dc.subjectFinanciamento de projetospt_BR
dc.subjectOrçamento-programapt_BR
dc.subjectProgramação linearpt_BR
dc.titleMixed-integer linear programming based approaches for the resource constrained project scheduling problem.pt_BR
dc.typeTesept_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
TESE_MixedIntegerProgramming.pdf
Size:
4.22 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
924 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Doutorado (Teses)