### 3.7.219. Sequence dependent set-up

modelling: sequence dependent set-up Denotes that a constraint can be used for modelling sequence dependent set-up between pairs of tasks. Given,

• a collection of $n$ tasks $𝒯$, where each task ${t}_{i}\in 𝒯$ $\left(1\le i\le n\right)$ has an origin ${o}_{i}$, a duration ${d}_{i}$, an end ${e}_{i}$ $\left({o}_{i}+{d}_{i}={e}_{i}\right)$ and a machine ${m}_{i}$ to which it will be assigned,

• and a $n$ by $n$ matrix $ℳ$ of positive integers ${\delta }_{ij}$ $i,j\in \left[1,n\right]$ where ${\mathrm{𝑟𝑜𝑤}}_{i}$ denotes the ${i}^{th}$ row of matrix $ℳ$,

we want to express that ${\delta }_{ij}$ enforces a minimum distance between the completion of task ${t}_{i}\in 𝒯$ and the start of task ${t}_{j}\in 𝒯$ $\left(i\ne j\right)$ under the hypotheses that (a) both tasks are assigned the same machine (i.e., ${m}_{i}={m}_{j}$) and that (b) task ${t}_{j}$ immediately follows task ${t}_{i}$ (i.e., there is no task ${t}_{k}\in 𝒯$ $\left(k\notin \left\{i,j\right\}\right)$ such that ${m}_{k}={m}_{i}\wedge {e}_{i}\le {o}_{k}\wedge {e}_{k}\le {o}_{j}$). In addition, tasks assigned to the same machine should not overlap (i.e., $\forall i\in \left[1,n\right],\forall j\ne i\in \left[1,n\right]$ such that ${m}_{i}={m}_{j}$ we have ${e}_{i}\le {o}_{j}\vee {e}_{j}\le {o}_{i}$). We show how to model the previous sequence dependent set-up constraint under the hypothesis that we have a single machine. Without loss of generality we assume that ${\delta }_{ii}=0$ for all $i\in \left[1,n\right]$.

In a first phase we create for each task ${t}_{i}\in 𝒯$ $\left(1\le i\le n\right)$ three additional variables ${s}_{i}$, ${g}_{i}$ and ${c}_{i}$ that respectively correspond to:

• The successor variable ${s}_{i}\in \left[1,n\right]$ allows to get the immediate successor of task ${t}_{i}$. On the one hand, the assignment ${s}_{i}=i$ denotes that task ${t}_{i}$ has no immediate successor (i.e., task ${t}_{i}$ is the last task running on machine ${m}_{i}$), on the other hand, ${s}_{i}=j$ $\left(j\ne i\right)$ denotes that task ${t}_{j}$ is the immediate successor of task ${t}_{i}$.

• The gap variable ${g}_{i}$ represents the size of the gap between the end of task ${t}_{i}$ and the start of its immediate successor (the gap is equal to 0 when task ${t}_{i}$ has no immediate successor).

• The extended completion variable ${c}_{i}$ represents the sum of the end of task ${t}_{i}$ and the corresponding gap variable ${g}_{i}$ (i.e., ${c}_{i}={e}_{i}+{g}_{i}$).

In a second phase we post for each task ${t}_{i}\in 𝒯$ $\left(1\le i\le n\right)$ the following constraints:

Finally in a third phase we create a collection of nodes $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ where each item corresponds to a task ${t}_{i}\in 𝒯$ $\left(1\le i\le n\right)$ and has an $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute set to $i$, a $\mathrm{𝚜𝚞𝚌𝚌}$ attribute set to ${s}_{i}$, a $\mathrm{𝚜𝚝𝚊𝚛𝚝}$ attribute set to ${o}_{i}$ and an $\mathrm{𝚎𝚗𝚍}$ attribute set to ${c}_{i}$. We post a $\mathrm{𝚝𝚎𝚖𝚙𝚘𝚛𝚊𝚕}_\mathrm{𝚙𝚊𝚝𝚑}$$\left(1,\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$ constraint for linking the successor variables, the start variables and the extended completion variables associated with the different tasks. The first argument of the $\mathrm{𝚝𝚎𝚖𝚙𝚘𝚛𝚊𝚕}_\mathrm{𝚙𝚊𝚝𝚑}$ constraint forces a single path corresponding to the succession of the different tasks on the unique machine.