Modeling Sequence-Dependent Setup Times

Hello! Welcome back.

In our previous lesson, we established the critical distinction between sequence-independent and sequence-dependent setup times. We concluded that sequence-dependent setups ( $S T_{s d}$ ) pose a significant modeling challenge because the time required for a setup, $s_{ij}$ , depends on the specific sequence of jobs $(i, j)$ .

Today, we will tackle that challenge directly. Our learning outcome is to incorporate sequence-dependent setup times into disjunctive graph and MILP models. This is a fundamental skill for your thesis work, as it allows you to build mathematical models that accurately reflect the complexities of many real-world flexible job shop environments.

Let's begin by revisiting the graphical representation of scheduling problems.

1. Modeling SDST in Disjunctive Graphs

In Module 5, you learned to represent a job shop problem using a disjunctive graph. As a quick refresher:

Nodes represent the operations.
Conjunctive (solid) arcs connect operations of the same job, representing the fixed technological sequence. The weight of an arc from operation $u$ to $v$ is the processing time of $u$ , $p_{u}$ .
Disjunctive (dashed) arcs connect operations that compete for the same machine. For any two operations $u$ and $v$ on the same machine, there's a pair of arcs: one from $u$ to $v$ and one from $v$ to $u$ .
Solving the problem is equivalent to selecting one arc from each disjunctive pair to create a directed acyclic graph (DAG). The makespan is the length of the longest path in this resulting DAG.

Disjunctive Graph Visualization: Example — A typical disjunctive graph for a job shop problem. Black arrows are conjunctive arcs (within-job precedence), and red arrows represent disjunctive arcs (on-machine choices). The goal is to select one direction for each pair of red arrows to minimize the longest path from S to T.

Now, how do we introduce sequence-dependent setup times, $s_{uv}$ ?

In a standard JSP model, the time between two consecutive operations $u$ and $v$ on a machine is simply the processing time of the first, $p_{u}$ . The start time of $v$ must be after the completion time of $u$ : $S_{v} \geq S_{u} + p_{u}$ . This is what the arc weight of $p_{u}$ represents.

With SDST, if $u$ is followed by $v$ , the constraint becomes more stringent: the machine is occupied for $p_{u}$ and then for the setup $s_{uv}$ . Therefore, operation $v$ cannot start until after $u$ is processed and the setup is complete.

$S_{v} \geq S_{u} + p_{u} + s_{uv}$

To model this in the disjunctive graph, we modify the meaning of the disjunctive arcs. When we decide to sequence operation $u$ before $v$ on a machine, we add a directed arc from $u$ to $v$ with a weight of $p_{u} + s_{uv}$ .

This is a crucial change. The "cost" of a sequence is no longer just the processing time but includes the setup time that depends on the chosen predecessor.

To learn more about this formal representation, we can look at a paper that models this exact problem.

Job shop scheduling with setup times and maximal time-lags

The paper 'Job shop scheduling with setup times and maximal time-lags' by Laborie provides a formal definition of the Job Shop Problem with Sequence-Dependent Setup Times (SDST-JSP) and its constraints. It clearly shows how the standard disjunctive constraints are modified.

Please read section '3.1 Job Shop Scheduling Problem with Sequence Dependent Setup-times' and the 'Specific Implementation Choices' subsection within it. Focus on constraint (3.3) and the disjunctive constraint formulation that follows. Notice how they explicitly add the setup time si,j into the standard disjunctive logic.

As the paper shows, the standard disjunction $S_{v} \geq C_{u} \lor S_{u} \geq C_{v}$ becomes $S_{v} \geq C_{u} + s_{uv} \lor S_{u} \geq C_{v} + s_{v u}$ . Finding the optimal sequence now involves choosing disjunctions that minimize the longest path in a graph where arc weights are sequence-dependent.

2. Modeling SDST in a Mixed-Integer Linear Program (MILP)

For your thesis, formulating a MILP model is a powerful and common approach. Let's extend the standard FJSP MILP to include sequence-dependent setup times.

First, let's define our key decision variables for a pair of operations, $u$ and $v$ , that could potentially be scheduled on the same machine $k$ :

