Global Constraint Catalog: Ccumulative_with_level_of

5.100. cumulative_with_level_of_priority

DESCRIPTION

LINKS

GRAPH

Origin

H. Simonis

Constraint

$𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 (𝚃𝙰𝚂𝙺𝚂, 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂)$

Arguments

$𝚃𝙰𝚂𝙺𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (\begin{matrix} 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 𝚒𝚗𝚝, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 𝚍𝚟𝚊𝚛, \\ 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, \\ 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛, \\ 𝚑𝚎𝚒𝚐𝚑𝚝 - 𝚍𝚟𝚊𝚛 \end{matrix})$
$𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍 - 𝚒𝚗𝚝, 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 - 𝚒𝚗𝚝)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝚂𝙺𝚂, [𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢, 𝚑𝚎𝚒𝚐𝚑𝚝])

𝚛𝚎𝚚𝚞𝚒𝚛𝚎_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝

(2, 𝚃𝙰𝚂𝙺𝚂, [𝚘𝚛𝚒𝚐𝚒𝚗, 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, 𝚎𝚗𝚍])

𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 \geq 1

𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 \leq | 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 |

𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 \geq 0

𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗 \leq 𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍

𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂, [𝚒𝚍, 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢])

𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚒𝚍 \geq 1

𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚒𝚍 \leq | 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 |

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂, 𝚒𝚍)

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂, 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢)

Purpose

Consider a set $𝒯$ of tasks described by the $𝚃𝙰𝚂𝙺𝚂$ collection where each task has a given priority chosen in the range $[1, 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂]$ . Let $𝒯_{i}$ denote the subset of tasks of $𝒯$ that all have a priority less than or equal to $i$ . For each set $𝒯_{i}$ , the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint forces that at each point in time, the cumulated height of the set of tasks that overlap that point, does not exceed a given limit. A task overlaps a point $i$ if and only if (1) its origin is less than or equal to $i$ , and (2) its end is strictly greater than $i$ . Finally, it also imposes for each task of $𝒯$ the constraint $𝚘𝚛𝚒𝚐𝚒𝚗 + 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 = 𝚎𝚗𝚍$ .

Example

(\begin{matrix} 〈\begin{matrix} 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 1 & 𝚘𝚛𝚒𝚐𝚒𝚗 - 1 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 3 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 1 & 𝚘𝚛𝚒𝚐𝚒𝚗 - 2 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 & 𝚎𝚗𝚍 - 5 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 1 & 𝚘𝚛𝚒𝚐𝚒𝚗 - 5 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 7 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 2 & 𝚘𝚛𝚒𝚐𝚒𝚗 - 3 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 5 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 2 & 𝚘𝚛𝚒𝚐𝚒𝚗 - 6 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 & 𝚎𝚗𝚍 - 9 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1 \end{matrix}〉, \\ 〈𝚒𝚍 - 1 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 - 2, 𝚒𝚍 - 2 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 - 3〉 \end{matrix})

Figure 5.100.1 shows the cumulated profile associated with both levels of priority. To each task of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint corresponds a set of rectangles containing the same number (i.e., the position of the task within the $𝚃𝙰𝚂𝙺𝚂$ collection): the sum of the lengths of the rectangles corresponds to the duration of the task, while the height of the rectangles (i.e., all the rectangles associated with a task have the same height) corresponds to the resource consumption of the task. Tasks that have a priority of 1 are coloured in pink, while tasks that have a priority of 2 are coloured in blue. The $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint holds since:

At each point in time the cumulated resource consumption profile of the tasks of priority 1 does not exceed the upper capacity 2 enforced by the first item of the $𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂$ collection.
At each point in time the cumulated resource consumption profile of the tasks of priority 1 and 2 does not exceed the upper capacity 3 enforced by the second item of the $𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂$ collection.

Figure 5.100.1. Resource consumption profiles according to both levels of priority for the tasks of the Example slot

ctrs/cumulative_with_level_of_priority-1-tikz

Typical

| 𝚃𝙰𝚂𝙺𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝) > 1

𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 > 0

𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝 > 0

| 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 | > 1

𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 > 0

𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 <

𝚜𝚞𝚖

(𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝)

| 𝚃𝙰𝚂𝙺𝚂 | > | 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 |

Symmetries

Items of $𝚃𝙰𝚂𝙺𝚂$ are permutable.
$𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ can be increased to any value $\leq | 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 |$ .
$𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝$ can be decreased to any value $\geq 0$ .
One and the same constant can be added to the $𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚎𝚗𝚍$ attributes of all items of $𝚃𝙰𝚂𝙺𝚂$ .
$𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢$ can be increased.

Arg. properties

Contractible wrt. $𝚃𝙰𝚂𝙺𝚂$ .

Usage

The $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint was suggested by problems from the telecommunication area where one has to ensure different levels of quality of service. For this purpose the capacity of a transmission link is split so that a given percentage is reserved to each level. In addition we have that, if the capacities allocated to levels $1, 2, \dots, i$ is not completely used, then level $i + 1$ can use the corresponding spare capacity.

Remark

The $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint can be modelled by a conjunction of $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraints. As shown by the next example, the consistency for all variables of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraints does not implies consistency for the corresponding $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint. The following $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint

(\begin{matrix} 〈\begin{matrix} 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 1 & 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{1} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 1 & 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{2} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 - 2 & 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{3} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 1 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 3 \end{matrix}〉, \\ 〈\begin{matrix} 𝚒𝚍 - 1 & 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 - 2, \\ 𝚒𝚍 - 2 & 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 - 3 \end{matrix}〉 \end{matrix})

