In cluster tools widely used for semiconductor manufacturing, a wafer processed in a chamber should wait until a robot arm unloads it. Such wafer delays degrade the wafer quality due to residual chemicals and heat and hence cause quality variability and even failures. To prevent excessive wafer delays and their variability for single-armed and dual-armed cluster tools, we propose a simple, effective, and robust feedback control method called Kanban feedback control(KFC) that postpones a wafer loading task until a completion event of an associated task triggers it. We model the feedback control design problem as a problem of adding a feedback path between a pair of transitions to regulate token delays at a place in a timed event graph model. We develop closed formulae for wafer delays of the tools with KFC. We prove that KFC minimizes the worst-case wafer delay. We also prove that KFC makes the tool have a unique 1-cyclic schedule with constant wafer delays and ensures strong stability that recovers the same 1-cyclic schedule and the constant wafer delay at each chamber in a few cycles after a time disruption. By experimentation, we verify that KFC significantly reduces wafer delays and robustly regulates wafer delays and even cycle times against persistent time variation and significant sporadic time disruptions. Note to Practitioners—As circuit widths shrink to a few nanometers and chip architectural complexity soars up due to FinFET, GAA, and high-rise circuit stack-ups, quality risk in wafer fabrication processes surges. Therefore, wafer delays within a chamber after processing can cause more serious quality variations and failures. We propose a simple, effective, and robust way of regulating wafer delays. It can significantly contribute to yield enhancement.

A cluster tool, widely used for semiconductor wafer fabrication, consists of several single-wafer processing chambers and a wafer handling robot. A chamber for critical processes is periodically cleaned for removing chemical impurities to reduce quality risk due to extreme circuit width shrinkage. We examine the problem of determining a cleaning plan for dual-armed cluster tools with general chamber cleaning periods$k_{i} > 1$for chamber$i$using the popular swap sequence to minimize the cycle time. We derive conditions for which the popular swap sequence minimizes the tool cycle time regardless of the cleaning plan. For the other cases, we develop a cleaning rule named DGC(Dispersing and Gathering Cleaning) that disperses cleaning operations along the robot cycle and gathers the cleaning operations that are interlaced along the robot cycle. For parallel flows with a single process step, we develop a closed-formula for the cycle time and prove that DGC minimizes the cycle time for the swap sequence. We also present conditions under which the swap sequence with the cleaning rule achieves the minimum cycle time compared to all other sequences and cleaning plans. For serial wafer flows, we show that DGC minimizes the cycle time when the cleaning period and the cleaning time are the same for all process steps. We also show by experiments that the proposed DGC effectively reduces the cycle time for the other general cases.Note to Practitioners—Our proposed cleaning rule can significantly improve the tool cycle time and regulate wafer flow times. It is easily applied or adapted to and effective for most wafer flow patterns, sequences, and tool architectures.

In this research, we examinefeedback control-based cluster tool scheduling methods to maintainconsistentwafer sojourn times when a tool is subject torandom disruptive events. In our previous work, we proposed a feedback control design that regulates wafer sojourn times not to exceed the upper limits on wafer delays in a deterministic processing environment. Although such a feedback controller may ensure that wafer delay upper limits are always satisfied, it does not necessarily guarantee that the tool always restores its initial tool state after the occurrence of time disruptive events. This article thus further examines under which conditions a feedback controller enforces the wafer sojourn times to bestabilizedin astochasticprocessing environment with unexpected random time disruptions.Note to Practitioners—In semiconductor manufacturing, excessive wafer sojourn times at wafer fabrication tools increase the risk of wafer quality failures. In particular, the wafer quality fluctuates when the sojourn times are inconsistent over different wafers. Therefore, in cluster tools, wafer sojourn times are often strictly regulated to be minimized or to remain constant with an objective of reducing the risk of wafer quality degradation. In this research, we examine a cluster tool scheduling framework that enables to maintain stable tool operations even when a tool is randomly disrupted by unexpected exceptional events.

