Noncyclic Scheduling for Timed Discrete-Event Systems With Application to Single-Armed Cluster Tools Using Pareto-Optimal Optimization

Abstract

Recently, semiconductor manufacturing fabs tend to reduce the wafer lot size, down to just a few. Consequently, the wafer recipe or wafer flow pattern changes frequently. For such problems, it is impossible to apply conventional prevalent cyclic scheduling methods that repeat processing of wafers in an identical cyclic tool operation sequence. We therefore consider the noncyclic scheduling problem of single-armed cluster tools that process wafers with different recipes. Our proposed method is to transforms the problem into a multiobjective problem by considering the ready times of the resources as objectives to minimize. Only feasible states are generated based on the initial state of the system. These feasible states form a multiobjective shortest path problem and give us O((r + 1)(m)n) as an upper bound for the number of states, where r, n, and m are the number of different wafer recipes, wafers, and processing chambers. We solve this problem with implicit enumeration by making our scheduling decisions based on the Pareto optimal solutions for each state. The experimental results show that the proposed algorithm can quickly solve large sized problems including ones with arbitrary initial tool states, changing recipes, reentrant wafer flows, and parallel chambers.