Evaluating Scheduling Algorithms: Benchmarks and Metrics

1. The Foundation of Credible Research: Benchmark Instances

Imagine you've designed a new hybrid metaheuristic for the FJSP. To claim it's effective, you can't just test it on one or two problems you created yourself. Your results would lack comparability and credibility. The academic community relies on standardized benchmark instances to create a level playing field where different algorithms can be fairly compared.

Using benchmarks allows your work to be:

• Comparable: Your results can be placed in context with decades of prior research.
• Reproducible: Other researchers can test their own algorithms on the same data to verify or challenge your findings.
• Credible: It shows that your algorithm performs well on problems that are widely recognized as challenging, not just on hand-picked examples.

1.1. The Classic FJSP Benchmark Libraries

For FJSP, one of the most important resources is a collection of benchmark libraries that have been established over the years. A central hub for these is FJSPLib. Let's explore its structure.

As you can see, the literature provides a rich set of instances with varying sizes and characteristics. The question is, which ones should you choose for your thesis? A good experimental design often involves a selection of instances with different difficulty levels.

1.2. How to Select Instances for Your Experiment

Not all benchmark instances are created equal. Some are easily solved to optimality, while others remain unsolved after decades of research. FJSPLib provides a useful classification system based on how modern solvers perform on them.

Based on this classification, you can build a strategic testbed for your algorithm:

• Easy/Medium Instances: Use these for initial development, debugging, and validation. If your algorithm can't solve these correctly and quickly, it's a sign that there is a fundamental issue in your implementation.
• Closed Instances: These are problems where the optimal solution is known, but it might still be hard to prove. They are perfect for verifying the correctness of an exact method or checking how close a heuristic gets to the true optimum.
• Hard Instances: These are the proving grounds for powerful algorithms. Showing that your method can solve (or find high-quality solutions for) these difficult problems demonstrates its strength and scalability.
• Open Instances: This is where you can make a significant research contribution. For these problems, no optimal solution has been proven. If your algorithm finds a new, better solution (a new upper bound), it advances the state of the art.

For a thesis, a good approach is to select a representative subset from several well-known sets (e.g., a few small, medium, and large instances from Brandimarte, Dauzère-Pérès, and Behnke) to show how your algorithm performs across different problem structures and sizes.

1.3. Beyond Classical Benchmarks: The Need for Realism

While classical benchmarks are essential, they often simplify reality. They typically omit complex constraints like sequence-dependent setup times, transport resources, limited buffers, or personnel—constraints that are central to your thesis goals.

This gap between theory and practice is a major area of modern research. The following paper discusses the limitations of classical benchmarks and proposes a path toward creating more realistic ones.

This brings up a critical question for your thesis: What if a benchmark for your specific, highly-constrained problem doesn't exist? You have two primary options:

1. Adapt Existing Benchmarks: This is a very common and accepted practice. You can take a classical instance (e.g., mk01 from Brandimarte) and systematically generate the missing data. For example, you could generate sequence-dependent setup times from a uniform distribution within a certain range of the processing times, or define a transport time matrix based on a logical layout. The key is to clearly and formally describe the generation procedure in your thesis so others can replicate it.
2. Generate New Instances: You can follow a methodology like the one in the paper you just read to generate a completely new set of instances. The paper even mentions making its data generator available, which is a huge asset. This approach can be a research contribution in itself, but requires careful justification of all your parameter choices.

2. Measuring Success: Performance Metrics

Once you have selected your benchmark instances, you need to define how you will measure your algorithm's performance. The choice of metric is not trivial; an algorithm that excels at one objective may perform poorly on another.

2.1. Metrics for Classical Problems with Known Bounds

For the classical benchmarks from FJSPLib, the research community has been competing for years to find the best possible solutions. The results of this competition are the Best Known Solutions (BKS), which are recorded as lower and upper bounds.

• Lower Bound (LB): A value that the optimal solution is proven to be greater than or equal to. LBs are often found through mathematical relaxations of the problem.
• Upper Bound (UB): The makespan of the best feasible schedule found so far for an instance. This is typically achieved by a high-performing heuristic or metaheuristic.
• When LB = UB, the problem is solved to optimality.

Your primary goal when running a metaheuristic on these instances is to find a high-quality UB. The standard way to measure your performance is the Relative Percentage Deviation (RPD) from the best-known UB.

The formula is:
$RPD(\%)=\frac{U{B}_{alg}-BK{S}_{UB}}{BK{S}_{UB}}\times 100$

Where:

• $U{B}_{alg}$ is the makespan (or other objective value) found by your algorithm.
• $BK{S}_{UB}$ is the Best Known Upper Bound from the literature (e.g., from the FJSPLib tables).

In your thesis, you will typically present a table for each benchmark set, showing the instance name, the BKS, your algorithm's UB, the RPD, and the computation time required to find that solution. Achieving a low average RPD or finding a new BKS (where RPD < 0) is a powerful way to demonstrate the merit of your algorithm.

2.2. Metrics for New Problems without Established Bounds

What happens when you work on a problem variant so new that no benchmarks (and therefore no Best Known Solutions) exist? This is often the case when incorporating complex constraints or Industry 5.0 objectives.

In this scenario, you cannot use RPD. Instead, you need to establish a baseline to compare against. The paper "How Good is my Scheduling Algorithm?" proposes a robust methodology for this.

The key metric here is Average Relative Improvement (ARI) over a baseline. The process is as follows:

1. Choose a simple, fast baseline heuristic. This could be a standard priority rule like First-In-First-Out (FIFO) or, as the paper suggests, even a rule that makes random (but valid) dispatching decisions.
2. Generate multiple problem instances (the paper suggests 100) to ensure your results are not due to chance.
3. For each instance, run the baseline heuristic to get a baseline performance score ($P_{base}$).
4. Run your advanced algorithm to get its performance score ($P_{alg}$).
5. Calculate the Relative Improvement (RI) for that instance:
   $RI(\%)=\frac{P_{base}-P_{alg}}{P_{base}}\times 100$
6. The final metric is the ARI, which is the average RI over all 100 instances.

This approach is powerful because it normalizes performance, allowing you to meaningfully aggregate results across a set of diverse, newly generated instances.

Conclusion

You have now learned the two essential components for experimentally validating your research. Choosing the right benchmarks and metrics is not just a technical detail; it is fundamental to the credibility and impact of your thesis.

Key Takeaways:

• Benchmark Instances: Use standard libraries like FJSPLib to ensure your work is comparable and credible. Select a mix of easy, hard, and open instances to rigorously test your algorithm. For novel problem variants, you can adapt existing benchmarks or systematically generate new ones.
• Performance Metrics: The metric depends on the context.
  • For classical problems, the standard metric is the Relative Percentage Deviation (RPD) from the Best Known Solution. Finding a new upper bound is a major contribution.
  • For new problems without known bounds, the best practice is to measure the Average Relative Improvement (ARI) over a simple, reproducible baseline heuristic (e.g., FIFO or a random rule).

Preview of the Next Lesson:

With the "what" (benchmarks) and the "how to measure" (metrics) covered, we are ready to assemble the full experimental plan. In our next lesson, we will focus on how to "Define a formal experimental protocol, including comparison algorithms and parameter tuning strategies." This will equip you to design and execute the complete computational study for your thesis.