Timed Petri nets (TPNs) have been widely used for modeling discrete-event systems of diverse manufacturing and service industries. In this article, we introduce a reachability tree-based optimization algorithm to optimize cyclic schedules of TPNs. In particular, we focus on a special class of cyclic schedules that are referred to as one-cyclic schedules, i.e., the algorithm efficiently finds the optimal one-cyclic transition firing schedule of a TPN. The proposed scheduling method can be robustly applied and extended to a number of different scheduling models since the methodology is not bounded to a specific domain. To enhance the computational performance, we establish a set of transition ordering constraints that can reduce the tree size during the search procedure. We evaluate the computational efficiency of the suggested algorithm by examining robotized manufacturing systems where one-cyclic schedules are popularly being used. It is numerically shown that the proposed algorithm is computationally more efficient than the previously studied Petri net-based optimization methods.Note to Practitioners—Resource scheduling is one of the most important managerial issues in diverse industrial systems. An optimal scheduling method for a certain industrial system is often locally developed by utilizing domain-specific operational properties. Although such domain-dependent knowledge can contribute to enhancing the computational efficiency of an optimization method, such an approach has a weak point that the method might not be applicable to scheduling problems of different industrial fields. Our motivation is to develop an algorithm for optimizing steady-state schedules that can be robustly applied for various types of discrete-event systems. The algorithm is developed on the basis of the Petri net modeling framework as it is widely being used for describing cyclic behaviors of diverse manufacturing systems, service systems, and social systems. It is experimentally shown that the proposed algorithm is computationally efficient compared with the existing cyclic scheduling methods.

We examine a scheduling problem for a dual-armed cluster tool that processes multiple similar wafer types concurrently. It has been recently proved that the well-known swap sequence, which is widely used for single wafer type processing, also minimizes the cycle time for concurrent processing. In this article, we wish to minimize wafer delays in a process chamber, which are critical to wafer quality degradation, while maintaining the minimum cycle time. In particular, we show that concurrent processing of wafers with different processing times complicates the analysis of wafer delays significantly, and the wafer delays can be remarkably reduced by finding a proper cycle plan which is the release sequence of different wafer types. We first characterize wafer delays for a given cycle plan by analyzing the circuits of the timed event graph (TEG) model. From this, we prove that concurrent processing of wafers may cause a significant workload imbalance between parallel chambers of a process step, and hence the wafer delays increase substantially. We present that the wafer delays are minimized by a cycle plan that evenly balances workloads between parallel chambers. We also propose how wafer loading task at each process step has to be postponed to meet wafer delay constraints while maintaining the minimum cycle time.Note to Practitioners—Wafer quality control has become an essential fab operational problem in semiconductor manufacturing industry. In cluster tools, which are dominantly being used for diverse wafer fabrication stages, it has been proven that the wafer delays within process chambers have a crucial impact on the wafer quality. Accordingly, modern fabs have introduced stringent quality control to regulate wafer delays in cluster tools. In this research, we propose a scheduling strategy to minimize the wafer delays when a cluster tool concurrently processes multiple wafer types. We first show that the release sequence of different wafer types significantly impacts the wafer delays under concurrent processing, and we then propose how these wafer delays can be minimized by finding the optimal wafer release sequence.

A cluster tool consists of several single-wafer processing chambers and a wafer handling robot. A wafer has to wait within a chamber after being processed there until it is unloaded by the robot. Such wafer delays may cause wafer quality degradation or variability due to residual gases and heat in the chamber. The tool operation schedule has to maintain identical timing patterns or schedules for each cycle so as to keep wafer delays constant for every wafer. However, at the beginning of the tool operation, the tool is in an empty state and hence we need to make the tool reach such steady schedule by loading wafers into the tool. In this article, we develop a method of scheduling the robot tasks during the start-up period of a cluster tool to reach a target steady schedule quickly as possible. To do this, we model the behaviors of a cluster tool using timed Petri nets and linear system matrices in the max-plus algebra. By analyzing the matrices, we first identify a class of steady schedules which can be reached from the empty tool. We develop the matrices that explain the schedule evolution of the start-up period before reaching the steady period. By examining the matrices, we develop a method of choosing the most desirable one from such class of reachable steady schedules that can be achieved in the minimum time. We also prove that the schedule also minimizes the time duration of the close-down. Finally, we present computational experiments.

A cluster tool consists of several single-wafer processing chambers and a wafer-handling robot. Cluster tools are widely used for wafer fabrication in semiconductor manufacturing fabs. As the circuit width shrinks down to below 20 or even several nanometers, wafer waiting within a chamber after processing becomes more critical to wafer quality due to residual gases and heat. Conventional tool scheduling rules, such as the swap sequence and the backward sequence, may not satisfy strict upper limits on wafer delays, especially when process times fluctuate randomly. We examine a scheduling problem for cluster tools with strict upper limits on wafer delays under process time variation. We propose a new class of schedules, which not only keeps timing patterns steady as possible but also adapts timing of tasks in response to process time variation so as to satisfy wafer delay constraints robustly. We also derive conditions for which there exists such a schedule. We develop a mixed-integer programming model to find an optimal schedule among such adaptive schedules. By numerical experiments, we show that the proposed scheduling method can effectively cope with tight wafer delay constraints even under large process time variations.

