Scheduling analysis of time-constrained dual-armed cluster tools

Cluster tools, each of which consists of several single-wafer processing chambers and a wafer handling robot, have been increasingly used for diverse wafer fabrication processes. Processes such as some low pressure chemical vapor deposition processes require strict timing control. Unless a wafer processed at a chamber for such a process leaves the chamber within a specified time limit, the wafer is subject to quality problems due to residual gases and heat. We address the scheduling problem for such time-constrained dual-armed cluster tools that have diverse wafer flow patterns. We propose a systematic method of determining the schedulable process time range for which there exists a feasible schedule that satisfies the time constraints. We explain how to select the desirable process times within the schedulable process time range. We present a method of determining the tool operation schedule. For more flexible scheduling under the time constraints, we propose a modification of the conventional swap operation in order to allow wafer delay on a robot arm during a swap operation. We compare the performance of the new swap strategy with that of the conventional swap strategy.     

An optimal residency-aware scheduling technique for cluster tools with buffer module

Cluster tools provide a flexible, reconfigurable, and efficient environment for several manufacturing processes (e.g., semiconductor manufacturing). A new timing constraint (distinct from a simple deadline), referred to as residency constraint, puts a timing limit on the time that a wafer can stay in a processing module in a cluster tool. The authors demonstrate that a solution that does not address residency constraints can be found easily. However, when residency constraints are added to the model, the problem becomes complex and a scheduling technique may spend a long time searching for a good solution. Also, in some cases, one may need to decrease throughput to satisfy residency constraints. The authors introduce a new technique to address cluster tool scheduling in the presence of residency constraints. The proposed technique uses a buffer resource for temporarily holding wafers to release other resources such as the robot arm. This resource is usually available in the tool for maintenance reasons. A tradeoff is discussed in using the buffer resource and a scheduling algorithm is presented that will use this resource when it can help to increase throughput under residency constraints. The experiments show that in many cases that are common in semiconductor manufacturing, use of their proposed technique can improve throughput.     

Analysis of Wafer Sojourn Time in Dual-Arm Cluster Tools With Residency Time Constraint and Activity Time Variation

When scheduling cluster tools under wafer residency time constraints, wafer sojourn time in a processing module should be carefully controlled such that it is in a permissive range. Activity time variation often results in wafer sojourn time fluctuation and makes an originally feasible schedule infeasible. Thus, it is very important to know how the wafer sojourn time changes when activity time varies. With bounded activity time variation considered, this paper conducts a detailed analysis of wafer sojourn time variation in dual-arm cluster tools. To do so, a Petri net (PN) model and a real-time control policy are presented. Based on the PN model, real-time operational architecture, and real-time control policy, this paper analyzes the effect of activity time variation on wafer sojourn time delay at a process module and presents its upper bounds. The upper bounds are given in an analytical form and can be easily evaluated. With the wafer sojourn time analysis, it is possible to develop an effective method for schedulability analysis and optimal steady-state scheduling. An example is used to show the applications of the proposed approach.      

Scheduling single-armed cluster tools with reentrant wafer flows

A cluster tool for semiconductor manufacturing consists of several single-wafer processing chambers and a wafer-handling robot in a closed environment. The use of cluster tools is extended to reentrant processes such as atomic layer deposition, where a wafer visits a processing chamber more than once. Such a reentrant wafer How complicates scheduling and control of the cluster tool and often causes deadlocks. We examine the scheduling problem for a single-armed cluster tool with various reentrant wafer flows. We develop a convenient method of modeling tool operational behavior with reentrant wafer flows using Petri nets. By examining the net model, we then develop a necessary and sufficient condition for preventing a deadlock. We also show that the cycle time for the asymmetric choice Petri net model for a reentrant wafer How can be easily computed by using the equivalent event graph model. From the results, we systematically develop a mixed integer programming model for determining the optimal tool operation sequence, schedule, and cycle time. We also extend a workload measure for cluster tools with reentrant wafer flows. Finally, we discuss how our results can be used for engineering a cluster tool. We compare two proposed strategies, sharing and dedicating, of operating the parallel processing chambers for identical process steps.     

Online Scheduling of Integrated Single-Wafer Processing Tools With Temporal Constraints

