Hybrid Flow Shop with Parallel Machines

From Flow Shop to Hybrid Flow Shop

Recall the standard flow shop model: a set of jobs must be processed by a set of machines in a fixed series. Every job follows the exact same path, for example, Machine 1 → Machine 2 → Machine 3. The core constraint is that each stage in this process has only a single machine.

Now, imagine a bottleneck at one of these stages. A common industrial engineering solution is to add capacity by installing a second, parallel machine. If jobs can be processed by either of these machines before moving to the next stage, the production environment is no longer a simple flow shop. It has become a hybrid flow shop.

This configuration is very common in industry. Think of a production line where a particular task, like painting or curing, can be done in one of several identical booths before all items move on to the next stage, like inspection.

This diagram provides a clear visual representation of the hybrid flow shop environment.

To get a formal definition, let's consult an academic text that lays out the core concepts.

As the text states, a Hybrid Flow Shop (HFS) consists of a series of production stages, where at least one stage has multiple machines operating in parallel. The job flow remains unidirectional, which is the "flow shop" characteristic. The "hybrid" nature comes from this combination of a sequential flow between stages and parallel processing options within stages.

Key Characteristics and Terminology

The HFS model introduces a new layer of decision-making compared to the standard flow shop. Not only do we need to decide the sequence of jobs, but we also need to decide which machine should process each job at stages with multiple options. This is a fundamental challenge you will also face in FJSP.

The literature uses the terms Hybrid Flow Shop (HFS) and Flexible Flow Shop (FFS) largely interchangeably. Being aware of both terms is important for your own research and literature review. Let's look at another resource that uses the FFS terminology and lists the key characteristics.

Synthesizing these definitions, we can identify the defining properties of an HFS/FFS environment:

1. Staged Production: The system is divided into a series of k stages, processed in order (stage 1, stage 2, ..., stage k).
2. Parallel Machines: Each stage j has one or more parallel machines. For the system to be "hybrid," at least one stage must have more than one machine.
3. Unidirectional Job Flow: All jobs follow the same sequence of stages. This is the "flow" aspect. However, as noted in the resource, some variations allow jobs to skip certain stages, increasing flexibility.
4. Dual Decision Problem: A solution must specify two things:
   • Assignment: Which machine at each stage will process each job.
   • Sequencing: In what order the jobs assigned to a particular machine should be processed.

Types of Parallel Machines

The machine assignment decision depends heavily on the nature of the parallel machines at a stage. Are they identical copies, or do they have different capabilities? This is a critical detail for mathematical modeling. The document we looked at earlier provides a clear classification.

Let's break down these three categories. Suppose a job j needs to be processed at stage i, which has several parallel machines. Let $p_{ijk}$ be the processing time of job j at stage i on machine k.

1. Identical Parallel Machines:
   This is the simplest case. All machines at a stage are perfect substitutes for one another. The processing time of a job is the same no matter which machine at that stage processes it.

   • Condition: $p_{ij{k}_1}=p_{ij{k}_2}$ for any two machines $k_1,k_2$ at stage i.
   • Example: A set of five identical 3D printers for a prototyping stage.

2. Uniform Parallel Machines:
   Machines at a stage perform the same function but at different speeds. The speed of a machine is constant regardless of the job. You can think of each machine k having a speed factor $v_k$. The processing time is a base time for the job, divided by the machine's speed.

   • Condition: $p_{ijk}=p_{ij}/v_k$, where $p_{ij}$ is the base processing time for job j at stage i.
   • Example: An old CNC machine and a new, faster model working in parallel. The new machine might have a speed factor of $v_{new}=1.5$ while the old one has $v_{old}=1.0$.

3. Unrelated Parallel Machines:
   This is the most general and complex case. The processing time depends on the specific job-machine pairing. A machine might be faster for one type of job but slower for another due to its specific tooling or capabilities.

   • Condition: $p_{ijk}$ is unique for each combination of job j and machine k at stage i. There is no simple relationship between them.
   • Example: At a metalworking stage, you might have a high-precision laser cutter and a high-speed water-jet cutter. The laser might be faster for thin steel (job A), while the water jet is faster for thick aluminum (job B).

Understanding this distinction is fundamental because it dictates the complexity of the machine assignment subproblem.

Conclusion

In this lesson, we have formally defined the hybrid flow shop environment, a crucial step up in complexity from the classic flow shop. This environment is not only common in real-world manufacturing but also serves as an essential building block for understanding even more complex scheduling problems like FJSP.

Key Takeaways:

• A Hybrid Flow Shop (HFS), also known as a Flexible Flow Shop (FFS), is a production system with sequential stages, where at least one stage contains multiple parallel machines.
• Solving an HFS problem requires making both assignment decisions (which machine to use) and sequencing decisions (in what order to run jobs).
• The parallel machines at a stage can be classified as identical, uniform, or unrelated, which significantly changes the nature of the assignment problem.

Preview of the Next Lesson:

Now that we have a clear conceptual and descriptive understanding of the HFS environment, our next task is to translate this into a precise mathematical formulation. In the next lesson, we will learn how to formulate a hybrid flow shop problem as a Mixed-Integer Linear Program (MILP). This will involve defining new decision variables and constraints to handle the critical machine assignment choice, building directly on the MILP modeling skills you developed earlier in the course.