$S_{u}, S_{v}$ : Continuous variables for the start times of operations $u$ and $v$ .
$y_{u k}$ : Binary variable, 1 if operation $u$ is assigned to machine $k$ , 0 otherwise.
$z_{uv}$ : Binary variable, 1 if operation $u$ is scheduled immediately before operation $v$ on the same machine, 0 otherwise. (Note: some models define this as $u$ anytime before $v$ , but for setups, an immediate successor formulation is often used).

Our goal is to modify the "no-overlap" constraints. For any two operations $u$ and $v$ assigned to the same machine $k$ , one of the following must hold:

$u$ comes before $v$ : $S_{v} \geq S_{u} + p_{u} + s_{uv}$
$v$ comes before $u$ : $S_{u} \geq S_{v} + p_{v} + s_{v u}$

We can enforce this logic using the "big-M" method. Let's assume for simplicity a model where $z_{uv k}$ is 1 if $u$ precedes $v$ (not necessarily immediately) on machine $k$ .

For every pair of operations $(u, v)$ that can be processed on the same machine $k$ :

$S_{v} \geq S_{u} + p_{u} + s_{uv} - M \cdot (3 - y_{u k} - y_{v k} - z_{uv k})$
$S_{u} \geq S_{v} + p_{v} + s_{v u} - M \cdot (2 + y_{u k} + y_{v k} - z_{uv k})$
... wait, that's not quite right. A cleaner way to write this is:

$S_{v} \geq S_{u} + p_{u} + s_{uv} - M \cdot (3 - y_{u k} - y_{v k} - z_{uv k})$
$S_{u} \geq S_{v} + p_{v} + s_{v u} - M \cdot (z_{uv k} + 2 - y_{u k} - y_{v k})$

A more standard and easier-to-read formulation uses two constraints per pair of operations $(u, v)$ that could conflict on a machine $k$ :

If $u$ precedes $v$ on machine $k$ :
$S_{v} \geq S_{u} + p_{u} + s_{uv} - M \cdot (3 - y_{u k} - y_{v k} - z_{uv k})$
If $u$ is on $k$ ( $y_{u k} = 1$ ), $v$ is on $k$ ( $y_{v k} = 1$ ), and $u$ precedes $v$ ( $z_{uv k} = 1$ ), the big-M term becomes $M \cdot (3 - 1 - 1 - 1) = 0$ , and the constraint is active: $S_{v} \geq S_{u} + p_{u} + s_{uv}$ . In all other cases (e.g., different machines, different order), the constraint is relaxed.
If $v$ precedes $u$ on machine $k$ :
$S_{u} \geq S_{v} + p_{v} + s_{v u} - M \cdot (3 - y_{u k} - y_{v k} - (1 - z_{uv k}))$
Here, if $u$ and $v$ are on machine $k$ and $v$ precedes $u$ ( $z_{uv k} = 0$ ), the big-M term becomes $M \cdot (3 - 1 - 1 - (1 - 0)) = 0$ , and the constraint is active: $S_{u} \geq S_{v} + p_{v} + s_{v u}$ .

This pair of constraints ensures that for any two jobs competing for a machine, their processing intervals are separated by the required sequence-dependent setup time.

The following research paper provides a full MILP formulation for an FJSP with sequence-dependent setup and transport times. While the notation is dense, it implements the exact logic we just discussed.

Flexible job shop scheduling problem with sequence- ...

The paper 'Flexible job shop scheduling problem with sequence-dependent...' by Varone et al. presents a complete MILP model for a complex FJSP. It's an excellent example of how these constraints are formulated in academic literature.

Please review section 'III. MODEL', focusing on the subsection '4) No conflict on the same machine'. Try to map their constraints back to the logic we just discussed. xj1,Oj1,l1 is a start time, p is processing time, prepT is the setup time, y is the machine assignment variable, and z (or pred in their text) is the sequencing variable. Don't worry about memorizing the exact syntax, but focus on recognizing the pattern.

The model in the paper demonstrates that while the core idea is simple (add $s_{ij}$ to the precedence constraint), the full formulation for a flexible shop requires careful handling of assignment and sequencing variables simultaneously.

