Redundant cumulative constraints to compute preemptive bounds

We introduce a reformulation of the cumulative resource in scheduling. This reformulation yields a lower bound on the makespan which is at least as good as that of a preemptive schedule on the original resource. Its computation relies on a linear program whose size depends on the resource capacity but not on the number of tasks, which enables to precompute the reformulations. It provides a significant improvement for all algorithms which rely on energy-based reasonings for propagating cumulative constraints, such as edge-finding and energy reasoning techniques. We improve the lower bounds of some RCPSP instances from the PSPLIB.