This paper addresses the issues of online scheduling for integrated single-wafer processing tools with temporal constraints. The integrated single-wafer processing tool is an integrated processing system consisting of single-wafer processing modules and transfer modules. Certain chemical processes require that the wafer flow satisfies temporal constraints, especially, postprocessing residency constraints. This paper proposes an online scheduling method that guarantees both logical and temporal correctness for the integrated single-wafer processing tools. First, mathematical formulation of the scheduling problem using temporal constraint sets is presented. Then, an online, noncyclic scheduling algorithm with polynomial complexity is developed. The proposed scheduling algorithm consists of two subalgorithms: FEASIBLE_SCHED_SPACE and OPTIMAL_SCHED. The former computes the feasible solution space in the continuous time domain, and the latter computes the optimal solution that minimizes the completion time of the last operation of a newly inserted wafer.     

Multicluster tools scheduling: an integrated event graph and network model approach

Steady-state throughput and scheduling of a multicluster tool become complex as the number of modules and clusters grows. We propose a new methodology integrating event graph and network models to study the scheduling and throughput of multicluster tools. A symbolic decision-move-done graph modeling is developed to simplify discrete-event dynamics for the multicluster tool. This event graph is further used for searching feasible action sequences of the cluster tool. By representing sequences with networks, an extended critical path method is applied to calculate the corresponding cycle time. Grouping methods that are based on network are also introduced to reduce the searching complexity. Compared with optimization-based scheduling approaches, the proposed methodology can directly capture the cyclic characteristic of cluster tool schedules and be applied to analyze the impact of process and wafer flow variations on cycle time and robot schedules. We have successfully applied this new methodology to dozens of cluster tools at Intel Corporation. A chemical-mechanical planarization polisher is employed as an example to illustrate and validate the proposed methodology.     

A steady-state throughput analysis of cluster tools: dual-bladeversus single-blade robots

An analysis of throughput in a cluster tool with a dual-blade robot operating in steady-state mode is presented. The analysis is based on a single-wafer serial processing cluster tool. Two types of schedules are distinguished, called transport-bound schedules and process-bound schedules. In a transport-bound schedule changes in process times do not affect the throughput of the cluster tool, and denotes the maximum throughput achievable in the cluster tool. In a process-bound schedule, the process time predominates the effect on the throughput. The analysis indicates that a dual-blade robot improves the throughput of the cluster tool over a single-blade robot under process-bound conditions. Under process-bound conditions, a cluster tool with a single-blade robot would need to double the speed of the robot, compared with a dual-blade robot of equivalent speed, to achieve similar throughput. Under transport-bound conditions, the throughput of the cluster tool is the same for both dual-blade and single-blade cluster tools     

A Multiagent-Based Decision-Making System for Semiconductor Wafer Fabrication With Hard Temporal Constraints

This paper presents a decision-making system for semiconductor wafer fabrication facilities, or wafer fabs, with hard interoperation temporal constraints. The decision-making system is developed based on a multiagent architecture that is composed of scheduling agents, workcell agents, machine agents, and product agents. The decision-making problem is to allocate lots into each workcell to satisfy both logical and temporal constraints. A dynamic planning-based approach is adopted for the decision-making mechanism so that the dynamic behaviors of the wafer fab such as aperiodic lot arrivals and reconfiguration can be taken into consideration. The scheduling agents compute quasi-optimal schedules through a bidding mechanism with the workcell agents. The proposed decision-making mechanism uses a concept of temporal constraint sets to obtain a feasible schedule in polynomial steps. The computational complexity of the decision-making mechanism is proven to be, where is the number of operations of a lot and is the cardinality of the temporal constraint set.     

Scheduling Tests for 3D Stacked Chips under Power Constraints

This paper addresses Test Application Time (TAT) reduction under power constraints for core-based 3D Stacked ICs (SICs) connected by Through Silicon Vias (TSVs). Unlike non-stacked chips, where the test flow is well defined by applying the same test schedule both at wafer sort and at package test, the test flow for 3D TSV-SICs is yet undefined. In this paper we present a cost model to find the optimal test flow. For the optimal test flow, we propose test scheduling algorithms that take the particulars of 3D TSV-SICs into account. A key challenge in testing 3D TSV-SICs is to reduce the TAT by co-optimizing the wafer sort and the package test while meeting power constraints. We consider a system of chips with cores that are accessed through an on-chip JTAG infrastructure and propose a test scheduling approach to reduce TAT while considering resource conflicts and meeting the power constraints. Depending on the test schedule, the JTAG interconnect lines that are required can be shared to test several cores. This is taken into account in experiments with an implementation of the proposed scheduling approach. The results show significant savings in TAT.     

基于随机高级Petri 网的主动自调度集群系统的性能分析

