Modeling Hybrid Flow Shop with MILP

From Concept to Mathematical Model

A Mixed-Integer Linear Program is a powerful way to formally describe an optimization problem. It consists of three main components:

1. Decision Variables: The quantities we need to decide (e.g., which machine to use, when to start a job). These can be continuous, integer, or binary (0/1).
2. Objective Function: A linear expression of the decision variables that we want to minimize or maximize (e.g., makespan, total tardiness).
3. Constraints: A set of linear equations or inequalities that the decision variables must satisfy, representing the rules of the system (e.g., a machine can only process one job at a time).

To learn how to construct such a model for an HFS, we will analyze a formulation from a recent research paper. This model is particularly relevant as it includes sequence-dependent setup times (SDST), a topic we will cover in detail in Module 7, giving you an early look at how to handle such complexities.

Deconstructing the MILP Formulation

Let's break down the model from the paper step-by-step. A clear understanding of each component is essential for both implementing and extending such models in your own research.

1. Indices and Parameters

These are the "given" inputs to our problem.

• Indices:
  • $j,j^{\prime }$: Jobs
  • $k$: Stages
  • $i$: Machines
• Parameters:
  • $p_{j,k}$: Processing time of job $j$ at stage $k$. (Note: The paper's model assumes this is independent of the machine, implying an identical or uniform parallel machine environment).
  • $s{t}_{k,j,j^{\prime }}$: Setup time required at stage $k$ when switching from job $j$ to job $j^{\prime }$.
  • $m_k$: The set of machines available at stage $k$.
  • $L$: A very large positive number, used in "big-M" constraints.

2. Decision Variables

These are the "outputs" our model will determine. They represent the core decisions of assignment and sequencing.

• Assignment Variable (Binary): $X_{j,k,i}\in \{0,1\}$
  • This is the key to the machine assignment problem. $X_{j,k,i}=1$ if job $j$ is assigned to machine $i$ at stage $k$, and $0$ otherwise.
• Sequencing Variable (Binary): $Y_{j,j^{\prime },k}\in \{0,1\}$
  • This variable determines the relative order of jobs. The paper defines this as $1$ if job $j$ is processed before job $j^{\prime }$ at stage $k$. This variable is only meaningful when both jobs are on the same machine.
• Timing Variables (Continuous):
  • Start Time: $E_{j,k}\ge 0$. The time at which processing for job $j$ begins at stage $k$.
  • Completion Time: $B_{j,k}\ge 0$. The time at which processing for job $j$ is completed at stage $k$.
  • Makespan: $C_{max}$. The completion time of the last job in the entire schedule.

Note on Notation: There appears to be a typo in the paper's variable list and Constraint (3). Based on the logic of scheduling models, Completion Time = Start Time + Processing Time. Constraint (3) in the paper is E = B + p while the list says B is completion and E is start. The logically consistent interpretation is that $E_{j,k}$ is the start time and $B_{j,k}$ is the completion time. We will proceed with this corrected understanding.

3. Objective Function

$\min C_{max}$

The goal is to minimize the makespan, which is the time when all jobs are finished. This is a very common and important objective in production scheduling.

4. Constraints

These are the rules that shape a valid schedule. Let's analyze them one by one.

• Assignment Constraint:
  ${\sum }_{i\in m_k}{X}_{j,k,i}=1,\forall j\in J,k\in S$

  • Meaning: For each job $j$ at each stage $k$, it must be assigned to exactly one machine from the set of available machines $m_k$. The sum of the $X$ variables over all machines at that stage must be 1.

• Precedence Constraint:
  $B_{j,k}\le E_{j,k+1},\forall j\in J,k\in \{1,\dots ,s-1\}$

  • Meaning: The start time of job $j$ at stage $k+1$ must be greater than or equal to its completion time at the preceding stage $k$. This enforces the "flow shop" sequence of operations for each job.

• Sequencing (Disjunctive) Constraints:
  These are the most complex and crucial constraints for modeling the sequencing on a shared machine.
  $E_{j^{\prime },k}\ge B_{j,k}+s{t}_{k,j,j^{\prime }}-L(3-Y_{j,j^{\prime },k}-X_{j,k,i}-X_{j^{\prime },k,i})$
  $E_{j,k}\ge B_{j^{\prime },k}+s{t}_{k,j^{\prime },j}-L(2+Y_{j,j^{\prime },k}-X_{j,k,i}-X_{j^{\prime },k,i})$

  • Meaning: These two constraints work together for any pair of jobs ($j,j^{\prime }$) on any machine $i$. Let's analyze the first one.
  • If jobs $j$ and $j^{\prime }$ are both assigned to machine $i$ ($X_{j,k,i}=1$ and $X_{j^{\prime },k,i}=1$) and job $j$ is scheduled before job $j^{\prime }$ ($Y_{j,j^{\prime },k}=1$), then the term in the parenthesis becomes $3-1-1-1=0$. The constraint simplifies to $E_{j^{\prime },k}\ge B_{j,k}+s{t}_{k,j,j^{\prime }}$. This correctly states that the start time of job $j^{\prime }$ must be after job $j$ is complete, plus any necessary setup time.
  • In any other case (e.g., jobs are on different machines, or $j^{\prime }$ comes before $j$), the term in the parenthesis is non-zero, making $-L(\dots )$ a very large negative number. The constraint becomes $E_{j^{\prime },k}\ge B_{j,k}+s{t}_{k,j,j^{\prime }}-L$, which is always true and thus non-binding. This is the classic "big-M" technique to enforce conditional logic. The second constraint works symmetrically for the case where $j^{\prime }$ precedes $j$.

• Makespan Definition:
  $C_{max}\ge B_{j,s},\forall j\in J$

  • Meaning: The makespan must be greater than or equal to the completion time of every job at the final stage ($s$). Since the objective is to minimize $C_{max}$, the solver will push $C_{max}$ down until it equals the largest $B_{j,s}$.

An Alternative Formulation

It is important to recognize that there is often more than one way to model a problem. Different formulations can have vastly different performance when solved. For example, another approach could use a three-index sequencing variable, like $z_{ij{j}^{\prime }}=1$ if job $i$ precedes job $j$ on machine $j^{\prime }$.

The paper "Mixed-Integer Linear Programming, Constraint..." (ID: LINK) presents such an alternative model for a hybrid flow shop. It also uses a different objective function: minimizing total tardiness instead of makespan. We won't go through it in detail, but it's valuable to know that different objectives and variable definitions can be used to capture the logic of the same production environment. This flexibility is key to advanced modeling.

The Limits of Exact Methods

MILP models, when solved with commercial solvers like CPLEX or Gurobi, guarantee finding the optimal solution if given enough time. However, the time required can be immense. This is because HFS problems are NP-hard.

Let's look at the results from the paper we studied.

As you can see from Table 1, the MILP model solved with CPLEX finds the optimal solution (Gap = 0%) for small instances (e.g., 10 jobs, 5 stages) in a reasonable amount of time. However, as the problem size increases to 20 jobs, the solver hits the 600-second time limit and terminates with a significant optimality gap (e.g., 31.8%, 40.2%).

This "combinatorial explosion" happens because the number of binary variables and constraints grows polynomially, but the underlying search space grows exponentially. For an instance with 40 jobs, 10 stages, and 5 machines per stage, the number of possible schedules is astronomically large, making it impossible for an exact method to explore them all.

Table 7 further illustrates this. For small problems, the MILP finds the true optimum, which the IABC heuristic sometimes misses. But for larger problems (the bottom of the table), the heuristic finds a much better solution within the time limit than the MILP solver could.

Conclusion

In this lesson, we have translated the abstract concept of a hybrid flow shop into a concrete mathematical reality: a Mixed-Integer Linear Program. This is a critical skill for any researcher in the field of scheduling.

Key Takeaways:

• An HFS MILP formulation requires at least two types of binary decision variables: assignment variables ($X_{j,k,i}$) and sequencing variables ($Y_{j,j^{\prime },k}$).
• "Big-M" constraints are a standard and powerful technique for modeling the disjunctive "either-or" logic inherent in sequencing operations on a shared resource.
• While MILP models are essential for defining problems formally and finding optimal solutions for small instances, they are computationally intractable for most real-world problem sizes due to their NP-hard nature.

Preview of the Next Lesson:

The computational limitations of MILP directly motivate our next topic. Since we often cannot wait hours or days for an optimal solution (or cannot find one at all), we turn to faster, approximate methods. In the next lesson, we will apply list scheduling heuristics to hybrid flow shop problems, which provide good-quality solutions in a fraction of the time.