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

modelling: 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 forces 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.

• Each task, whether it is resumable or not, is passed to the resource scheduling constraints as well as to the precedence constraints. In addition, we represent each non-crossable unavailability period as a fixed task that is also passed to the resource scheduling constraints.

• The $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ constraint ensures the link between variables (i.e., the start and the end of the tasks no matter whether they are resumable or not) expressed in these two coordinate systems with respect to the crossable unavailability periods.

We now provide the corresponding detailed model. Given:

1. A set of machines $ℳ=\left\{{m}_{1},{m}_{2},\cdots ,{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 $𝒯=\left\{{t}_{1},{t}_{2},\cdots ,{t}_{n}\right\}$, where each task ${t}_{i}$ (with $i\in \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 ${\mathrm{𝑣𝑠}}_{i}$ gives the start of task ${t}_{i}$ in the virtual coordinate system.

4. The virtual duration ${\mathrm{𝑣𝑑}}_{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{𝑣𝑒}}_{i}$ provides the end of task ${t}_{i}$ in the virtual coordinate system. We have that ${\mathrm{𝑣𝑠}}_{i}+{\mathrm{𝑣𝑑}}_{i}={\mathrm{𝑣𝑒}}_{i}$.

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

7. The real duration ${\mathrm{𝑟𝑑}}_{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{𝑟𝑑}}_{i}={\mathrm{𝑣𝑑}}_{i}$).

8. The real end ${\mathrm{𝑟𝑒}}_{i}$ indicates the end of task ${t}_{i}$ in the real coordinate system. We have that ${\mathrm{𝑟𝑠}}_{i}+{\mathrm{𝑟𝑑}}_{i}={\mathrm{𝑟𝑒}}_{i}$.

The link between the virtual starts (respectively virtual ends) and the real starts (respectively real ends) of the different tasks of $𝒯$ is ensured by a $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$$\left(\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂},\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}\right)$ constraint. More precisely, for each task ${t}_{i}$ (with $i\in \left[1,n\right]$), no matter whether it is resumable or not, we create the following items for the collection $\mathrm{𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$:

$\begin{array}{c}〈\begin{array}{cccc}\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}-{m}_{i}\hfill & \mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}-{\mathrm{𝑣𝑠}}_{i}\hfill & \mathrm{𝚒𝚛𝚎𝚊𝚕}-{\mathrm{𝑟𝑠}}_{i}\hfill & \mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}-0\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cccc}\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}-{m}_{i}\hfill & \mathrm{𝚟𝚒𝚛𝚝𝚞𝚊𝚕}-{\mathrm{𝑣𝑒}}_{i}\hfill & \mathrm{𝚒𝚛𝚎𝚊𝚕}-{\mathrm{𝑟𝑒}}_{i}\hfill & \mathrm{𝚏𝚕𝚊𝚐𝚎𝚗𝚍}-1\hfill \end{array}〉.\hfill \end{array}$

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\in \left[1,p\right]$) and its corresponding list of crossable unavailability periods, denoted $\mathrm{𝑐𝑟𝑜𝑠𝑠𝑎𝑏𝑙𝑒}_{\mathrm{𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦}}_{i}$, we create the following item of the collection $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$:

$\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚍}-i\hfill & \mathrm{𝚌𝚊𝚕}-\mathrm{𝑐𝑟𝑜𝑠𝑠𝑎𝑏𝑙𝑒}_{\mathrm{𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦}}_{i}\hfill \end{array}〉.\hfill \end{array}$

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{𝚐𝚎𝚘𝚜𝚝}$$\left(2,\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂},\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}\right)$ constraint. For each task ${t}_{i}$ (with $i\in \left[1,n\right]$) we create one item for the $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}$ collection as well as one item for the $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}$ collection:

$\begin{array}{c}〈\begin{array}{ccc}\mathrm{𝚘𝚒𝚍}-i\hfill & \mathrm{𝚜𝚒𝚍}-i\hfill & 𝚡-〈{m}_{i},{\mathrm{𝑣𝑠}}_{i}〉\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚜𝚒𝚍}-i\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈1,{\mathrm{𝑣𝑑}}_{i}〉\hfill \end{array}〉.\hfill \end{array}$

The first item corresponds to an object with $i$ as unique identifier, with a rectangular shape identifier $i$ and with ${m}_{i},{\mathrm{𝑣𝑠}}_{i}$ as the coordinates of its lower left corner. The second item corresponds to a rectangular shape with $i$ as unique identifier, $〈0,0〉$ as shift offset with respect to its lower left corner, and $〈1,{\mathrm{𝑣𝑑}}_{i}〉$ as the sizes of the rectangular shape.

Similarly, to express 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{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}$ collection as well as one item for the $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}$ collection:

$\begin{array}{c}〈\begin{array}{ccc}\mathrm{𝚘𝚒𝚍}-n+i\hfill & \mathrm{𝚜𝚒𝚍}-n+i\hfill & 𝚡-〈{r}_{i},{s}_{i}〉\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚜𝚒𝚍}-n+i\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈1,{e}_{i}-{s}_{i}+1〉\hfill \end{array}〉.\hfill \end{array}$

Finally, a precedence constraint between two distinct tasks ${t}_{i}$ and ${t}_{j}$ (with $i,j\in \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 ${\mathrm{𝑟𝑒}}_{i}\le {\mathrm{𝑟𝑠}}_{j}$. Figure 3.7.60 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 a single non-crossable unavailability corresponding to interval $\left[6,8\right]$.

• Machine ${m}_{4}$ has a 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 cpu time is donated for performing huge tasks, machines are typically partially available