首先在体系结构上对主动自调度集群系统(ASACS)与传统Web集群服务器系统进行了比较;然后提出了主动自调度集群系统的随机高级Petri网(SHLPN)模型,并设计了模型的精化方案;接着为传统Web服务器集群系统中2种负载均衡调度策略和ASACS的主动自调度策略进行了建模;最后利用SPNP工具对服务器集群系统中的3种调度策略在吞吐量、响应时间及拒绝概率等性能上作了数值分析,发现采用主动自调度策略实现的集群系统能更好地满足QoS的要求。     

集束型半导体制造设备的预防维修计划优化

研究了生产200mm以上晶圆的半导体制造企业中的主要设备--集束型设备(cluster tools)的预防维修计划优化问题.基于半导体集成电路生产线的复杂性及集束型设备的特点,建立了基于系统观的集束型设备预防维修计划实时优化模型,设计了用遗传算法求解模型的方法,最后以一个实例及运行结果说明了研究的实用性.     

Optimal scheduling techniques for cluster tools with process-module and transport-module residency constraints

This paper discusses two scheduling techniques for dual-arm cluster tools that address both process-module and transport-module residency constraints and throughput requirements. The first technique is the extension of our previous work that only addressed process-module residency constraints. For cases with long process times, this technique can take a long time to find the solution and is not practical. Hence, we use this algorithm mainly as a benchmark for comparison. The second technique that uses a linear programming technique with use of several heuristics can find the optimal solution very efficiently. Analytical and experimental analysis of this technique shows the correctness, completeness and efficiency of this technique.     

A genetic algorithm approach to a general category projectscheduling problem

A genetic algorithm (GA) approach is proposed for the general resource-constrained project scheduling model, in which activities may be executed in more than one operating mode, and renewable as well as nonrenewable resource constraints exist. Each activity's operation mode has a different duration and requires different amounts of renewable and nonrenewable resources. The objective is the minimization of the project duration or makespan. The problem under consideration is known to be one of the most difficult scheduling problems, and it is hard to find a feasible solution for such a problem, let alone the optimal one. The GA approach described in this paper incorporates problem-specific scheduling knowledge by an indirect chromosome encoding that consists of selected activity operating modes and an ordered set of scheduling rules. The scheduling rules in the chromosome are used in an iterative scheduling algorithm that constructs the schedule resulting from the chromosome. The proposed GA is denoted a hybrid GA (HGA) approach, since it is integrated with traditional scheduling tools and expertise specifically developed for the general resource-constrained project scheduling problem. The results demonstrate that HGA approach produces near-optimal solutions within a reasonable amount of computation time     

Cooperative scheduling and its application to steelmaking processes

A cooperative approach to scheduling problems is proposed, and its application to creating daily schedules for steelmaking processes is described. In cooperative scheduling, procedures, rules, and the user cooperate to make a feasible schedule efficiently. The procedures, collectively called a scheduling engine, work as a local constraint satisfier to solve general primitive constraints. Rules that represent domain-dependent knowledge then solve the domain-specific constraints by means of a pattern-matching function. The user evaluates the schedule and modifies it by means of a user-friendly interface with direct-manipulation functions. The user interaction is therefore included in the system architecture as a global constraint satisfier. The iteration of this cycle improves the schedule until it becomes feasible. Experimental results obtained with Scheplan, the scheduling environment that applies this approach to scheduling steelmaking processes, show that the daily scheduling time is much less than in manual scheduling and the quality of the schedule is much improved     

Single-wafer cluster tool performance: an analysis of the effectsof redundant chambers and revisitation sequences on throughput

Recent trends in the semiconductor industry indicate the need to explore alternatives to batch-wafer manufacturing. One proposed alternative is a micro-factory based on cluster tools. This paper presents an analysis of the effect of redundant chambers and chamber revisitation process sequences on the throughput in an individual cluster tool. Theoretical models which quantify the time required to process a lot of wafers in a cluster tool are developed for these situations. The differences between scheduling algorithms which use the load-lock as a queue and those that do not are also explored. Finally, the models developed in the work are integrated into a model which bounds the minimum theoretical turn-around-time which can be achieved in a cluster based fab     

Scheduling of mask shop E-beam writers

