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

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

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

Figure 5.61.1 shows the solution associated with the example. Each rectangle of the figure corresponds to a task of the $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ constraint. Tasks that have their colour attribute set to 1 and 2 are respectively coloured in blue and pink. The $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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 one single colour in parallel (which is actually the maximum capacity for machine 2).

Figure 5.61.1. Assignment of the tasks on the two machines

• Items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ are permutable.

• Items of $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$ are permutable.

• $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}.\mathrm{𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢}$ can be increased.

• All occurrences of two distinct values in $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ or $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}.\mathrm{𝚒𝚍}$ can be swapped; all occurrences of a value in $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ or $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}.\mathrm{𝚒𝚍}$ can be renamed to any unused value.

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.

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

1. For each pair of tasks $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right],\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right]$ $(i,j\in [1,\left|\mathrm{𝚃𝙰𝚂𝙺𝚂}\right|\left]\right)$ of the $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ collection we create a variable $C_{ij}$ which is set to the colour of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right]$ if both tasks are assigned to the same machine and if task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right]$ overlaps the origin attribute of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$, and to the colour of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ otherwise:

   • If $i=j$:

     • $C_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}$.

   • If $i\ne j$:

     • $C_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}\vee C_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}$.

     • $\left(\right(\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}\wedge$

          $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\le \mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\wedge$

          $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚎𝚗𝚍}>\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗})\wedge (C_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}))\vee$

       $\left(\right(\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}\ne \mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}\vee$

          $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}>\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\vee$

          $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚎𝚗𝚍}\le \mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗})\wedge (C_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}))$

2. For each task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ $(i\in [1,\left|\mathrm{𝚃𝙰𝚂𝙺𝚂}\right|\left]\right)$ we create a variable $N_i$ which gives the number of distinct colours associated to the tasks that both are assigned to the same machine as task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ and overlap the origin of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ ($\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ overlaps its own origin) and we impose $N_i$ to not exceed the maximum number of distinct colours $\mathrm{𝙻𝙸𝙼𝙸𝚃}$ allowed at each instant:

   • $N_i\ge 1\wedge N_i\le \mathrm{𝙻𝙸𝙼𝙸𝚃}$.

   • $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$(N_i,\langle C_{i1},C_{i2},...,C_{i\left|\mathrm{𝚃𝙰𝚂𝙺𝚂}\right|}\rangle )$.

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

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

related: $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

used in graph description: $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎𝚜}$.

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.

$\mathrm{𝚃𝙰𝚂𝙺𝚂}$

For all items of $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$:

$\mathrm{𝚃𝙰𝚂𝙺𝚂}$ $\mathrm{𝚃𝙰𝚂𝙺𝚂}$

Parts (A) and (B) of Figure 5.61.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 $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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.61.2. Initial and final graph of the $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ constraint

(a)

(b)

Since $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ is the maximum number of vertices of the final graph of the first graph constraint we can rewrite $\mathrm{𝐍𝐀𝐑𝐂}$ $=$ $\left|\mathrm{𝚃𝙰𝚂𝙺𝚂}\right|$ to $\mathrm{𝐍𝐀𝐑𝐂}$ $\ge$ $\left|\mathrm{𝚃𝙰𝚂𝙺𝚂}\right|$. This leads to simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.