As the order size for modern fabs tends to be smaller, fabs wish to process a class of similar wafer lots at a tool concurrently to reduce the work-in-progress lots as well as the total manufacturing lead time. We examine a scheduling problem for a dual-armed cluster tool that simultaneously produces multiple wafer types with identical wafer flow patterns but different process times. We prove that the conventional swap sequence, which is optimal and prevalently being used for single-wafer-type processing, is also optimal for such concurrent processing. We then propose a way of determining a release sequence of wafer types into the tool, called cycle plan, that maximizes the utilization of parallel chambers and hence increases the tool throughput rate. We present conditions for which the parallel chambers are shared by all wafer types and their workloads are evenly balanced so as to maximize the throughput rate. We also report the experimental results.

Robotized cluster tools for semiconductor wafer fabrication may have a wafer wait within a processing chamber after processing there until the wafer is unloaded from the chamber by a robot. Such wafer delays cause wafer quality degradation or variability due to residual gases and heats within the chamber. There have been numerous works on characterizing wafer delays and scheduling under upper limits on wafer delays while presuming that the tools are operated by well-known simple robot task sequences such as swap or backward sequences. However, when the wafer delay constraints are tight, there may not be feasible schedules for such sequences. We wish to know whether there can be alternative robot task sequences which can satisfy such tight wafer delay constraints. In this paper, we identify a new class of robot task sequences that can better satisfy tight wafer delay constraints than the conventional swap or backward sequences while keeping the same minimum tool cycle time. By examining the circuits of timed event graph (TEG) models for the tool operation behaviors in many different robot task sequences, we identify that such robot task sequences do not make interferences between the work cycles of the resources such as the robot and chambers. The resource interference can cause delays in the work cycles, and hence increase the wafer delays or the tool cycle time. To prove this, we examine circuits in an extended TEG model, a negative event graph, which incorporates time constraints as negative places and tokens. From this, we derive closed-form conditions for which such sequences are feasible against given wafer delay constraints. By experiments, we show that the proposed new sequences have shorter wafer delays, and hence better satisfy tight wafer delay constraints than conventional sequences. Note to Practitioners-As circuit widths shrink down to several nanometers, cluster tools for semiconductor fabrication require extreme process quality control. Even wafer delays within processing chambers of cluster tools can cause wafer quality degradation and variability. Therefore, it is desirable for cluster tools to have much shorter wafer delays. However, conventional sequences such as the swap and backward sequences, which are being prevalently used in practice, may not satisfy tight wafer delay constraints. Our proposed sequences, which are as simple as the conventional sequences, have much shorter wafer delays while keeping the same minimum tool cycle time.

Circuit widths and nodes of semiconductor wafers have been continually shrinking down to less than 20 nm. Therefore, modern wafer fabs enforce extremely strict process control to prevent wafer quality failures. A wafer processing chamber is now frequently cleaned to remove residual chemicals and impurities. Yu et al. show that such cleaning operations significantly change the tool operation of single-armed cluster tools, and they suggest an idea of partial wafer loading to improve the tool throughput under cleaning requirements. However, little is known about how a dual-armed tool could be effectively scheduled when chamber cleaning exists. A dual-armed robot allows more flexible tool operational sequences, and hence, the scheduling problem becomes further complicated and challenging. In this paper, we propose a scheduling method by which the dual arms can be properly exploited for better tool productivity. We show that the suggested hybrid sequence significantly reduces the tool cycle time as compared to previously developed scheduling methods. Through this research, we conclude that the productivity gain of the dual arms against single arm is more significant when chambers are cleaned.

To improve the performance of semiconductors, manufacturers shrink the wafer circuit width dramatically. This increases the importance of quality control during wafer fabrication process. Thus, fabs recently tend to clean each chamber for every predetermined period to remove chemical residues and heat in the chamber. Such a chamber cleaning process can improve the quality of wafers, but the productivity is lowered. Therefore, the quality and the productivity of wafers have trade-off relations according to the cleaning period. In this paper, we propose a new class of cleaning process, condition based cleaning, which aims to maximize productivity while maintaining wafers quality. We then propose a way to find scheduling cluster tools based on multi-agent reinforcement learning. Finally, we experimentally verify that our algorithm can archive higher performance than existing sequences, under condition-based cleaning.

As wafer circuit widths shrink down, wafer fabrication processes require stringent quality control. Therefore, fabs recently tend to clean a chamber after processing each wafer, in order to remove chemical residuals within the chamber. Such chamber cleaning, called purge operation, increases scheduling complexity in robotized cluster tools. In this paper, we examine scheduling problems of single-armed cluster tools with purge operations for series-parallel chambers. By extending the wellknown backward sequence, we propose a backward(z) sequence that allows partial loading for parallel chambers, where vector z specifies how many chambers zi of each process step i are kept empty for cleaning. We then propose a way of finding optimal vector z* and identify when backward(z*) achieves the minimum cycle time among all possible sequences. We present experimental results on the accuracy of backward(z*).

