Global Constraint Catalog: Cdisjoint

5.125. disjoint_tasks

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ .

Constraint

$𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜 (𝚃𝙰𝚂𝙺𝚂 1, 𝚃𝙰𝚂𝙺𝚂 2)$

Arguments

$𝚃𝙰𝚂𝙺𝚂 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒𝚐𝚒𝚗 - 𝚍𝚟𝚊𝚛, 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛)$
$𝚃𝙰𝚂𝙺𝚂 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒𝚐𝚒𝚗 - 𝚍𝚟𝚊𝚛, 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛)$

Restrictions

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

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

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

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

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

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

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

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

Purpose

Each task of the collection $𝚃𝙰𝚂𝙺𝚂 1$ should not overlap any task of the collection $𝚃𝙰𝚂𝙺𝚂 2$ . Two tasks overlap if they have an intersection that is strictly greater than zero.

Example

(\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - 6 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 5 & 𝚎𝚗𝚍 - 11, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 8 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 10 \end{matrix}〉, \\ 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - 2 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 4, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 3 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 & 𝚎𝚗𝚍 - 6, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 12 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 1 & 𝚎𝚗𝚍 - 13 \end{matrix}〉 \end{matrix})

Figure 5.125.1 displays the two groups of tasks (i.e., the tasks of $𝚃𝙰𝚂𝙺𝚂 1$ and the tasks of $𝚃𝙰𝚂𝙺𝚂 2$ ). Since no task of the first group overlaps any task of the second group, the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ constraint holds.

Figure 5.125.1. The $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ solution to the Example slot with at most one distinct colour in parallel (tasks in $𝚃𝙰𝚂𝙺𝚂 1$ have the pink colour, while tasks in $𝚃𝙰𝚂𝙺𝚂 2$ have the blue colour)

Typical

| 𝚃𝙰𝚂𝙺𝚂 1 | > 1

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

| 𝚃𝙰𝚂𝙺𝚂 2 | > 1

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝚃𝙰𝚂𝙺𝚂 1, 𝚃𝙰𝚂𝙺𝚂 2)$ .
Items of $𝚃𝙰𝚂𝙺𝚂 1$ are permutable.
Items of $𝚃𝙰𝚂𝙺𝚂 2$ are permutable.
One and the same constant can be added to the $𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚎𝚗𝚍$ attributes of all items of $𝚃𝙰𝚂𝙺𝚂 1$ and $𝚃𝙰𝚂𝙺𝚂 2$ .

Arg. properties

Contractible wrt. $𝚃𝙰𝚂𝙺𝚂 1$ .
Contractible wrt. $𝚃𝙰𝚂𝙺𝚂 2$ .

Remark

Despite the fact that this is not an uncommon constraint, it cannot be modelled in a compact way with a single $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint. But it can be expressed by using the $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint: We assign a first colour to the tasks of $𝚃𝙰𝚂𝙺𝚂 1$ as well as a second distinct colour to the tasks of $𝚃𝙰𝚂𝙺𝚂 2$ . Finally we set up a limit of 1 for the maximum number of distinct colours allowed at each time point.

Reformulation

The $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ constraint can be expressed in term of $| 𝚃𝙰𝚂𝙺𝚂 1 | \cdot | 𝚃𝙰𝚂𝙺𝚂 2 |$ reified constraints. For each task $𝚃𝙰𝚂𝙺𝚂 1 [i]$ $(i \in [1, | 𝚃𝙰𝚂𝙺𝚂 1 |])$ and for each task $𝚃𝙰𝚂𝙺𝚂 2 [j]$ $(j \in [1, | 𝚃𝙰𝚂𝙺𝚂 2 |])$ we generate a reified constraint of the form $𝚃𝙰𝚂𝙺𝚂 1 [i] . 𝚎𝚗𝚍 \leq 𝚃𝙰𝚂𝙺𝚂 2 [j] . 𝚘𝚛𝚒𝚐𝚒𝚗 \lor 𝚃𝙰𝚂𝙺𝚂 2 [j] . 𝚎𝚗𝚍 \leq 𝚃𝙰𝚂𝙺𝚂 1 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗$ . In addition we also state for each task an arithmetic constraint that states that the end of a task is equal to the sum of its origin and its duration.

