Lower Bounds for the Cumulative Scheduling Problem Based on Energetic Reasoning

This paper addresses the Resource-Constrained Project Scheduling Problem (RCPSP) by decomposing it into multiple Cumulative Scheduling Problems (CuSPs), each handling resource constraints independently. The CuSP involves scheduling non-preemptive tasks within fixed time windows while respecting resource limitations. We focus on determining lower bounds for the minimal makespan in CuSP and present both destructive and constructive approaches while exploring the impact of redundant resources. To achieve this, we leverage energetic reasoning, an advanced filtering technique for the Cumulative Scheduling Problem. While the classical definition of energetic reasoning assesses the portions of tasks processed inside a given time interval, our refined approach instead evaluates the portions processed outside the interval. This alternative perspective allows us to exploit the constraint that, immediately before and after the interval, resource availability is limited by an integer <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex>. By formulating this as a tripartition problem and solving it via Dynamic Programming, we improve the evaluation of scheduling intervals, leading to a more effective constraint propagation. Experimental results demonstrate the effectiveness of our approach in optimizing project scheduling.