Specifications PyCSP³ Tools Instances Competitions About

Constraint cumulative

Here, we have a collection of tasks, each one described by 4 attributes: origin, length, end and height. In XCSP³, the element ends is optional. The constraint cumulative [AB93] enforces that at each point in time, the cumulated height of tasks that overlap that point, respects a numerical condition $(\odot,k)$ composed of an operator in {lt,le,ge,gt,in,notin} and a right operand which is an integer value, a variable or an integer interval. When the operator `le’ is used, this corresponds to not exceeding a given limit.

cumulative($X$, $L$, $H$, ($\odot$,$k$)) with $X=\langle x_1,x_2,\ldots\rangle$ $L=\langle l_1,l_2,\ldots\rangle$ and $H=\langle h_1,h_2,\ldots\rangle$, iff $\forall t, \sum \{h_i : 1 \leq i \leq |H| \land x_i \leq t \lt x_i + l_i\} \odot k$

If the element ends is present, for the semantics, we have additionally that: $\forall i : 1 \leq i \leq |X| , x_i + l_i = e_i$

Syntax

<cumulative>
  <origins> (intVar wspace)2+ </origins>
  <lengths> (intVal wspace)2+ | (intVar wspace)2+ </lengths>
  [<ends> (intVar wspace)2+ </ends>]
  <heights> (intVal wspace)2+ | (intVar wspace)2+ </heights>
  <condition> "(" operator "," operand ")" </condition> 
</cumulative>

Example

<cumulative>
  <origins> s1 s2 s3 s4 </origins>
  <lengths> l1 l2 l3 l4 </lengths>
  <heights> h1 h2 h3 h4 </heights>
  <condition> (le,4) </condition>
</cumulative>

A refined form of cumulative corresponds to the constraint sometimes called cumulatives [BC02] We have a set of available machines (resources), with their respective numerical conditions in conditions which replaces condition through a sequence of pairs composed of an operator and an operand. Each task is thus performed by a machine, which is given in an element machines. For each machine, the cumulated height of tasks that overlap a time point for this machine must respect the numerical (capacity) condition associated with the machine. The optional attribute startIndex gives the number used for indexing the first numerical condition (and so, the first machine) in this list (0, by default).

cumulative($X$, $L$, $H$, $M$, $C$) with $X=\langle x_1,x_2,\ldots\rangle$ $L=\langle l_1,l_2,\ldots\rangle$ $H=\langle h_1,h_2,\ldots\rangle$ $M=\langle m_1,m_2,\ldots\rangle$ and $C=\langle (\odot_1,k_1),(\odot_2,k_2),\ldots\rangle$, iff $\forall m \in \{m_i : 1 \leq i \leq |M|\}, \forall t : \exists 1 \leq i \leq |H| : x_i \leq t \lt x_i + l_i \land m_i=m,$ $\sum \{h_i : 1 \leq i \leq |H| \land x_i \leq t \lt x_i + l_i \land m_i=m\} \odot_m k_m$

Syntax

<cumulative>
  <origins> (intVar wspace)2+ </origins>
  <lengths> (intVal wspace)2+ | (intVar wspace)2+ </lengths>
  [ <ends> (intVar wspace)2+ </ends> ]
  <heights> (intVal wspace)2+ | (intVar wspace)2+ </heights>
  <machines> (intVar wspace)2+ </machines>
  <conditions  [ startIndex="integer" ]> 
    ("(" operator "," operand ")")2+ 
  </conditions>
</cumulative>