We examine wafer delays, particularly the worst-case delay, of a dual-armed cluster tool for a K-cyclic schedule. We propose two useful concepts related to robot operations for the analyses, which are the time difference σ and the robot delay R. By using these concepts, we formulate a mixed-integer linear programming for computing the worst-case wafer delay. An upper bound for the worst-case wafer delay and experimental results are suggested. We also suggest an improved wafer delay regulation method by exploiting workload balancing. We introduce the effects of workload balancing and the strategies for achieving workload balancing. Explanations related to the configuration of the tool also are suggested.

Robotized cluster tools for semiconductor manufacturing have strict time constraints such that a wafer processed at a processing chamber should be unloaded within a specified time limit. Otherwise, it has a serious quality problem due to residual gases and heat within the chamber. Even though there have been studies on identifying a feasible tool operation schedule over such time constraints on wafer delays, such a schedule is subject to timing disruptions or time variation, and thus may violate the time constraints. In this study, we propose a more robust method of regulating wafer delays against timing disruptions not to exceed a specified limit. We first model the discrete-event behavior of a tool by a timed event graph. We then develop a feedback controller for single-armed and dual-armed cluster tools that can satisfy the time constraints by regulating wafer delays. To do this, we develop a feedback controller for the timed event graph by analyzing the timing behavior in a linear system model based on the max-plus algebra. The feedback controller postpones an event or firing of a transition, i.e., loading a wafer into a chamber, until a properly determined time elapses after an associated preceding event occurs. Finally, we present examples of feedback control and show that the feedback control is quite robust even under persistent time variation. Wafer delay within a processing chamber after processing is critical to wafer quality variation or failures due to residual gases and heat within the chamber. Although there have been theoretical studies on scheduling tools to control wafer delays, they are not easy to implement for real tool operation. It is because it is not easy to change the tool operation sequence, which is determined by considering many other factors, and a feasible schedule determined under some assumptions is also subject to frequent timing disruptions. We therefore use a simple feedback control method that can keep the current tool operation sequence and is robust against timing disruptions. It can be implemented by a small change in a tool scheduler.

Cluster tools have been extensively used for many semiconductor manufacturing processes such as lithograph, etching, deposition, and testing. Most previous studies on cluster tool scheduling have focused on steady cycles in which cluster tools repeat identical work cycles. However, the proportion of noncyclic transient operation cycles such as start-up cycles and close-down cycles becomes larger as the lot size tends to be smaller. We examine optimal transient scheduling for a single-armed cluster tool, in which there are parallel chambers and a process chamber is a bottleneck, while minimizing the makespan of a lot. To do this, we first identify fundamental properties of noncyclic transient cycles in a tool by analyzing resource workloads. We then propose a simple robot task sequence, a generalized backward sequence, which performs backward operations incrementally for start-up cycles and decrementally for close-down cycles. We also develop workload-based conditions for which the generalized backward sequence has the minimum makespan for single-armed cluster tools with parallel chambers. Finally, we develop a linear programming model to find the minimum makespan of the generalized backward sequence for the cases in which the conditions are not met and show its effectiveness. Note to Practitioners-Scheduling transient cycles such as start-up, close-down, and lot-switching cycles is an important issue for cluster tools due to frequent lot switchings, cleaning, and machine breakdown. In this paper, we propose a generalized backward sequence to schedule a wafer lot from the start-up cycle to the close-down cycle in a single-armed cluster tool with parallel chambers. The workload-based analysis is used for computing a lower bound on the makespan of a lot. We prove that the generalized backward sequence has an optimal makespan in most practical cases. Process engineers can adjust the workloads of process steps to improve the tool productivity based on our results. Even though the optimality conditions are not satisfied, we show that the generalized backward sequence still provides a reasonable makespan experimentally.

We consider a scheduling problem of a robotized cluster tool for semiconductor manufacturing, which should control wafer delays within a chamber so as not to exceed a specified limit under time variation. The prior research has proposed a p+-time event graph, an extension of Petri nets, for modeling the scheduling problem and developed a method of verifying whether a cyclic p+-time event graph or a cluster tool, which repeats identical work cycles, can satisfy the time constraints under time variation. In this paper, we extend and simplify the schedulability analysis method in the prior research for a noncyclic event graph or a cluster tool which performs start-up and close-down operation for a lot or lot switching, and obtain specialized results. We assume that a robot task sequence or firing sequence of transitions is given. Based on the schedulability analysis, we also propose a way of modifying a not always schedulable noncyclic p+-time event graph with some qualifications to be always schedulable, that is, we prolong token holding times at some places or equivalently delay firings of some transitions so as to be always feasible.

