Scheduling is difficult. Scheduling your workday ahead in the morning is difficult. However, this blog is about wafer fabs, and let's start by saying that scheduling a wafer fab to run optimally is one of the most challenging mathematical problems that exists in modern day manufacturing. Why?

Wafer fabrication is extremely complex. Lots of wafers may re-enter tools numerous times, and compete for capacity against hundreds of other lots. Not to mention a whole host of unique scheduling constraints as well as unexpected events, such equipment suddenly going offline.

Scheduling problems are widely researched, and there are various methods used to solve them. However, in the semiconductor industry, there are two commonly debated techniques: heuristics (rules-based) and mathematical optimization.  

Both methods provide effective scheduling solutions, however, each has limitations, which is the topic of the discussion below.

Heuristics

A heuristic algorithm is essentially a ‘best-guess’ approach to a decision problem.  

By taking approximations and algorithmic shortcuts, heuristics can arrive at a final decision very quickly. Think of a heuristic as a long decision-tree of if-then logic. Heuristics are fantastic at finding realistic solutions extremely quickly. Since wafer fabs are extremely dynamic, this method is widely adopted for this reason.

However, the benefit that heuristics have on speed, gives way to its biggest flaw - solution quality. Being rules-based, it can only search through a restricted number of scenarios and follow a 'familiar' path. Hence, you never really know how good the final solution is in terms of quality (there could be a much more optimal solution available).

A heuristic simply cannot optimize a decision problem - leaving wasted productivity on the table.

Mathematical optimization

Mathematical Optimization is used when you want to find the optimal (best possible) solution.

A classic optimization problem is the ‘travelling salesman’ problem, where the objective is to seek the shortest path for a salesman to travel, given a number of nodes that must be visited. Here there is only one optimal solution, and mathematical optimization is a method of finding it.  

In wafer fab scheduling, optimization can be used to similar effect: where, as an example, the objective may be to find a schedule that minimises cycle time for both production and R&D wafers. Here, all possible scheduling scenarios can be evaluated and the best one chosen (a major benefit over heuristics, where only one schedule is evaluated and chosen).

In a fab, factory states change frequently making it an extremely dynamic environment to schedule. As a result, a scheduler must be fast enough to re-run schedules in order to cope with the factory dynamics. However, optimization algorithms need time to find the best possible solution. In practice – it might be even hours, which makes pure optimization scheduling impractical and unrealistic for wafer fabs.

Which method for high-quality wafer fab scheduling?

This is the dilemma. Heuristics are widely adopted because they are fast and realistic. But the quality of solutions is inferior compared to the potential of using an optimization technique. Pure optimization, on the other hand, is not feasible in a fast-paced live fab environment.

What is needed is a ‘best of both worlds’ approach. A scheduler that is quick, reliable and optimal. This is exactly what a hybrid-approach seeks to achieve.

In our recently published white paper, we examine a new hybrid optimization approach that enables fast and near-optimal scheduling. In this, we compare the hybrid approach with the two widely used methods described above. The white paper can be viewed and downloaded by clicking here.