An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

In this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.

► We propose an exact algorithm for the RCPSP with generalized precedence relations. ► The proposed branch and bound algorithm exploits a novel mathematical formulation. ► A Lagrangian relaxation based lower bound is proposed. ► A comparison with four competing algorithms is presented. ► Our algorithm achieved better results with respect to the competing approaches.