Dual-armed cluster tools for semiconductor manufacturing typically have had two arms fixed in opposite directions. Recently, new cluster tool robot systems with two independent robot arms have been introduced with the expectation that the arms' flexibility will improve the throughput. However, the productivity gain has yet to be examined. Accordingly, we examine under which circumstances and the extent to which productivity gains can be achieved and how the robot task sequences should be scheduled to maximize the throughput. For this purpose, we develop a Petri net model that represents the tool behavior. We show that the well-known swap sequence, which is known to be optimal for conventional dual-armed tools, is not always optimal. Instead, we identify two other sequences that are optimal under certain conditions. We define the workloads for each process step and the transport module to derive conditions for optimality of the sequences, based on the Petri net model and the workload. We also develop a mixed integer programming (MIP) model to determine optimal sequences among one-cyclic schedules for the cases in which the proposed sequences are not optimal. Furthermore, we analyze and demonstrate how the two independent arms can increase the throughput in comparison to a conventional dual-armed robot.

A timed Petri net (TPN) has been widely used for modeling, scheduling, and analyzing discrete event dynamic systems. This study examines cyclic scheduling problems of a TPN to minimize the cycle time especially for automated manufacturing systems. Appropriate token routing at each conflict place can make a TPN repeat an identical firing sequence. We propose a systematic procedure to transform a TPN with such cyclic token routing into an equivalent timed event graph (TEG) for which the cycle time and firing schedules can be evaluated by a linear programming (LP). Based on the transformation procedure, we develop an efficient branch and bound algorithm to solve the scheduling problem. A partial solution is defined as a partial token route that has only a subset of token routes for determining the complete schedule. The lower bound of a partial solution is determined by the cycle time of a TEG that has the partial token route. The cycle time of a TEG with an additional token route for a new partial solution is computed by a dual-simplex algorithm which avoids solving the LP completely again. A dynamic branching strategy that prevents unnecessary branching for the scheduling decision is also proposed. We demonstrate the computational efficiency through intensive experiments of cluster tools and robotic flow shops. Note to Practitioners-There are many systems which repeat an identical task sequence such as manufacturing systems, transportation systems, and robotic systems. Maximizing the throughput of such a system by optimizing the cyclic task sequence, which is called a cyclic scheduling problem, has been an important problem. In order to deal with cyclic scheduling problems, this paper uses a timed Petri net (TPN) which is a graphical modeling tool for discrete event dynamic systems. As the size of TPN model increases, the computational complexity of the cyclic scheduling problem exponentially increases due to the combinatorial nature of sequencing problems. Therefore, an efficient algorithm for optimal cyclic scheduling of TPNs is needed. This study proposes an efficient branch and bound algorithm which is kind of a tree search algorithm. Several important techniques are developed. First, a transformation procedure from a TPN to timed event graph is developed. Second, an efficient branching rule which reduces the size of the search tree is proposed. Third, the lower bound which evaluates the cycle time of each node in the search tree is suggested. We verify the efficiency of the algorithm through the experiments on manufacturing systems such as a cluster tool and a robotic flow shop.

Cluster tools, each of which consists of multiple processing modules, one material handling robot, and loadlocks, are widely used for wafer fabrication processes, such as lithography, etching, and deposition. There have been many approaches and algorithms for cyclic scheduling of cluster tools in which the robot repeats a specified sequence for processing identical wafers. However, the lot order size has recently been decreasing due to the larger wafer size and circuit width reductions. In modern fabs, each wafer lot can have different flow patterns and process times for the same process step, and heterogeneous lots are processed consecutively in a tool. Even some tools in a fab have idle time waiting for wafer lots depending on the work-in-process fluctuations. Such different wafer lots and frequent tool state changes cannot be handled with cyclic scheduling methods, and accordingly noncyclic scheduling methods for such cases are required. Therefore, we develop an efficient branch and bound (B&B) procedure for noncyclic scheduling problems of cluster tools to minimize the makespan. Since a timed Petri net (TPN) is known for its powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. We verify the efficiency of the B&B procedure with various cluster tool scheduling problems. There have been many studies on scheduling cluster tools, but most of them utilize different scheduling approaches or develop problem specialized properties. It is impractical to implement all the different methods to a tool scheduler because the scheduling requirements continuously change depending on wafer types and tool architectures. Hence, it is required to have an efficient solution method to address diverse cluster tool scheduling problems in fabs especially for frequent lot switchings and tool state changes due to larger wafer size and smaller lot order size. Therefore, we develop an efficient branch and bound procedure for noncyclic scheduling of a cluster tool with the makespan measurement. Since TPNs have the powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. From the experimental results, we observe that one lot with 25 wafers can be easily solved in a reasonable time. The proposed method can be used for many different scheduling problems of a cluster tool by generating each corresponding TPN model.

