[BeldiceanuR00]

$\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}(\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂},\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂})$

Figure 5.45.1 illustrates the example. It present four machines with their respective unavailability periods (in grey) as well as four tasks (in blue and pink). Each item of the $\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ collection corresponds to the start or to the end of one of the previous four tasks. The $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint holds since:

• The real date 3 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[1\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=3$) associated with the start ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[1\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=0$) of task (a) in the universal time corresponds to the virtual date 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[1\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=2$) on machine 1 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[1\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=1$).

• The real date 6 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[2\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=6$) associated with the end ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[2\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=1$) of task (a) in the universal time corresponds to the virtual date 5 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[2\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=5$) on machine 1 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[2\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=1$).

• The real date 5 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[3\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=5$) associated with the start ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[3\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=0$) of task (b) in the universal time corresponds to the virtual date 4 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[3\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=4$) on machine 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[3\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=2$).

• The real date 9 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[4\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=9$) associated with the end ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[4\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=1$) of task (b) in the universal time corresponds to the virtual date 6 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[4\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=6$) on machine 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[4\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=2$).

• The real date 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[5\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=2$) associated with the start ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[5\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=0$) of task (c) in the universal time corresponds to the virtual date 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[5\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=2$) on machine 3 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[5\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=3$).

• The real date 5 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[6\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=5$) associated with the end ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[6\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=1$) of task (c) in the universal time corresponds to the virtual date 5 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[6\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=5$) on machine 3 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[6\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=3$).

• The real date 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[7\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=2$) associated with the start ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[7\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=0$) of task (d) in the universal time corresponds to the virtual date 2 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[7\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=2$) on machine 4 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[7\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=4$).

• The real date 9 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[8\right].\mathrm{𝚒𝚛𝚎𝚊𝚕}=9$) associated with the end ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[8\right].\mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}=1$) of task (d) in the universal time corresponds to the virtual date 7 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[8\right].\mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}=7$) on machine 4 ($\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}\left[8\right].\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}=4$).

Figure 5.45.1. Four machines with their unavailability periods as well as four tasks assigned to these machines (virtual dates mentioned in the Example slot use a bold font)

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

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

The $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint is used as a channelling constraint in resource scheduling problems where resources have unavailability periods that can preempt the execution of a task. In this context two time coordinates systems are used:

• A first coordinate system, so called the virtual coordinate system, ignores all unavailability periods on the different resources. All resource constraints are stated within this virtual coordinate system.

• A second coordinate system, so called the real coordinate system, corresponds to the real time. All temporal constraints (e.g., precedence constraints) are stated within this real coordinate system.

In this context, each task has a virtual origin, a virtual duration, a virtual end, a real origin, a real duration, a real end and the $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint links together the virtual origin and the real origin as well as the virtual end and the real end. The virtual duration (i.e., the real duration plus the sum of the unavailability periods crossed by the task) is linked to the virtual end and the virtual origin through an equality constraint on the difference between the virtual end and the virtual origin. The real duration is linked in a similar way to the real end and the real origin. The keyword scheduling with machine choice, calendars and preemption provides a concrete example of resource scheduling problem using the $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint.

The $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint can be reformulated into two generalised $\mathrm{𝚌𝚊𝚜𝚎}$ constraints (i.e., two $\mathrm{𝚌𝚊𝚜𝚎}$ constraints augmented with linear constraints). Part (A) (respectively Part (B)) of Figure 5.45.2 provides the dag that allows mapping the virtual start and real start (respectively the virtual end and real end) of a task. This dag can be computed directly from the arguments of the $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint:

1. We create an initial root node labelled by $m$ and we partition the set of machines into classes of consecutive machines that all share exactly the same unavailability periods. For each such class we create an arc from the root node to a new node $\mathrm{𝑣𝑠}$ labelled by the corresponding interval of consecutive machines identifiers. In Part (A) this corresponds to node $m$ and its three outgoing arcs respectively labelled by intervals $[1,2]$, $[3,3]$ and $[4,4]$.

2. For each class of consecutive machines found previously, we label in increasing order each timepoint that is not part of an unavailability period. We create an arc from the corresponding node $\mathrm{𝑣𝑠}$ for each maximum interval of available timepoints to a new node labelled by $\mathrm{𝑟𝑠}$. In Part (A) this translate to:

   • For the class corresponding to machines 1 and 2 we create three outgoing arcs labelled by the time intervals $[1,1]$, $[2,4]$ and $[5,6]$.

   • For the class corresponding to machine 3 we create the outgoing arc labelled by time interval $[1,9]$.

   • For the class corresponding to machine 4 we create the two outgoing arcs labelled by the time intervals $[1,2]$ and $[3,7]$.

3. For each class of consecutive machines and for each maximum interval $[i,j]$ of available timepoints previously computed, we find out the number of unavailable timepoints $b_i$ on the same class of machines that are located before the virtual coordinate $i$. We create an outgoing arc from the corresponding node $\mathrm{𝑟𝑠}$ to a new node labelled by $\mathrm{true}$ (there is one single $\mathrm{true}$ node for the full dag). This arc is labelled by the interval $[i+b_i,j+b_i]$ and by the linear constraint $r_s=v_s+b_i$. In Part (A) this translate to:

   • For the class corresponding to machines 1 and 2 and for each $r_s$ node associated with the time intervals $[1,1]$, $[2,4]$ and $[5,6]$ we respectively create an outgoing arc labelled by intervals $[1,1]$, $[3,5]$ and $[8,9]$. To each of these arcs we also respectively associate the linear constraints $r_s=v_s+0$ ($+0$ since on machines 1 and 2 there is no unavailability period before the virtual coordinate 1), $r_s=v_s+1$ ($+1$ since on machines 1 and 2 there is one single unavailable timepoint before the virtual coordinate 2) and $r_s=v_s+3$ ($+3$ since on machines 1 and 2 there is three unavailable timepoints before the virtual coordinate 5).

   • For the class corresponding to machine 3 and for the $r_s$ node associated with the time interval $[1,9]$ we create the outgoing arc labelled by time interval $[1,9]$ and by $r_s=v_s+0$ (i.e., since their is no unavailability period at all on machine 3).

   • For the class corresponding to machine 4 and for each $r_s$ node associated with the time intervals $[1,2]$ and $[3,7]$ we respectively create an outgoing arc labelled by $[1,2]$ and $[5,9]$. To each of these arcs we also respectively associate the linear constraints $r_s=v_s+0$ ($+0$ since on machine 4 there is no unavailability period before the virtual coordinate 1) and $r_s=v_s+2$ ($+2$ since on machine 4 there is two unavailable timepoints before the virtual coordinate 3).

Figure 5.45.2. The two generalised $\mathrm{𝚌𝚊𝚜𝚎}$ constraints for respectively mapping (1) the virtual start and real start of a task corresponding to the Example slot as well as (2) the virtual end and real end

common keyword: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ (scheduling constraint), $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$, $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ (scheduling with machine choice, calendars and preemption), $\mathrm{𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎}$ (scheduling constraint),

$\mathrm{𝚐𝚎𝚘𝚜𝚝}$ (scheduling with machine choice, calendars and preemption).

constraint type: predefined constraint, temporal constraint, scheduling constraint.

modelling: channelling constraint, scheduling with machine choice, calendars and preemption, assignment dimension.

modelling exercises: scheduling with machine choice, calendars and preemption.