Please use this identifier to cite or link to this item:
Title: Strong bounds for resource constrained project scheduling : preprocessing and cutting planes.
Authors: Araujo, Janniele Aparecida Soares
Santos, Haroldo Gambini
Gendron, Bernard
Jena, Sanjay Dominik
Brito, Samuel Souza
Souza, Danilo Santos
Keywords: Mixed-integer linear programming
Issue Date: 2020
Citation: ARAUJO, J. A. S. et al. Strong bounds for resource constrained project scheduling: preprocessing and cutting planes. Computers & Operations Research, v. 113, jan. 2020. Disponível em: <>. Acesso em: 10 mar. 2020.
Abstract: Resource 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.
ISSN: 0305-0548
Appears in Collections:DECSI - Artigos publicados em periódicos

Files in This Item:
File Description SizeFormat 
  Restricted Access
1,14 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.