Petri nets are useful for modeling and analyzing complex scheduling problems of automated manufacturing systems, such as robotized cluster tools for semiconductor manufacturing and robot cells with diverse and complex tool architectures and scheduling requirements. While there are many scheduling works on cyclic operation cycles of such systems and their Petri net models, automated manufacturing systems have significant noncyclic operation cycles. For instance, cluster tools cannot repeat identical work cycles for start-up and close-down operations of a lot, lot switching, nonidentical wafers, and too small lots. Such noncyclic scheduling problems can also be well modeled by timed Petri nets (TPNs) and can be solved by a branch and bound procedure that explores feasible states by branching and deleting the corresponding nodes in the reachability tree. The tree in general tends to be large, which significantly limits the computational efficiency. The tree generates nodes for all feasible markings regardless of the time evolution information associated with token holding times or firing delays. In this paper, we develop a way of significantly reducing the reachability tree by deleting the nodes or states that are infeasible in view of time evolution. To do this, we propose a time-feasible reachability tree that generates only time-feasible solutions under the earliest starting policy. We then use it for a branch and bound procedure for scheduling a TPN. We demonstrate its computational efficiency improvement with linear cluster tool scheduling problems. Note to Practitioners-TPNs have been widely used for modeling, analyzing, and scheduling discrete-event dynamic systems. Many works have improved the performance of automated manufacturing systems by developing efficient mixed integer programming models, branch and bound algorithms, or specialized strategies with a TPN. The branch and bound procedures and many other scheduling methods for a TPN search solutions by exploring paths in the reachability tree because every possible sequence can be identified as a path in the tree. However, the tree is so large even for a small Petri net. Hence, we propose a reduced reachability tree called a time-feasible reachability tree by eliminating infeasible solutions in view of time evolution. We use the time-feasible reachability tree for a branch and bound procedure for solving a TPN, and its effectiveness is verified with linear cluster tool scheduling problems. A dual-armed linear cluster tool with 25 wafers can be solved easily. We can extend the solvable problem ranges of many scheduling problems with this research.

We examine a non-cyclic scheduling problem of a wet station that performs cleaning processes for removing residual contaminants on wafer surfaces. Several chemical and rinse baths, and multiple robots for transporting jobs are linearly combined in a wet station. A wet station in a fab tends to have different types of jobs. Therefore, it is realistic to consider non-cyclic release of jobs into a wet station. We therefore examine a non-cyclic scheduling problem of a wet station that determines the task sequence of each robot so as to minimize the makespan of a given sequence of different jobs. We develop an efficient branch and bound procedure by examining the scheduling problem. To do this, we first develop a Petri net model for the scheduling problem. By identifying deadlock prevention conditions from the Petri net model, we eliminate partial solutions in advance that eventually will lead to a deadlock. By examining the feasible transition firings or state transition behavior of the Petri net model, we branch only feasible partial solutions or nodes that correspond to feasible state transitions or transition firings. We also develop a tight lower bound based on the bottleneck workload of the baths. We prove computational efficiency of the branch and bound procedure for practical problems.

We examine a scheduling problem of cluster tools that concurrently process two wafer types in a cyclic operational sequence. Whereas the process steps for different wafer types are assigned to different processing modules (PMs), the wafer loading and unloading tasks at the PMs are performed by a single robot. For a given cycle plan, which is a mix of different wafers for each cycle, we wish to determine the robot task sequence so as to minimize the tool cycle time. When a single wafer type is processed, the backward and swap sequences are optimal for single-armed and dual-armed tools, respectively. They are being prevalently used because of their simplicity and robustness. To maintain such advantages in concurrent processing, we introduce and define the concurrent backward and swap sequences (CBSs and CSSs, respectively). We then develop conditions on process times, robot task times, and the number of wafers produced in a cycle for which such CBSs and CSSs are still optimal for concurrent processing. We also show that, for some special cases, the two wafer types can achieve their maximum throughput rates as if each wafer type exclusively uses the tool regardless of other wafer types in progress. When the developed conditions do not hold, an effective mixed integer programming (MIP) model based on the CBSs and CSSs is used for robot task sequencing. Finally, we experimentally verify its efficiency and effectiveness by comparing to the existing scheduling methods for optimal scheduling of cluster tools.