where the domains of $o_{1}$ , $o_{2}$ and $o_{3}$ are respectively equal to ${1, 2, 3}$ , ${1, 2, 3}$ and ${1, 2, 3, 4}$ corresponds to the following conjunction of $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraints

𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎 (\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{1} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{2} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1 \end{matrix}〉, 2 \end{matrix})

𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎 (\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{1} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{2} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - o_{3} & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 1 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 3 \end{matrix}〉, 3 \end{matrix})

Even if the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint could achieve arc-consistency, the previous conjunction of $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraints would not detect the fact that there is no solution.

used in graph description: $𝚜𝚞𝚖_𝚌𝚝𝚛$ .

Keywords

characteristic of a constraint: derived collection.

constraint type: scheduling constraint, resource constraint, temporal constraint.

modelling: zero-duration task.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝚃𝙸𝙼𝙴_𝙿𝙾𝙸𝙽𝚃𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (\begin{matrix} 𝚒𝚍𝚙 - 𝚒𝚗𝚝, \\ 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, \\ 𝚙𝚘𝚒𝚗𝚝 - 𝚍𝚟𝚊𝚛 \end{matrix}), \\ [\begin{matrix} 𝚒𝚝𝚎𝚖 (\begin{matrix} 𝚒𝚍𝚙 - 𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢, \\ 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, \\ 𝚙𝚘𝚒𝚗𝚝 - 𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗 \end{matrix}), \\ 𝚒𝚝𝚎𝚖 (\begin{matrix} 𝚒𝚍𝚙 - 𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢, \\ 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, \\ 𝚙𝚘𝚒𝚗𝚝 - 𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍 \end{matrix}) \end{matrix}] \end{matrix})

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂$

Arc generator

𝑆𝐸𝐿𝐹

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚝𝚊𝚜𝚔𝚜)

Arc arity

Arc constraint(s)

𝚝𝚊𝚜𝚔𝚜 . 𝚘𝚛𝚒𝚐𝚒𝚗 + 𝚝𝚊𝚜𝚔𝚜 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 = 𝚝𝚊𝚜𝚔𝚜 . 𝚎𝚗𝚍

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚃𝙰𝚂𝙺𝚂 |

For all items of $𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂$ :

Arc input(s)

$𝚃𝙸𝙼𝙴_𝙿𝙾𝙸𝙽𝚃𝚂$ $𝚃𝙰𝚂𝙺𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜, 𝚝𝚊𝚜𝚔𝚜)

Arc arity

Arc constraint(s)

• 𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚒𝚍𝚙 = 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚒𝚍

• 𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚒𝚍𝚙 \geq 𝚝𝚊𝚜𝚔𝚜 . 𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢

• 𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 > 0

• 𝚝𝚊𝚜𝚔𝚜 . 𝚘𝚛𝚒𝚐𝚒𝚗 \leq 𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚙𝚘𝚒𝚗𝚝

• 𝚝𝚒𝚖𝚎_𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚙𝚘𝚒𝚗𝚝 < 𝚝𝚊𝚜𝚔𝚜 . 𝚎𝚗𝚍

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Sets

\begin{matrix} 𝖲𝖴𝖢𝖢 \mapsto \\ [\begin{matrix} 𝚜𝚘𝚞𝚛𝚌𝚎, \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 - 𝚌𝚘𝚕 (\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚃𝙰𝚂𝙺𝚂 . 𝚑𝚎𝚒𝚐𝚑𝚝)] \end{matrix}) \end{matrix}] \end{matrix}

Constraint(s) on sets

𝚜𝚞𝚖_𝚌𝚝𝚛

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, \leq, 𝙿𝚁𝙸𝙾𝚁𝙸𝚃𝙸𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢)

Graph model

Within the context of the second graph constraint, part (A) of Figure 5.100.2 shows the initial graphs associated with priorities 1 and 2 of the Example slot. Part (B) of Figure 5.100.2 shows the corresponding final graphs associated with priorities 1 and 2. On the one hand, each source vertex of the final graph can be interpreted as a time point $p$ . On the other hand the successors of a source vertex correspond to those tasks that both overlap that time point $p$ and have a priority less than or equal to a given level. The $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint holds since for each successor set $𝒮$ of the final graph the sum of the height of the tasks in $𝒮$ is less than or equal to the capacity associated with a given level of priority.

Figure 5.100.2. Initial and final graph of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint

(a)

(b)

Signature

Since $𝚃𝙰𝚂𝙺𝚂$ is the maximum number of vertices of the final graph of the first graph constraint we can rewrite $𝐍𝐀𝐑𝐂$ $=$ $| 𝚃𝙰𝚂𝙺𝚂 |$ to $𝐍𝐀𝐑𝐂$ $\geq$ $| 𝚃𝙰𝚂𝙺𝚂 |$ . This leads to simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.100. cumulative_with_level_of_priority

Figure 5.100.1. Resource consumption profiles according to both levels of priority for the tasks of the Example slot

Figure 5.100.2. Initial and final graph of the 𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢 constraint

Figure 5.100.2. Initial and final graph of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚠𝚒𝚝𝚑_𝚕𝚎𝚟𝚎𝚕_𝚘𝚏_𝚙𝚛𝚒𝚘𝚛𝚒𝚝𝚢$ constraint