## 5.122. disj

Origin
Constraint

$\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi °\pi \pi Ί\pi }\right)$

Argument
 $\mathrm{\pi \pi °\pi \pi Ί\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi },\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi },\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi },\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\hfill \end{array}\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi °\pi \pi Ί\pi },\left[\mathrm{\pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi \pi °\pi \pi Ί\pi }.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta ₯1$ $\mathrm{\pi \pi °\pi \pi Ί\pi }.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta ₯0$ $\mathrm{\pi \pi °\pi \pi Ί\pi }.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }<|\mathrm{\pi \pi °\pi \pi Ί\pi }|$
Purpose

All the tasks of the collection $\mathrm{\pi \pi °\pi \pi Ί\pi }$ should not overlap. For a given task $t$ the attributes $\mathrm{\pi \pi \pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ respectively correspond to the set of tasks starting before task $t$ (assuming that the first task is labelled by 1) and to the position of task $t$ (assuming that the first task has position 0).

Example
$\left(\begin{array}{c}β©\begin{array}{cccc}\mathrm{\pi \pi \pi \pi \pi }-1\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-3\hfill & \mathrm{\pi \pi \pi \pi \pi \pi }-\mathrm{\beta  }\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-0,\hfill \\ \mathrm{\pi \pi \pi \pi \pi }-9\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-1\hfill & \mathrm{\pi \pi \pi \pi \pi \pi }-\left\{1,3,4\right\}\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi \pi \pi }-7\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-2\hfill & \mathrm{\pi \pi \pi \pi \pi \pi }-\left\{1,4\right\}\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-2,\hfill \\ \mathrm{\pi \pi \pi \pi \pi }-4\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-1\hfill & \mathrm{\pi \pi \pi \pi \pi \pi }-\left\{1\right\}\hfill & \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-1\hfill \end{array}βͺ\hfill \end{array}\right)$

FigureΒ 5.122.1 shows the tasks of the example. Since these tasks do not overlap the $\mathrm{\pi \pi \pi \pi }$ constraint holds.

Typical
$|\mathrm{\pi \pi °\pi \pi Ί\pi }|>1$
Symmetries
• One and the same constant can be added to the $\mathrm{\pi \pi \pi \pi \pi }$ attribute of all items of $\mathrm{\pi \pi °\pi \pi Ί\pi }$.

• $\mathrm{\pi \pi °\pi \pi Ί\pi }.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ can be decreased to any value $\beta ₯1$.

Usage

The $\mathrm{\pi \pi \pi \pi }$ constraint was originally appliedΒ [MonetteDevilleDupont07] to solve the open-shop problem.

Remark

This constraint is similar to the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. In addition to the $\mathrm{\pi \pi \pi \pi \pi }$ and the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ attributes of a task $t$, the $\mathrm{\pi \pi \pi \pi }$ constraint introduces a set variable $\mathrm{\pi \pi \pi \pi \pi \pi }$ that represents the set of tasks that end before the start of task $t$ as well as a domain variable $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ that gives the absolute order of task $t$ in the resource. Since it assumes that the first task has position 0 we have that, for a given task $t$, the number of elements of its $\mathrm{\pi \pi \pi \pi \pi \pi }$ attribute is equal to the value of its $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ attribute.

Algorithm

The main idea of the algorithm is to apply in a systematic way shaving on the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ attribute of a task. It is implemented in

Keywords
Arc input(s)

$\mathrm{\pi \pi °\pi \pi Ί\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$

Arc arity
Arc constraint(s)
 $\beta ’\beta \left(\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi },\hfill \\ \mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi }\hfill \end{array}\right)$ $\beta ’\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi }\beta \hfill \\ \mathrm{\pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi ’},\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi \pi }\right)\hfill \end{array}$ $\beta ’\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi }\beta \hfill \\ \mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }<\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\hfill \end{array}$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=|\mathrm{\pi \pi °\pi \pi Ί\pi }|*|\mathrm{\pi \pi °\pi \pi Ί\pi }|-|\mathrm{\pi \pi °\pi \pi Ί\pi }|$

Graph model

We generate a clique with a non-overlapping constraint between each pair of distinct tasks and state that the number of arcs of the final graph should be equal to the number of arcs of the initial graph. For two tasks ${t}_{1}$ and ${t}_{2}$, the three conditions of the arc constraint respectively correspond to:

• The fact that ${t}_{1}$ ends before the start of ${t}_{2}$ or that ${t}_{2}$ ends before the start of ${t}_{1}$.

• The equivalence between the fact that ${t}_{1}$ ends before the start of ${t}_{2}$ and the fact that the identifier of task ${t}_{1}$ belongs to the $\mathrm{\pi \pi \pi \pi \pi \pi }$ attribute of task ${t}_{2}$.

• The equivalence between the fact that ${t}_{1}$ ends before the start of ${t}_{2}$ and the fact that the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ attribute of task ${t}_{1}$ is strictly less than the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ attribute of task ${t}_{2}$.

PartsΒ (A) andΒ (B) of FigureΒ 5.122.2 respectively show the initial and final graph associated with the Example slot. The $\mathrm{\pi \pi \pi \pi }$ constraint holds since all the arcs of the initial graph belong to the final graph: all the non-overlapping constraints holds.