Araujo, Janniele Aparecida SoaresSantos, Haroldo GambiniGendron, BernardJena, Sanjay DominikBrito, Samuel SouzaSouza, Danilo Santos2020-10-132020-10-132020ARAUJO, 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.0305-0548http://www.repositorio.ufop.br/handle/123456789/12841Resource 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.en-USrestritoMixed-integer linear programmingArtigo publicado em periodicohttps://www.sciencedirect.com/science/article/abs/pii/S0305054819302242?via%3Dihubhttps://doi.org/10.1016/j.cor.2019.104782