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 tasks , where each task has an origin , a duration , an end and a machine to which it will be assigned,
and a by matrix of positive integers where denotes the row of matrix ,
we want to express that enforces a minimum distance between the completion of task and the start of task under the hypotheses that (a)Β both tasks are assigned the same machine (i.e.,Β ) and that (b)Β task immediately follows task (i.e., there is no task such that ). In addition, tasks assigned to the same machine should not overlap (i.e., such that we have ). 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 for all .
In a first phase we create for each task three additional variables , and that respectively correspond to:
The successor variable allows to get the immediate successor of task . On the one hand, the assignment denotes that task has no immediate successor (i.e., task is the last task running on machine ), on the other hand, denotes that task is the immediate successor of task .
The gap variable represents the size of the gap between the end of task and the start of its immediate successor (the gap is equal to 0 when task has no immediate successor).
The extended completion variable represents the sum of the end of task and the corresponding gap variable (i.e.,Β ).
In a second phase we post for each task the following constraints:
Finally in a third phase we create a collection of nodes where each item corresponds to a task and has an attribute set to , a attribute set to , a attribute set to and an attribute set to . We post a 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 forces a single path corresponding to the succession of the different tasks on the unique machine.