Strong bounds for resource constrained project scheduling : preprocessing and cutting planes.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.creatorAraujo, Janniele Aparecida Soares-
Autor(es): dc.creatorSantos, Haroldo Gambini-
Autor(es): dc.creatorGendron, Bernard-
Autor(es): dc.creatorJena, Sanjay Dominik-
Autor(es): dc.creatorBrito, Samuel Souza-
Autor(es): dc.creatorSouza, Danilo Santos-
Data de aceite: dc.date.accessioned2022-02-21T19:59:31Z-
Data de disponibilização: dc.date.available2022-02-21T19:59:31Z-
Data de envio: dc.date.issued2020-10-13-
Data de envio: dc.date.issued2020-10-13-
Data de envio: dc.date.issued2019-
Fonte completa do material: dc.identifierhttp://www.repositorio.ufop.br/handle/123456789/12841-
Fonte completa do material: dc.identifierhttps://www.sciencedirect.com/science/article/abs/pii/S0305054819302242?via%3Dihub-
Fonte completa do material: dc.identifierhttps://doi.org/10.1016/j.cor.2019.104782-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/650860-
Descrição: dc.descriptionResource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known N Phard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. In this paper, 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 conflict 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-theart mixed-integer linear programming solver to find provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsrestrito-
Palavras-chave: dc.subjectMixed-integer linear programming-
Título: dc.titleStrong bounds for resource constrained project scheduling : preprocessing and cutting planes.-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.