Scheduling time constraints in wafer fabrication
Time constraints (also known as time links) between consecutive process steps are designed to eliminate queueing time at subsequent steps. In a highly complex wafer fabrication environment, even the most advanced fabs struggle with scheduling time constraints. While our engineering team works on applying Flexciton technology to solve the time links problem, Begun Efeoglu Sanli, our Optimisation Engineer, reviews a recently published technical paper on this particular subject.
A fab manager perspective: time constraints and a fab performance.
A silicon wafer undergoes a fabrication process by entering multiple production steps, where each step is performed by different, highly sophisticated tools. Optimizing the transition and waiting time of the lots has a huge impact not only on a fab production performance but also its profitability. As an example, by introducing time constraints at the wet etch and furnace process steps, we prevent the likelihood of oxidation and contamination. Failing to do so, risks contact failures, low and unstable yields, the consequence of which is either rework or the wafers must be scrapped. Such problems are difficult to discover during wafer processing, and to run special monitoring lots would be a considerable effort.
Yield optimization has long been considered to be one of the key goals, yet difficult to achieve in semiconductor wafer fab operations. As the semiconductor manufacturing industry becomes more competitive, effective yield management is a determining factor to deal with increasing cost pressures. Time links between consecutive process steps are one of the most difficult constraints to schedule, with a significant impact on yield management.
Some factories avoid the problem by dedicating tools to each process group that requires a previous cleaning or etch step. This strategy's obvious disadvantage is the higher demand from wet tools, which leads to higher investment, more cleanroom space, and ultimately to lower capital efficiency. The tradeoff between increasing throughput and a higher likelihood of violating lots’ time constraints is an everyday battle for fab managers trying to meet yield targets.
Technology perspective: scheduling time constraints.
An example of time constraints for a single lot is illustrated in Figure 1 below. It shows a time link system between four consecutive process steps. In this example, we can see that the lot has time links constraining Step 2 to Step 4 as well as from Step 3 to Step 4, with overlapping time lag phases (also known as a nested time link constraint). This means that after completing process Step 3, the lot begins a new time lag phase (Time Link 3) whilst already transitioning through an existing time lag (Time Link 2) started upon completion of Step 2. As you might expect, the need to simultaneously look ahead and consider future decisions whilst also being constrained by past decisions is not trivial to model well in a heuristic or as real-time dispatch rules.
Time constraints are already difficult to navigate, but nesting them adds yet another layer of complexity for heuristics to wrestle with. In the example below, if the final step cannot be brought forward, scheduling Step 3 too close to Step 2 may make it impossible to meet the "Time Link 3". It is because the time between Steps 3 and 4 is now greater than the maximum allowed. This would not be a problem if the time constraints were not nested and we only have to schedule according to the "Time Link 2".
Figure 1. An example of time constraints for a single lot
The technical paper review.
Surprisingly, although time constraints are an important topic, they have not been widely discussed in the tech literature so far. That said, an interesting paper on this topic was presented at the Winter Simulation Conference 2012 in December, by A. Klemmt and L. Mönch, “Scheduling Jobs with Time Constraints between Consecutive Process Steps in Semiconductor Manufacturing” of Infineon Technologies and University of Hagen.
The authors propose mixed-integer programming (MIP) model formulation and share some preliminary experimentation. Unfortunately, even state of the art MIP solvers can only solve problem instances up to 15 jobs and 15 machines to optimality in a reasonable amount of time.
Consequently, the authors develop two alternative approaches:
A heuristic that focuses on creating a feasible schedule where all time constraints are respected
A mathematical approach based on their MIP model that extends the heuristic in (1). The idea is to break the overall problem down into many smaller optimization problems that are easily solvable individually. These problems aim to ensure all lots are delivered on time and no time constraints are violated.
This novel decomposition approach allows for solving considerable problem instances including more than 100 machines, more than 20 steps, nested time constraints, and a large number of jobs.
The paper referenced above highlights that both approaches can provide good feasible schedules quickly and as expected, the MIP-based heuristic outperforms the simple heuristic. Nevertheless, as with most heuristic approaches, there are some important tuning parameters that might affect the schedule quality. In the paper, the lots are sorted with respect to their due dates to build subproblems. This approach could perhaps be reevaluated if cycle time is the most important KPI for a fab or if some jobs are of higher priority. Similarly, if time constraint violations are allowed to some degree, then one could relax the importance of this in the heuristic.
The most important consequence, which is also mentioned, is that the cycle time of time-constrained processes correlates highly with utilization of upstream (start of the time link) processes. This eliminates waiting time in front of the upstream tool and enables higher utilization. However, if downstream tools are bottlenecks, then WIP may have to be withheld such that time constraints are not violated by stagnating in front of busy tools.
Another tradeoff to be considered is how low-priority time-constrained steps are scheduled among high-priority non-time-constrained steps. For example, is it worth risking a time constraint violation for the sake of rushing an urgent lot through the toolset? This needs to be quantified and considered by the fab manager. Therefore, all these tradeoffs should be taken into account in order to provide the best schedule.
The Flexciton Way
At Flexciton, we include time constraints as part of our optimization engine that attempts to eliminate all violations of time links as the highest priority. Only as a last resort are time constraints relaxed if it is not possible to provide an otherwise “feasible” schedule. This could occur if the time windows provided are unrealistically short considering all operational constraints, especially tool capacities.
As mentioned in the previous publications, the Flexciton optimization engine is a multi-objective solution that can balance various KPIs according to user-chosen weights, one of which controls the degree to which violations of time constraints are penalized. The main advantage of this approach is that, with all the other competing objectives, our solution can balance throughput, cycle time and priority-weighted time constraint violations simultaneously.
Begun Efeoglu Sanli is an Optimisation Engineer at Flexciton. She holds a Master of Science, Industrial Engineering degree from Middle East Technical University. After working in academia for a few years, she joined Flexciton 3 years ago. Since then, she's been involved in developing an optimization engine of the Flexciton scheduling system.