Decomposing FJSP: Machine Assignment & Operation Sequencing

Hello! Welcome to your next lesson on the Flexible Job Shop Problem (FJSP).

In our last session, we focused on the core concept of flexibility, learning to distinguish between totally flexible and partially flexible job shops. We established that partial flexibility is the more common and complex scenario, which accurately reflects most real-world industrial environments.

Today, we will build directly on that understanding. The primary goal of this lesson is to decompose the Flexible Job Shop Problem into its constituent subproblems: machine assignment and operation sequencing. Understanding this decomposition is the most critical step in moving from defining the FJSP to actually solving it. It provides the conceptual framework for almost all solution methods you will encounter in your research.

The Two Fundamental Decisions in FJSP

As we've touched upon, the flexibility of the FJSP introduces a layer of decision-making that doesn't exist in the classical job shop problem. Solving an FJSP requires answering two fundamental and interconnected questions:

The Routing Subproblem (Machine Assignment): For each operation, which machine should be chosen from its set of eligible machines?
The Sequencing Subproblem (Scheduling): Once machines have been assigned, in what order should the operations assigned to each machine be processed to satisfy the job precedence constraints and optimize the objective function?

Let's start by getting a clear definition of this decomposition from a couple of key academic sources.

Multiobjective Flexible Job Shop Scheduling Using ...

The paper 'Multiobjective Flexible Job Shop Scheduling Using...' provides a very direct and concise definition of this decomposition.

Please read section II-A, 'Formulation of the MO-FJSP'. Focus on the paragraph that begins 'The scheduling consists of two sub-problems...'.

Mathematical Modelling and Optimization of Flexible Job Shops ...

Similarly, the thesis 'Mathematical Modelling and Optimization of Flexible Job Shops...' explicitly breaks down the problem.

Please read section 1.5, 'Mechanics of F-JSSP'. Focus on the two bullet points that describe the 'two distinct decisions' that have to be made.

Both resources state unequivocally that the FJSP is comprised of these two distinct, yet related, subproblems. To visualize this, consider the following diagram.

Decomposition of Flexible Job Shop Problem — This diagram illustrates the FJSP decomposition. Panel (a) shows the **Instance**, where operations (e.g., O1,1) have potential assignments to multiple machines (dashed lines), representing the routing subproblem. Panel (b) shows a **Solution**, where the machine assignment has been made (solid lines) and the sequencing of operations on each machine is implied.

In panel (a), the challenge is to choose one of the dashed lines for each operation. This is the routing subproblem. Once you make those choices, you arrive at a situation like panel (b). Now, the problem is to determine the start and end times for all operations on their assigned machines, respecting the job-specific precedence constraints (the orange arrows) and ensuring no two operations overlap on the same machine. This is the sequencing subproblem.

Strategies for Tackling the Subproblems

Conceptually separating the problem into assignment and sequencing naturally leads to different high-level strategies for solving it. The two main families of approaches are:

Hierarchical (or Sequential) Approaches: These methods solve the problem in stages. First, the routing subproblem is solved to assign every operation to a machine. This transforms the FJSP into a set of classical Job Shop Problems (one for each machine). Then, a separate algorithm solves the resulting sequencing subproblem.
Integrated (or Simultaneous) Approaches: These methods consider both subproblems at the same time. The decision of which machine to use and where to place an operation in the sequence are made concurrently.

Hierarchical methods are often simpler to implement, but decisions made in the first stage (routing) without considering the second (sequencing) can lead to poor-quality schedules. Integrated approaches are more complex but can find better solutions because they can trade off routing and sequencing decisions against each other.

Decomposition in Practice: Solution Representation

For your thesis work, it's vital to see how this theoretical decomposition translates into practical solution methods. The structure of your data and algorithms will directly reflect the way you handle these two subproblems.

1. Representation in Metaheuristics

Many modern heuristics, like Genetic Algorithms, represent a complete solution to the FJSP using a structure that explicitly mirrors the problem decomposition.

Multiobjective Flexible Job Shop Scheduling Using ...

Let's return to the paper 'Multiobjective Flexible Job Shop Scheduling...'. It describes a very common and intuitive way to encode an FJSP solution.

Please read section IV-A, 'Chromosome Encoding'. Pay close attention to the description of the 'machine assignment vector' and the 'operation sequence vector'.

As the paper describes, a solution (a "chromosome") is composed of two distinct parts:

A Machine Assignment Vector: This is a list that, for every operation in the problem, specifies which machine it is assigned to. This part of the chromosome is the solution to the routing subproblem.
An Operation Sequence Vector: This is a permutation of all operations. It defines the priority for scheduling, forming the basis for solving the sequencing subproblem.

