A new LP-based lower bound for the cumulative scheduling problem

This paper deals with the computation of lower bounds for Cumulative Scheduling Problems. Based on a new linear programming formulation, these lower bounds take into account how resource requirements can be satisfied simultaneously for a given resource capacity. One of the main interests of this paper is that the solutions of the LP can be tabulated, for a given value of resource capacity. Thus, even if it is based on a linear programming formulation, the computation of the bounds is low time consuming as confirmed by our computational results on the Resource Constrained Project Scheduling Problem.