Reducing wafer fabrication cycle time and providing on-time wafer deliveries are among the top priorities of semiconductor companies. Mask manufacturing is essential to the overall wafer fabrication process since on-time delivery of masks significantly affects wafer fabrication cycle times. Moreover, delivering wafers on time means deliveries of masks must be on time as well. This research studies the scheduling problem of the bottleneck machine-the Electrical Beam (E-beam) Writer-of a mask shop. The criterion of minimum total tardiness is used as our performance measure to schedule this bottleneck operation. Using a predetermined Earliest-Due-Date (EDD) dispatch policy set by management, this study first addresses the problem of scheduling batches of a single mask size on a single machine. The approach is extended to the problem of scheduling batches of two mask sizes on a single machine; finally, a heuristic for a multiple-machine problem is developed. For the problem of a single machine under EDD dispatching policy, the problem can be formulated as a Dynamic Program (DP). Thus, it can be solved for an optimal solution in polynomial time. For the multiple machines problem, we heuristically allocate the masks to each machine. Each machine with allocated masks can then be solved by the DP formulation designed for the single machine problem. Based on the computational experiments in this study, the proposed DP approach reduces total tardiness by an average of 55% from the method currently in use at a major IC manufacturing foundry. Furthermore, in the case that due dates are set realistically, the DP approach reduces the tardiness about 95% from the shop's current method and about 88% from a simple full-batch method of scheduling     

Due-date based scheduling and control policies in a multiproductsemiconductor wafer fabrication facility

This paper focuses on lot release control and scheduling problems in a semiconductor wafer fab producing multiple products that have different due dates and different process flows. For lot release control, it is necessary to determine the type of a wafer lot and the time to release wafers into the wafer fab, while it is necessary to determine sequences of processing waiting lots in front of workstations for lot scheduling. New dispatching rules are developed for lot release control and scheduling considering special features of the wafer fabrication process. Simulation experiments are carried out to test the dispatching rules. Results show that lot release control and lot scheduling at photolithography workstations are more important than scheduling at other workstations. Also, it is shown that new dispatching rules work better in terms of tardiness of orders than existing rules such as the EDD (earliest due date) rule and other well-known dispatching rules for multimachine scheduling     

On the hard-real-time scheduling of embedded streaming applications

In this paper, we consider the problem of hard-real-time (HRT) multiprocessor scheduling of embedded streaming applications modeled as acyclic dataflow graphs. Most of the hard-real-time scheduling theory for multiprocessor systems assumes independent periodic or sporadic tasks. Such a simple task model is not directly applicable to dataflow graphs, where nodes represent actors (i.e., tasks) and edges represent data-dependencies. The actors in such graphs have data-dependency constraints and do not necessarily conform to the periodic or sporadic task models. In this work, we prove that the actors in acyclic Cyclo-Static Dataflow (CSDF) graphs can be scheduled as periodic tasks. Moreover, we provide a framework for computing the periodic task parameters (i.e., period and start time) of each actor, and handling sporadic input streams. Furthermore, we define formally a class of CSDF graphs called matched input/output (I/O) rates graphs which represents more than 80 % of streaming applications. We prove that strictly periodic scheduling is capable of achieving the maximum achievable throughput of an application for matched I/O rates graphs. Therefore, hard-real-time schedulability analysis can be used to determine the minimum number of processors needed to schedule matched I/O rates applications while delivering the maximum achievable throughput. This can be of great use for system designers during the Design Space Exploration (DSE) phase.     

Single-wafer cluster tool performance: an analysis of throughput

Cluster tools gained greater acceptance over the past several years, although concerns still exist over the throughput these tools can achieve. This paper presents an analysis of the relationship between process times, transport times, and maximum throughput in an individual cluster tool. Theoretical models which quantify the time required to process both an individual wafer and a lot in a cluster tool are developed. Three techniques for increasing throughput, based on these models, are also presented. These modifications require minimal modification of many existing designs and can yield significant increases in performance     

Modeling and performance analysis of cluster tools using Petri nets

The performance of cluster tools is gaining ever-increasing importance as the semiconductor industry migrates to larger wafer sizes, and smaller device geometries. Customers demand higher throughput-to-footprint ratios for semiconductor equipment. Cluster tool throughput is the outcome of complex interactions of various subsystems, and there is a critical need for appropriate tools that aid in understanding these interactions, and their effects on throughput. Current methods for throughput analysis are not very well oriented toward understanding the dynamics in cluster tool processing. In this paper we present a procedure to model cluster tools using Petri nets. These models help designers to comprehend the flow of wafers during processing. While Petri nets have been used extensively in the modeling and analysis of diverse manufacturing processes/systems, this to the best of our knowledge is the first attempt to specifically model cluster tools. A state cycle analysis is discussed next; this method enables equipment designers to extract steady state throughput information, as well as understand the interplay of subsystems during the wafer Row. Two example configurations are used to illustrate Petri net-based model building and analysts. These two examples encompass a variety of design features found in the industry today, e.g., sequential and parallel processing, single and dual end effector robots, anticipatory and simple scheduling