### 3.7.213. Scheduling with machine choice, calendars and preemption

A set of constraints that can be used for modelling aΒ scheduling problem where:

• We have tasks that have both to be assigned to machine and time.

• Each task has a fixed duration.

• Machines can run at most one task at a given instant.

• Each machine has its own fixed unavailability periods (i.e.,Β a calendar of unavailability periods).

• AnΒ unavailability period that allows (respectively forbids) a task to be interrupted and resumed just after is calledΒ crossable (respectivelyΒ non -crossable). A task that can be (respectively cannot be) interrupted by a crossable unavailability period is calledΒ resumable (respectively non -resumable).

• We have a precedence constraint between specific pairs of tasks. Each precedence enforces the fact that a given task ends before the start of another given task.

This model illustrates the use of two time coordinates systems:

Consequently, each task has a start and an end that are expressed within the virtual coordinate system as well as within the real coordinate system.

We now provide the corresponding detailed model. Given:

1. A set of machines $\mathrm{\beta ³}=\left\{{m}_{1},{m}_{2},...,{m}_{p}\right\}$, where each machine has a list of fixed unavailability periods. An unavailability ${u}_{i}$ is defined by the following attributes:

1. The crossable flag ${c}_{i}$ tells whether unavailability ${u}_{i}$ is crossable (${c}_{i}=1$) or not (${c}_{i}=0$).

2. The machine ${r}_{i}$ indicates the machine (i.e.,Β a value in $\left[1,p\right]$) to which unavailability ${u}_{i}$ corresponds (i.e.,Β since different machines may have different unavailability periods).

3. The start ${s}_{i}$ of the unavailability ${u}_{i}$ which indicates the first unavailable timepoint of the unavailability.

4. The end ${e}_{i}$ of the unavailability ${u}_{i}$ which gives the last unavailable timepoint of the unavailability.

2. A set of tasks $\mathrm{\pi ―}=\left\{{t}_{1},{t}_{2},...,{t}_{n}\right\}$, where each task ${t}_{i}$ (with $i\beta \left[1,n\right]$) has the following attributes which are all domain variables except the resumable flag and the virtual duration:

1. The resumable flag ${r}_{i}$ tells whether task ${t}_{i}$ is resumable (${r}_{i}=1$) or not (${r}_{i}=0$).

2. The machine ${m}_{i}$ indicates the machine (i.e.,Β a value in $\left[1,p\right]$) to which task ${t}_{i}$ will be assigned.

3. The virtual start gives the start of task ${t}_{i}$ in the virtual coordinate system.

4. The virtual duration ${\mathrm{\pi £\pi }}_{i}$ corresponds to the duration of task ${t}_{i}$ without counting the eventual unavailability periods crossed by task ${t}_{i}$.

5. The virtual end ${\mathrm{\pi £\pi }}_{i}$ provides the end of task ${t}_{i}$ in the virtual coordinate system. We have that .

6. The real start gives the start of task ${t}_{i}$ in the real coordinate system.

7. The real duration ${\mathrm{\pi \pi }}_{i}$ corresponds to the duration of task ${t}_{i}$ including the eventual unavailability periods crossed by task ${t}_{i}$. When task ${t}_{i}$ is non -resumable (i.e.,Β ${r}_{i}=0$) its real duration is equal to its virtual duration (i.e.,Β ${\mathrm{\pi \pi }}_{i}={\mathrm{\pi £\pi }}_{i}$).

8. The real end ${\mathrm{\pi \pi }}_{i}$ indicates the end of task ${t}_{i}$ in the real coordinate system. We have that .

The link between the virtual starts (respectively virtual ends) and the real starts (respectively real ends) of the different tasks of $\mathrm{\pi ―}$ is ensured by a $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi ½\pi \pi \pi °\pi ½\pi \pi },\mathrm{\pi Ό\pi °\pi ²\pi ·\pi Έ\pi ½\pi ΄\pi }\right)$ constraint. More precisely, for each task ${t}_{i}$ (with $i\beta \left[1,n\right]$), no matter whether it is resumable or not, we create the following items for the collection $\mathrm{\pi Έ\pi ½\pi \pi \pi °\pi ½\pi \pi }$:

The first item links the virtual and the real start of task ${t}_{i}$, while the second item relates the virtual and real ends. For each machine ${m}_{i}$ (with $i\beta \left[1,p\right]$) and its corresponding list of crossable unavailability periods, denoted , we create the following item of the collection $\mathrm{\pi Ό\pi °\pi ²\pi ·\pi Έ\pi ½\pi ΄\pi }$:

