Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound

In this paper we study an extension of the classical Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing a further type of precedence constraints denoted as “Feeding Precedences” (FP). This kind of problem happens in that production planning environment, like make-to-order manufacturing, when the effort associated with the execution of an activity is not univocally related to its duration percentage and the traditional finish-to-start prece- dence constraints or the generalized precedence relations cannot completely represent the overlapping among activities. In this context we need to introduce in the RCPSP the FP constraints. For this problem we propose a new mathematical formulation and define a lower bound based on a resource constraints Lagrangian relaxation. A computational experimentation on randomly generated instances of sizes of up to 100 activities show a better performance of this lower bound with respect to others. More- over, for the optimally solved instances, its value is very close to the optimal one.