Evolutionary optimization of dispatch rule parameters

Hi, my name is Harel Yedidsion and I’m part of the AI/ML group at Applied Materials. The work I’ll present here was done jointly with my colleagues Derek Adams, David Norman, and Emrah Zarifoglu. The work is titled Evolutionary Optimization of Dispatch Rule Parameters. The agenda of this talk is as follows.

I’ll give a brief introduction to the semiconductor manufacturing process and the dispatch rule used to schedule lots in the fab. I’ll introduce our method for tuning the dispatch rules parameters, and I’ll show some empirical results comparing our method to a baseline method.

A bit of background, Applied Materials supplies equipment, services, and software for the manufacture of semiconductor chips. As you may know, there is a global shortage of chips, and FABs are struggling to supply the demand. Building new fabs is expensive and costs billions of dollars.

That is why we focus our attention on improving the efficiency of existing fabs. In the semiconductor fabrication process, wafers go through multiple steps and pass between stations. A typical route consists of 600 to 1500 steps.

A full production cycle can take up to two months. Scheduling the lots in a fab can have a dramatic effect on the fab’s efficiency. This type of scheduling process is called flow shop with job re-entry.

It is notoriously difficult to model and to solve efficiently, and in practice, heuristic dispatch rules are commonly used to schedule the lots in the FABs. The dispatch rule uses heuristic logic to rank the lots in the queue in front of each station. The rule is triggered approximately 2.5 million times in 90 days of operation.

It has about 80 parameters, both continuous, discrete, and nominal, and the parameter’s values can drastically affect the Key Performance Indicators, or KPIs. Some common KPIs which are used to measure the fab’s efficiency are on-time percentage, cycle time, lot late hours, average daily moves, Work In Progress or WIP, and number of lots completed. We’ll focus our attention on on-time percentage and average cycle time.

The problem we are addressing is how to tune the parameter’s values. Finding the optimal combination for every fab condition is computationally intractable. One possible solution is to use simulation optimization with the AutoSketch fab simulator, where in each simulation we choose a different combination of parameter values and measure the resulting KPIs.

However, simulating 90 days of operation takes about 10 hours, and we need at least 90 days to calculate meaningful KPIs. To mitigate that, we developed an efficient parameter tuning method based on Evolutionary Optimization combined with Simulated Annealing. Here I’ll show an example of how parameter values are optimized using grid search, which is a method we use to benchmark our proposed Evolutionary Optimization method.

We chose four parameters that we found to have significant impact on KPIs. The line balance parameters determine when to prioritize lots based on the work-in-progress in their next bottleneck stations. If a lot’s next bottleneck station is start, then that lot will get priority and will be processed first in its current step, so that it can quickly reach the start bottleneck station.

The idea is that bottleneck stations have to be running at full capacity to maximize throughput. In grid search, we discretize the range that each parameter value can take. Then we sample a different combination of values at each run, and each chosen combination is run for 90 days of simulation and its KPIs are measured.

This figure shows how different combinations of parameter values can generate significant differences in KPIs. We are interested in parameter values that produce a low cycle time, high on-time percentage, and a high number of lots completed, like the bunch marked and read here. To reiterate the problem and to give some more motivation, even if we discretize the parameters range, the number of combinations is infinitely large, and each run takes 10 hours.

Therefore, we cannot evaluate many combinations in a reasonable time. But can we find a better way than Grid search to optimize the parameters values? We propose a simulation optimization approach that uses Evolutionary Optimization combined with Simulated Annealing. Our approach is more efficient than grid search because it focuses on areas of the search space where good solutions were found.

Evolutionary strategy is an optimization algorithm of this form. In the first iteration, generate the initial population of individuals randomly. Then, repeat the following steps until termination.

Evaluate the fitness of each individual in the population. In our case, we’ll evaluate the KPIs at cycle time and on-time percentage. Then, select the fittest individuals for reproduction, the parents.

Bring new individuals through mutation and crossover of the parents. We combine this approach with Simulated Annealing. which is an exploration technique which gradually decreases the probability of accepting worse solutions. We use simulated annealing in the regeneration process by gradually reducing the range from which offspring are created. We basically reduce the strength of the mutation as the search goes on. Here is an example of how we implement our search algorithm on a parameter called Line Balance Threshold 1. We start from choosing a value randomly from the full range of possible values 0 to 24.

We evaluate the solutions and center the next range to pick from around the best solution found so far. We repeat the process and in each iteration the range size decreases. We stop when there is no more improvement in the solution values.

We compare our results with the best results obtained from 300 Grid search runs. The grid search samples solutions uniformly at random from all possible parameter values. The best average cycle time is 922 hours, which is approximately 40 days, and the best on-time percentage is 86.9 percent.

Here we can see the performance of Evolutionary Optimization, which found a better solution in two iterations, where each iteration is 12 runs, and it reached the solution of 902 hours of cycle time compared to 922 hours found by grid search in 300 runs.

Also for the on-time percentage KPI, Evolutionary Optimization reached a better solution than grid search in less than half the number of runs with 88.2 percent on-time percentage compared to 86.9 percent found by grid search. In addition to optimizing continuous value parameters, our approach can also optimize nominal value parameters.

In this example, we optimize which station families should be considered as bottleneck stations. We first rank the stations based on these criteria average WIP, percent of idle time, and average cycle time. And we took the top eight to be possible candidates, out of which in each run we choose only three.

The ones marked in blue were the originally the bottleneck station families. So in each run we chose three out of the top eight candidates, and in each iteration we adjusted the probability of choosing a station family based on its frequency of occurrence in the top runs of previous iterations. Then we combined the optimization of continuous parameters, a line balance parameters, and the nominal parameters, the bottleneck station parameters. And we optimized them jointly using Evolutionary Optimization and measured the on-time percentage KPI. In this figure we can see the best on-time percentage KPI for each iteration. Each iteration consists of 20 simulation runs.

In each run we vary both the line balance parameter values and the combination of bottleneck station families. By the ninth iteration, the on-time percentage reached 98.83 percent, which is a huge improvement compared to 88.2 from optimizing line balance separately, and 86.9 which grid search got. The same thing happened with cycle time.

Here again we jointly optimized the line balance parameters and the bottleneck stations using Evolutionary Optimization while measuring the average cycle time KPI. In this figure we can see that the best cycle time in each iteration goes down. Each iteration is 20 runs, and in each run we vary both the line balance parameters and the combination of bottleneck station families.

By the seventh iteration, the cycle time reached 886 hours, which is a huge improvement compared to 902 obtained from optimizing line balance separately, and much better than the 922 obtained from 300 grid search runs. So what we can see is that jointly optimizing continuous and nominal parameters using Evolutionary Strategy can reach very good KPI values. To conclude, optimizing the dispatch rules parameters requires testing an exponential number of combinations.

To mitigate that, we developed an efficient method for finding good combinations. Our method is a Simulation Optimization method, which uses Evolutionary Strategy and Simulated Annealing. Our method can handle both continuous and nominal parameter values, and we demonstrate how it outperforms Grid search on two KPIs, the average cycle time and the on-time percentage. The main advantage of our method is that it zooms-in on good solutions quickly and narrows the search space to candidate solutions in their vicinity. The main takeaway is that our approach allows finding better solutions with less simulation runs. With that, I will conclude, and I thank you very much for listening.