Cumulative constraint

From Glossary

Jump to: navigation, search


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.


Views
Personal tools