A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints

This paper deals with the resource constrained project scheduling problem (RCPSP) with generalized precedence constraints (RCPSP/Max). We propose an exact method that tackles a relaxed version of the original problem by modeling it as a satisfiability problem (SAT). Several SAT formulations are introduced, as well as workload-based procedures that were developed in order to reduce the domain of the decision variables, and custom propagators that were implemented with a view of improving the efficiency of the SAT solver. Extensive computational experiments involving different configurations of the method were carried out on 2430 RCPSP/Max benchmark instances ranging from 10 to 500 activities and with 5 resources, and on 2040 RCPSP benchmark instances ranging from 30 to 120 activities and with 4 resources. The results obtained suggest that the proposed method is extremely competitive as almost all known optima were found and 86 instances were solved to optimality for the first time. Moreover, a number of bounds were improved for those instances that still remain open. (C) 2019 Elsevier B.V. All rights reserved.

Automated summary

This paper addresses the resource constrained project scheduling problem with generalized precedence constraints by proposing an exact method that models the problem as a satisfiability problem. Extensive computational experiments show that the method is competitive and almost all known optima were found.