AddCumulative for Capacity-Limited Resources

The AddCumulative constraint models a single renewable resource of fixed capacity shared among many tasks, each with its own demand. This lesson covers verifying feasibility of a cumulative schedule, computing peak resource usage to find the minimum feasible capacity, and bounding the demand of an unknown task so the schedule remains feasible.

Step 1 of 157%

Tutorial

The Cumulative Constraint

The AddCumulative constraint generalizes AddNoOverlap to model a single renewable resource of fixed capacity that is shared among many tasks. Each task consumes a fixed amount of the resource — its demand — while it is running, and the total demand of tasks running at any instant must not exceed the resource capacity.

For tasks $1, 2, \ldots, n$ with start $s_i$ , duration $d_i$ , end $e_i = s_i + d_i$ , and demand $r_i$ , sharing a resource of capacity $C$ , the cumulative constraint requires

\sum_{i \,:\, s_i \le t < e_i} r_i \le C \qquad \text{for every time } t.

The sum runs over all tasks that are active at time $t$ — those that have started but not yet ended. AddNoOverlap is the special case in which every $r_i = 1$ and $C = 1$ .

Example. Three tasks share a server of capacity $5$ :

Task	start	duration	demand
A	0	3	3
B	1	2	1
C	2	3	2

At $t=2$ all three tasks are active, with total demand $3 + 1 + 2 = 6$ . Since $6 > 5$ , this schedule violates the cumulative constraint.