Global Constraint Catalog: Ccoloured

5.74. coloured_cumulatives

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ and $𝚗𝚟𝚊𝚕𝚞𝚎𝚜$ .

Constraint

$𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜 (𝚃𝙰𝚂𝙺𝚂, 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂)$

Synonym

$𝚌𝚘𝚕𝚘𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ .

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝚂𝙺𝚂, [𝚖𝚊𝚌𝚑𝚒𝚗𝚎, 𝚌𝚘𝚕𝚘𝚞𝚛])

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

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

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

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂, [𝚒𝚍, 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢])

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂, 𝚒𝚍)

𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 \geq 0

Purpose

Consider a set $𝒯$ of tasks described by the $𝚃𝙰𝚂𝙺𝚂$ collection. The $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint forces for each machine $m$ of the $𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂$ collection the following condition: at each point in time $p$ , the numbers of distinct colours of the set of tasks that both overlap that point $p$ and are assigned to machine $m$ does not exceed the capacity of machine $m$ . 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$ . It also imposes for each task of $𝒯$ the constraint $𝚘𝚛𝚒𝚐𝚒𝚗 + 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 = 𝚎𝚗𝚍$ .

Example

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

Figure 5.74.1 shows the solution associated with the example. Each rectangle of the figure corresponds to a task of the $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint. Tasks that have their colour attribute set to 1 and 2 are respectively coloured in blue and pink. The $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint holds since for machine 1 we have at most two distinct colours in parallel (which is the maximum capacity for machine 1), while for machine 2 we have no more than a single colour in parallel (which is actually the maximum capacity for machine 2).

Figure 5.74.1. The coloured cumulative solution to the Example slot with at most two distinct colours in parallel on machine 1 and at most one distinct colour in parallel on machine 2

Typical

| 𝚃𝙰𝚂𝙺𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎) > 1

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚌𝚘𝚕𝚘𝚞𝚛) > 1

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

| 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 | > 1

𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 > 0

𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢 <

𝚗𝚟𝚊𝚕

(𝚃𝙰𝚂𝙺𝚂 . 𝚌𝚘𝚕𝚘𝚞𝚛)

| 𝚃𝙰𝚂𝙺𝚂 | > | 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 |

Symmetries

Items of $𝚃𝙰𝚂𝙺𝚂$ are permutable.
Items of $𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂$ are permutable.
$𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢$ can be increased.
All occurrences of two distinct values in $𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎$ or $𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚒𝚍$ can be swapped; all occurrences of a value in $𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎$ or $𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚒𝚍$ can be renamed to any unused value.

Arg. properties

Contractible wrt. $𝚃𝙰𝚂𝙺𝚂$ .

Usage

Useful for scheduling problems where several machines are available and where you have to assign each task to a specific machine. In addition each machine can only proceed in parallel a maximum number of tasks of distinct types.

Reformulation

The $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint can be expressed in term of a set of reified constraints and of $| 𝚃𝙰𝚂𝙺𝚂 |$ $𝚗𝚟𝚊𝚕𝚞𝚎$ constraints:

For each pair of tasks $𝚃𝙰𝚂𝙺𝚂 [i], 𝚃𝙰𝚂𝙺𝚂 [j]$ $(i, j \in [1, | 𝚃𝙰𝚂𝙺𝚂 |])$ of the $𝚃𝙰𝚂𝙺𝚂$ collection we create a variable $C_{i j}$ which is set to the colour of task $𝚃𝙰𝚂𝙺𝚂 [j]$ if both tasks are assigned to the same machine and if task $𝚃𝙰𝚂𝙺𝚂 [j]$ overlaps the origin attribute of task $𝚃𝙰𝚂𝙺𝚂 [i]$ , and to the colour of task $𝚃𝙰𝚂𝙺𝚂 [i]$ otherwise:
- If $i = j$ :
  - $C_{i j} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛$ .
