Hierarchical Approaches for Solving FJSP

The "Divide and Conquer" Strategy: Hierarchical Approaches

The core idea behind hierarchical approaches is to decompose the FJSP into its two fundamental components and solve them sequentially. This strategy trades the guarantee of optimality for significant gains in computational speed and scalability.

To begin, let's get a formal definition of this method.

As the paper highlights, the hierarchical method splits the FJSP into two distinct stages:

1. Stage 1: The Machine Assignment Subproblem (Routing). In this stage, we decide which machine will perform each operation. We essentially fix the routing for every job, ignoring the detailed sequencing of operations for the moment.
2. Stage 2: The Operation Sequencing Subproblem (Scheduling). With the machine assignments now fixed from Stage 1, the problem is simplified. It becomes a standard Job Shop Scheduling Problem (JSP), where the task is to sequence the operations assigned to each machine to minimize the objective (e.g., makespan).

This separation of concerns is a classic engineering strategy for managing complex systems.

The primary drawback of this method is that the decisions made in Stage 1 are irrevocable and might not lead to the globally optimal solution. An assignment that looks good in isolation (e.g., assigning an operation to its fastest machine) might create an unavoidable bottleneck in Stage 2. A truly optimal schedule might require a "bad" assignment locally to achieve a better overall result.

Stage 1: Solving the Assignment Problem

The first task is to assign every operation $O_{ij}$ to a machine $k$ from its set of eligible machines $M_{ij}$. The goal is to make "good" assignments that will likely lead to a good final schedule. Here are a few common heuristics for this stage:

• Shortest Processing Time (SPT) Assignment: Assign each operation to the machine that can process it the fastest. This is a greedy, intuitive rule that aims to minimize the total time spent in processing.
• Workload Balancing Assignment: Assign the next operation to the eligible machine that currently has the minimum total processing time of all operations already assigned to it. This heuristic tries to distribute the work evenly to avoid creating a single, heavily loaded bottleneck machine.
• Random Assignment: Assign each operation to a random eligible machine. While seemingly naive, this can be a useful baseline or a starting point for more advanced improvement algorithms.

Let's consider the physical system we're modeling.

Stage 2: Solving the Sequencing Problem

Once Stage 1 is complete, we have a fixed set of operations assigned to each machine. The problem is no longer an FJSP; it has been reduced to a classical Job Shop Scheduling Problem (JSP). Now, we must determine the sequence of operations on each machine.

You have already encountered methods for this in previous lessons:

• Dispatching Rules: We can apply rules locally on each machine to decide which of its waiting jobs to process next. Examples include First-In-First-Out (FIFO), Shortest Processing Time (SPT), or Earliest Due Date (EDD).
• Constructive Heuristics for JSP: The Giffler-Thompson algorithm, which we covered in Module 5, is designed specifically for this. It can be applied directly to the problem resulting from Stage 1 to generate a feasible and active schedule.
• Improvement Heuristics: One could start with a simple sequence (e.g., from a dispatching rule) and then apply a local search procedure, like the swap-based methods from the flow shop module, to improve the makespan. Brandimarte's original paper used a Tabu Search metaheuristic in this stage.

A Walkthrough Example

Let's make this concrete with a small example.

Problem Instance:

• Job 1: $O_{1,1}\to O_{1,2}$
• Job 2: $O_{2,1}\to O_{2,2}$
• Processing Times $p_{ijk}$:

Step 1: Hierarchical Approach - Stage 1 (Assignment)

Let's use the SPT assignment rule.

1. For $O_{1,1}$: M1 (p=5) is faster than M2 (p=8). Assign $O_{1,1}$ to M1.
2. For $O_{1,2}$: M2 (p=6) is faster than M3 (p=7). Assign $O_{1,2}$ to M2.
3. For $O_{2,1}$: M1 (p=9) is faster than M3 (p=11). Assign $O_{2,1}$ to M1.
4. For $O_{2,2}$: M2 (p=4) is faster than M1 (p=10). Assign $O_{2,2}$ to M2.

Result of Stage 1: The assignments are now fixed.

• M1 processes: $O_{1,1}$ (p=5) and $O_{2,1}$ (p=9).
• M2 processes: $O_{1,2}$ (p=6) and $O_{2,2}$ (p=4).
• M3 processes: Nothing.

Step 2: Hierarchical Approach - Stage 2 (Sequencing)

We now have a standard JSP. We need to sequence the operations on M1 and M2.

• On M1: Sequence ($O_{1,1}$, $O_{2,1}$) or ($O_{2,1}$, $O_{1,1}$)?
• On M2: Sequence ($O_{1,2}$, $O_{2,2}$) or ($O_{2,2}$, $O_{1,2}$)?

Let's apply a simple sequencing rule: process operations in the order of their job index, then operation index.

• On M1: $O_{1,1}$ comes before $O_{2,1}$. Sequence is $⟨O_{1,1},O_{2,1}⟩$.
• On M2: $O_{1,2}$ comes before $O_{2,2}$. Sequence is $⟨O_{1,2},O_{2,2}⟩$.

Now we can build the schedule (e.g., by drawing a Gantt chart):

1. At t=0, $O_{1,1}$ starts on M1. It finishes at t=5.
2. At t=0, $O_{2,2}$ could potentially start on M2, but it must wait for $O_{2,1}$. So M2 is idle.
3. At t=5, $O_{1,1}$ finishes. M1 is now free. $O_{2,1}$ can start. It runs from t=5 to t=14.
4. Also at t=5, $O_{1,1}$ finishing means $O_{1,2}$ can start on M2. It runs from t=5 to t=11.
5. At t=11, $O_{1,2}$ finishes on M2.
6. At t=14, $O_{2,1}$ finishes on M1. Now $O_{2,2}$ can start on M2. M2 is free since t=11. So $O_{2,2}$ starts on M2 at t=14. It runs from t=14 to t=18.

The last operation to finish is $O_{2,2}$ at t=18. The makespan is 18.

Conclusion

In this lesson, we explored a practical and widely-used strategy for tackling the complex FJSP: hierarchical decomposition. By separating the problem into assignment and sequencing stages, we can leverage simpler, faster heuristics to find good solutions for large problem instances where exact methods fail.

Key Takeaways:

• Hierarchical approaches solve the FJSP by decomposing it into two subproblems: machine assignment (routing) followed by operation sequencing (scheduling).
• This "divide and conquer" strategy drastically reduces computational complexity at the potential cost of solution optimality.
• Stage 1 (Assignment) can be solved using heuristics like Shortest Processing Time (SPT) or workload balancing.
• Stage 2 (Sequencing) solves the resulting Job Shop Problem, often using dispatching rules (e.g., FIFO) or dedicated JSP algorithms (e.g., Giffler-Thompson).

Preview of the Next Lesson:

Our simple hierarchical model made assignments based only on processing time. But as your thesis requires, real-world factories have additional complexities. What if changing from one job to another on a machine requires a lengthy setup? What if jobs need to be moved between work centers by a limited number of vehicles?

In the next module, we will begin tackling these challenges. Our first lesson will focus on distinguishing between sequence-independent and sequence-dependent setup times and how to start incorporating them into our models. This will add another layer of realism and complexity, moving us closer to the models you will develop in your research.