Petri Net-Based Optimal Scheduling And Control Of Multi-Cluster Tools

In semiconductor manufacturing, to ensure a high quality and precision, cluster tools with single wafer processing technologyare widely adopted to process wafers. A typical cluster tool is composed of a wafer handling robot,one or two loadlocks and, a few of process modules to process wafers. In recent years, with the waferfabrication processes become more and more complicated, multi-cluster tools are used to accommodate the industrial needs. They are composed of several single-cluster tools connected by buffering modules with a linear or tree-like topology.As a multi-cluster tool is extremly expensive, it is very significant to developan efficient way to schedule and control it.To schedule such a tool,the main complexity comes from the interaction dependency among the individual tools andone needs to coordinate the multi-robot activities for accessing the buffering modules.Considering the robot moving times, this thesis focuses on the scheduling problem of two types of process-dominant multi-cluster tools, one is single-arm linear multi-cluster tools with two-space buffering modules and the other is hybrid linear multi-cluster tools with one-space buffering modules. For the former, existing work shows that with a deeomposition way, the system can always reach the lower bound of cycle time, however, it fails to present a schedule to realize it and how can the system reach the steady state from the initial transient process remains unsolved. For the latter, to the best knowledge of the authors, there is no research report on the scheduling analysis of hybrid mutli-cluster tool that consists of both single and dual-arm tool. Although existing studiesderive the optimal k-wafer (k?2) cyclic scheduling for single-arm linear multi-cluster tools with one-space buffering modules, compared with one-wafer cyclic scheduling,a k-wafer cyclic one has many drawbacks, such as difficulty for control and implementation, and its fatal drawback is that, in some cycles, the processed wafers have a longer wafer residency time, leading to an easy violation of wafer residency time constraints.Scheduling a multi-cluster tool is shown to be NP-hard.It is very significant in the sense of both theory and practical applications to obtain an efficient way to schedule such asystem. This thesis focuses on the scheduling and control problem of linear multi-cluster tools. AsPetri net is an effective tool for handling event-driven systems, it is widely adopted for modeling, analysis, and control of manufacturing systems.This thesis uses Petri net to model a multi-cluster tool as a multi-robot manufacturing system. Based on the developed Petri net models, the following studies are conducted:1) Optimal one-wafer cyclic scheduling of single-arm multi-cluster tools with two-space buffering modules. To explore the effect of two-space buffering modules on the performance of a multi-cluster tool, first,Petri net model is developed to model the tool. The dynamic behavior of robot waiting and tasks, process modules and buffers is well described by the Petri net model. With the model, this thesis shows that there is always a one-wafer cyclic schedule that reaches the lower bound of cycle time of a process-dominant tool. Furthermore, an efficient algorithm is developed to find such a schedule for the first time for such multi-cluster tools. Finally, illustrative examples are given to show the application and power of the proposed method;2) Optimal one-wafer cyclic scheduling of hybrid multi-cluster tools with one-space buffering modules.To obtain an optimal one-wafer cyclic schedule for hybrid multi-cluster tools, first, a Petri net model is developed for the system. Based on it, necessary and sufficient schedulability conditions under which there is a one-wafer cyclic schedule that reaches the lower bound of cycle time are proposed. Furthermore, an efficient algorithm is given to check whether such a one-wafer periodic schedule exists. If so, it is found via simple calculation. Otherwise, if the conditions are violated, this thesis develops algorithms to find the minimal cycle time and the optimal one-wafer cyclic schedule. It is computationally efficient and easy-to-implement in practice. Examples are given to show the application and effectiveness of the proposed method;3) Optimalone-wafer cyclic scheduling of time-constrained hybrid multi-cluster tools.Scheduling a multi-cluster tool with wafer residency time constraints is highly challenging yet important in ensuring high productivity of wafer fabrication. Based on the obtained optimal one-wafer cyclic schedule, this thesisintends to establish the necessary and sufficient conditions under which there is a feasible one-wafer cyclic schedule and derive the algorithm to find such a schedule if exisiting. To do so, a Petri net is developed to model its dynamic behavior. By using this model, its schedule is found and analytically expressed as a function of robots' waiting time. In addition, this thesis developes the necessary and sufficient conditions under which a feasible one-wafer cyclic schedule exists and efficient algorithms to find such a schedule that is optimal. These algorithms require one to determine the robots' waiting time via simple calculation and thus are efficient. Examples are given to show the application and effectiveness of the proposed method.