3.7.207. Sequence dependent set-up

Denotes the fact 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 βˆˆπ’― (1≀i≀n) has an origin o i , a duration d i , an end e i (o i +d i =e i ) and a machine m i to which it will be assigned,

  • and a n by n matrix β„³ of positive integers Ξ΄ ij i,j∈[1,n] where π‘Ÿπ‘œπ‘€ i denotes the i th row of matrix β„³,

we want to express the fact that Ξ΄ ij enforces a minimum distance between the completion of task t i βˆˆπ’― and the start of task t j βˆˆπ’― (iβ‰ j) 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 βˆˆπ’― (kβˆ‰{i,j}) such that m k =m i ∧e i ≀o k ∧e k ≀o j ). In addition, tasks assigned to the same machine should not overlap (i.e.,Β βˆ€i∈[1,n],βˆ€jβ‰ i∈[1,n] such that m i =m j we have e i ≀o j ∨e j ≀o i ). We show how to model the previous sequence dependent set -up constraint under the hypothesis that we have one single machine. Without loss of generality we assume that Ξ΄ ii =0 for all i∈[1,n].

In a first phase we create for each task t i βˆˆπ’― (1≀i≀n) three additional variables s i , g i and c i that respectively correspond to:

  • The successor variable s i ∈[1,n] allows to get the immediate successor of task t i . On the one hand, the assignment s i =i denotes the fact 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 (jβ‰ i) denotes the fact 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 βˆˆπ’― (1≀i≀n) the following constraints:

Finally in a third phase we create a collection of nodes π™½π™Ύπ™³π™΄πš‚ where each item corresponds to a task t i βˆˆπ’― (1≀i≀n) and has an πš’πš—πšπšŽπš‘ attribute set to i, a 𝚜𝚞𝚌𝚌 attribute set to s i , a πšœπšπšŠπš›πš attribute set to o i and an πšŽπš—πš attribute set to c i . We post a πšπšŽπš–πš™πš˜πš›πšŠπš•_πš™πšŠπšπš‘(1,π™½π™Ύπ™³π™΄πš‚) constraint for linking the successor variables, the start variables and the extended completion variables associated with the different tasks. The first argument of the πšπšŽπš–πš™πš˜πš›πšŠπš•_πš™πšŠπšπš‘ constraint enforces one single path corresponding to the succession of the different tasks on the unique machine.