Systems

disjoint in Choco.

See also

generalisation: $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ (tasks colours and limit on maximum number of colours in parallel are explicitly given).

specialisation: $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ ( $𝚝𝚊𝚜𝚔$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

constraint type: scheduling constraint, temporal constraint.

geometry: non-overlapping.

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂 1$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚃𝙰𝚂𝙺𝚂 1 |

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂 2$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚃𝙰𝚂𝙺𝚂 2 |

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂 1$ $𝚃𝙰𝚂𝙺𝚂 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

• 𝚝𝚊𝚜𝚔𝚜 1 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 > 0

• 𝚝𝚊𝚜𝚔𝚜 2 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 > 0

• 𝚝𝚊𝚜𝚔𝚜 1 . 𝚘𝚛𝚒𝚐𝚒𝚗 < 𝚝𝚊𝚜𝚔𝚜 2 . 𝚎𝚗𝚍

• 𝚝𝚊𝚜𝚔𝚜 2 . 𝚘𝚛𝚒𝚐𝚒𝚗 < 𝚝𝚊𝚜𝚔𝚜 1 . 𝚎𝚗𝚍

Graph property(ies)

𝐍𝐀𝐑𝐂

= 0

Graph model

$𝑃𝑅𝑂𝐷𝑈𝐶𝑇$ is used in order to generate the arcs of the graph between all the tasks of the collection $𝚃𝙰𝚂𝙺𝚂 1$ and all tasks of the collection $𝚃𝙰𝚂𝙺𝚂 2$ . The first two graph constraints respectively enforce for each task of $𝚃𝙰𝚂𝙺𝚂 1$ and $𝚃𝙰𝚂𝙺𝚂 2$ the fact that the end of a task is equal to the sum of its origin and its duration. The arc constraint of the third graph constraint depicts the fact that two tasks overlap. Therefore, since we use the graph property $𝐍𝐀𝐑𝐂$ $=$ 0 the final graph associated with the third graph constraint will be empty and no task of $𝚃𝙰𝚂𝙺𝚂 1$ will overlap any task of $𝚃𝙰𝚂𝙺𝚂 2$ . Figure 5.125.2 shows the initial graph of the third graph constraint associated with the Example slot. Because of the graph property $𝐍𝐀𝐑𝐂$ $=$ 0 the corresponding final graph is empty.

Figure 5.125.2. Initial graph of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ constraint (the final graph is empty)

Signature

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

We can apply a similar remark for the second graph constraint.

Finally, since 0 is the smallest number of arcs of the final graph we can rewrite $𝐍𝐀𝐑𝐂$ $=$ 0 to $𝐍𝐀𝐑𝐂$ $\leq$ 0. This leads to simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\underset{̲}{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.125. disjoint_tasks

Figure 5.125.1. The 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜 solution to the Example slot with at most one distinct colour in parallel (tasks in 𝚃𝙰𝚂𝙺𝚂1 have the pink colour, while tasks in 𝚃𝙰𝚂𝙺𝚂2 have the blue colour)

Figure 5.125.2. Initial graph of the 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜 constraint (the final graph is empty)

Figure 5.125.1. The $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ solution to the Example slot with at most one distinct colour in parallel (tasks in $𝚃𝙰𝚂𝙺𝚂 1$ have the pink colour, while tasks in $𝚃𝙰𝚂𝙺𝚂 2$ have the blue colour)

Figure 5.125.2. Initial graph of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚝𝚊𝚜𝚔𝚜$ constraint (the final graph is empty)