# Cumulative constraint

is a global constraint that models scheduling problems as follows. Given are a collection of tasks $LaTeX: T=t_1 \dots t_n$, such that each task $LaTeX: t_i$ is associated with four variables:

• release time, $LaTeX: r_i$, is the earliest time at which it can begin executing,
• deadline (or due date), $LaTeX: d_i$, is the time by which it must complete
• processing time, $LaTeX: p_i$, is the length of time it takes to complete
• capacity requirement, $LaTeX: c_i$, is the capacity of the resource that it uses while it executes.

In addition, we are given the capacity variable $LaTeX: C$ of the resource.

The $LaTeX: cumulative(\{s_1 \dots s_n\},\{p_1 \dots p_n\}, \{c_1 \dots c_n\}, C)$ constraint assigns a starting time $LaTeX: s_i$ for each task $LaTeX: t_i$ such that:

• $LaTeX: r_i\leq s_i \leq d_i - p_i$: the task starts at or after its release date and end at or before its deadline, and
• $LaTeX: \forall u \sum_{i|s_i\leq u\leq s_i+p_i} c_i\leq C$: at any time unit $LaTeX: u$, the capacity of the resource is not exceeded.