FJSP as a MILP Model

From Physical System to Mathematical Model

Before we dive into the equations, let's establish a clear framework for what a MILP model entails. We are essentially creating a mathematical representation of the physical job shop system.

To build the model, we need four key ingredients:

1. Indices and Sets: Symbols that represent the objects in our system (e.g., jobs, operations, machines).
2. Parameters: The known data about the problem instance (e.g., the processing time of a specific operation on a specific machine).
3. Decision Variables: The unknown values our model must determine. These represent the decisions we need to make—namely, machine assignments and operation sequences. They can be continuous (like a start time) or binary (representing a yes/no choice).
4. Objective Function & Constraints: The goal we want to achieve (e.g., minimize makespan) and the rules that any valid schedule must follow (e.g., precedence relations, machine capacity).

With this structure in mind, we will now build a complete MILP formulation.

A Sequence-Based MILP Formulation for FJSP

There are many ways to formulate the FJSP. We will start with a classic and intuitive sequence-based approach that directly mirrors the assignment and sequencing decomposition we discussed previously. This type of model is often called a "disjunctive" formulation.

The following reading presents two MILP models. We will focus on the second one, which they call the "alternative model" or Alt-Cmax. It uses separate variables for the assignment and sequencing decisions, making it a clear example of a hierarchical representation within an integrated model.

Let's break down the Alt-Cmax model from the paper step-by-step.

1. Indices, Sets, and Parameters

• Indices:
  • $j,q$: indices for jobs.
  • $i,p$: indices for operations. $O_{ij}$ denotes the $i$-th operation of job $j$.
  • $k$: index for machines (or resources).
• Sets:
  • $J$: set of all jobs.
  • $O_j$: set of operations for job $j$.
  • $M$: set of all machines.
  • $M_{ij}$: set of eligible machines that can process operation $O_{ij}$.
• Parameters:
  • $p_{ijk}$: processing time of operation $O_{ij}$ on machine $k$.
  • $M$: a very large positive number (the "big-M").

2. Decision Variables

These variables directly capture the assignment and sequencing decisions:

• Assignment Variable (Routing):
  • $z_{ijk}\in \{0,1\}$: A binary variable that is 1 if operation $O_{ij}$ is assigned to machine $k$, and 0 otherwise. This variable solves the routing subproblem.
• Sequencing Variable:
  • $y_{ijpqk}\in \{0,1\}$: A binary variable that is 1 if operation $O_{ij}$ precedes operation $O_{pq}$ on machine $k$, and 0 otherwise. This variable solves the sequencing subproblem for operations assigned to the same machine.
• Timing Variable:
  • $t_{ijk}\ge 0$: A continuous variable representing the start time of operation $O_{ij}$ on machine $k$.
• Objective Variable:
  • $C_{max}\ge 0$: A continuous variable representing the makespan (the completion time of the last job).

3. Objective Function

The goal is to minimize the makespan:
$\text{Minimize}{C}_{max}$

4. Constraints

These are the rules that enforce a valid schedule.

• Assignment Constraint (Constraint 3b): Each operation must be assigned to exactly one of its eligible machines.
  ${\sum }_{k\in M_{ij}}{z}_{ijk}=1\forall O_{ij}$

• Precedence Constraints (Constraint 3f): An operation cannot start before its direct predecessor in the same job has finished. For operation $O_{i-1,j}$ followed by $O_{ij}$:
  ${\sum }_{k\in M_{ij}}{t}_{ijk}\ge {\sum }_{k\in M_{i-1,j}}(t_{i-1,j,k}+p_{i-1,j,k}\cdot z_{i-1,j,k})\forall j,\forall i>1$
  Note: The paper's formulation (3f) is slightly different but achieves the same goal. The version above is a common way to write it.

• Disjunctive Constraints (Constraints 3d, 3e): This is the core of the sequencing logic. For any two operations, $O_{ij}$ and $O_{pq}$, that could potentially be processed on the same machine $k$, one must finish before the other starts.
  $t_{ijk}+p_{ijk}\cdot z_{ijk}\le t_{pqk}+M(1-y_{ijpqk})$
  $t_{pqk}+p_{pqk}\cdot z_{pqk}\le t_{ijk}+M(y_{ijpqk})$
  Let's analyze this pair of "big-M" constraints. The variable $y_{ijpqk}$ acts as a switch.

  • If $y_{ijpqk}=1$, it means $O_{ij}$ is scheduled before $O_{pq}$ on machine $k$.
    • The first constraint becomes $t_{ijk}+p_{ijk}\cdot z_{ijk}\le t_{pqk}$, ensuring $O_{pq}$ starts after $O_{ij}$ finishes.
    • The second constraint becomes $t_{pqk}+p_{pqk}\cdot z_{pqk}\le t_{ijk}+M$. Since M is huge, this constraint becomes redundant and non-binding.
  • If $y_{ijpqk}=0$, it means $O_{pq}$ is scheduled before $O_{ij}$ on machine $k$. The logic is reversed.
    These constraints only apply if both operations are actually assigned to machine $k$ (i.e., when $z_{ijk}=1$ and $z_{pqk}=1$).

• Makespan Definition (Constraint 3g): The makespan must be greater than or equal to the completion time of every operation.
  $C_{max}\ge t_{ijk}+p_{ijk}\cdot z_{ijk}\forall O_{ij},\forall k\in M_{ij}$

The combination of these variables, objective, and constraints forms a complete MILP model that an optimization solver (like Gurobi or CPLEX) can process to find an optimal schedule.

The Landscape of FJSP Formulations

The sequence-based model is just one of several ways to formulate the FJSP. For your thesis research, it's beneficial to be aware of the other main paradigms, as they have different characteristics in terms of model size and solver performance.

The thesis by Azadeh et al. that we looked at previously provides an excellent and deep survey of these alternatives.

The key takeaway is that different choices of decision variables lead to fundamentally different model structures.

• Sequence-based models (like the Alt-Cmax we detailed) are generally more intuitive but can have a very large number of sequencing variables ($y_{ijpqk}$).
• Position-based models create a "slot" for each potential operation on a machine's schedule. They can be more compact but sometimes yield weaker linear relaxations, making them slower for a solver to prove optimality.

Knowing these alternatives will be invaluable when you review literature for your thesis or decide on a baseline model for your own work.

Conclusion

In this lesson, we have taken the conceptual idea of the FJSP and translated it into a formal, solvable Mixed-Integer Linear Program. This is a critical step from understanding a problem to optimizing it.

Key Takeaways:

• An FJSP can be formulated as a MILP using indices, parameters, decision variables, an objective function, and constraints.
• The core of the formulation involves binary assignment variables (like $z_{ijk}$) to handle the routing subproblem and binary sequencing variables (like $y_{ijpqk}$) to handle the sequencing subproblem.
• "Big-M" constraints are a standard and powerful technique for modeling the "either-or" logic required to prevent operations from overlapping on a machine.
• The sequence-based formulation we studied is just one approach; other paradigms like position-based models also exist and offer different trade-offs.

Preview of the Next Lesson:

While the integrated MILP model we built is powerful, it can be very difficult to solve for large, real-world problems. This motivates other approaches. In our next lesson, we will explore hierarchical approaches to solve the FJSP. Instead of solving everything at once, these methods first solve the assignment problem and then solve the sequencing problem in a second step. This will provide a practical contrast to the MILP model and serve as a bridge to understanding more advanced heuristic methods.