To express the resource constraint, i.e.,Β the fact that two tasks assigned to the same machine should not overlap in time, we use a $\mathrm{\pi \pi \pi \pi \pi }$$\left(2,\mathrm{\pi Ύ\pi ±\pi Ή\pi ΄\pi ²\pi \pi },\mathrm{\pi \pi ±\pi Ύ\pi \pi ΄\pi }\right)$ constraint. For each task ${t}_{i}$ (with $i\beta \left[1,n\right]$) we create one item for the $\mathrm{\pi Ύ\pi ±\pi Ή\pi ΄\pi ²\pi \pi }$ collection as well as one item for the $\mathrm{\pi \pi ±\pi Ύ\pi \pi ΄\pi }$ collection:

The first item corresponds to an object with $i$ as unique identifier, with a rectangular shape identifier $i$ and with as the coordinates of its leftmost lower corner. The second item corresponds to a rectangular shape with $i$ as unique identifier, $\beta ©0,0\beta ͺ$ as shift offset with respect to its leftmost lower corner, and $\beta ©1,{\mathrm{\pi £\pi }}_{i}\beta ͺ$ as the sizes of the rectangular shape.

Similarly, to express the fact that each task does not overlap a non -crossable unavailability period, we create for each non -crossable unavailability period $i$ one item for the $\mathrm{\pi Ύ\pi ±\pi Ή\pi ΄\pi ²\pi \pi }$ collection as well as one item for the $\mathrm{\pi \pi ±\pi Ύ\pi \pi ΄\pi }$ collection:

$\begin{array}{c}β©\begin{array}{ccc}\mathrm{\pi \pi \pi }-n+i\hfill & \mathrm{\pi \pi \pi }-n+i\hfill & \mathrm{\pi ‘}-\beta ©{r}_{i},{s}_{i}\beta ͺ\hfill \end{array}βͺ,\hfill \\ β©\begin{array}{ccc}\mathrm{\pi \pi \pi }-n+i\hfill & \mathrm{\pi }-\beta ©0,0\beta ͺ\hfill & \mathrm{\pi }-\beta ©1,{e}_{i}-{s}_{i}+1\beta ͺ\hfill \end{array}βͺ.\hfill \end{array}$

Finally, a precedence constraint between two distinct tasks ${t}_{i}$ and ${t}_{j}$ (with $i,j\beta \left[1,n\right]$) is modelled by an inequality constraint between the real end of task ${t}_{i}$ and the real start of task ${t}_{j}$, namely . FigureΒ 3.7.48 provides a toy example of such problem with:

• Four machines, numbered from 1 to 4, where:

• Machine ${m}_{1}$ has two crossable unavailability periods respectively corresponding to intervals $\left[2,2\right]$ and $\left[6,7\right]$.

• Machine ${m}_{2}$ has two crossable unavailability periods respectively corresponding to intervals $\left[2,2\right]$ and $\left[6,7\right]$, as well as one non -crossable unavailability period corresponding to interval $\left[3,3\right]$.

• Machine ${m}_{3}$ has one single non -crossable unavailability corresponding to interval $\left[6,8\right]$.

• Machine ${m}_{4}$ has one single crossable unavailability period corresponding to interval $\left[3,4\right]$.

• Five tasks, numbered from 1 to 5, where:

• Task ${t}_{1}$ is a non -resumable task that has a virtual duration of 3.

• Task ${t}_{2}$ is a resumable task that has a virtual duration of 2.

• Task ${t}_{3}$ is a non -resumable task that has a virtual duration of 3.

• Task ${t}_{4}$ is a resumable task that has a virtual duration of 5.

• Task ${t}_{5}$ is a resumable task that has a virtual duration of 2.

• Finally, (1)Β all five tasks should not overlap, (2)Β task ${t}_{3}$ should precedes task ${t}_{2}$ and (3)Β task ${t}_{1}$ should precedes task ${t}_{5}$.

A survey on machine scheduling problems with unavailability constraints both in the deterministic and stochastic cases can be found inΒ [SaidyTaghaviFard08]. Unavailability can have multiple causes such as:

• In the context of production scheduling, machine unavailability corresponds to accepted orders that were already scheduled for a given date. This can typically corresponds to unavailability periods at the beginning of the planning horizon. Preemptive maintenance can also be another cause of machine unavailability.

• In the context of timetabling, unavailability periods may come from work regulation which enforces not to work in a continuous way more than a given limit. Unavailability periods may also come from scheduled meetings during the working day.

• In the context of distributed computing where cputime is donated for performing huge tasks, machines are typically partially availableΒ