This two-part encoding is a perfect example of a hierarchical representation used within an integrated search algorithm. The algorithm searches for the best combination of an assignment vector and a sequence vector.

2. Representation in Mathematical Models

Given your interest in mathematical analysis, it's particularly useful to see how this decomposition appears in formal Mixed-Integer Linear Programming (MILP) models. The choice of decision variables in a MILP often reveals whether it treats the problem hierarchically or integrally.

Mathematical Modelling and Optimization of Flexible Job Shops ...

The thesis by Azadeh et al. provides an excellent discussion on how different MILP formulations handle the subproblems.

Please read the end of section 3.3, which introduces the classification of MILPs as 'integrated' or 'hierarchical'. Then, skim the descriptions of the different models in sections 3.4 and 3.5.1. Notice how MILP-2 (in 3.4) uses a single binary variable to handle both routing and sequencing, while MILP-4 (in 3.5.1) uses two different binary variables: one for assigning and one for sequencing.

From this reading, we can see the two approaches embodied in the mathematics:

Hierarchical Model (e.g., MILP-4/5/6): These models use separate binary variables. For instance, a variable $Y_{ij k}$ might be 1 if operation $O_{ij}$ is assigned to machine $k$ , solving the routing problem. A different variable, $Z_{ij, g h, k}$ , might be 1 if operation $O_{ij}$ precedes operation $O_{g h}$ on machine $k$ , solving the sequencing problem. This explicitly separates the decisions.
Integrated Model (e.g., MILP-2): This model uses a more complex variable, like $X_{ij k f}$ , which equals 1 if operation $O_{ij}$ is assigned to the $f$ -th processing position on machine $k$ . This single variable simultaneously makes the machine assignment (via index $k$ ) and determines the sequence (via index $f$ ).

This distinction is fundamental when you formulate your own models. An integrated formulation can be more powerful but often leads to a much larger number of variables and constraints, making it harder to solve.

Test your understanding!

Consider a small FJSP with 2 jobs and 2 machines.

Job 1: $O_{1, 1} \to O_{1, 2}$
Job 2: $O_{2, 1}$

The machine eligibility and processing times are:

$O_{1, 1}$ : Machine 1 (5 min) or Machine 2 (6 min)
$O_{1, 2}$ : Machine 2 only (4 min)
$O_{2, 1}$ : Machine 1 only (8 min)

Decompose this problem by providing:

A feasible solution to the routing subproblem (a complete machine assignment for all operations).
Based on your assignment, provide a feasible solution to the sequencing subproblem (an ordered list of operations for each machine).

Show answer

Routing Subproblem Solution:
We need to assign each operation to a machine from its eligible set.
- For $O_{1, 1}$ , we can choose either M1 or M2. Let's choose M1.
- For $O_{1, 2}$ , the only eligible machine is M2.
- For $O_{2, 1}$ , the only eligible machine is M1.
  So, a feasible machine assignment is: $O_{1, 1} \to M 1$ , $O_{1, 2} \to M 2$ , $O_{2, 1} \to M 1$ .
Sequencing Subproblem Solution:
Based on the assignment above, we need to sequence the operations on each machine.
- Machine 1 has two operations assigned to it: $O_{1, 1}$ and $O_{2, 1}$ . We can sequence them in any order. Let's choose the sequence: $O_{2, 1} \to O_{1, 1}$ .
- Machine 2 has only one operation assigned to it: $O_{1, 2}$ . The sequence is simply $O_{1, 2}$ .
  This completes the schedule. Note that we must still respect the precedence $O_{1, 1} \to O_{1, 2}$ , meaning $O_{1, 2}$ cannot start until $O_{1, 1}$ is finished.

Conclusion

In this lesson, we have formally broken down the complex Flexible Job Shop Problem into its two core components. This decomposition is not just a theoretical exercise; it is the conceptual foundation upon which practical solution methodologies are built.

Key Takeaways:

The FJSP consists of two interdependent subproblems: machine assignment (routing) and operation sequencing.
This decomposition allows us to classify solution approaches as hierarchical (solving one subproblem then the other) or integrated (solving both simultaneously).
Solution representations directly reflect this decomposition. We saw this in the two-part chromosome of a genetic algorithm and in the choice of decision variables in hierarchical vs. integrated MILP models.

Preview of the Next Lesson:

Now that we have a firm grasp of the FJSP's structure and its subproblems, we are ready to build a complete mathematical model. In the next lesson, we will formulate the FJSP as a Mixed-Integer Linear Program (MILP). We will draw upon the concepts of hierarchical and integrated formulations discussed today to construct a precise, solvable model from the ground up, a critical skill for your thesis research.

Recommended resources