In the semiconductor manufacturing industry, the lot size currently tends to be extremely small, even being only 5-8 wafers, whereas conventional lots have 25 identical wafers. The smaller lot size is made because customers demand extremely small lots, and the number of chips in a large 300 mm wafer has increased. Cyclic scheduling is not applicable for such small lot production because the number of identical work cycles accounts for a small proportion of scheduling as compared to the lengths of the starting and closing transient periods. We therefore examine a new noncyclic scheduling problem of cluster tools for small lot production that considers ready time constraints on the chambers and the robot. The ready times are the epochs when the resources are freed from processing the preceding lot. To solve the scheduling problem, we develop a Petri net model which is a graphical and mathematical method for discrete event dynamic systems. Based on the Petri net model, we also develop a mixed integer programming (MIP) model and a branch and bound (B&B) algorithm for determining an optimal schedule. The B&B algorithm solves lots with up to 25 wafers and eight wafers within 500 s for a single-armed cluster tool and a dual-armed cluster tool, respectively, when three process steps are considered. Therefore, we propose an approximation method for the dual-armed cluster tool that schedules only the first few wafers with the B&B algorithm and the succeeding wafers with a well-known cyclic sequence. From experiments, we conclude that the difference between the approximation method and an optimal makespan is less than 1%. The methods we propose can be used for general noncyclic scheduling problems that can be modeled by Petri nets.

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 as an upper bound for the number of states, where , and 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 Ωows, and parallel chambers. Note to Practitioners-The scheduling method developed in this paper is designed for scheduling robots used in semiconductor production. The method is able to efficiently represent the state of the manufacturing system and uses this to find an optimal schedule to maximize productivity. The same approach can be used for other manufacturing systems with discrete events. The main advantage of this method is that it can fast find an optimal schedule based on the current state of the system. A long-time horizon can be used because of the high efficiency of the algorithm with respect to the number of jobs. However, the method is best suited for manufacturing systems with few buffers and limited degrees of freedom, in other words highly interconnected systems.

Semiconductor manufacturing fabs recently tend to reduce the lot size, that is, the number of identical wafers in a lot, because of small lot orders and increased die throughput per wafer due to wafer size increase. Therefore, cluster tools for wafer processing, which mostly repeat identical work cycles, are subject to frequent lot changes. We therefore examine scheduling problems for transient periods of single-armed cluster tools that are scheduled to repeat identical work cycles for a number of identical wafers. We first develop a Petri net model for the tool's operational behavior including the initial transient periods as well as the steady cycles. We then develop a mixed integer programming model for finding an optimal schedule. We also examine how to adapt the simple backward sequence, which is mostly used for scheduling steady work cycles of single-armed cluster tools, for a transient period. We identify a deadlock-free condition and also propose two efficient heuristic algorithms by modifying the backward sequence. Finally, through computational experiments, we analyze the efficiency of the proposed algorithms.

Cluster tools for semiconductor manufacturing have been studied widely in terms of transportation robot scheduling. Cluster tool systems are discrete event systems, and usually modeled in timed Petri nets and timed event graphs. Many efficient robot operation sequences such as the backward sequence and the swap sequence have been developed, but they do not guarantee efficiency under consideration of wafer residency time constraints for some process modules. In this paper, we propose a way to control cluster tools with wafer residency time constraints using the max-plus algebra and timed event graphs. Conditions to meet time constraints are developed, and we introduce a methodology to add feedback control arcs to timed event graph models of single-armed cluster tools with the backward sequence, and dual-armed cluster tools with the swap sequence. Bounded variation on processing times also considered as well as time constraints.

We examine a non-cyclic scheduling problem of a timed Petri net (TPN) with a branch and bound (B&B) algorithm. There have been many approaches and algorithms for conventional scheduling problems such as job shops, resource-constrained project scheduling problems (RCPSPs), and robotized system scheduling problems. Most of these methods have focused on their effectiveness or efficiency in solving their own problems. However, they tend to ignore the issue of compatibility with other scheduling problems and the solution methods are ad hoc and hard to be used for other scheduling problems with even small changes. Petri nets have been widely used for modeling and analyzing complex discrete event dynamic systems, such as robotized manufacturing cells or other automated manufacturing systems. There are studies on scheduling cyclic Petri net models and some non-cyclic Petri net models for specific applications. In this paper, we examine a scheduling problem for non-cyclic TPNs, where there is the starting and end transitions, and the transitions do not repeat an identical firing cycle. We also allow multiple arc weights in TPNs so as to model batch processing of tasks at a resource and multiple units of a resource required for a task. We briefly explain how various scheduling constraints and objectives can be modeled by TPNs. Then, we develop an efficient B&B procedure that utilizes a dynamic branching strategy and a resource-based lower bound. We finally present examples of the B&B algorithm for an RCPSP and a single-armed cluser tool scheduling problem.

