The reticle allocation problem and how to approach it [technical paper review]
The photolithography process is considered the most critical step in semiconductor wafer fabrication, where geometric shapes and patterns are reproduced onto a silicon wafer, ultimately creating the integrated circuits.
What makes this process unique is the use of additional resources, called reticles. The reticle is a photomask used to expose ultraviolet radiation that generates a specific pattern into the wafer. When not in use, reticles are stored in dedicated storage with a fixed capacity, called a stocker. Although the problem of allocating reticles in a stocker is not a “core” one in wafer production scheduling, if not optimized, it might significantly impact overall production efficiency by causing bottlenecks.
This week, Daniel Cifuentes Daza, one of our Optimization Engineers here at Flexciton, explores this problem by reviewing a technical paper by Benzoni, A. et. al. – “Allocating reticles in an automated stocker for semiconductor manufacturing facility” – and contrasting their approach with the one we use when scheduling at Flexciton.
The reticle and stocker bottleneck:
A fab working with a wide variety of products may need several thousand reticles at any given time to fulfil their production requirements . Not only must reticles be stored in a stocker, as explained above, but they often need to be transported in a container known as a pod in order to prevent contamination too. Therefore, the capacity and availability of stockers and pods within the fab makes deciding where each reticle should be stored at each step of the production schedule extremely complex – frequently causing bottlenecks .
To manage this process, fabs need to decide the best way to allocate reticles into pods, and then try to find an optimal assignment between pods and tools. However, there is another optimization problem at hand that complicates the process further; the position of reticles within the limited-capacity compartments of the stocker itself.
The time to retrieve a reticle from storage can be drastically different depending on its own location inside the stocker, thus leading to large inconsistencies in the so-called processing time of the stocker. As a result, the stocker can become a bottleneck by not dispensing reticles fast enough to meet wafer demand. Therefore, the reticle allocation problem also consists of choosing which reticles are to be stored in the low-capacity fast-retrieval compartment (“retpod”) vs the high-capacity slow-retrieval compartment.
In order to explore what might be the best way to address this problem, we have reviewed a tech paper published by IEEE for the WSC conference in 2020. The authors of the paper address the allocation issue using the famous knapsack problem. This approach will be evaluated in the next section of this article – with the pros and cons being discussed – before discussing how the proposed solution compares to how we model photolithography tools here at Flexciton.
The reviewed paper approach:
In “Allocating reticles in an automated stocker for semiconductor manufacturing facility” by Benzoni, A. et. al. (2020)  the stockers examined by the authors have two compartments – one where reticles are stored using pods; retpod, and another where they do not use pods. The main objective is to allocate reticles into the retpod compartment, as this has faster retrieval times.
Additionally, the authors consider:
(1) the reticles, as the main resource of the problem,
(2) the steps where wafers will need to use the reticles in the near future, and
(3) the capacitated storage for reticles; the compartments of the stockers. Additionally, they see each reticle as having a profit value; the number of wafers processed in the batch. With this initial information, the problem can be modelled as the well-known knapsack problem.
Sheveleva, A. et. al (2021)  defines the knapsack problem as the following:
“There are k items with weight nk and value ck, and a knapsack with a capacity N. The problem is to fill the knapsack with items with the maximum total value, respecting the knapsack’s capacity limit”
In this case, each k item is a reticle, where its corresponding weight is always 1, and its value ck refers to the profit value. The knapsack is the retpod compartment of the stocker.
The knapsack problem is an NP-hard combinatorial problem that has been studied for many years within computer science, operations research, and other sciences. Therefore, due to its complexity, the authors decided to use a well-known heuristic. Here, the approach is to rank each reticle according to a specified objective value ratio and then fill the knapsack with the first N elements fulfilling its capacity.
The authors benchmarked three different objective functions for this heuristic as follows:
Reticles are ranked according to their priority and their probability of being used soon. Reticles required by wafers in the short term have higher priority than those needed in wafers for later steps.
Similar to (1), but the ranking also considers the total number of wafers that each reticle is being used by.
Ranks reticles by the priority and probability of the reticle to be used, but only considers the most immediate reticles being used by at least one wafer.
The three approaches reported an increase in the utilisation of the reticles from around 8% to 20%. This implementation also led to a reduction of processing times for the stockers of 1 hour. Strategies 1 and 2 showed the lowest error percentage, which is expected as Strategy 3 does not consider future steps where reticles are used.
Using the knapsack approach to solve this problem certainly has some positive points. Firstly, using a heuristic method is easy to implement and does not require much computational time, which also makes it scalable to industrial-sized problems. Secondly, it is trivial to work out why certain allocation decisions are taken, making it highly understandable. Lastly, the approach is flexible because the user can modify the objective function of the heuristic depending on the fab’s goals.
However, the issue of reticle allocation is just a small piece of the complex wafer manufacturing process. Since this approach is modelled as a standalone problem, it is creating feasible solutions for the reticle stocker alone without considering the state of the rest of the fab. This will likely lead to inconsistencies as the wafer schedule is intrinsically linked to the reticle allocation.
In addition, the approach described in the paper models a simplification of the photolithography area. There is relevant information missing, such as the availability of pods in the fab and their possible allocation to machines, transfer times, and load and unload times. The use of this information would give robustness to the approach.
At Flexciton, we consider that the best way to tackle the reticle allocation problem is to proactively generate not only feasible solutions, but optimized production schedules. In order to do this, we take into account all the scheduling constraints for reticles available within our optimization engine – using information such as:
Availability and capacity of pods for reticles
The scheduling of pod usage – taking into account the number of pod ports in the machine
Storage of pods into stockers, considering its capacity
Transition of pods between stocker and machine
Load, and unload times for reticles into pods and pods into machines
Variable stocker unload time on account of where the reticles are located
The reticles and pods already loaded into the machines; where they are in the fab at the time of scheduling
The benefit of considering a multitude of information like this all in one optimization model means that we can provide a consistent and robust production schedule that takes into account all the constraints of reticles, pods and stockers. Additionally, our scheduler allows the user to configure their specific business objectives into the optimization process in order to meet their fab’s KPIs – the algorithm is then calculated and an optimized schedule is returned in a matter of minutes. All of this means that our technology is able to return a reliable, scalable and flexible solution that is tailored to our client’s needs – whilst optimizing the photolithography area in its entirety.
Daniel Cifuentes Daza is an Industrial Engineer with a background in Operations Research and Data Science. He has been involved with combinatorial optimization problems, such as Scheduling and Routing, for the past two years and has recently been supporting the development of Flexciton’s scheduling engine as an Optimization Engineer.
 Y. T. Lin, C. C. Hsu and S. Tseng, "A Semiconductor Photolithography Overlay Analysis System Using Image Processing Approach," Ninth IEEE International Symposium on Multimedia Workshops (ISMW 2007), 2007, pp. 63-69, doi: 10.1109/ISM.Workshops.2007.16.
 S. L. M. de Diaz, J. W. Fowler, M. E. Pfund, G. T. Mackulak and M. Hickie, "Evaluating the impacts of reticle requirements in semiconductor wafer fabrication," in IEEE Transactions on Semiconductor Manufacturing, vol. 18, no. 4, pp. 622-632, Nov. 2005, doi: 10.1109/TSM.2005.858502.
 You-Jin Park and Ha-Ran Hwang, "A rule-based simulation approach to scheduling problem in semiconductor photolithography process," 2013 8th International Conference on Intelligent Systems: Theories and Applications (SITA), 2013, pp. 1-4, doi: 10.1109/SITA.2013.6560788.
 A. M. Sheveleva and S. A. Belyaev, "Development of the Software for Solving the Knapsack Problem by Solving the Traveling Salesman Problem," 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), 2021, pp. 652-656, doi: 10.1109/ElConRus51938.2021.9396448.
 A. Benzoni, C. Yugma, P. Bect and A. Planchais, "Allocating Reticles in an Automated Stocker for Semiconductor Manufacturing Facility," 2020 Winter Simulation Conference (WSC), 2020, pp. 1711-1717, doi: 10.1109/WSC48552.2020.9383933.