Strong bounds for resource constrained project scheduling : preprocessing and cutting planes.
Data
2020
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
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.
Descrição
Palavras-chave
Mixed-integer linear programming
Citação
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: <https://www.sciencedirect.com/science/article/pii/S0305054819302242>. Acesso em: 10 mar. 2020.