We examine a scheduling problem of a wet station with multiple job flows. The wet station performs cleaning processes for removing residual contaminants after wafer fabrication processes. It consists of several chemical and rinse baths, and multiple transport robots. Most studies on scheduling robotized systems including a wet station assume identical jobs and deal with cyclic scheduling that repeats a predefined work cycle. However, jobs arrive dynamically and many different jobs are processed concurrently at a wet station. We therefore examine a non-cyclic scheduling problem of the wet station to minimize the makespan. We first develop a Petri net model and solve the problem using a branch and bound (B&B) algorithm. We also propose a dynamic branching method and evaluate a lower bound based on a bottleneck process. During searching the nodes, we analyze deadlocks and add places to the Petri net model for precedence relations among the robot tasks by applying the deadlock prevention conditions. We finally show that the proposed B&B algorithm is sufficient to solve practical problems.

Cluster tools for some wafer fabrication processes such as low-pressure chemical vapor deposition have strict wafer delay constraints. A wafer that completes processing in a processing chamber should leave the chamber within a specified time limit. Otherwise, the wafer suffers from severe quality troubles due to residual gases and heat within the chamber. An important engineering problem is to verify whether for given task times there exists a tool operation schedule that satisfies the wafer delay limit. There have been studies on the problem, which all assume deterministic task times. However, in reality, the task times are subject to random variation. In this paper, we develop a systematic method of determining schedulability of time-constrained decision-free discrete-event systems, where time variation can be confined within finite intervals. To do this, we propose an extended Petri net for modeling such systems. We then develop a necessary and sufficient condition for which there always exists a feasible schedule and one for which there never exists any feasible schedule. We develop a graph-based computational procedure for verifying the schedulability conditions and determining the worst-case task delay. We demonstrate how the procedure can be used for cluster tool engineering to control wafer delays against wafer alignment failures and time variation.

We introduce places with negative holding times and tokens with negative token counts into a timed event graph in order to model and analyze time window constraints. We extend the enabling and firing rules for such an extended event graph named a negative event graph (NEG). We develop necessary and sufficient conditions based on the circuits for which the NEG is live, that is, an infinite sequence of feasible firing epochs exist for each transition. We prove that the minimum cycle time is the same as the maximum circuit ratio of the circuits with positive token counts. We also show that when there exists circuits with negative token counts, the maximum cycle time is bounded and the same as the minimum circuit ratio of such circuits. A scheduling example for a robot-based cluster tool with wafer residency time constraints for semiconductor manufacturing is explained. Note to Practitioners-Scheduling and control problems for modern man-made systems, including automated manufacturing systems such as cluster tools for semiconductor manufacturing, microcircuits, and real-time software systems, are usually modeled as discrete event systems. Such systems often have strict time constraints on timings of some events. Our results can be used for identifying whether there can be a feasible schedule that satisfies all time constraints, computing the range of the feasible cycle times, and determining a steady schedule with the minimum cycle time. By using the feasibility condition, we also can accommodate the system configuration, the task times, and the task sequence so that the system can satisfy the time constraints while meeting the target cycle time. Such practice is already used for real cluster tool engineering. We have more results on implementing a real-time scheduler and controller for time constrained systems.

Stable schedules that repeat identical timing patterns for each work cycle have been important implication for cyclic manufacturing systems such as cluster tools for semiconductor manufacturing or flexible manufacturing systems. While it has been claimed that stable schedules have advantages including steady operation, predictable behavior, minimum cycle times, less work-in-progress inventory, recently stable schedules also play essential roles for meeting critical time window constraints on the operations such as wafer residency time constraint in a cluster tool or track equipment for some chemical vapor deposition processes or wet cleaning processes. However, when the process times or robot task times are subject to random variation of abrupt random disturbances, the stable schedule is disturbed and the perturbed wafer residency times may violate time window constraints. We prove that a cluster tool with dual arms, after any schedule disturbance, can be stabilized to the stable schedule. We characterize the condition for stabilization based on the event graph theory. We also present a control strategy that guarantees such stabilization and reduces the stabilization time.

A cluster tool integrates several processing modules with a wafer handling module. Cluster tools are essential for semiconductor manufacturing automation. A CTC (cluster tool controller) is a complex distributed control application that monitors and coordinates the component modules and is also monitored and commanded by the MES (Manufacturing Execution System). Recently, SEMI (Semiconductor Equipment and Materials International) released two important CIM standards, CTMC (Cluster Tool Module Communication) and OBEM (Object-Based Equipment Model). CTMC defines high-level messaging and application-level communication service standards between a CTC and the module controllers, which are based on an object-oriented model of the CTC communication functions. OBEM specifies high-level application object models for equipment with which the objects of an MES application based CIM Framework Standard, a SEMI standard for an object-oriented MES application framework, communicate through distributed object invocation. We discuss issues and strategies for integrating the two object-oriented communication interface standards, CTMC and OBEM, into an object-oriented CTC application framework.