- If $i \neq j$ :
  - $C_{i j} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛 \lor C_{i j} = 𝚃𝙰𝚂𝙺𝚂 [j] . 𝚌𝚘𝚕𝚘𝚞𝚛$ .
  - $((𝚃𝙰𝚂𝙺𝚂 [j] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 \land$
    
        $𝚃𝙰𝚂𝙺𝚂 [j] . 𝚘𝚛𝚒𝚐𝚒𝚗 \leq 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗 \land$
    
        $𝚃𝙰𝚂𝙺𝚂 [j] . 𝚎𝚗𝚍 > 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗) \land (C_{i j} = 𝚃𝙰𝚂𝙺𝚂 [j] . 𝚌𝚘𝚕𝚘𝚞𝚛)) \lor$
    
    $((𝚃𝙰𝚂𝙺𝚂 [j] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 \neq 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 \lor$
    
        $𝚃𝙰𝚂𝙺𝚂 [j] . 𝚘𝚛𝚒𝚐𝚒𝚗 > 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗 \lor$
    
        $𝚃𝙰𝚂𝙺𝚂 [j] . 𝚎𝚗𝚍 \leq 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗) \land (C_{i j} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛))$
For each task $𝚃𝙰𝚂𝙺𝚂 [i]$ $(i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |])$ we create a variable $N_{i}$ which gives the number of distinct colours associated with the tasks that both are assigned to the same machine as task $𝚃𝙰𝚂𝙺𝚂 [i]$ and overlap the origin of task $𝚃𝙰𝚂𝙺𝚂 [i]$ ( $𝚃𝙰𝚂𝙺𝚂 [i]$ overlaps its own origin) and we impose $N_{i}$ to not exceed the maximum number of distinct colours $𝙻𝙸𝙼𝙸𝚃$ allowed at each instant:
- $N_{i} \geq 1 \land N_{i} \leq 𝙻𝙸𝙼𝙸𝚃$ .
- $𝚗𝚟𝚊𝚕𝚞𝚎$ $(N_{i}, 〈 C_{i 1}, C_{i 2}, \dots, C_{i | 𝚃𝙰𝚂𝙺𝚂 |} 〉)$ .

See also

assignment dimension removed: $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ ( $𝚖𝚊𝚌𝚑𝚒𝚗𝚎$ attribute removed), $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ ( $𝚖𝚊𝚌𝚑𝚒𝚗𝚎$ attribute removed and number of distinct $𝚌𝚘𝚕𝚘𝚞𝚛𝚜$ replaced by sum of $𝚝𝚊𝚜𝚔$ $𝚑𝚎𝚒𝚐𝚑𝚝𝚜$ ).

common keyword: $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ , $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ (resource constraint).

related: $𝚗𝚟𝚊𝚕𝚞𝚎$ .

used in graph description: $𝚗𝚟𝚊𝚕𝚞𝚎𝚜$ .

Keywords

characteristic of a constraint: coloured.

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

filtering: compulsory part.

modelling: number of distinct values, assignment dimension, zero-duration task.

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚃𝙰𝚂𝙺𝚂 |

For all items of $𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂$ :

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂$ $𝚃𝙰𝚂𝙺𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

• 𝚝𝚊𝚜𝚔𝚜 1 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 = 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚒𝚍

• 𝚝𝚊𝚜𝚔𝚜 1 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 = 𝚝𝚊𝚜𝚔𝚜 2 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎

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

• 𝚝𝚊𝚜𝚔𝚜 2 . 𝚘𝚛𝚒𝚐𝚒𝚗 \leq 𝚝𝚊𝚜𝚔𝚜 1 . 𝚘𝚛𝚒𝚐𝚒𝚗

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

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Sets

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

Constraint(s) on sets

𝚗𝚟𝚊𝚕𝚞𝚎𝚜

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, \leq, 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂 . 𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢)

Graph model

Parts (A) and (B) of Figure 5.74.2 respectively shows the initial and final graph associated with machines 1 and 2 involved in the Example slot. On the one hand, each source vertex of the final graph can be interpreted as a time point $p$ on a specific machine $m$ . On the other hand the successors of a source vertex correspond to those tasks that both overlap that time point $p$ and are assigned to machine $m$ . The $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint holds since for each successor set $𝒮$ of the final graph the number of distinct colours in $𝒮$ does not exceed the capacity of the machine corresponding to the time point associated with $𝒮$ .

Figure 5.74.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.74. coloured_cumulatives

Figure 5.74.1. The coloured cumulative solution to the Example slot with at most two distinct colours in parallel on machine 1 and at most one distinct colour in parallel on machine 2

Figure 5.74.2. Initial and final graph of the 𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜 constraint

Figure 5.74.2. Initial and final graph of the $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint