List Scheduling for Hybrid Flow Shops

What are Heuristics and Why Do We Need Them?

As you saw with the MILP model, the number of possible schedules in an HFS problem explodes as the number of jobs and machines increases. This NP-hard nature means we often can't find the optimal solution in a reasonable amount of time. Heuristics offer a practical alternative.

A heuristic is essentially a problem-solving approach that uses practical rules or shortcuts to produce a good solution quickly. The key trade-off is that a heuristic does not guarantee optimality, but it can find a high-quality solution in a fraction of the time an exact method would require.

The List Scheduling Algorithm

List scheduling is one of the most intuitive and fundamental heuristic frameworks. The core idea is to make scheduling decisions greedily whenever a resource becomes available.

To understand the basic principle, let's watch a short video that explains list scheduling in the context of a classic load-balancing problem. While this is not an HFS problem, it perfectly illustrates the greedy, priority-based logic.

As the video shows, list scheduling operates in two general steps:

1. Create a priority list of tasks. This list determines the order in which tasks will be considered for scheduling.
2. Assign tasks to resources. As machines become available, select the highest-priority task from the list that is ready to be processed and assign it to an available machine.

In the HFS context, this process occurs at each stage. When a machine at stage $k$ becomes free, it looks at the queue of jobs that have completed stage $k-1$ and are waiting. The decision of which job to process next is where specific heuristics come into play.

The "List": Common Dispatching Rules

The "list" in list scheduling is often not a static, pre-ordered list but is dynamically created using a dispatching rule (or priority rule). This rule tells you which job to pick from a queue of waiting jobs. There are many such rules, each with its own logic.

Here are some of the most common dispatching rules used in scheduling:

• SPT (Shortest Processing Time): Prioritize the job with the shortest processing time for the imminent operation. This rule is known to be very effective for minimizing objectives like mean flow time and total tardiness.
• LPT (Longest Processing Time): Prioritize the job with the longest processing time. This is often a good heuristic for minimizing makespan, as it aims to get the large, difficult jobs started early to avoid them delaying the entire schedule at the end.
• FCFS (First Come, First Served) or FIFO (First In, First Out): Prioritize the job that arrived at the queue first. This is simple and fair but often not the most efficient.
• MWKR (Most Work Remaining): Prioritize the job that has the largest total processing time for all of its remaining operations. This is a look-ahead rule that prioritizes jobs that still have a long way to go.
• LWKR (Least Work Remaining): The opposite of MWKR. It prioritizes jobs that are close to being finished.

The resource LINK provides a good list of these rules. You can find them under the section "1.5.3 Dispatching rules as a parameter of comparison." It's valuable to see how these fundamental rules are cited in academic literature, often as benchmarks to evaluate more sophisticated algorithms.

Applying List Scheduling to a Hybrid Flow Shop

Applying list scheduling to an HFS problem involves managing queues at each stage. The process is event-driven, where decisions are made whenever a machine becomes free. A complete list scheduling heuristic for HFS needs two components:

1. A Job Sequencing Rule: The dispatching rule (e.g., SPT, LPT) to select the next job from the queue at a stage.
2. A Machine Assignment Rule: The rule to select which of the parallel machines at that stage will process the chosen job. A common rule is Earliest Completion Time (ECT): assign the job to the machine that can finish it the soonest. For identical parallel machines, this simplifies to assigning it to the first available machine.

Let's walk through an example.

Worked Example

Consider the following 3-job, 2-stage HFS problem. Our objective is to minimize makespan ($C_{max}$).

• Stage 1: 2 identical parallel machines (M11, M12).
• Stage 2: 1 machine (M21).
• Processing Times ($p_{jk}$):

We will use the SPT rule for job sequencing at each stage and assign jobs to the first available machine.

Let's build the schedule step-by-step, tracking machine availability and job completion times. A Gantt chart is the perfect tool for this.

Step-by-Step Construction:

1. Time = 0:

   • Machines: M11, M12, M21 are all free.
   • Queue for S1: {J1, J2, J3}. Their S1 processing times are {3, 4, 2}.
   • Decision (S1): Applying SPT, J3 (p=2) has the highest priority. Assign J3 to M11. M11 will be busy until t=2.
   • Now, M12 is still free. The next highest priority job is J1 (p=3). Assign J1 to M12. M12 will be busy until t=3.

2. Time = 2:

   • Event: J3 finishes on M11. M11 becomes free.
   • Queue for S1: {J2} is the only job left.
   • Decision (S1): Assign J2 to M11. M11 will be busy until t = 2 + 4 = 6.
   • Queue for S2: {J3} is now waiting. M21 is free.
   • Decision (S2): Assign J3 to M21. M21 will be busy until t = 2 + 6 = 8.

3. Time = 3:

   • Event: J1 finishes on M12. M12 becomes free.
   • Queue for S1: Empty.
   • Queue for S2: {J1} is now waiting. M21 is busy until t=8.

4. Time = 6:

   • Event: J2 finishes on M11. M11 becomes free.
   • Queue for S1: Empty.
   • Queue for S2: {J1, J2} are now waiting. M21 is busy until t=8.

5. Time = 8:

   • Event: J3 finishes on M21. M21 becomes free.
   • Queue for S2: {J1, J2}. Their S2 processing times are {5, 2}.
   • Decision (S2): Applying SPT, J2 (p=2) has the highest priority. Assign J2 to M21. M21 will be busy until t = 8 + 2 = 10.

6. Time = 10:

   • Event: J2 finishes on M21. M21 becomes free.
   • Queue for S2: {J1} is the only job left.
   • Decision (S2): Assign J1 to M21. M21 will be busy until t = 10 + 5 = 15.

7. Time = 15:

   • Event: J1 finishes on M21. All jobs are complete.
   • Final Makespan $C_{max}$ = 15.

Final Gantt Chart:

• M11: [J3, 0-2], [J2, 2-6]
• M12: [J1, 0-3]
• M21: [Idle, 0-2], [J3, 2-8], [J2, 8-10], [J1, 10-15]

Hierarchies of Heuristics

The simple dispatching rules we've discussed are the building blocks of scheduling. In your literature review for your thesis, you will encounter them frequently, but often as a baseline for comparison.

More advanced constructive heuristics, like the NEH algorithm you saw for permutation flow shops, build a complete schedule through a more intelligent, iterative process. The research paper LINK provides an excellent academic perspective on this.

The key takeaway is that simple heuristics like list scheduling can be used on their own for quick schedule generation or can be embedded within more powerful metaheuristic frameworks (like Genetic Algorithms, which we will cover in Module 8) to evaluate candidate solutions.

Conclusion

Today, we've explored a practical and efficient way to tackle HFS scheduling problems when exact methods are not feasible. You've moved from the theoretical world of MILP formulations to the practical application of heuristic rules.

Key Takeaways:

• List scheduling is a greedy, constructive heuristic framework that builds a schedule by prioritizing jobs and assigning them to available machines.
• The prioritization is determined by dispatching rules such as SPT, LPT, and FCFS. Each rule has its own strengths and is suited for different objectives.
• Applying list scheduling to an HFS requires both a job sequencing rule (for the queue at a stage) and a machine assignment rule (for the parallel machines).
• Simple heuristics provide fast, good-quality solutions and serve as essential benchmarks for evaluating more complex algorithms in academic research—a crucial point for your thesis work.

Preview of the Next Lesson:

We have now examined single machine, flow shop, and hybrid flow shop environments. Our next step takes us towards even greater complexity, preparing you for the Flexible Job Shop problem. In the next lesson, we will define the job shop scheduling problem and contrast it with the environments we've studied so far. We will also introduce the powerful disjunctive graph representation, a critical tool for modeling and solving these more intricate scheduling challenges.