Gantt Charts Illustrating Different Production Schedules and Makespans — These Gantt charts visualize the output of such complex models. The white blocks represent the setup times ($s_{ij}$) we have just modeled. The objective of the MILP would be to find an assignment and sequence (a schedule) that minimizes a certain objective, like the makespan shown in each chart.

Test your understanding!

Consider a simple problem with two jobs, J1 and J2, on a single machine, M1.

J1 has one operation, O1, with processing time $p_{1} = 10$ .
J2 has one operation, O2, with processing time $p_{2} = 8$ .

The sequence-dependent setup times are:

Setup from an idle machine to O1: $s_{01} = 2$
Setup from an idle machine to O2: $s_{02} = 3$
Setup from O1 to O2: $s_{12} = 5$
Setup from O2 to O1: $s_{21} = 4$

Disjunctive Graph:
- What would be the weight of the directed arc from O1 to O2 in the disjunctive graph?
- What would be the makespan if you choose the sequence O1 $\to$ O2?
- What would be the makespan if you choose the sequence O2 $\to$ O1?
MILP Formulation:
- Let $S_{1}$ and $S_{2}$ be the start times. Let $z_{12}$ be a binary variable that is 1 if O1 precedes O2, and 0 otherwise.
- Write the two big-M constraints that model the disjunction for this single-machine case. (Since it's a single machine, you don't need the $y_{u k}$ assignment variables).

Show answer

Disjunctive Graph Answers:
- The weight of the arc from O1 to O2 is $p_{1} + s_{12} = 10 + 5 = 15$ .
- Sequence O1 $\to$ O2: Makespan = (Setup to O1) + (Process O1) + (Setup to O2) + (Process O2) = $s_{01} + p_{1} + s_{12} + p_{2} = 2 + 10 + 5 + 8 = 25$ .
- Sequence O2 $\to$ O1: Makespan = (Setup to O2) + (Process O2) + (Setup to O1) + (Process O1) = $s_{02} + p_{2} + s_{21} + p_{1} = 3 + 8 + 4 + 10 = 25$ .
- In this specific case, both sequences result in the same makespan. In more complex problems, this is rarely the case.
MILP Formulation Answers:
Let M be a large number.
The two constraints are:
- $S_{2} \geq S_{1} + p_{1} + s_{12} - M \cdot (1 - z_{12})$
  $⟹ S_{2} \geq S_{1} + 10 + 5 - M \cdot (1 - z_{12})$
  If $z_{12} = 1$ , this becomes $S_{2} \geq S_{1} + 15$ . If $z_{12} = 0$ , it's relaxed.
- $S_{1} \geq S_{2} + p_{2} + s_{21} - M \cdot z_{12}$
  $⟹ S_{1} \geq S_{2} + 8 + 4 - M \cdot z_{12}$
  If $z_{12} = 0$ , this becomes $S_{1} \geq S_{2} + 12$ . If $z_{12} = 1$ , it's relaxed.

Conclusion

You have now learned how to integrate one of the most common real-world complexities—sequence-dependent setup times—into both graphical and mathematical scheduling models.

Key Takeaways:

Disjunctive Graph: SDST are modeled by adding the setup time $s_{uv}$ to the processing time $p_{u}$ as the weight of the selected directed disjunctive arc from $u$ to $v$ .
MILP Model: SDST are incorporated by modifying the big-M "no-overlap" constraints. The relevant setup time $s_{uv}$ is added to the right-hand side of the inequality that is activated by the sequencing variable $z_{uv}$ .
These modeling techniques are essential for capturing the true cost of a given sequence and are foundational for building the sophisticated models required for your thesis.

Preview of the Next Lesson:

We have successfully modeled setups that occur on a machine. But what happens between machines? In many modern facilities, jobs don't teleport instantly. They are moved by vehicles like AGVs or conveyors. Our next lesson will address this by showing you how to define transport constraints and model transport resources, adding another critical layer of realism to our FJSP model.

Recommended resources

1. Modeling SDST in Disjunctive Graphs

2. Modeling SDST in a Mixed-Integer Linear Program (MILP)

Conclusion