US 6,738,682 B1Grant

Method and apparatus for scheduling based on state estimation uncertainties

Issue Date:2004-05-18

•36 Claims

•18 Drawing Sheets

Abstract

A method for scheduling activities in a manufacturing system includes defining a plurality of observed states associated with the manufacturing system. State estimates are generated for the observed states. Uncertainty values for the state estimates are generated. A plurality of candidate schedules for performing activities in the manufacturing system is identified. Changes to the uncertainty values are predicted based on the candidate schedules. One of the candidate schedules is selected based on the predicted changes to the uncertainty values.

Metadata

Assignee

Advances Micro Devices, Inc.

Inventor

Alexander J. Pasadyn

Application Information

Application Number:US 10/210,753

Filing Date:2002-07-31

Priority Date:2001-09-13

Art Unit:7

Classifications

IPC:

G06F 1900G05B 1304

Field of Search:

700 44700 51700 52700 96700 97700103700100705 8705 9706 48

Patent Drawings (18 sheets)

Description

[0002] Applicant claims under 35 U.S.C §119(e) the earlier effective filing date of co-pending U.S. Provisional Application Serial No. 60/318,792, entitled “An Adaptive Run-To-Run Scheme For Simultaneous Control and Identification for Multiple Product and Process Environments,” filed Sep. 13, 2001, in the name of Alexander J. Pasadyn, for all common subject matter.

Background of the Invention

[0003] 1. Field of the Invention

[0004] This invention relates generally to the field of semiconductor device manufacturing and, more particularly, to a method and apparatus for scheduling based on state estimation uncertainties.

[0005] 2. Description of the Related Art

[0006] It is typical in semiconductor manufacturing to see many different products being made by using a variety of process conditions on the same pieces of equipment. Because of the nature of the process conditions and the high cost of materials, it is very difficult and often impossible to obtain measurements of key process variables while the process is operating. Product wafers are run in batches on processing tools using recipes, which specify the parameters necessary to run the tool such as pressure, temperature, and processing time. Measurements are made after processing steps are completed to determine if batches meet their specifications. Run-to-run control methods use the measurement data available at the end of each run to determine better recipe settings for subsequent batches. This task is made more difficult by the fact that measurements are often confounded by several different possible sources of variation.

[0007] The manufacture of semiconductor devices is characterized by expensive equipment and raw materials being used to create microscopic features in a batch processing environment. In this environment, batches of wafers are subjected to a series of unit operations with the ultimate goal being to create functional parts. Throughout the operations, extreme processing conditions and features with a critical dimension being constructed are recurring themes. These conditions ultimately mean that it is difficult (and in many cases impossible) to measure important quality variables in situ. Variables of interest are typically measured after a batch has been processed. Unfortunately, it is typically not possible to go back and perform an operation again to correct a misprocessed batch. Therefore, effective process control is needed to ensure that every run goes according to plan.

[0008] Run-to-run control in semiconductor manufacturing is a type of batch control, where a batch may be as small as one wafer or as large as several lots of wafers. The standard output of a run-to-run controller is a process recipe. This recipe defines the set points for “low-level” controllers built into the processing tool. In this way, the run-to-run controller supervises the tool controller by specifying required values for process variables such as temperature, pressure, flow, and process time. The tool controller handles the actuations necessary to maintain these variables at the requested values. A typical run-to-run control setup includes a feedback loop where adjustments are made to the recipe parameters based on batch properties measured after processing. Typically, the job of the run-to-run controller is to ensure that each batch hits its inline targets. Inline targets refer to measurements that are taken while the wafers have only completed some of their processing steps. The inline targets are designed to provide guidelines for having functional parts at the end of the manufacturing line.

[0009] Run-to-run controllers for discrete parts manufacture have several inherent complications. Unlike a continuous process, where plant outputs can be blended together to make particular products, each part that is produced must meet all of its quality or performance objectives to function correctly. As a result, aggressive control laws must be chosen because the manufacturing constraints do not allow a series of off-target batches while the controller approaches the target. When the system model is able to make accurate predictions, the controller can be quite aggressive. This is because the stability of the controller is tied to the ability of the model to match the behavior of the real system. A controller that is too aggressive in the presence of model error and other uncertainties can actually exhibit poor performance and may lead to instability. This situation may arise because a controller makes process decisions based on assumptions about how its input changes will affect the process. The qualitative effects of small input changes are often easily understood and predicted in terms of the underlying physics of the system. On the other hand, larger, more dramatic changes can upset the process by introducing dynamics more quickly than the process can handle. With better understanding of the process, changes can be made more quickly and effectively.

[0010] The most aggressive controller that can be used is a plant inverse, or deadbeat controller. This controller attempts to immediately reject any measured incoming disturbances and set the controlled parameters for each batch exactly at their targets. The parameters may be determined by substituting the desired outputs into the process model and solving directly for the inputs. More conservative control actions can be obtained by imposing limits on how quickly input variables are allowed to change.

[0011] Because the process gain and other variables important to the manufacturing processes can change over time, a successful controller must adapt to changing process conditions. At the foundation of such an adaptive controller are system identification techniques. System identification techniques aim to determine a model with the same input-output characteristics and possibly the same natural model structure as the physical system under study. In many practical applications, it is not feasible to obtain an exact model form for the process under study. So, online system identification often takes the form of a parameter estimation problem. In this formulation, a form for the model is predetermined, and the model parameters are updated recursively from process data. Changing process conditions can be seen as a change in the estimated model parameters over time.

[0012] In microelectronics manufacturing, it is standard practice to apply statistical process control (SPC) techniques to the process outputs. SPC can also be applied to the outputs of a system under automated control. These outputs include not only the controlled outputs of the process but also the measured deviation of the real process from the prediction used by the controller. In general, the use of SPC techniques involves setting limits on the variables of interest and investigating the process when it strays outside the limits. As its name implies, statistical process control is heavily rooted in treating the process variables of interest as distributions. Several different statistics can be monitored to ensure that the process remains stationary. These techniques are designed to indicate whether a process is running in control or not, but decisions about what to do when the process goes out of control are left to engineers.

[0013] These SPC techniques can represent how well an automated controller is doing in terms of keeping the process running inside the control limits. When the limits are exceeded, either the process or the automatic controller must be adjusted. However, real processes and the disturbances to them change over time, so it is not necessarily true that all process variables of interest will remain stationary. In addition, there are many systems where all of the measurements important to control cannot be taken as frequently as desired. For these systems, it is possible that some measurements that would be outliers are not identified simply because they are not measured. In this context, static limits on process variables do not always make sense. The ideal solution is an automatic controller that can detect process changes and adjust itself to account for them. Such an automatic controller could adjust the process before the control limits on the quality outputs are even violated. This controller must recognize that the model it uses may become invalid, so it must always treat new measurement data as an opportunity to remodel the process.

[0014] To achieve adequate performance in an uncertain environment, the control system must react to process changes. Adaptive control techniques are a class of control schemes where the controller automatically adjusts its model parameters and tuning to account for observed changes in the process itself. These techniques often rely on online model parameter estimation, and the controller settings are continually adjusted to match the current system model derived from the measurements. Adaptive control is useful when the true model of the system is complicated or of high order, since the control law can be based on a simpler model with adjustable parameters. These controllers can be obtained from a variety of design methods including pole placement techniques and minimization of quadratic cost functions. Adaptive control techniques can enable advanced control concepts such as optimal control to be used in cases where the system under study is very complicated or poorly understood.

[0015] For a given system with manipulated inputs and a quantitative performance objective, optimal control theory can be used to find the best set of inputs. The optimal control problem is to determine the set of inputs that minimize (or maximize) an objective function while satisfying the constraints of the system model and any additional process requirements. Mathematically, this is described by the equations below, where x represents the process state, u represents the manipulated input, t represents time, 𝑓 is the objective function, and g_iare a series of constraints on the solution.

\begin{matrix} \min_{u} f (x, u, t) & (1) \end{matrix}

g_i(x,u,f)≧0 (2)

[0016] For certain types of systems, this works well for solving the control problem. One advantage of optimal control is that the control objective is clearly defined. Evaluating the objective function at the solution provides a quantitative measure of the expected performance of the controller. When paired with adaptive techniques, optimal control can meet the control objectives even when the system changes over time. The optimal control equations are very general, and are not limited to describing simple systems. The constraint equations, g_i, normally include differential equations or difference equations that govern the process as well as operating limits that are imposed on the process inputs and states. For most real processes, the above problem often results in a set of nonlinear differential equations with mixed boundary conditions.

[0017] Optimal solutions have been derived for some simple process models. One class of such problems is a linear (L) model and quadratic (Q) objective function with additive Gaussian (G) noise in the model, also called the LQG problem. For these systems, the optimal controller can be derived. In general, approximations must be made for real processes, and a sub-optimal controller must be used. This is because the true model of the system is often either unknown or too complicated for the optimal controller to have a closed form solution. A common approach is to formulate the problem as LQG and to use the corresponding linear controller.

[0018] One method used in adaptive control is a sub-optimal approach, where the process model is assumed to have a simple model form, but the values of the model parameters are undetermined or time-varying. In this formulation, the optimal control law for the chosen model form can be derived in terms of the unknown model parameters. Then, system identification techniques can be used to determine the values of the model parameters that best explain the observed system behavior.

[0019] In this case the controller has a model that is accurate in the vicinity of the current operating point. As the process moves to other operating points, the model parameters are updated, so that the controller can still function effectively. The key constraint is that the model must match the input-output behavior of the real process in the current region of interest. The presence of disturbances and dynamics that are not accounted for by the model can affect the stability of the controller. The controller must be able to respond intelligently to errors in the parameter estimates as well as actual changes in the process that require changes in the model parameters. An adaptive controller recursively estimates the model parameters after each sample, and the control action is then calculated using the new values of the parameter estimates.

[0020] There are different approaches to adaptive control. The procedure described above is an indirect method, where the control action is computed based on estimated model parameter values. In the direct adaptive control method, parameters in the control law itself (such as gains) are computed recursively from the measured errors. The optimal adaptive controller tries to solve a dual control problem using a formulation having as a goal the simultaneous control and identification of the process. A sufficiently advanced controller takes into account the need to characterize the process and “probes” the process to obtain better parameter estimates.

[0021] The adaptive controller relies on system identification techniques to bridge the gap between the chosen model form and the actual model used for control by choosing appropriate values for all the parameters in the model form. System identification techniques fall into two main categories (i.e., offline and online) depending on whether or not they are performed in real time on data that are obtained while the system is operating.

[0022] Offline system identification schemes examine a complete set of process input and output data to arrive at a model. These schemes are very flexible because many different model forms can be tried, and they have the advantage of being able to analyze all of the process data at one time. Such a system can even use models such as artificial neural networks (ANN) that do not have prescribed structure. The main limitation of an offline system identification scheme is that it cannot predict how the model may change in the future.

[0023] Online system identification techniques are active as the process under study is running. They use process measurements and recursively update a system model of predetermined form. The estimator observes the system and adjusts the model parameters within the chosen model structure. In general, the estimator does not have a complete set of data with which to work. It only has access to the measurements that have already been made. However, an online system identification scheme has one distinct advantage over an offline method. The online method can quickly react to changes in the process. Process changes appear as errors in the values of the model parameters. If the process change is gradual over time, the online system identification method can adjust the model as the process changes, so the prediction error is kept low.

[0024] The common exponentially weighted moving average (EWMA) filtering technique can be used in recursive parameter estimation. Here, a new parameter estimate is obtained by using a weighted combination of a parameter estimate based on the current measurement and the current parameter estimate as shown in

[0025] {tilde over (x)}_k+1=λx_k−1+(1−λ){tilde over (x)}_k, (3)

[0026] where x is the measured value, and {tilde over (x)} is the estimate.

[0027] The choice of the EWMA weighting parameter, λ, affects whether the estimator will respond slowly (for slowly drifting processes) or quickly (for processes undergoing a rapid change). So, different choices of the weighting parameter affect the stability of a controller using the parameter estimates under different circumstances.

[0028] To effectively estimate model parameters in an online recursive fashion, some process characteristics are required. Identification of a process under automatic control is complicated because the actions of the controller mask the underlying behavior of the process. In general, the inputs to the process have to vary in such a way that the model parameters can be uniquely identified. This requirement is called persistent excitation. A difficulty arises because the satisfaction of a typical control objective lowers the amount of excitation as the process reaches a steady state at the desired operating point.

[0029] Adaptive control techniques can be applied to batch processes for run-to-run control. The system model predicts the process behavior of each batch as well as how the system changes from batch to batch. The responsibility of the controller is to choose the optimal input settings for each batch. In a real manufacturing environment, process conditions are constantly changing, so the system models must be updated regularly. To arrive at the best inputs for each batch, the controller must react to the changing process conditions by adjusting the model parameters. This can be done by solving the system identification problem each time new data become available.

[0030] Run-to-run batch control in semiconductor manufacturing is often complicated by having multiple products and multiple processing tools. These situations arise very often in semiconductor manufacturing, but they are also an issue in other batch processing environments, such as the production of polymers. It is important that each batch meet its required specifications, but it is difficult to choose appropriate recipe settings when switching between different products and tools. Online system identification and adaptive control can help make this problem much more manageable. Of course, the success of the controller is dependent on the properties of the disturbances and system inputs as well as the controller design itself.

[0031] Consider a process that can be modeled linearly as a simple example,

[0032] x=rt. (4)

[0033] The extent of the reaction after time t is given by x, and r is the rate, which is known to fluctuate with changing process conditions. The target is a desired extent of reaction x*. After each run, a new estimate for the rate r is prepared based on the results of the run. In many applications, it is quickly observed that different products will have very different apparent reaction rates. However, the rate can drift from batch to batch, even if only one product is being made. This can be caused by reactor fouling, degradation of consumable materials, or process leaks.

[0034] Simply tracking an estimate for r from run to run is not acceptable because each switch to a different product appears as a step change. Each time the product switches, the rate estimate slowly moves to the new observed rate over the course of several runs. Reactor fouling causes the rate to continually decay over the course of the runs. An EWMA is used to filter the apparent rate data from each run, and the filtered values are used as the rate estimates. When a second product is run, the apparent rate is much different than what it was for the first product, and the filter causes the state estimate to slowly perceive this over time. The state estimate thus lags behind the observed value, especially when the products are switched. This difference between the estimate and the real state is what causes a controller using this estimate to miss the target.

[0035] Previous work in this area has led to the concept of observer scheduling. In this formulation, a model is developed for the tool state (x) that is independent of the product. This tool state is an intrinsic rate for the tool. A change in this rate affects all products that run on the tool.

[0036] x_k+1=Ax_k+Bu_k (5)

[0037] The process state x is mapped to the product state y using the output equation

[0038] y_k=Cx_k. (6)

[0039] Then, the estimator is used to track the tool state x, rather than product state y. Inspection of the Kalman optimal filtering equations indicates that optimal observer gain is a function of the output mapping C. So, by using offline analysis, the repeatable product dependence can be quantified to arrive at a new model for the rate r, where r₀is the “intrinsic rate” of the processing tool, and k_pis a product-specific correction factor.

[0040] r=r₀k_p. (7)

[0041] The observer then estimates r₀instead of r, by scaling the observed rate by the correct product-specific factor k_p. In a situation where the product specific factors are known exactly, the scheme described above works very well. Changes in the operation of the processing tool are observed regardless of which product is running. However, in a real manufacturing environment, several complications arise. For example, there can be several processing tools, new products appear, and experiments can be very expensive in terms of both raw materials and processing tool downtime. The impact here is that the product specific factors are not always known a priori, so it is not necessarily safe to assume k_p(and hence C) are known values.

[0042] The method above observes a single parameter (r₀), but it is necessary to find a way to quickly obtain estimates for new values of k_p. In principle, this can be done by observing the rate at each run, and updating the model parameters accordingly. In practice, observability concerns arise. The result of each run is a measurement of the apparent rate r, which is confounded by both r₀and k_p, so any estimation scheme must be able to use the information available to adjust all the parameters as necessary.

[0043] To estimate r₀and k_pfrom the data (r), the previous equation may be used with a Taylor series approximation,

[0044] Δr=r₀×Δk_p+k_p×Δr₀. (8)

[0045] An apparent change in the value of r can be expressed as a change in the estimates of r₀and k_p. So, it is necessary to classify the changes (using an analysis of variance technique) to determine how to distribute the error between the two parameters.

[0046] One simple method of distributing the error is to apply a linear filter to each parameter.

[0047] r_0.new=r_0.measλ_r+r_0.last(1−λ_r) (9)

[0048] k_p.new=k_p.measλ_k+k_p.last(1−λ_k) (10)

[0049] The lambda values are varied to reflect the confidence in the parameter estimates. In situations where r₀is expected to be changing, λ_ris high, and in situations where k_pis thought to be in error, λ_kis high.

[0050] As an example, for a well-established product, there is a high degree of confidence that k_pis accurate. In addition, r₀is known to drift over time. Thus, the relation λ_r>>λ_kis used. On the other hand, for a new product, there is less confidence in the value of k_p. It is expected that an inaccurate k_pwill affect the rate more than the noise or drift in r₀, so the condition λ_k>>λ_ris set.

[0051] This technique, while simple to understand, is limited because it is a rule-based scheme that relies on concepts that are difficult to quantify. Furthermore, it is not always possible to solve the model equations for each parameter in turn.

[0052] A successful controller for the types of processes described herein would be able to address the dual problems of simultaneous identification and control. It is easier to learn about the process by making large input changes or running non-production experiments, but this directly opposes the primary goal of the controller. Making the process choices involves a tradeoff between tightly tracking the targets and helping to characterize the process because the two objectives conflict with each other.

[0053] Run-to-run control as practiced in high-volume multi-product semiconductor manufacturing does not easily fit into the framework of traditional approaches to process control. A traditional approach defines a process model with a given set of states, inputs, and outputs. In some cases, the model is static, and in others, it changes over time. At each time step, inputs and disturbances affect the states, and outputs are measured. Then, the controller makes an update and the process repeats. One reason this approach is not always successful is that there are often multiple processing tools as well as multiple products. It is a common practice in today's microelectronics manufacturing facilities to have many different products and processes run on each processing tool, mainly because of the high capital costs associated with the tools and the limited capacity of the facility. In addition, of all the measurements important to a process, only a subset are generally made on each run. Determining how to do controller updates in this environment can be a challenging task.

[0054] A run-to-run controller relies on having a process model that is consistently correct from run to run. When the various processes run on the tool are significantly different, the controller may behave unexpectedly because a change to a new process can appear to be a large disturbance. In addition, it may take several successive runs of a given process for the controller to stabilize, but manufacturing constraints may prevent this from happening. In the best case, the controller would determine optimal settings for all processes that must run on the tool, regardless of the order in which they appear.

[0055] In an adaptive control strategy, an online system identification scheme runs along with the controller and constantly adjusts the model so that it mimics the true behavior of the system. One very difficult task in this situation is determining which of the many possibilities (parameters, bias estimates) is the source of the observed errors in the output. In semiconductor manufacturing, a common question is whether the errors are assignable to tool differences or to product differences.

[0056] The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.

Summary of the Invention

[0057] One aspect of the present invention is seen in a method for scheduling activities in a manufacturing system. The method includes defining a plurality of observed states associated with the manufacturing system. State estimates are generated for the observed states. Uncertainty values for the state estimates are generated. A plurality of candidate schedules for performing activities in the manufacturing system is identified. Changes to the uncertainty values are predicted based on the candidate schedules. One of the candidate schedules is selected based on the predicted changes to the uncertainty values.

[0058] Another aspect of the present invention is seen in a system for scheduling activities in a manufacturing system that includes a process controller and a scheduling controller. The process controller is configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed states, and generate uncertainty values for the state estimates. The scheduling controller is configured to identify a plurality of candidate schedules for performing activities in the manufacturing system, predict changes to the uncertainty values based on the candidate schedules, and select one of the candidate schedules based on the predicted changes to the uncertainty values.

Brief Description of the Drawings

[0059] The invention may be understood by reference to the following description taken in conjunction with the accompanying drawings, in which like reference numerals identify like elements, and in which:

[0060] FIG. 1 is a simplified block diagram of a manufacturing system in accordance with one illustrative embodiment of the present invention;

[0061] FIG. 2 is a simplified block diagram of a portion of the manufacturing system of FIG. 1;

[0062] FIGS. 3A and 3B are graphs of exemplary probability density functions;

[0063] FIGS. 4 through 29 a graphs illustrating the performance of a controller of FIG. 1 to under various scenarios; and

[0064] FIG. 30 represents a block diagram on a system including a process controller and a scheduling controller in accordance with another embodiment of the present invention; and

[0065] FIG. 31 represents a simplified flow diagram of a method for scheduling activities in a manufacturing system in Accordance with yet another embodiment of the present invention.

[0066] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that the description herein of specific embodiments is not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

Detailed Description of Specific Embodiments

[0067] Illustrative embodiments of the invention are described below. In the interest of clarity, not all features of an actual implementation are described in this specification. It will of course be appreciated that in the development of any such actual embodiment, numerous implementation-specific decisions must be made to achieve the developers' specific goals, such as compliance with system-related and business-related constraints, which will vary from one implementation to another. Moreover, it will be appreciated that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking for those of ordinary skill in the art having the benefit of this disclosure.

[0068] Referring to FIG. 1, a simplified block diagram of an illustrative manufacturing system 10 is provided. In the illustrated embodiment, the manufacturing system 10 is adapted to fabricate semiconductor devices. Although the invention is described as it may be implemented in a semiconductor fabrication facility, the invention is not so limited and may be applied to other manufacturing environments. The techniques described herein may be applied to a variety of workpieces or manufactured items including, but not limited to microprocessors, memory devices, digital signal processors, application specific integrated circuits (ASICs), or other similar devices. The techniques may also be applied to workpieces or manufactured items other than semiconductor devices.

[0069] A network 20 interconnects various components of the manufacturing system 10, allowing them to exchange information. The illustrative manufacturing system 10 includes a plurality of tools 30-80. Each of the tools 30-80 may be coupled to a computer (not shown) for interfacing with the network 20. The tools 30-80 are grouped into sets of like tools, as denoted by lettered suffixes. For example, the set of tools 30A-30C represent tools of a certain type, such as a chemical mechanical planarization tool. A particular wafer or lot of wafers progresses through the tools 30-80 as it is being manufactured, with each tool 30-80 performing a specific function in the process flow. Exemplary processing tools for a semiconductor device fabrication environment, include metrology tools, photolithography steppers, etch tools, deposition tools, polishing tools, rapid thermal processing tools, implantation tools, etc. The tools 30-80 are illustrated in a rank and file grouping for illustrative purposes only. In an actual implementation, the tools may be arranged in any order or grouping. Additionally, the connections between the tools in a particular grouping are meant to represent only connections to the network 20, rather than interconnections between the tools.

[0070] A manufacturing execution system (MES) server 90 directs the high level operation of the manufacturing system 10. The MES server 90 monitors the status of the various entities in the manufacturing system 10 (i.e., lots, tools 30-80) and controls the flow of articles of manufacture (e.g., lots of semiconductor wafers) through the process flow. A database server 100 is provided for storing data related to the status of the various entities and articles of manufacture in the process flow. The database server 100 may store information in one or more data stores 110. The data may include pre-process and post-process metrology data, tool states, lot priorities, etc.

[0071] Portions of the invention and corresponding detailed description are presented in terms of software, or algorithms and symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the ones by which those of ordinary skill in the art effectively convey the substance of their work to others of ordinary skill in the art. An algorithm, as the term is used here, and as it is used generally, is conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of optical, electrical, or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

[0072] It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, or as is apparent from the discussion, terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical, electronic quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0073] An exemplary information exchange and process control framework suitable for use in the manufacturing system 10 is an Advanced Process Control (APC) framework, such as may be implemented using the Catalyst system offered by KLA-Tencor, Inc. The Catalyst system uses Semiconductor Equipment and Materials International (SEMI) Computer Integrated Manufacturing (CIM) Framework compliant system technologies and is based the Advanced Process Control (APC) Framework. CIM (SEMI E81-0699—Provisional Specification for CIM Framework Domain Architecture) and APC (SEMI E93-0999—Provisional Specification for CIM Framework Advanced Process Control Component) specifications are publicly available from SEMI, which is headquartered in Mountain View, Calif.

[0074] The manufacturing system 10 also includes a controller 130 executing on a workstation 140. As described in greater detail below, the controller 130 determines operating recipe setting for various tools 30-80 in the manufacturing system 10. Abbreviations and symbol nomenclature used herein are summarized below in Appendix A.

[0075] The distribution of the processing and data storage functions amongst the different computers or workstations in FIG. 1 is generally conducted to provide independence and central information storage. Of course, different numbers of computers and different arrangements may be used.

[0076] Turning now to FIG. 2, a simplified block diagram of a portion of the manufacturing system 10 of FIG. 1 is provided. In the illustrated embodiment, the portion of the manufacturing system 10 includes first and second processing tools 200 and 210 interfacing with the controller 130 and configured to perform processes on three different products (A, B, and C). The number of tools 200, 210 and products is selected merely to facilitate the discussion. Of course, other number of tools 200, 210 and products may be used. The processes performed by the tools 200, 210 may be performed in any product/tool combination. The controller 130 includes a control law component 132, and an observer component 134. The observer component estimates and updates states of the manufacturing system 10. The control law component uses this state information to determine operating recipe parameters for the tools 200, 210.

[0077] Using a linearized form and assuming that there is a single “nominal” point for all combinations, the deviations from nominal removal for each context can be described by the equations

[0078] y_1A=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_At₀ (11)

[0079] y_1B=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_Bt₀ (12)

[0080] y_1C=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_Ct₀ (13)

[0081] y_2A=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_At₀ (14)

[0082] y_2B=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_Bt₀ (15)

[0083] y_2C=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_Ct₀, (16)

[0084] where the subscript “1” refers to the process tool 200, and the subscript “2” refers to the process tool 210.

[0085] The entire system can be combined into a single state-space model,

\begin{matrix} {[\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k + 1} = {[\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k} + {[\begin{matrix} r_{0} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] [t]}_{k} & (17) \\ {[\begin{matrix} y_{1 A} \\ y_{1 B} \\ y_{1 C} \\ y_{2 A} \\ y_{2 B} \\ y_{2 C} \end{matrix}]}_{k} = {[\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k}, & (18) \end{matrix}

[0086] where the states consist of the adjustment. (x_adj), tool biases (r₁and r₂), and product biases (𝑓_A, 𝑓_B, and 𝑓_C). This model is of a hypothetical situation where all product/tool combinations run simultaneously with the same input settings. Although this situation is unlikely to arise in practice, it is useful from the standpoint of understanding the interactions between the different processing contexts. It is clear, for instance, that the single product factor 𝑓_Ais used for all runs of product A, regardless of processing tool.

[0087] The observability test calculated here,

\begin{matrix} O^{T} = [\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 0 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \end{matrix}], & (19) \end{matrix}

[0088] is rank deficient by one, so the system is not observable in its current form. The reason for this situation is that all runs are confounded by both a product bias and a tool bias. An additional constraint would be needed to lock down one or the other. One method of adding additional measurements to the system involves the use of qualification experiments. During these events, standard tests are run on the equipment that can include the processing of specially prepared “reference” batches. As these tests are standardized across the group of tools, it is convenient to declare that there is no product-specific bias for these special runs. This means that the tool bias can be measured directly during the course of the test on a particular tool. When such experiments are not an option, it is also possible to simply select a reference tool or product that has a (known) nominal bias. The primary disadvantage of this method is that it may be difficult to identify a reference tool or product in a manufacturing environment that is constantly changing. The key here, though, is to find a way to make the system observable. The only ways to do this are to add needed outputs (measurements), add constraints (effectively reducing the number of states), or change the form of the model to something completely different.

[0089] In the example above, tool qualifications would appear as two new cases described by the following equations.

[0090] y₁=r₁ (20)

[0091] y₂=r₂, (21)

[0092] where y₁and y₂represent the deviations from nominal removal observed during qualification of tools 200 (i.e., 1) and 210 (i.e., 2), respectively. If the qualification experiments are added to the example system, then the new output equation for the combined system is

\begin{matrix} {[\begin{matrix} y_{1 A} \\ y_{1 B} \\ y_{1 C} \\ y_{2 A} \\ y_{2 B} \\ y_{2 C} \\ y_{1} \\ y_{2} \end{matrix}]}_{k} = {[\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k} & (23) \end{matrix}

[0093] The observability matrix for this new system is

\begin{matrix} O^{T} = [\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 0 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}] & (24) \end{matrix}

[0094] is full rank, so this system is observable. However, the system here is still tile fictional case where all possible runs can happen simultaneously. In practice, one run happens at a time. It is necessary to determine the appropriate way to update the model states after each run.

[0095] Structurally, this system resembles a real system where the different measurements are sampled at different frequencies. With such a system, the observability changes over time as different combinations of measurements are available. The underlying implicit requirement, though, is that the system be observable in the limiting case where all possible measurements are made at every time step.

[0096] As described above by the equations above, it is possible to have a discrete time system model where only a subset of the possible measurements are made at each time step. In such a system, it is necessary to make state updates whenever new measurements arrive, integrating as much information as possible from the new measurements into the state estimates. In general, prediction errors (deviations between the measured and predicted outputs) drive changes to the state estimates. In the illustrated embodiment, the primary case under investigation has a measurement that is affected by more than one state.

[0097] Conceptually, such a problem appears impossible to solve, because a single known measurement has to be used to update more than one unknown state. However, in the illustrated embodiment, the controller 130 uses additional available information to handle to state updates. As described in greater detail below, the observer component 134 maintains estimates for all the states as well as a measure of the certainty of those estimates and applies a statistical analysis to determine which states are most likely to be the cause of an observed error in the predicted measurement.

[0098] The discussion now focuses on the design of the observer component 134. A major benefit that results from the understanding of optimal control theory is the realization that the control actions may be separated from the learning about the system. This general principle enables intuitive possibilities for controller 130 tuning. For instance, the response of the control law component 132 can be made more sluggish without affecting the state estimation routine. The control law component 132 can use the best information about the state of the system 10 to make whatever decisions it needs. The following discussion focuses on the state estimation problem. Once this problem is solved, any type of control law may be used to take advantage of the state estimates.

[0099] The following discussion addresses the problem of performing state updates when not all measurements are taken at each time step. In addition to the control of a semiconductor manufacturing line, this kind of system also applies to a traditional chemical process where some variables are sampled more frequently than others. For example, a flow meter can be constantly producing flow rate measurements, but the compositional analysis might only be done every several hours.

[0100] It is necessary to determine the best guesses of the true values of the system states given only partial information. The first step is to ensure that the system is observable in the case where all of the possible measurements are taken at each time step, as described above.

[0101] The system states are generally unknown quantities that are affected by noise and disturbances in addition to the known effects captured in the system model. From the standpoint of analysis, each system state can be treated as a continuous random variable. For convenience in this description, it is assumed that each is normally distributed around its current estimate with some variance, σ².

[0102] At the beginning of an estimation procedure, all of the variances are initialized to static values based on an experimental analysis of the process. The probability density function of each state is then given by

\begin{matrix} f (x) = \frac{1}{\sqrt{2 π σ}} \exp (- \frac{{(x - \overline{x})}^{2}}{2 σ}), & (25) \end{matrix}

[0103] where {overscore (x)} is the mean and σ²is the variance. A plot of this function is shown in FIG. 3A.

[0104] For an n-vector of random variables, the probability density is given by

\begin{matrix} f (x) = \frac{1}{\sqrt{{(2 π)}^{″}} \det V} \exp (- \frac{1}{2} {(x - \overline{x})}^{T} V^{- 1} (x - \overline{x})), & (26) \end{matrix}

[0105] where {overscore (x)} is the vector of means and V is the covariance matrix given by

[0106] V=E((x−{overscore (x)})(x−{overscore (x)})^T). (27)

[0107] A plot of this multi-dimensional probability density function is shown in FIG. 3B. If there is nothing initially known about the interdependencies between the states, then V is simply a diagonal matrix of the variances of the state estimates

[0108] The expected values of all the states are needed, given the measurements taken at a particular time step. The procedure will be described for a simple example case and then generalized. For this example, assume a system has two states described by

\begin{matrix} x = [\begin{matrix} x_{1} \\ x_{2} \end{matrix}] & (28) \end{matrix}

[0109] and an output equation given by

[0110] y=Cx, (29)

[0111] where

\begin{matrix} C = [\begin{matrix} a_{1} & a_{2} \\ b_{1} & b_{2} \end{matrix}] . & (30) \end{matrix}

[0112] At any given time step, {circumflex over (x)}₁and {circumflex over (x)}₂are the current estimates for the states, while σ₁and σ₂are the variances associates with those estimates. Assuming the states are independent and normally distributed around the estimates, then the probability density function is given by

\begin{matrix} f (x) = \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) . & (31) \end{matrix}

[0113] The output matrix contains two measurements, but if only one is obtained, it is still necessary to do a state update. According to the equations above, the predicted value for the first measurement is given by

[0114] {tilde over (y)}₁=a₁{circumflex over (x)}₁+a₂{circumflex over (x)}₂. (32)

[0115] If a measurement of y_l,mis obtained for y_l, then the prediction error is

[0116] e_y=ŷ₁−y_l,m. (33)

[0117] The observer component 134 distributes this error between the states x₁and x₂. This distribution can be accomplished since a line l implied by the measurement,

[0118] y_l,m=a₁x₁+a₂x₂, (34)

[0119] is contained in the space where the probability density functions for the states are defined. The projection of the joint probability density function onto this line l provides an indication of the probability distribution after receiving the measurement. The line l may be visualized in FIG. 3B as the intersection between the plane, p, and the probability density function.

[0120] To compute the expected values of the states, let (x_1,0, x_2,0) represent the point on l closest to ({circumflex over (x)}₁,{circumflex over (x)}₂). This point is chosen for convenience as it exists for any line l. The point is derived here as the solution to the following problem

\begin{matrix} \min_{x1, x2} {(x_{1} - {\hat{x}}_{1})}^{2} + {(x_{2} - {\hat{x}}_{2})}^{2} & (35) \end{matrix}

a₁x₁+a₂x₂=y_l,m. (36)

[0121] If a₂0, then

\begin{matrix} - \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} = x_{2} . & (37) \end{matrix}

[0122] Substituting this into Equation 35 yields

\begin{matrix} \min_{x1, x2} {(x_{1} - {\hat{x}}_{1})}^{2} + {(- \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} - {\hat{x}}_{2})}^{2} . & (38) \end{matrix}

[0123] Setting the derivative with respect to x₁to zero yields

\begin{matrix} 2 (x_{1} - {\hat{x}}_{1}) + 2 (- \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} - {\hat{x}}_{2}) \frac{- a_{1}}{a_{2}} = 0. & (39) \end{matrix}

[0124] Grouping the x₁terms yields

\begin{matrix} x_{1} (1 + \frac{a_{1}^{2}}{a_{2}^{2}}) - {\hat{x}}_{1} - \frac{a_{1} y_{1}}{a_{2}^{2}} + \frac{a_{1} {\hat{x}}_{2}}{a_{2}} - 0. & (40) \end{matrix}

[0125] Therefore,

\begin{matrix} x_{1} = \frac{{\hat{x}}_{1} + \frac{a_{1} y_{1}}{a_{2}^{2}} - \frac{a_{1} {\hat{x}}_{2}}{a_{2}}}{1 + \frac{a_{1}^{2}}{a_{2}^{2}}} \frac{a_{2}^{2}}{a_{2}^{2}} = \frac{a_{2}^{2} {\hat{x}}_{1} + a_{1} y_{1} - a_{1} a_{2} {\hat{x}}_{2}}{a_{1}^{2} + a_{2}^{2}} . & (41) \end{matrix}

[0126] By symmetry,

\begin{matrix} x_{2} = \frac{a_{1}^{2} {\hat{x}}_{2} + a_{2} y_{1} - a_{2} a_{1} {\hat{x}}_{1}}{a_{1}^{2} + a_{2}^{2}} . & (42) \end{matrix}

[0127] So,

\begin{matrix} (x_{1.0}, x_{2.0}) = (\frac{a_{2}^{2} {\hat{x}}_{1} + a_{1} y_{1} - a_{1} a_{2} {\hat{x}}_{2}}{a_{1}^{2} + a_{2}^{2}}, \frac{a_{1}^{2} {\hat{x}}_{2} + a_{2} y_{1} - a_{2} a_{1} {\hat{x}}_{1}}{a_{1}^{2} + a_{2}^{2}}) & (43) \end{matrix}

[0128] The line, l, can be parameterized in t by

[0129] x₁(t)=x_1,0+a₂t (44)

[0130] x₂(t)=x_2,0−a₁t (45)

[0131] Now, the unnormalized integral, k_l, of the probability density function along line l may be defined by

\begin{matrix} k_{l} = \int_{l} \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ l, or & (46) \\ k_{l} = \int_{- \infty}^{\infty} \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} (t) - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} (t) - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ t . & (47) \end{matrix}

[0132] Then, the expected value of t is given by

\begin{matrix} t_{\exp} = \frac{1}{k_{l}} \int_{- \infty}^{\infty} t \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} (t) - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} (t) - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ t, & (48) \end{matrix}

[0133] and the expected values of the states are given by

[0134] x₁=x_1,0+a₂t_exp (49)

[0135] x₂=x_2,0−a₁t_exp. (50)

[0136] Conceptually, the update will distribute the prediction error between the two states in a way that the change made to the state estimate is larger for a parameter with more uncertainty (variance). This is because the expected point on the line l is dominated by the parameter estimate with a “wider” probability density. This is illustrated graphically in FIG. 3B. The plane, p, cutting through the probability density function represents the information contained in a new measurement that is a function of both x₁and x₂. The intersection of the plane, p, with the probability density function is the probability distribution given the new information.

[0137] The discussion above has a similar goal to a derivation of the discrete Kalman filter. It is desired to use uncertainty information to obtain better parameter estimates. There are multiple ways the Kalman filter can be derived. The formulation above treats the measurement information (l) as an absolute while in the Kalman filter derivation it carries uncertainty just as the state estimates do. Mathematically, the line l acts as a constraint above while in the Kalman filter formulation, it corresponds to a penalized term in an objective function that is being minimized. The Kalman filter approach to this problem will be outlined in greater detail herein as it is a much more general approach to the estimation problem.

[0138] Consider a system where {overscore (x)} is the current vector of state estimates, P is the error covariance matrix for the state estimates, and y is a vector of measurements described by

[0139] y=Cx+v, (51)

[0140] where v represents random measurement error with zero mean and covariance matrix R.

[0141] Given the system described above, the discrete Kalman filter essentially minimizes the performance index

\begin{matrix} J = \frac{1}{2} ({(x - \overline{x})}^{T} P^{- 1} (x - \overline{x}) + {(y - Cx)}^{T} R^{- 1} (y - Cx)), & (52) \end{matrix}

[0142] over x to arrive at the new state estimate vector.

[0143] This weighted least squares performance index minimizes the prediction error while penalizing changes to state estimates where the confidence in the current estimates is high. This is easy to see if the covariance matrix P is a diagonal matrix consisting only of the variances. A highly confident state estimate will have a low variance, so the corresponding element of P⁻¹will be very large. In addition, if multiple measurements are received, they are weighted in the objective function in accordance with their confidence levels (as determined by the variance terms in the matrix R).

[0144] It is useful to note that when the terms of R are very small in magnitude, the new x must do a good job of explaining the measurement y, because the (y−Cx) terms are heavily penalized for large R⁻¹. If R is small, there is very little uncertainty in the measurement vector y. In the extreme case, the solution approaches the case where the state estimates end up on the line (or plane) defined by the measurements as in Equation 34. The optimization problem described in Equation 52 can be solved analytically by setting the differential dJ to zero.

[0145] dJ=dx^TP⁻¹(x−{overscore (x)})−(Cdx)^TR⁻¹(y−Cx). (53)

[0146] Thus,

[0147] 0=dx^T[P⁻¹(x−{overscore (x)})−C^TR⁻¹(y−Cx)]. (54)

[0148] Since dx can vary arbitrarily, the term in brackets must be zero, and it is possible to solve for the optimal x algebraically.

[0149] 0=P⁻¹x−P⁻¹{overscore (x)}−C^TR⁻¹y+C^TR⁻¹Cx (55)

[0150] 0=(P⁻¹+C^TR⁻¹C)x−P⁻¹{overscore (x)}−C^TR⁻¹y (56)

[0151] (P⁻¹+C^TR⁻¹C)x=P⁻¹{overscore (x)}+C^TR⁻¹y+C^TR⁻¹{overscore (x)}−C^TR⁻¹{overscore (x)} (57)

[0152] (P⁻¹+C^TR⁻¹C)x=(P⁻¹+C^TR⁻¹C){overscore (x)}+C^TR⁻¹y−C^TR⁻¹C{overscore (x)} (58)

[0153] x={overscore (x)}+(P⁻¹+C^TR⁻¹C)⁻¹C^TR⁻¹(y−C{overscore (x)}). (59)

[0154] In the two-variable case described above,

[0155] C=[a₁a₂] (60)

[0156] and

\begin{matrix} P = [\begin{matrix} σ_{1}^{2} & 0 \\ 0 & σ_{2}^{2} \end{matrix}] . & (61) \end{matrix}

[0157] Since there is only one measurement, the matrix R is simply the single term R. So for this case

\begin{matrix} x = \overline{x} + {([\begin{matrix} \frac{1}{σ_{1}^{2}} & 0 \\ 0 & \frac{1}{σ_{2}^{2}} \end{matrix}] + [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [\begin{matrix} a_{1} & a_{2} \end{matrix}])}^{- 1} [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] . & (62) \end{matrix}

[0158] Equation 62 can be further simplified by

\begin{matrix} x = \overline{x} + {[\begin{matrix} \frac{σ_{1}^{2} a_{1}^{2} + R}{σ_{1}^{2} R} & \frac{a_{1} a_{2}}{R} \\ \frac{a_{1} a_{2}}{R} & \frac{σ_{2}^{2} a_{2}^{2} + R}{σ_{2}^{2} R} \end{matrix}]}^{- 1} [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] & (63) \\ x = \overline{x} + \frac{σ_{1}^{2} σ_{2}^{2} R}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} \frac{σ_{2}^{2} a_{2}^{2} + R}{σ_{2}^{2} R} & - \frac{a_{1} a_{2}}{R} \\ - \frac{a_{1} a_{2}}{R} & \frac{σ_{1}^{2} a_{1}^{2} + R}{σ_{1}^{2} R} \end{matrix}] [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] & (64) \\ x = \overline{x} + \frac{σ_{1}^{2} σ_{2}^{2} R}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} \frac{a_{1}}{σ_{2}^{2} R} \\ \frac{a_{2}}{σ_{1}^{2} R} \end{matrix}] [y - C \overline{x}] & (65) \\ x = \overline{x} + \frac{1}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} a_{1} σ_{1}^{2} \\ a_{2} σ_{2}^{2} \end{matrix}] [y - C \overline{x}] . & (66) \end{matrix}

[0159] This result demonstrates how the uncertainties in the state estimates and the measurement affect the update.

[0160] In the case where only a subset of the measurements arc obtained, y, R, and C in Equation 52 are replaced by the reduced versions. Here y_ris the vector of measurements obtained, C_rcontains the rows in C that give the measurements obtained, and R_ris the covariance matrix for this reduced set of measurements. In this situation, the state update is given by

[0161] x={overscore (x)}+(P⁻¹+C_r^TR_r⁻¹C_r)⁻¹C_r^TR_r⁻¹(y_r−C_r{overscore (x)}). (67)

[0162] As different measurements are taken, the effective C and R matrices change. Since the effective output matrix is not constant, the variance estimates (and hence the effective update weights) never reach a steady state, even when the controller 130 runs for many time steps. The observer component 134 is constantly changing its gain as the processing mix changes.

[0163] State and variance estimates are updated at two distinct times: at the processing time and when measurement information arrives. The update at the processing time is a predictive update using the known model of the system. In this case, the model error is assumed to have zero mean and known covariance. The current state and variance estimates are both passed through the state transition matrix to arrive at new estimates. The update at the measurement step (the innovation) takes into account the new information learned from the measurements by solving the problem stated in Equation 52.

[0164] The evolution of x in time is given by

[0165] x_k+1=A_kx_k+B_ku_k+G_kw_k (68)

[0166] where u_kis the process input and w_kis a random process error with zero mean and covariance matrix Q. As above, the measurement taken is given by

[0167] y_k=C_kx_k+v_k, (69)

[0168] where v represents random measurement error with zero mean and covariance matrix R.

[0169] Any time the process is run, the state estimates and error covariance are updated using the following equations:

[0170] x_new=Ax_old+Bu (70)

[0171] P_new=AP_oldA^T+GQG^T (71)

[0172] These equations update the estimate for x assuming there is no noise, but the uncertainty contained in P increases. Any time a measurement is taken, the state estimates and error covariance are updated using these equations:

[0173] x_new=x_old+(P_old⁻¹+C^TR⁻¹C)⁻¹C^TR⁻¹(y−Cx_old) (72)

[0174] P_new=(P_old⁻¹+C^TR⁻¹C)⁻¹. (73)

[0175] These equations ensure that the new estimate of x reflects the measurement data, and the uncertainty contained in P decreases. It is useful to note that the measurement update changes the off-diagonal terms in the error covariance matrix. These terms retain a memory of how states are related to each other based on past measurements.

[0176] So after each time step, the error covariance matrix is updated along with the state estimates. In general, a processing step increases the uncertainty (variance) while an additional measurement decreases the uncertainty. The fact that different combinations of measurements are made leads to different patterns in the covariance matrix.

[0177] Nonlinear systems can be handled by using the matrix of partial derivatives of the model equations instead of the matrices A, B, and C. In general, the same analysis still applies, and the process model is linearized around the current operating point at each time step.

[0178] In the nonlinear case, the model equations are a more general relation between the current and future state values.

[0179] x_k+1=f(x_k,u_k) (74)

[0180] y_k=h(x_k) (75)

[0181] At a given time step, these equations can be linearized to create the corresponding terms from the linear model.

\begin{matrix} A \approx [\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \frac{\partial f_{1}}{\partial x_{2}} & \dots \\ \frac{\partial f_{2}}{\partial x_{1}} & \frac{\partial f_{2}}{\partial x_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (76) \\ B \approx [\begin{matrix} \frac{\partial f_{1}}{\partial u_{1}} & \frac{\partial f_{1}}{\partial u_{2}} & \dots \\ \frac{\partial f_{2}}{\partial u_{1}} & \frac{\partial f_{2}}{\partial u_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (77) \\ C \approx [\begin{matrix} \frac{\partial h_{1}}{\partial x_{1}} & \frac{\partial h_{1}}{\partial x_{2}} & \dots \\ \frac{\partial h_{2}}{\partial x_{1}} & \frac{\partial h_{2}}{\partial x_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (78) \end{matrix}

[0182] The following discussion outlines the use of an estimation algorithm based on the Kalman filter to be used in a run-to-run control situation with multiple processing contexts. The algorithm utilizes {overscore (x)}_kand {overscore (P)}_k, the state estimate vector and the uncertainty information contained in the error covariance matrix. When it is time to compute settings for a particular run, the observer component 134 must first identify the states and measurements that apply to the run. Since the objective for the run is to achieve a particular value of the system output, the controller 130 must calculate the effective output mapping, C_rfor the given context.

[0183] Given the correct output mapping and the current state estimates, the control law component 132 can compute the process inputs and allow the process to proceed. Also at this time, the observer component 134 computes estimates for the post-process states {circumflex over (x)}_k+1and covariance {circumflex over (P)}_k+1using the process model. Using the effective output matrix, the observer component 134 can also predict the output ŷ_k+1.

[0184] After the run, the observer component 134 receives a measurement y_k+1. The observer component 134 can use the current state and covariance estimates along with the new measurement to minimize Equation 52. This results in new values for {circumflex over (x)}k+1 and {circumflex over (P)}_k+1. As new products or tools 200, 210 are added, their state estimates must be added to the states already being stored and updated.

[0185] Due to changing process conditions such as the addition of new products or tools 200, 210, it is possible for the number of states tracked by the observer component 134 to change. It is beneficial for these changes to disturb the controller 130 as little as possible. To achieve this minimized disturbance, the information about the new state is merged into the existing state vector and error covariance matrix. After choosing an appropriate initial guess for the state estimate, a new element is added to the state vector to track the new state. In addition, a new row and column are added to the error covariance matrix. These new elements in the covariance matrix can all be initialized with zero except the variance term, which should be set relatively high to indicate that the new state is not well characterized.

[0186] The tuning parameters include the estimated noise properties for the model uncertainty (the G and Q matrices in the system model equations) and measurements (the R matrix). Also, the initial guesses for new states and state estimate variances must be determined. By choosing a high initial guess for the uncertainty in a new state estimate, the observer component 134 will be forced to update it preferentially until it more closely matches the performance of the existing states.

[0187] The choice of the R matrix affects how quickly the estimation scheme responds to measurement data. Larger values lead to a more sluggish response. The choices for the G and Q matrices affect how quickly the relative uncertainties in the different model states increase with processing. These can be used to cause the estimation scheme to favor updating certain parameters more than others.

[0188] The optimal tuning and even the model form depend heavily on process conditions. There is no perfect controller, but rather only a best controller for a given set of process conditions. A good understanding of the expected disturbances leads to a design that performs well under those circumstances.

[0189] In the state estimation scheme described above, there are two times that the state and uncertainty estimates are changed. These are the prediction made at processing time and the update at measurement time. To function correctly, the state estimation algorithm maintains a complete history of all runs that have been processed including all known measurements relating to them. In a batch-oriented processing environment with measurements taken before and after processing, it is possible for measurements to be delayed or even skipped entirely. It is necessary to ensure that the state estimator correctly assembles the information it receives into an accurate processing history.

[0190] In principle, it is possible to retain a complete processing history for the system, containing the inputs and outputs for each processing run. Then, when a measurement arrives, it is simply inserted into the history at the appropriate point. All the current state estimates can be computed by starting with the original guesses and iterating through each time step in the history.

[0191] Such a method requires very large data storage capacity. However, it is not always necessary to store all this data to calculate the correct current state estimates. In a system with 100% metrology (all variables measured for every run), the results from all of the runs will eventually be measured. If a record for the run is created at the processing step, it can be updated with the measurement data when the information becomes available.

[0192] All of the complete (process and metrology data available) records starting from the beginning of the history table and continuing until the first unmeasured run can be collapsed into the running “initial guesses” for the table. This is accomplished by performing both the prediction update and measurement update for each record. Nothing can be processed without making a processing record, so there is no chance of acquiring a measurement that does not correspond to a process event still in the table. This reduces the history table down to only the period of time where there are still measurements missing.

[0193] In the case where the operating constraints do not allow every run to be measured, it is necessary to define an expiration time. Runs older than the expiration time that have not yet been measured are discarded with the assumption that they will never be measured. This allows the standard collapsing described above to go on even in the case of incomplete metrology. An unmeasured process run only has the predictive update done when it is collapsed.

[0194] The adjustments described above allow the controller to treat the measurement data as a continuous stream even though the data can really arrive late and sometimes not at all. The following example shows how the controller for a multiple tool and product process would handle a typical situation. In this case, it is assumed that the tool and product names are sufficient to determine which model states are affected in each run. Table 1 illustrates a list of process events for this case.

TABLE 1

Process Events: Case 1

[0195] If the process proceeds in the order described in Table 1, then no historical information needs to be saved at all. Each event can update the controller states in the normal way as described in the table. Here, the only data that must be saved are included in x*, which denotes the “running total” of the set of state and uncertainty estimates. The values for x* are updated with each event, and then the event data are discarded.

[0196] However, if the processing occurs as described in Table 2 below, then the observer component 134 must decide how to interpret each new piece of data. Handling the measurement events is not as simple as before because the measurement information is out of date. Clearly, the observer component 134 still needs to do a state update with each new measurement, but it cannot simply base new state values on the latest measurement because the new information refers to an operation that took place in the past. The solution is to save all the event information so that the complete history can be constructed as the information becomes available. Information is then discarded only when it is no longer needed.

TABLE 2

Process Events: Case 2

[0197] Let x⁰denote the set of state and uncertainty estimates before any stored events are included. Then x* can be calculated by starting at x⁰and iterating over the stored events, applying the necessary updates.

[0198] For the first event in Table 2, there is no dependence on other information. Therefore, the state estimates can be predicted, and x⁰can be updated. In this case x* is equal to x⁰, and the event data are discarded.

[0199] The next three events (2-4) in Table 2 are incomplete because the measurement steps for earlier batches have been skipped. In this case, x⁰remains constant, and the data for the three events are added to an internal history maintained by the observer component 134. This history is illustrated below in Table 3. Note that the event that is known to be missing is denoted with “N/A.” Now, x* can be calculated by starting at x⁰and iterating over the three events in Table 3.

TABLE 3

Controller Internal History (Events 2-4)

[0200] When the next event (5) arrives, the observer component 134 has a complete set of data for all batches so far, so x⁰can be updated. Here the internal history contains the events listed in Table 4. The observer component 134 can update x⁰by iterating over these events. Then, the event data are safely discarded.

TABLE 4

Controller Internal History (Events 2-5)

[0201] The next two events (6-7) are incomplete because batch 3 was never measured. As before, the observer component 134 adds them to its internal history as shown in Table 5 and does not update x⁰. As described above, it is possible to define an allowable time window for the data to arrive. If enough time passes, the observer component 134 can assume that the batch 3 measurement data will never arrive, and it can proceed by collapsing the data from events 6 and 7 into x⁰.

TABLE 5

Controller Internal History (Events 6-7)

[0202] Based on the analysis above, each element in the measurement matrix is a random variable equal to a function of one or more of the states. Thus, it is possible to define a probability density function for the predicted values of the vector of measurements. If x has an error covariance matrix P, and the prediction of the output is given by Cx, then the covariance for the predicted output is given by CPC^T. This covariance matrix may be used to construct a probability density function for the predicted output using Equation 26.

[0203] Confidence intervals calculated for the predicted measurements can then be compared to specified operating limits to determine the processing and sampling requirements necessary to stay within the operating limits. This comparison gives the controller 130 a metric for estimating its own performance and potentially warning the user or even taking action to prevent a problem before it happens.

[0204] In this discussion, it has been shown that there is a statistical basis for using an uncertainty term to drive state estimate updates. The technique described updates states in a model even when direct measurements of them are not available. The discussion now presents simulation data for many different combinations of operating conditions as well as some comparisons to other control methods.

[0205] The state estimation scheme described above is designed to analyze large systems with several sources of variation using only portions of the desired data at any given time. The following discussion describes several simulations that illustrate how the state estimation scheme responds to different processing conditions. First, a base case is built to verify the controller 130 performance under nominal conditions. Then, complications are added sequentially to build up to more realistic operating conditions. The performance is also compared to a different controller (not shown) using the same challenge data.

[0206] In this section the initial testing environment is described, and some of the basic assumptions made in the remainder of the tests are justified based on the results obtained. To study the real effects of the changing process conditions, a simple run-to-run plant model is chosen. This plant model is a discrete-time model that evolves over the run number. The continuous-time effects that occur during processing of each batch are integrated to represent average characteristics of the batch as a whole. According to the plant model, the output is simply equal to the input plus the plant bias. The plant bias is not affected in any way by the chosen value of the input.

[0207] Since the following runs simulate the use of several different kinds of products and different processing tools, it is necessary to determine the sources of variation so that appropriate system states may be chosen. In a real application this involves a detailed analysis of available process data, but in this example, an assumption is made that the bias consists of a component from the processing tool as well one from the product being run.

[0208] In terms of the simulation, product refers not only to distinct products, but to the general class of features that make one run on a tool different from another. In other words, each product/layer combination in a real environment would be a different “product” in this simulation.

[0209] The process model for a particular tool and product can be written

[0210] y=x_t+x_p+u, (79)

[0211] where y is the output, x_tand x_pare the tool and product biases, and u is the chosen process input. The target is a particular value of y. For most of the simulations, a value of zero is chosen as the target. A further assumption is that tool qualification events are available and capable of measuring x_tdirectly for every tool i. This assumption of qualification events results in the system being observable.

[0212] A traditional discrete time state space model is used, including the terms for process and metrology noise,

[0213] x_k+1=A_k+B_ku_k+G_kw_k, (80)

[0214] y_k=C_kx_k+v_k. (81)

[0215] So, for a system with m tools and n products, a state vector is constructed as

[0216] x=[x_adjx_tx_t. . . x_tx_px_p. . . x_p]^T (82)

[0217] where x_adjis the adjustment state, and all tools and products are tracked with individual elements. The vectors w and v represent the process noise and measurement noise, respectively, and they are both assumed to be normally distributed with zero mean. The noise vectors are used in the control model so that assumptions can be made in the state estimation routines. In the simulations, other disturbances are added to the model in addition to the noise terms. These other disturbances affect the system by directly modifying the states in a way that the controller 130 cannot predict.

[0218] The state transition matrix is a square matrix of size m+n+1 and is given by

\begin{matrix} A = [\begin{matrix} 0 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \end{matrix}], & (83) \end{matrix}

[0219] which shows that all the tool and product parameters are nominally stationary. The process input is assumed to affect only x_adj, so it is of size m+n+1 by 1 with an effect given by

[0220] B=[1 0 . . . 0]^T. (84)

[0221] The complete output matrix (of size mn+m by m+n+1) for the process is given by

\begin{matrix} C = [\begin{matrix} 1 & 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \\ 1 & 1 & 0 & \dots & 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 1 & 0 & \dots & 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 1 & \dots & 0 & 1 & 0 & \dots & 0 \\ 1 & 0 & 1 & \dots & 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 1 & \dots & 0 & 0 & 0 & \dots & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 1 & 0 & \dots & 0 \\ 1 & 0 & 0 & \dots & 1 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & 0 & \dots & 0 & 0 & 0 & \dots & 0 \\ 1 & 0 & 1 & \dots & 0 & 0 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 0 \end{matrix}], & (85) \end{matrix}

[0222] which results in an observable system. In each simulation run, only one row from the output matrix is active. This reduced subset of the output matrix is denoted by C_eff.

[0223] The simulations in this description employ three main components that are constrained to communicate only in certain ways. The primary component is the simulation driver 136, which is responsible for maintaining the “real” parameter values and calculating “measurements” based on control moves. Although, the simulation driver 136 is illustrated in FIG. 2, it would not normally be used in an actual implementation. It is depicted to aid in the understanding of the illustrations below. The control law component 132 is responsible for computing the settings to use for each run based on tool and product IDs provided by the simulation driver 136. The observer component 134 is responsible for updating the state estimates based on measurement information calculated by the simulation driver. This flexibility allows for a different model to be used for the plant than the controller 130 itself uses, but for ease of illustration, this capability is not used in these initial simulations.

[0224] In these initial tests, a plant with ten tools and ten different products is used. Each tool and product is assigned a unique bias, so there are twenty bias states in the model. In addition, each bias is assigned its own disturbance properties including noise and drift. The noise in each state is roughly an order of magnitude smaller than the average difference between the values of different states. A similar amount of noise is added to each measurement taken. A nominally stationary process is chosen to highlight the state estimation. As the states are not normally moving, the effects of disturbances are easier to visualize.

[0225] First, the process signal dataset is generated by choosing products and tools to run at random, with all tools and products having equal probability. This dataset is saved as a history of tool IDs, product IDs, and real states for each run. For each run in the simulation, the simulation driver sends the product and tool IDs, the target, and a unique ID for the particular run to the control law component 132. The control law component 132 returns the chosen process input and is responsible for maintaining its own set of information about each run. The simulation driver 136 then computes the process output based on the given input and the true states. This output is then passed to the observer component 134 of the controller 130 along with the unique ID for the run. The observer component 134 updates the state estimates for the controller 130 based on the supplied output data.

[0226] Since the focus of this discussion is on state estimation, a very simple control law is chosen for implementation by the control law component 132. The control law component 132 uses the state estimates for the current tool and product biases and uses a plant inversion to solve for the input that will place the output at the target. Of course, in an actual implementation, a variety of different control laws may be used. Using this control law, the deviation of the output from the target shows the error in the state estimates used.

[0227] The design of the observer component 134 contains many adjustable parameters that can be used for tuning. As described above, these parameters deal with the assumed noise properties of the system under study. In these simulations, a number of assumptions are made. First, all of the measurements are assumed to be equally reliable, so the variance estimate contained in the R_effmatrix is always the same. In a real manufacturing facility, maintenance information from measurement tools and information about certain products may provide different values. The other assumptions deal with the process noise. The noise terms in the process model are constant throughout the simulation. The G and Q matrices are set so that the noises affecting the different states are not related, and tool states are noisier than product states. Again, in a real application, offine analysis must be used to determine these values. According to the model, the noise affects all the states, even the ones corresponding to tools and products that are not active for the current run.

[0228] These noise estimates are part of the model and are not related to the actual noise inserted into the simulations as they run. It is possible to manipulate the estimates to achieve different results. For example, if the observer is too sluggish, the process noise terms can be set higher. Since the parameters would then have more uncertainty, the observer component 134 would make larger adjustments to the state estimates.

[0229] The first test for the controller 130 is to start with no information about the states of the system to be sure that it is able to bring the system under control. The real states contain noise and slight amounts of drift. FIG. 4 illustrates a plot of the output when the controller 130 is placed on a process with 10 tools and 10 products. The controller 130 has no prior information about the values of the states, and it is able to learn them quickly and bring the process under control.

[0230] The controller is initialized with all of its state estimates at zero. There is also an initial covariance matrix. Here, a diagonal matrix is used as the starting point with values chosen to represent the initial uncertainty in each of the states. Because product to product differences can be more dramatic than tool differences, the initial variance for the product states is set higher than that for tool states.

[0231] As shown in FIG. 4, the controller 130 negates the majority of the error after about 25 runs, and the controller 130 runs at a steady operating state after that. The steady noise level in the output is approximately equal to the magnitude of the noise being inserted into the process states by the simulation driver 136. The controller 130 begins with 20 unknown states, and it identifies them all reasonably well after about as many runs.

[0232] While it is important to be able to illustrate that the controller 130 can accomplish this task, it is not a case that is likely to appear in a real production environment. Offline analysis could be used to determine reasonable initial guesses for the controller 130 states. If a process is running with this combination of tools and products before a controller 130 is to be deployed, the observer component 134 of the controller 130 could be run on the production data to establish the correct state estimates before starting the controller 130.

[0233] It is more common for new products to be introduced slowly over time, while existing ones gradually disappear. In this example, there are a total of 10 tools and 10 products, as in the previous case, but the rules for the simulation are different. All 10 tools arc available at the start, but products are added slowly over time. Initially, only one product is available, but every 100 runs a new product is added to the mix. The response of the controller 130 is shown in FIG. 5, which shows a plot of the effective combined tool and product bias as 10 products are ramped up on 10 tools. For each run, the product to run and tool to use are selected at random from the available set. The plot of FIG. 5 is obtained by charting the output y when the input u is held at zero.

[0234] Each new product appears as a disturbance when it is first added, but the controller 130 quickly addresses disturbances. It is unlikely that entire batches of brand new products would be committed to production without any preparation in a real manufacturing environment. When a new product is introduced, in many cases, partial batches can be run to provide the controller 130 with the appropriate information. In other cases, an engineer may have enough knowledge to effectively choose a reasonable initial guess for the new state.

[0235] Intuitively, when a new product appears, there is a high probability that the initial state estimate is in error. For this reason, the state for the new product should be adjusted if indeed the controller 130 does not hit the target. In the control algorithm, this is accomplished by specifying an initial variance estimate for new states. When a new state is added, a new element with the initial state estimate is inserted into the state vector, and a new row and column are added to the error covariance matrix. In these simulations, the new row and column in the covariance matrix are all zeros except the diagonal element. This element is set to the initial variance estimate for the state. Specifying a higher value for this initial estimate means that the new state will absorb more of the error from the first run where the new state is used.

[0236] Subsequent test cases begin with stable systems and assuming that the controller 130 begins near the correct state values. In this manner, individual disturbances can be injected and analyzed without the observer component 134 having to do the initial state estimate learning again each time. In this section a series of standard disturbances are generated and used as the process signal for the controller 130. In each case, the system begins at a stable operating point, and the controller 130 has current state estimates. The ability of the controller 130 to respond to step disturbances, ramp disturbances, and target changes is tested first. Then, more difficult challenges such as measurement lag and missing measurements are illustrated to see the robustness of the controller 130 in the face of more realistic situations.

[0237] It should be noted that the disturbances under study here involve repeatable and systematic effects. In general, there are also random and unpredictable high-frequency components that appear as noise because they are not captured by elements of the chosen process model. The observer component 134 can only detect variations within the scope of the chosen model form, and the goal of the controller 130 is to eliminate them.

[0238] There are many events that can result in an apparent immediate shift in the performance of a tool. A step disturbance is a common signal used to test filters and controllers. Mathematically, the step disturbance is represented as a step function

[0239] δ_k(t)=0, t<k (86)

[0240] δ_k(t)=1, t>k (87)

[0241] The simulation driver 136 adds a step disturbance to one of the tool states after 100 runs to ensure that the controller correctly rejects the unexpected disturbance. In a multiple processing setup such as this system, the step disturbance is not as straightforward as in a traditional process. In a simple system, a step disturbance remains visible from the time it appears until a correction is made. However, in the system under study here, the controller 130 observes combinations of different states at every time step. The disturbance only shows up occasionally because it is only visible when the perturbed state is used.

[0242] As shown in FIG. 6, the controller is able to compensate for the step disturbance at run 100. There is more than one “spike” on the graph is because the controller 130 has to determine whether the disturbance was in the product or the tool state, and a few runs pass before the suspect tool and product are used again. When the controller incorrectly predicts the results for a run, it is not immediately apparent which of the state estimates is in error. As described above, the observer component 134 uses the current estimates for the parameter uncertainties to assign the error to the parameters. Intuitively, to isolate the state that is in error, a subsequent run that shares either the tool state or the product state must be used. Each subsequent run exhibits the disturbance to a lesser degree.

[0243] The error covariance matrix that is present in a Kalman estimation scheme contains information about how the states are related. In this case, when the step disturbance first appears, the observer component 134 does not know whether the tool state or the product state used is in error. However, it distributes the error between the two states according to their relative uncertainties, meaning that one state estimate is partially moved incorrectly in the case of a disturbance to only a single state. However, the cross terms in the error covariance matrix relating the two states involved are also adjusted. This adjustment essentially provides information to the observer component 134 that it can use to repair the incorrectly moved state estimate once appropriate information becomes available.

[0244] This backfilling of information is a useful property of the observer component 134. As noted earlier, common state and parameter estimation schemes for multiple process environments are based on the partitioning of data. A characteristic of partitioned data is that one measurement only affects its own peers. Information from a new measurement of one parameter, for example, cannot be used to confirm or reject an observed signal in a different parameter. This combined estimation scheme can share data in this way, though, which means that fewer measurements are required to achieve proper state estimates.

[0245] Another example of the usefulness of this technique is in the use of qualification data. While many qualification events in a real plant are performed after tool maintenance or other discrete events, it is possible to use a qualification event to aid in state estimation. When a major disturbance is detected, the observer component 134 does indeed have to assign the error between different states. However, running a qualification test immediately on the affected tool can help minimize the impact of the disturbance on the controller 130. The qualification event is a direct measurement of the state associated with a particular processing tool. Intuitively, this will demonstrate whether the observed error was due to a tool issue or a product issue. Because the covariance matrix remembers what adjustments are made, after the tool state is measured, both the affected states will be moved to the correct values.

[0246] The simulation presented in FIG. 7 is identical to the one in FIG. 6 except that in this case a tool qualification is forced immediately after the disturbance is discovered. In this case the disturbance is rejected much sooner.

[0247] There are also many circumstances where a ramp, or continual drift may appear in the process. In this simulation, one of the tools is ramping between runs 100 and 400. To the controller 130, this type of disturbance appears as a persistent deviation from target, even as the states estimates are continuously updated. There has been a small amount of drift in all the simulations so far, but in this case, the magnitude of the drift is much larger.

[0248] As shown in FIG. 8, the controller 130 is able to compensate for this disturbance to some extent. Generally, this is a difficult disturbance to reject, and overall controller performance is degraded during the length of the drift. Controllers can be specially tuned to reject this kind of disturbance by augmenting the state matrix so that the ramp disturbance is included in the model, but this causes a trade-off in the performance with other types of disturbances. This particular controller is much more suited to dealing with step disturbances. Ramp disturbances of the magnitude of the one in the simulation generally indicate a major tool problem and would most likely result in a shutdown.

[0249] In a real manufacturing environment, it is not always possible to wait for measurement results before running the next batch of product. The measurements can take considerable time because wafers must be picked up individually, and usually several sites are examined on each wafer destined for metrology. It is important to keep the processing tools busy, so they must go ahead and start running again as soon as possible after each batch finishes. Thus, the measurements can lag behind the processing steps by several runs. This is not a straightforward example of a time delayed process because the delay is not constant. Measurements arrive as they are finished, and the controller 130 needs to take them into account as soon as possible.

[0250] In this series of tests, the process datasets from the earlier tests are used again, but the measurements are not sent to the observer component 134 right away. Instead, the measurements constantly lag behind the processing by a fixed number of runs. The simulation depicted in FIG. 9 has a delay of 10 runs on the measurements, and the simulation depicted in FIG. 10 has a delay of 30 runs.

[0251] In these tests, the controller 130 is still able to reject the step disturbance, but the response is delayed because the error is not seen until the measurements arrive. Compared to the case without measurement delay, there are many more runs that miss their targets, and the test with the longer delay takes longer to settle after the disturbance. As with a traditional single-input/single-output process, if the measurement delay is too large, the controller 130 will be ineffective.

[0252] It is not always possible to measure the properties important to control on every batch at every processing step. This is a result of a number of factors. First, measuring wafers from a batch after a particular processing operation increases the time those wafers will be in the plant. The need for accurate characterization must be balanced with the need to move material through the line as quickly as possible. Only as much material as is needed to build a representative sample is measured. Also, the number of measurements that are to be taken in a given period of time determines the number of metrology tools that must be present in the plant. As the tools are normally very expensive, this is also a limiting constraint.

[0253] So, there can be runs where the controller 130 must compute the settings but never receives feedback from the measurement system. In the simulation environment, the impact of this situation can be measured because the simulation driver 136 can always determine what the missing measurements would have been and add them to the chart of the controller output. In these simulations, the step disturbance case from above is used, but the controller 130 only receives one third of the measurements.

[0254] FIG. 11 shows how the output appears to the controller 130, while FIG. 12 shows the real outputs, including the batches the controller 130 did not get to see. The measurements visible to the controller 130 compare reasonably well with the complete measurements case depicted in FIG. 6. However, many of the unmeasured batches around the time of the step disturbance were away from the target. The fact that there are three spikes on the graph is coincidental and not related to the fact that one out of every three measurements were used. In this particular case, the third run affected by the disturbance was the first one measured. FIG. 13 illustrates the same case as the scenario of FIGS. 11 and 12, but with different measurements removed (i.e., a different third of the measurements were not received by the controller 130). As seen in FIG. 13, when different measurements are removed, the overall performance of the controller 130 changes.

[0255] Depending on process conditions, different variables may be easier or harder to observe. In the following section, a series of tests were run with a similar setup to the earlier ones, but with different processing rules and conditions. The scenarios in these tests attempt to impose realistic constraints on the operation of the process. Variables studied include plant size, product prioritization, and business operating rules.

[0256] Real manufacturing facilities have large numbers of tools and products. A values in the range of 20 tools and 50 products are reasonable values for a process area. The number of products can get very large because each process area contains batches at many different points in their process flow. Each layer being formed on a given product can behave just as differently as a different product as far as the state estimation algorithm is concerned. The simulation run here contains 10 tools and 50 products. The response of the controller 130 in this larger system to a step disturbance is plotted in FIG. 14

[0257] The plot of FIG. 14 is very similar to the plot for a 10×10 system shown in FIG. 6. The controller 130 is able to quickly identify the offending state and reject the disturbance. This result is important because it illustrates the ability of the state estimation routine to scale up to much larger systems.

[0258] One technique for addressing the problems associated with the large number of products and tools is to keep running specific products on specific tools for a long as possible before switching. This technique is commonly referred to as tool dedication, and is in fairly widespread use. In a situation where there are more tools than products, it reduces the control problem from a large multivariate problem to a number of simpler single variable problems. For each tool-product combination, only the combined state needs to be tracked, and no information is shared between contexts. Usually there are more products than tools, so tools are dedicated to long runs of particular products between switches.

[0259] However, tool dedication involves a trade-off. A tool dedication scheme reduces flexibility by limiting the potential tools where a given batch is allowed to run. When throughput of a particular product is a concern, tool dedication can cause unacceptable delays. Also, a problem occurs when a tool must be taken out of service (even temporarily). The products that run on the particular tool must be moved to other tools, and it is necessary to experiment to find the appropriate processing settings for the new combination.

[0260] The parameter estimation scheme described herein is affected by tool dedication, because dedicating causes certain combinations of tool and product states to be much more common than others. Intuitively, if a given product always runs on the same tool, it becomes more difficult to differentiate between errors in the state estimates for that tool and product. The next two simulations described use the 10 tool and 50 product step change datasets used above, but vary in the degree to which dedication is enforced.

[0261] FIG. 15 illustrates the response when the controller 130 on a 10 tool and 50 product process reacts to an unanticipated step disturbance at run 100. During the simulation, short continuous runs of tool dedication are encouraged by only switching to a different tool 25% of the time. FIG. 16 illustrates the case where longer durations of tool dedication are encouraged (i.e., switching only 10% of the time).

[0262] The results of the simulations of FIGS. 15 and 16 show many spikes in the controlled output, and the spike with the longer runs of dedication is much more dramatic. Each of the spikes is caused by a switch to a different tool/product combination. By contrast, the step disturbance is rejected much more rapidly than in previous cases. The other useful thing to notice is that between the spikes, the noise level is lower than in the previous simulations. Ideally, the controller 130 would achieve this reduced noise level all the time, but this is a part of the unavoidable trade-off. As will be discussed in greater detail below, the system as defined in these tests is unobservable when dedication is in effect. During a run of dedication, the measurements that are taken are a combination of a tool state and a product state. The controller 130 has to adjust one or both whenever output errors are detected, and it has no way to determine which one is really in error. When it is time to switch, there is a high probability that at least one state estimate has a significant error. Thus, tool dedication is a trade-off where short term gains are accepted at the cost of having greater uncertainty when the inevitable switch occurs.

[0263] In the next scenario a typical manufacturing case is tested where one particular product appears much more frequently than the others. The goal of the scenario is to illustrate that the minor products are not “forgotten” during long runs of the major product. Furthermore, the major product should not be disturbed when switching back from the minor ones. During this 10 tool and 10 product simulation, over half the runs are of a single product. The other nine products are evenly distributed among the other runs. As in the previous simulations, a step disturbance affects one of the tools at run 100. As illustrated in FIG. 17, the controller 130 handles this scenario effectively.

[0264] From a robustness and stability standpoint, there are two main ideas to consider. Traditionally, the idea is to be sure that the control actions and state updates are not so aggressive that they respond to noise or outdated measurements in a way that causes the process to become unstable. This analysis is very dependent on the particular control law that is chosen and how well the model represents the true process. Because the manufacturing application requires a very aggressive control law, this discussion will focus on the stability of the state estimation itself and how well it tracks the true states.

[0265] In a traditional time-invariant observable process where the same measurements are made at each time step, the error covariance matrix used in a Kalman estimation scheme eventually reaches a steady state. At this steady state, the increases in uncertainty due to the noise inherent in the process exactly balance the reductions in uncertainty due to the measurements. As long as the model of the uncertainty in the process is fairly accurate, the diagonal terms of the covariance matrix provide steady state values for the uncertainties in each state estimate. This means that with the exception of unanticipated process disturbances the uncertainties in the controlled process outputs are known as well. Proper process characterization is important here because these results are only meaningful if the inherent process noise is well understood.

[0266] When the Kalman state estimator is used on a process where the output matrix varies, the error covariance matrix cannot reach a steady state. Each time the output matrix changes, relative uncertainties between different state estimates change. Even though a steady state cannot be achieved, it is still important to be able to bound the uncertainty in the parameter estimates. This allows the uncertainty in the controlled process outputs to remain bounded as well. Clearly, enough measurements must be taken to ensure that the parameter estimate uncertainty remains at an acceptable level. The next portion of the description details how this uncertainty changes with different types of processing conditions and measurements.

[0267] The system parameter estimation portion of an adaptive control method consists of a closed-loop system identification scheme. Closed-loop system identification can be difficult because the controller 130 can significantly change the apparent input-output behavior of the process. If the controller 130 is working well, the process is running near the target with very little variability. In this case, the dynamics of the system are difficult to observe.

[0268] A common approach used in closed-loop system identification is the use of a persistent excitation constraint. The general idea is to be sure that the process conditions are varied sufficiently to excite all the modes in the chosen model form. When the controller 130 is running a process at the target without any disturbances, there is very little movement in the process states, and the dynamics of the system are difficult (or sometimes impossible) to observe.

[0269] Persistent excitation injects small perturbations into the manipulated variables so that the dynamics become visible at the cost of small fluctuations around the process targets. It may also be possible to look at process inputs in the same way as a designed experiment. When designing an experiment to estimate model parameters, input points are chosen that attempt to examine all possible modes of the model form. If the process were to ever run with inputs that resemble the ones in the experiment, then it should be possible to prove that this results in the best possible estimates of the model parameters.

[0270] It is not straightforward to apply standard persistent excitation techniques to many of the process systems and models that are prevalent in a batch processing environment. In many cases, the state variable to be estimated is not directly affected by the commonly chosen input variables. A common example is a timed process, where the state to be estimated is a rate and the processing time is manipulated. Due to reactor fouling or consumable degradation, the chosen processing time can indeed have an effect on the processing rate for future runs. However, the time would have to be adjusted well outside the standard operating range for the rate differences to become noticeable.

[0271] There are processes where standard persistent excitation techniques can be used, but for many processes, a somewhat different approach must be used. Because of the high importance placed on every batch reaching its targets, a technique is explored for choosing times to excite the process while letting it run undisturbed at the target most of the time.

[0272] It is important to realize that not all data obtained in a manufacturing environment are the same. Some data are more informative because the quality of data is dependent on what is measured and the conditions under which the measurements are taken. The information content of data is dependent on what the observer is trying to learn from the data. For example, repeated measurements of temperature at a given pressure show clearly what the temperature is, but they do not provide any insight into what the temperature would be at a different pressure.

[0273] Based on a chosen model form, different input signals can highlight different modes and frequency ranges. As will be illustrated in the next section, it is necessary to have the right information at the right time to control a process well. Only an understanding of the process under consideration leads to the knowledge of exactly what information is required.

[0274] Standard tests for observability conditions can be used to compare different strategies for locating sensors from the standpoint of the information they can provide. Even when a system is observable, there are varying degrees of ease with which parameters can be estimated. The condition number of the observability matrix can provide insight into these effects. Techniques for testing observability are used herein to compare the estimation ability under different operating conditions.

[0275] A simple example illustrates the importance of good information when closed-loop identification is practiced in conjunction with process control. Consider a simple process where the output stays constant unless an input is applied. The objective is to respond quickly to target changes, but the gain on the input fluctuates in an unpredictable way.

[0276] The equation,

[0277] y_k+1=𝑓(y_k,b_k,u_k)=y_k+b_ku_k, (88)

[0278] where b_kis the unknown gain (effective at time k) and u_kis the applied input, describes the process.

[0279] Since b is an unknown parameter, it must be added as an extra state for the purposes of estimation. A standard Kalman estimation scheme can be used by linearizing the system around the current operating point. This is accomplished as described by the following equations:

\begin{matrix} {[\begin{matrix} x \\ b \end{matrix}]}_{k + 1} \approx {[\begin{matrix} \frac{δ f}{δ x} & \frac{δ f}{δ b} \\ 0 & 1 \end{matrix}] [\begin{matrix} x \\ b \end{matrix}]}_{k} + {[\begin{matrix} \frac{δ f}{δ u} \\ 0 \end{matrix}] [u]}_{k} & (89) \\ {[y]}_{k} = {[\begin{matrix} 1 & 0 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} . & (90) \end{matrix}

[0280] Note that

\frac{δ f}{δ x_{k}} = 1, \frac{δ f}{δ b_{k}} = u_{k}, and \frac{δ f}{δ u_{k}} = b_{k} .

[0281] For this system, the observability test matrix is given by

\begin{matrix} O = [\begin{matrix} 1 & 1 \\ 0 & u_{k} \end{matrix}] . & (91) \end{matrix}

[0282] Thus, the system is only observable when u_kis not zero. This is important because the steady state operating point has u at zero. The unknown parameter b can only be identified when u is kept away from zero, which is what would be accomplished by a persistent excitation constraint on the controller. This simple example illustrates how a persistent excitation condition can be related to an observability condition.

[0283] In general, allowing a state estimator to run at the unobservable point will lead to unpredictable results. However, it is necessary to do feedback control in case there is a disturbance. A Kalman estimation scheme will keep the estimates moving slowly because the estimates are moved only as much as is needed to explain the measurements.

[0284] In the following simulations, the process described above was run with different excitation conditions. The first one has no excitation. The second run has a persistent excitation constraint imposed, and the third run has excitation enforced only for a small portion of the time. In all cases, a plant inversion was used by the control law component 132, and a Kalman state estimator was used for the observer component 134. During the course of the simulation, the true value of the gain b is ramping as shown in FIG. 18. Because the plant inversion is used as the control law, errors in state estimation are immediately visible as errors in the controlled output.

[0285] In the first simulation, shown in FIG. 19, the input is not applied until the target changes. Because the gain has changed, there is a significant deviation from the target for the first time step where the new target is in effect. During most of the simulation, the controller 130 is starved for information as there is no way to observe the unknown gain.

[0286] In the second simulation, shown in FIG. 20, a persistent excitation constraint is applied. Here, the input varies enough at each time step so that the gain can be estimated. When the target changes, the controller 130 makes the switch with less error than in the previous case. However, perturbations have been introduced throughout the entire simulation to make the gain apparent.

[0287] The rank of the observability test matrix is commonly used to test for observability. When this matrix has full rank, its condition number is bounded. In the first simulation, the condition number of the observability test matrix went to infinity because the matrix became rank deficient. By contrast, under persistent excitation, the condition number stays well within reasonable limits. FIG. 21 tracks the condition number of the observability test matrix for the second simulation. Another useful piece of information is the trace (sum of diagonal elements) of the error covariance matrix used in the state estimation routine. The trace provides an overall measure of the uncertainty evident in the covariance matrix. FIGS. 22 and 23 show this value for the first and second simulations, respectively.

[0288] In the third simulation, shown in FIG. 24, it is assumed that it is known ahead of time when the target change will occur. In this case, it is not necessary to perturb the process until the information about the gain is needed. Here everything runs smoothly until the target change is imminent. The target change still happens correctly, and the process it not disturbed until the information is needed.

[0289] The case where the process is excited to learn about the parameters is contradictory to what a controller using a pure mean squared error objective would try to obtain. In semiconductor manufacture, a different sort of performance function lends itself to the problem. In general, the devices being manufactured have tolerances for most of the inline targets. As long as the measured value is reasonably close to the target value, the device will function properly. Within the tolerance region, there is very little noticeable difference in the final output characteristics of the device. However, there is a very steep drop-off past which the device simply will not work. An example of this is in the alignment of process layers to make electrical contact. It is possible to have a performance function that mimics this behavior by treating all data points within the tolerance region as good and all points outside as bad. This kind of performance metric is very well matched to an observation scheme involving persistent excitation because the excitation can induce learning while staying safely inside the tolerance region.

[0290] The number of data points is not the only thing that matters in determining the efficacy of the controller 130. Each of the preceding simulations had the same number of measurements of the same output variable. The order of the data and the actual values affect the information content. The conditions under which the data are obtained are also important.

[0291] It is not necessary to have perfect information all the time. In the second simulation, the correct value of the process gain was known at all times. However, the third simulation was able to control the process just as well with the gain known only at certain times.

[0292] In a real process, it is often possible to know about upcoming target changes before then occur. However, the process is also subject to unknown disturbances. In both of these cases, it is important to have enough information to drive the process quickly to the target value. So, clearly there is a balance between learning everything there is to know about the process and letting it run without perturbations.

[0293] In the examples above, both the trace of the error covariance matrix and the condition number of the observability test matrix were shown to be indicators of the amount of process information available. These values can be used to create excitation constraints that the controller 130 can use to keep the process observable.

[0294] Turning now to FIG. 31, a simplified flow diagram of a method for Scheduling activities in a manufacturing system is provided. In block 3100, a plurality of observed states associated with the manufacturing system is defined. In block 3110, state estimates are generated for the observed states. In block 3120, uncertainty values for the state estimates are generated. In block 3130, a plurality of candidate schedules for performing activities in the manufacturing system is identified. In block 3140, changes to the uncertainty values are predicted based an the candidate schedules. In block 3150, one of the candidate schedules is selected based on the predicted changes to the uncertainty values.

[0295] The discussion now focuses on using the information identified above to make scheduling decisions for the manufacturing system 10. In discrete parts manufacture, it is imperative that each batch be on target, and intentional perturbations of the process are discouraged. In addition, it is common to assume a process model where the process inputs for one run do not affect any subsequent runs. Therefore, it is beneficial to look at the identification problem in another way. In this technique, nontraditional manipulated variables are shown to affect the process in a similar way to standard persistent excitation.

[0296] The previous section illustrated that having the right information at the right time is important. Each of the cases had the same number of data points, but the results were very different. Clearly it is useful to be able to define what is meant by the night data to extrapolate these findings to more useful situations.

[0297] This section attempts to find some ways to quantify the idea of having the right information at the right time. For instance, it is intuitive that all appropriate information should be available before attempting to run an important product through a process. However, to apply the theory consistently and objectively, it is helpful to know what information is important as well as how it is to be used as described in greater detail below, a mathematical objective function is created that concisely expresses the expected value of the output in terms of the decisions to be made. By comparing the value of an appropriately crafted objective function for different choices of actions, it is possible to reach a solution that satisfies the needs described above.

[0298] The covariance matrix that is available when using a Kalman estimation scheme can provide valuable insight. The diagonal elements of this matrix measure the current amount of uncertainty in their corresponding state estimates. The evolution of the covariance is completely determined by the processing order and chosen measurements. When the system advances to the next time step, the uncertainties in the states cause the error covariance matrix to be updated per the equation

[0299] P_new=APA^T+GQG^T. (92)

[0300] When a measurement is taken (using a particular C_rand R_r, the error covariance is updated according to

[0301] P_new=(P_old⁻¹+C^TR⁻¹C)⁻¹. (93)

[0302] These equations do not depend on the actual numerical values that are measured or on the current state of the process. They simply define the effects of measuring different quantities given some assumptions about the structure of the underlying system.

[0303] Tracking the terms of the covariance matrix is a complicated exercise. This is because everything that is known about the relationships between different variables is taken into account. Taking a measurement of one variable affects how future measurements of other related variables will be treated.

[0304] A very simple example system illustrates these ideas. Consider a nominally stationary process with two states and two measurements as described by the equations below.

\begin{matrix} {[\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k + 1} = {[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (94) \\ {[\begin{matrix} y_{1} \\ y_{2} \end{matrix}]}_{k} = {[\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (95) \end{matrix}

[0305] This system can be thought of as describing a simple process where x₁is a measurable tool state while x₂is a product parameter that has no available direct measurement. In any case, it is important to be able to identify both parameters as well as possible, and a direct measurement is only available for one of them.

[0306] In each of the following series of simulations, an equal number of y₁and y₂measurements are taken. In each new simulation, the measurement order is varied to determine its effect on the error covariance. A Kalman filter-based scheme as described earlier is used as the state estimator with all noise and variance estimates starting at unity. The variance terms for both states are plotted for each of the cases. The effective measurement mapping matrices for the two measurements are described by the following equations.

\begin{matrix} {[y_{1}]}_{k} = C_{r} x_{k} = {[\begin{matrix} 1 & 0 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (96) \\ {[y_{2}]}_{k} = C_{r} x_{k} = {[\begin{matrix} 1 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} . & (97) \end{matrix}

[0307] In the first simulation, shown in FIG. 25 all of the y₂measurements are performed first. Because the measurement is affected by both states and there is no information about the relative values of the states, the uncertainty of both states increases steadily through the first half of the simulation. In the second half, the y₁measurements are being taken. Since this is a direct measurement of x₁, the uncertainty associated with that state quickly drops.

[0308] However, since there is no information about x₂, its uncertainty grows rapidly. It is important to note that the point on the chart with the lowest total uncertainty is the run immediately after the halfway point. Here, the first bit of information about the true value of x₁is provided, and the covariance already contains the information about how x₁and x₂are related.

[0309] In the second simulation, shown in FIG. 26, all of the y₁measurements are done first. The results are similar to the previous case. While y₁is being measured, the uncertainty in the estimate of x₁stays low while that of x₂climbs rapidly. While y₂is being measured, the uncertainty in both estimates rises. Again, the point with the lowest total uncertainty is at the switchover. Whenever only one measurement is being taken, the total uncertainty continues to grow until a complementary measurement is taken.

[0310] The third simulation, illustrated in FIG. 27, utilizes some of the findings of the first two simulations. Here, the measurements alternate between y₁and y₂. The constant sharing of information allows the uncertainty in both parameter estimates to remain low. Because the state transition matrix for the process is the identity matrix, the observability test matrix for this simple system is given by

\begin{matrix} O = [C^{T}] [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}] . & (98) \end{matrix}

[0311] For this system, a rank of 2 is required, and this matrix satisfies that constraint. However, if either measurement were not available, the system would not be observable. This is why the uncertainty grows when only one of the measurements is used for long periods of time. Table 6 summarizes the results in terms of the average values of the variances.

TABLE 6

Processing Order Dependence Results

[0312] In a typical manufacturing facility, there would be more products and many fewer qualification runs. However, the concept that the processing and measuring order affects the quality of the parameter estimation does not change. What the tests show is that long stretches of a particular kind of run reduce the overall effectiveness of an estimator trying to identify all of the process parameters. When there are multiple sources of variation, performing only a single type of run does not allow an estimation scheme to distinguish between the different error sources. This series of tests provides a theoretical basis for the idea that frequent product and tool switching may be better from a parameter estimation perspective.

[0313] The previous simulations suggest that it is possible to quantify the amount of information in a set of data. It is clear that the quality of the information obtained is completely separate from the quantity of data. The value of information depends heavily on the properties of the system under consideration. In a completely static system without disturbances, new information is not as crucial. Once the system properties are determined, any new data just serves as a confirmation. However, in a dynamic system with potential disturbances, fresh information is always needed. When more about the system is known, disturbances can be identified more readily.

[0314] The error covariance matrix is a useful and convenient indicator of the need for more information. Proper initial process characterization leads to accurate estimates of the amount of noise in the system, and the evolution of the covariance matrix captures those estimates. The evolution of the covariance matrix does not depend on the values of the measured data. Along with the system noise characterization built into the model, only the order and choice of the measurements affect the covariance matrix.

[0315] Every processing or measurement event affects the state estimate {circumflex over (x)} and the covariance matrix P_xin a known way. The trace (sum of diagonal elements) of P_xprovides a measure of the total amount of uncertainty in the state estimates. Previous mean-square estimation routines attempt to minimize the trace of the error covariance matrix by changing the state estimates. It is now possible to look at processing decisions in terms of how they affect the trace of P_x.

[0316] The following section examines some common processing decisions from the perspective of how they relate to the information quality. Rather than focusing on typical run-to-run process settings, such as recipe setpoints, this section looks at overall trends instead. The impact of processing order and tool selection are investigated for their effects on the information available about the system.

[0317] Simply put, the final objective of a semiconductor manufacturing facility is that working products are obtained as quickly as possible at minimum cost. It is possible to identify several (possibly conflicting) objectives that can be expressed mathematically. Some common objectives are summarized below:

[0318] Maximize throughput (minimize time).

[0319] Minimize use of raw materials.

[0320] Minimize mean-squared deviation from inline targets.

[0321] Minimize the number of gross outliers from inline targets.

[0322] Intuitively, it is obvious that a trade-off must be made amongst these objectives. At one extreme, special experiments could be run before each batch of product material is processed at each unit operation so that all the important parameters are known. Conversely, the material gets out the door fastest if no experiments are ever run and no measurements are taken on the product. In reality, the balance shifts as business needs change. An ideal control system would be able to understand and respond to these changing requirements at a very high level.

[0323] A number of processing decisions have an effect on the information available to a state estimation algorithm. A few key decisions are described here along with specifics on how they could be optimized to aid in the state estimation. One apparent decision is which batches to measure. In many run-to-run control applications, it is not practical to measure all the parameters important to control on every batch. Taking measurements uses possible manufacturing time, and in some cases, additional materials (such as pilot wafers) are required as well. For these reasons, a run-to-run controller in an industrial setting may have a reduced set of process measurements with which to work. Clearly it is beneficial to choose the set of measurements that provide the most information about the process, and an overall cost minimization would be appropriate.

[0324] Typically, rule-based methods are used to select sampling plans. In these methods, a series of criteria are checked to determine if a given batch will be measured. For example, it might be specified to measure the first batch that runs on each tool after each maintenance event, all batches of a particular product, and every third batch not covered by the earlier rules.

[0325] While these plans are easy to implement, it is difficult to understand how they really affect the process. The methods described herein are based on objective functions. An objective function is defined that can be used to compare one plan to another and make a judgment about which is better.

[0326] Another important decision is the processing order itself. In a processing environment with uncertainties and subject to disturbances, changing the order of processing (and measuring) changes the information available when each batch is processed. The allocation of material to run on different processing tools has a large effect on the information available. This effect is described in more detail below.

[0327] Each of these scheduling decisions can be analyzed in terms of its effect on the state error covariance matrix. However, it is useful to note that there are other effects as well. Changing the processing order or the tool allocation impacts throughput, so it is helpful to take downstream consequences into account. The strategy employed here is to first analyze each of these process decisions individually. Then, a more general formulation is presented that addresses the combinations that appear in practical use.

[0328] For a given processing plan (tool allocation and processing order), there is a constraint on the total number of measurements. The particular measurements to take can be chosen freely as long as they satisfy the constraint. In a processing area, all of the material either being processed or waiting to be processed defines a queue of possible measurements. This queue defines the prediction horizon for a selection algorithm and is assumed to be of length n.

[0329] A vector u of binary variables is defined, with each element u_icorresponding to one batch in the queue. In this vector, a 1 means the batch will be measured, while a 0 means it will not be measured. For a given choice of the vector u, the process model can be used to evolve the covariance matrix over the entire prediction horizon taking into account all the processing and the chosen measurements.

[0330] Let J(P) define a performance index in terms of a particular covariance matrix P. An exemplary index would be the trace of P. The sum of the diagonal elements in the error covariance matrix is a good measure of the amount of uncertainty in the particular estimates. Alternatively, the values corresponding to particular parameters could be weighted more or less heavily based on arbitrary concerns.

[0331] Let 𝑓n(u) refer to the sum over all time steps in the prediction horizon of the value of the performance index calculated based on the input vector u. The value of this objective function depends on the structure of the underlying system model and the chosen values of the noise parameters. Also, depending on the current values in the covariance matrix at the time the optimization is solved, different results may be obtained. This is intuitive because at different times, different measurements are in greater need.

[0332] Now, an optimization problem can be defined to identify the proper measurements. At a particular instance, if c denotes the number of batches in the queue that are allowed to be measured, then the following equations define the problem mathematically:

\begin{matrix} \min_{u} f_{n} (u) & (99) \\ \sum_{i = 1}^{n} u_{i} \leq c & (100) \end{matrix}

u_i∈{0,1}. (101)

[0333] The vector u that solves the optimization problem minimizes the uncertainty in the parameter estimates while satisfying the constraint on the maximum number of measurements.

[0334] For a given processing and sampling plan, there is some flexibility in the order in which material is processed. There is a queue of material waiting to be processed in the area, and batches may be selected from the queue in any order, as long as certain constraints are met. As shown previously, the error covariance matrix is path dependent. Changing the order of runs can have an effect on the information available when each run is to be processed. So again, the error covariance matrix can be used to drive an optimization problem. It is predetermined which batches will be measured and that will only run without being measured.

[0335] The queue of batches is again assumed to be of length n. A vector u of integer variables is defined, with each element u_icorresponding to one batch in the queue. In this vector, the value u_iof each element i denotes the time step when the batch will run. For this reason, the vector u must be constrained to contain all the integers between 1 and n.

[0336] Again a performance index J(P) can be defined in terms of a particular covariance matrix P, and for the purposes of choosing the processing order, the trace of P would be a reasonable choice, although the weighting could be adjusted to make some parameters more important than others.

[0337] Let 𝑓n(u) refer to the sum over all time steps in the prediction horizon of the value of the performance index calculated based on the input vector u. As above, the value of the objective function depends on the system model and the initial values in the P matrix. As in the case above, an optimization problem can be defined to determine the proper choice of the input vector u.

\begin{matrix} \min_{u} f_{n} (u) & (102) \end{matrix}

u_i∈{0,1,2, . . . , n} (103)

[0338] u_i≠u_j(i≠j). (104)

[0339] For a given set of material to process, appropriate tools must be selected for processing. Naturally, constraints exist because of capacity and throughput concerns. However, within the boundaries of the constraints, it is possible to select certain material for certain tools to gain more knowledge about the system. There are a number of heuristics that can be expressed given the framework of tracking parameter uncertainty in terms of different products and tools. Given the fact that some parameters will have higher confidence than others, it makes sense from a business perspective to run more important or critical products on tools with more reliable or current state information.

[0340] From an identification viewpoint, it is possible to learn about an unknown tool by running a well characterized product on the tool. Conversely, running a new product on a tool that is understood with a high degree of confidence can help to learn about the new product quickly. This section will attempt to define these rules more objectively.

[0341] This problem cannot be examined without considering the implications on total plant throughput. Tool scheduling decisions are traditionally made with the objective of minimizing time. In this test study, throughput concerns will be handled with a simple constraint, but in general this is just another part of a larger optimization problem. In fact, other researchers have investigated the use of the model predictive control formulation to optimize throughput and inventory.

[0342] As in the previous cases, there is a queue of n batches waiting to run in a process area. For each batch the product is known, and it is predetermined whether or not the batch will be measured. If the processing tools are numbered from 1 to k, then a vector u of integer variables can be defined, with each element u_icorresponding to one batch in the queue. In this vector, the value u_iof each element i denotes the tool where the batch will run.

[0343] Again a performance index J(P) can be defined in terms of a particular covariance matrix P. For the case of determining which process tools to run, the trace of P can again be used, and as before the weighting could be adjusted to make some parameters more important than others.

[0344] Let 𝑓n(u) refer to the sum over all time steps in the prediction horizon of the value of the performance index calculated based on the input vector u. Again, the value of the objective function depends on the system model and the initial values in the P matrix. As in the case above, an optimization problem can be defined to determine the proper choice of the input vector u.

\begin{matrix} \min_{u} f_{n} (u) & (105) \end{matrix}

u_i∈{0,1,2, . . . , k} (106)

[0345] In this section, it was shown that there is more to state estimation than the amount of data obtained. Methods were described that attempt to quantify the amount of information in a set of data. These methods can be used to make processing decisions that will lead to more information being available for state estimation. The following discussion unifies these last few scenarios into a coherent strategy for acquiring data. This strategy complements the uncertainty-based state estimation by providing a steady and reliable stream of new information.

[0346] The previous sample scenarios involved process decisions and their effects on state and parameter estimation. While each of the situations is worth studying in its own right, in a real production facility they must all be considered simultaneously. The following discussion addresses the need for a comprehensive plan for information collection and parameter estimation.

[0347] As a preliminary step, it is first demonstrated that processing decisions, such as scheduling and sampling, can be made using the needs of the state estimation algorithm as a guide. For this reason, a number of simulation runs are shown using the optimization problems described above. In each of these test scenarios, the plant and state estimation algorithm are initialized in the same way. A different processing decision is investigated in each one.

[0348] To limit the number of possible solutions and allow the cases to be easily understood, a system with three process tools and three products is specified by the simulation driver 136. As in earlier situations, the assumption is made that the only important sources of variation are the differences between the products and tools. Random noise and a slight drift are added to the states during the simulations. In each scenario, the controller 130 begins with no knowledge of the system states and runs for 200 time steps to completely settle. The next 20 runs are the subject of the test. All the tests use the same set of runs as the base case. Table 7 shows the base configuration used in all the scenarios.

TABLE 7

Process Decision Base Case Run Summary

[0349] The first set of tests deals with choosing an optimal sampling plan. The objective of the test is to choose the runs to measure so that the uncertainty in all the parameter estimates is minimized. This is accomplished by using the objective function defined in Equation 102 and its associated constraints. Evaluation of the objective function is a nonlinear, iterative process. Once an input vector u is chosen, the process model can be used to evolve the covariance matrix forward through time.

[0350] For this problem, the constraints (Equations 103 and 104) completely define the feasible solution space. Essentially, c measurements must be chosen out of the possible n. Since the processing order is fixed, the order in which the measurements are selected does not matter as long as they are all selected before processing begins. This means that the number of feasible candidate schedules that may be defined is given by

\begin{matrix} \frac{n!}{(n - c)! c!} . & (107) \end{matrix}

[0351] For a total of 20 runs this optimization problem can be solved by an exhaustive search of the feasible domain. Table 8 below summarizes the results of the tests for several different values of c.

TABLE 8

Summary of Sampling Optimization Tests

[0352] Several results are immediately apparent from these runs. First of all, run 5, the tool qualification run, is present in each solution. This particular run is the most helpful in locking down the true values of the parameters. Next, the algorithm favors measuring runs near the beginning of the test. This is intuitive because the uncertainty increases on every run. By measuring more runs near the beginning, the estimator can keep the average uncertainty down. The runs with fewer measurements illustrate that the algorithm attempts to learn about the entire system. By sampling several runs that cover the entire spectrum of tools and products, the estimation algorithm can have a complete picture of the system.

[0353] It is interesting to note that the value of the objective function levels off above about 10 measurements. This is more clearly illustrated in FIG. 28. This suggests that a practical use of this algorithm would be identifying measurements that do not provide enough new information to justify their costs in time and resources.

[0354] The second set of tests deals with choosing the order of processing. Here, the runs to be measured are predetermined, but the processing order can be arbitrarily arranged within the given queue of batches. Again, the objective is to minimize the uncertainty in the parameter estimates. The constraints in Equations 103 and 104 define a set of feasible solutions. The order is determined by selecting one batch at a time from the queue until all runs have been completed. Because this problem has n! possible solutions (i.e., candidate schedules), an exhaustive search of the solution space is not practical.

[0355] For these test runs, a sub-optimal approach is used to limit the number of candidate schedules and get approximate solutions that are sufficient to illustrate the key points. Rather than trying to cover the entire solution space, a series of n simpler problems can be solved. For each run, the one batch that provides the most immediate improvement in the objective is selected. This process is repeated until all the batches are run.

[0356] To run the test, it is necessary to predetermine the sampling plan. To test with varying amounts of information, tests are run measuring every batch, every other batch, every third batch, every fourth batch, and every fifth batch. Knowing when the measurements will be taken, the controller 130 must decide the processing order that maximizes the available information.

[0357] Table 9 below presents the results of the processing order study. In each of the tests, the value of the objective obtained using the new order is compared to the value obtained using the default order p resented in Table 7. In each of the tests, solving for a better processing order significantly improves the value of the objective function.

TABLE 9

Summary of Order Optimization Tests

[0358] The final set of tests deals with the tool allocation problem. Here, the processing order and sampling plan for a set of batches is predetermined. The objective is to minimize the uncertainty in the parameter estimates by choosing the most appropriate processing tool for each batch in the queue. The constraints in Equations 105 and 106 define a set of feasible solutions.

[0359] With a queue of n batches and a total of k tools, there are kⁿpossible solutions. As the number of potential solutions increases exponentially with the problem size, an exhaustive search of the solution space is not generally practical. As above, a sub-optimal approach is used to achieve approximate solutions by limiting the number of candidate schedules.

[0360] For each run, the tool is chosen that would result in the largest improvement in the objective function. Thus, a series of n simpler problems are solved to determine where to run all the batches. Table 10 below shows the processing order determined by the algorithm.

TABLE 10

Tool Allocation Run Summary

[0361] This allocation of batches on tools results in about a 10 percent improvement in the value of the objective function. However, there are some more striking results. FIG. 29 compares the simulated output error of the control algorithm when using the default tool allocation plan and the optimized plan. Large amounts of variability are removed in the optimized version, because the products with high parameter estimate uncertainty are run on tools with relatively small estimate uncertainty.

[0362] An important feature of this simulation is that there is no constraint that dictates even usage of the tools. The results show that the algorithm divided the runs up evenly among all the tools involved. The reason for this is that the uncertainty in the parameter estimate for a given tool increases over time, even if the tool is not selected for usage. Thus the algorithm has to utilize all the tools so that enough information is available to keep the uncertainty low across all the tools.

[0363] As shown in the previous section, manufacturing process decisions such as tool scheduling and sampling plans have a very real effect on the ability to effectively perform process control. Furthermore, it is shown that proper manipulation of these decision variables can improve the controlled output. While the decision variables do not directly affect the process variables that the controller 130 manipulates, they do affect the quantity and quality of the information available to the controller 130 for use in updating its state and parameter estimates. For a model-based controller, different values of the model parameters lead to different values of the objective function, and therefore different process inputs are chosen.

[0364] Using the error covariance matrix available in a Kalman state estimation scheme, the manufacturing decisions are shown to have an explicit relationship to the relative uncertainties in different parameter estimates in the controller 130. A model can be created that relates process decisions to their effects on the uncertainties in the parameter estimates. Depending on the current confidences in the parameter estimates, taking a particular measurement or running a particular processing tool can have very different effects.

[0365] At this point, it is convenient to separate the process model from the supervisory scheduling model, as shown in FIG. 30. A process controller 300 implements a low-level, process model 310 that describes how the process variables are affected when the inputs are manipulated. Process variables include recipe settings, measured batch properties, and sources of variation. In this model, batches are unknown until they appear, at which point their properties determine how they will be affected by the processing equipment. A scheduling controller 320 implements a supervisory, scheduling model 330 and is not concerned with the details of how batches are processed. Instead, it deals only with the movement of material through the plant.

[0366] The environment is made up of a series of discrete events. These events include batches being processed, tools being qualified, and batches being measured. For each one of these events, the process model 310 can be used to determine the anticipated effects on the real process states as well as the uncertainties in the parameter estimates. The higher-level, scheduling model 330 can be used to determine the effects of the event on inventory levels, cycle time, and tool utilization.

[0367] A multi-level control strategy is used here. The state estimation techniques described above and implemented by the process controller 300 are well-suited to solving the problem of determining the best parameter estimates given all the available process information. This state estimation has no input as to the order that material will be processed or what measurements it will receive, but it can effectively deal with the information as it arrives.

[0368] At the next level, the scheduling controller 320 handles the scheduling by analyzing candidate schedules to meet several objectives. In addition to ensuring that processing tools are effectively utilized and material gets through the plant in a reasonable amount of time, the scheduling controller 320 has to make sure that the lower-level process controller 300 and its state estimation algorithm receive appropriate information.

[0369] This cascade scheme allows for a modular design with each controller 300, 320 handling the tasks for which it is best suited. An even higher level factory optimization controller 340 may be provided for defining the objectives for the scheduling controller 320.

[0370] The inputs to the scheduling model 330 are the process decisions. At a given time step, there are a number of decisions to be made. For simplicity, assume that all the runs take the same amount of time and that they all start and end simultaneously. This allows for a simplification in the decision variables. If there is a queue of n_bbatches waiting to run in a process area, then at a given time step it must be decided which batches will run on all the tools in the process area during the time step. If there are n, tools in the process area, then the n_telements of the vector u define the batches that will be run on the tools. For generality, the batches in the queue do not all have to be production batches. Tool qualifications and other such events can also fit into the same framework. A second input vector v, also of length n_t, is needed to specify whether each of the runs described in u will be measured.

[0371] For the chosen decision vectors (i.e., candidate schedules) for a time step, the effect on the error covariance matrix for the process state estimator can be computed. As in the previous examples, an objective function can be defined in terms of operations on this matrix.

[0372] A model predictive control (MPC) formulation can provide an excellent vehicle for solving the optimization problems described above in a practical situation. While a simulation can be run with a predetermined queue of material in a known environment, a real manufacturing facility is more complicated. Processing conditions are always subject to change, and the decisions made by the controller can be overridden according to business needs. Using an MPC formulation, only the first decision is implemented each time the optimization problem is solved. After new information becomes available, the problem is solved again. This scheme is well suited to handle the quickly changing conditions in the plant.

[0373] MPC can look several time steps ahead to examine how current changes will affect future runs. To use an MPC formulation, the system states and a model for how they change are defined. The states are simply the parameter estimate uncertainties as determined using the state error covariance matrix used by the process controller 300. The model for how they change is determined from the equations that determine how the covariance matrix changes as batches are processed and measured.

[0374] The “measurements” that the scheduling controller 320 receives are the new values in the covariance matrix as provided by the process controller 300 after the actual processing decisions are implemented. The actual processing decisions may or may not match the decisions that the scheduling controller 320 desired because of outside influences.

[0375] Another major benefit of the MPC approach is the ability to include constraints on the decisions. By using the prediction horizon, complicated constraints such as the percentage of material measured over a long time period may be used. Constraints on tool allocation, sampling, and the time that batches wait to be processed can all be inserted into this very generic framework.

[0376] There are many benefits to this unified process and factory control strategy. Traditionally, the scheduling has been done as business needs dictate, with little or no analysis given to the impact on process control. The process control is something that has to be done within the limits of the factory constraints. Integrating the needs of scheduling with the needs of process control has several distinct advantages for both as outlined here.

[0377] In general, measurements are taken to ensure that batches are being processed correctly. By allowing the process controller to have input into the sampling plan, the understanding of the uncertainties in the processes can be used to select measurements that are relevant. Since the uncertainties in parameter estimates translate directly into uncertainties in the process outputs, it is possible to reduce measurements down to what is needed to ensure that all process outputs are within appropriate tolerances. Not only does this save time, but it also limits the number of measurement tools that must be present. Of course, the scheduling controller 320 can also suggest carefully selected measurements when output uncertainty becomes too high. It has the proper data to make an informed decision about which potential measurements will provide the most benefit.

[0378] Another exemplary application of the scheduling optimization is the processing of “important” lots. A particular lot may have been flagged as a high priority lot for various reasons (e.g., predicted performance characteristics, test lot, etc.). For such a lot it may be desirable to optimize the processing associated with the designated lot. The uncertainty analysis may be applied to different candidate schedules including the targeted lot, and the candidate schedule having the lowest uncertainty when processing the target lot may be selected.

[0379] The scheduling controller 320 can also choose times for special events such as tool qualifications. These events are normally used for equipment maintenance, but they can also be used to enhance the quality of data The scheduling controller 320 has the information available to know when the estimated parameters for a tool state have significant uncertainty. This is a good time to perform maintenance on the tool as the post-maintenance qualification will provide fresh information about the state of the tool parameters. This kind of action can reduce downtime and improve controlled output by scheduling events when they are really needed.

[0380] The scheduling and sampling optimization problems investigated earlier fall into a class of difficult mathematical problems. First of all, the evaluation of the objective function is a very nonlinear process. Even when the low-level process model is linear, the update to the error covariance matrix upon receipt of measurement data requires matrix inversion techniques. The problems are further complicated by the fact that the decision variables are discrete-valued rather than continuous. A common method for finding the extrema of a continuous nonlinear function is to take derivatives with respect to the independent variables. In general, these extrema do not correspond with the discrete values of the decision variables allowed by the system constraints, so more complicated search methods must be used.

[0381] As illustrated in the simulation runs earlier in this section, the number of objective function evaluations required by the most straightforward search schemes quickly becomes astronomical as the system size increases. Some relief can be found by breaking the problem into smaller pieces and joining the solutions together as was done in the later simulations. In addition, it is possible to work from a feasible solution, applying small changes that result in other feasible solutions to see if the objective value improves. The drawback of these methods is that there is no guarantee of reaching the global optimum. A balance must be achieved between the need for the most accurate answers and having the answers in a reasonable amount of time. There are a large number of factors that must be taken into account when determining the scheduling of runs in a large factory.

[0382] In one embodiment, a single objective function and associated constraints may be defined to encompass all the concerns. That objective would meet the needs of many different parties with different areas of expertise. For example, while a control engineer may be able to describe the importance of a particular batch in terms of how much process information it would yield, an operations research expert would be more concerned with how long the batch waits to run and how to move it through the line more efficiently. In addition, an engineer trying to improve a process may need to run certain batches on certain tools with special settings. Creating a single objective that meets all these needs requires the specification of the relative importance of each concern.

[0383] An alternative approach is to have separate systems tailored to the needs of each party. Each of these systems can easily determine the process decisions it would most like to see. A supervisory system would then be responsible for resolving conflicts. As mentioned in the previous section, rule-based systems are commonly used to schedule production runs. These systems are generally designed to minimize delays and costs with little regard to the needs of run-to-run control applications. Integration with this kind of system would be necessary to influence scheduling in an existing facility.

[0384] The techniques described herein present a powerful approach to understanding the handling of the many different processes that are simultaneously active in a large-scale semiconductor manufacturing plant. The study of the combined system model reinforces the fact that there is a great deal of data that can be shared between different processes. As the differences between equipment, products, and processes are often much larger than the run-to-run fluctuations of a single process, the combined model succeeds in capturing the differences between the different areas of the process by utilizing data from several runs at a time. The key benefit of this method is that information is shared between different processing contexts so that the system model is updated very quickly when errors are detected.

[0385] Another major result is that in a state and parameter estimation algorithm, understanding the amount of uncertainty in the estimates is just as important as obtaining the values of the estimates themselves. A recursive state estimation routine based on estimating confidence levels was proposed to perform updates even when only a portion of the desired measurement data is available. Practical manufacturing issues such as delayed and missing measurements were described and addressed. The result is a robust scheme that is applicable to many different processes in the manufacturing facility.

[0386] A distinction was made between the available data and the useful information it contains. The performance of a state estimation scheme is heavily dependent on the quality of the information it receives. The state estimate error covariance matrix was identified as an indicator of the uncertainty in the estimates, and the effects of measurements on that matrix were explained in terms of how the measurements affect the uncertainties in the estimates.

[0387] Processing decisions such as batch scheduling, tool allocation, and sampling plans were shown to have an effect on controller performance. Using the parameter estimate uncertainty information contained in the error covariance matrix, these processing decisions can be optimized to give more favorable process control results. Simulation results demonstrated that measurable improvements in state estimation and control output performance can be achieved by using information from the process controller to help make better scheduling and sampling decisions. In addition, it was shown that the state estimation algorithm can identify measurements that provide little information so that those measurements could potentially be skipped.

[0388] The particular embodiments disclosed above are illustrative only, as the invention may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. Furthermore, no limitations are intended to the details of construction or design herein shown, other than as described in the claims below. It is therefore evident that the particular embodiments disclosed above may be altered or modified and all such variations are considered within the scope and spirit of the invention. Accordingly, the protection sought herein is as set forth in the claims below.

Claims

What is claimed:

1. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed slates;

generating uncertainty values for the state estimates;

identifying a plurality of candidate schedules for performing activities in the manufacturing system;

predicting changes to the uncertainty values based on the candidate schedules; and

selecting one of the candidate schedules based on the predicted changes to the uncertainty values.

2. The method of claim 1, further comprising generating a state estimate matrix including the state estimates.

3. The method of claim 2, further comprising generating a covariance matrix associated with the state estimate matrix for each of the candidate schedules, the covariance matrix including the uncertainty values.

4. The method of claim 3, Wherein each candidate schedule includes a plurality of steps and selecting one of the candidate schedules based on the predicted uncertainty values further comprises:

calculating a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule;

determining an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule; and

selecting the candidate schedule having the lowest average trace value.

5. The method of claim of claim 3, wherein generating the covariance matrix further comprises generating the covariance matrix including the uncertainty values as diagonal terms.

6. The method of claim of claim 4, wherein generating the covariance matrix further comprises generating the covariance matrix including off-diagonal terns defining interdependency relationships amongst the observed states.

7. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises:

scheduling a plurality of processing activities; and

scheduling a plurality of metrology activities associated with a subset of the processing activities, each candidate schedule having a different subset of the processing activities.

8. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises scheduling a plurality of processing activities, each candidate schedule having a different order for the processing activities.

9. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises:

identifying a plurality of processing activities;

identifying a plurality of process tools capable of performing the processing activities; and

generating each candidate schedule having different process tools selected for performing the processing activities.

10. The method of claim 1, further comprising;

generating an uncertainty metric associated with each of the candidate schedules based on the predicted changes to the uncertainty values; and

selecting the candidate schedule having the lowest uncertainty metric.

11. The method of claim 10, wherein each candidate schedule includes a plurality of steps and generating the uncertainty metric further comprises:

generating a covariance matrix associated with the state vector for each of the candidate schedules for each of the steps, the covariance matrix including the uncertainty values;

calculating a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule; and

determining an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule to generate the uncertainty metric.

12. The method of claim 1, wherein each candidate schedule includes a priority process activity, and selecting one of the candidate schedules based on the predicted changes to the uncertainty values further comprises selecting the one of the candidate schedules having the lowest uncertainty while performing the priority process activity.

13. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed states;

generating uncertainty values for the state estimates;

identifying a plurality of candidate process activities in the manufacturing system;

predicting changes to the uncertainty values based on processing each of the candidate process activities first; and

selecting one of the candidate process activities for processing first based on the predicted uncertainty values.

14. The method of claim 13, further comprising:

removing the candidate process activity selected for first processing from the plurality of candidate process activities;

predicting changes to the uncertainty values based on processing each of the remaining candidate process activities second; and

selecting one of the remaining candidate process activities for processing second based on the predicted uncertainty values.

15. The method of claim 14, further comprising iteratively performing the removing, predicting, and selecting steps until a processing order is selected for each of the processing activities.

16. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed states;

generating uncertainty values for the state estimates;

identifying a plurality of candidate process tools capable of performing a selected process activity;

predicting changes to the uncertainty values based on performing the selected process activity on each of the candidate process tools; and

selecting one of the candidate process tools for performing the selected process activity based on the predicted uncertainty values.

17. A system for scheduling activities in a manufacturing system, comprising:

a process controller configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed states, and generate uncertainty values for the state estimates; and

a scheduling controller configured to identity a plurality of candidate schedules for performing activities in the manufacturing system, predict changes to the uncertainty values based on the candidate schedules, and select one of the candidate schedules based on the predicted changes to the uncertainty values.

18. The system of claim 17, wherein the process controller is further configured to generate a state estimate matrix including the state estimates.

19. The system of claim 18, wherein the process controller is further configured to generate a covariance matrix associated with the state estimate matrix for each of the candidate schedule, the covariance matrix including the uncertainty values.

20. The system of claim 19, wherein each candidate schedule includes a plurality of steps and the scheduling controller is further configured to calculate a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule, determine an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule, and select the candidate schedule having the lowest average trace value.

21. The system of claim of claim 19, wherein the scheduling controller is further configured to generate the covariance matrix including the uncertainty values as diagonal terms.

22. The system of claim of claim 20, wherein the scheduling controller is further configured to generate the covariance matrix including off-diagonal terms defining interdependency relationships amongst the observed states.

23. The system of claim 17, wherein the scheduling controller is further configured to schedule a plurality of processing activities and schedule a plurality of metrology activities associated with a subset of the processing activities, each candidate schedule having a different subset of the processing activities.

24. The system of claim 17, wherein the scheduling controller is further configured to schedule a plurality of processing activities, each candidate schedule having a different order for the processing activities.

25. The system of claim 17, wherein the scheduling controller is further configured to identify a plurality of processing activities, identify a plurality of process tools capable of performing the processing activities, and generate each candidate schedule having different process tools selected for performing the processing activities.

26. The system of claim 17, wherein the scheduling controller is further configured to generate an uncertainty metric associated with each of the candidate schedules based on the predicted changes to the uncertainty values and select the candidate schedule having the lowest uncertainty metric.

27. The system of claim 26, wherein each candidate schedule includes a plurality of steps, and the scheduling controller is further configured to generate a covariance matrix associated with the state estimate matrix for each of the candidate schedules for each of the steps, the covariance matrix including the uncertainty values, calculate a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate, schedule, and determine an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule to generate the uncertainty metric.

28. The system of claim 17, wherein each candidate schedule includes a priority process activity, and the scheduling controller is further configured to select the one of the candidate schedules having the lowest uncertainty while performing the priority process activity.

29. The system of claim 17, wherein the process controller and the scheduling controller are integrated into a single unit.

30. A system for scheduling activities in a manufacturing system, comprising:

a process controller configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed slates, and generate uncertainty values for the state estimates; and

a scheduling controller configured to identify a plurality of candidate process activities in the manufacturing system, predict changes to the uncertainty values based on processing each of the candidate process activities first, and select one of the candidate process activities for processing first based on the predicted uncertainty values.

31. The system of claim 30, the scheduling controller is further configured to remove the candidate process activity selected for first processing from the plurality of candidate process activities, predict changes to the uncertainty values based on processing each of the remaining candidate process activities second, and select one of the remaining candidate process activities for processing second based on the predicted uncertainty values.

32. The system of claim 31, the scheduling controller is further configured to iteratively performing the removing, predicting, and selecting steps until a processing order is selected for each of the processing activities.

33. The system of claim 30, wherein the process controller and the scheduling controller are integrated into a single unit.

34. A system for scheduling activities in a manufacturing system, comprising:

a scheduling controller configured to identify a plurality of candidate process tools capable of performing a selected process activity, predict changes to the uncertainty values based on performing the selected process activity on each of the candidate process tools, and select one of the candidate process tools for performing the selected process activity based on the predicted uncertainty values.

35. The system of claim 34, wherein the process controller and the scheduling controller are Integrated into a single unit.

36. A system for scheduling activities in a manufacturing system, comprising:

means for defining a plurality of observed states associated with the manufacturing system;

means for generating state estimates for the observed states;

means for generating uncertainty values for the state estimates;

means for identifying a plurality of candidate schedules for performing activities in the manufacturing system:

means for predicting changes to the uncertainty values based on the candidate schedules; and

means for selecting one of the candidate schedules based on the predicted changes to the uncertainty values.

Patent Citations (16)

Patent	Date	Inventor	Cited By
US5115391(A)	1992-05-01	Puthenpura et al.	Applicant
US5654907(A)	1997-08-01	Lange	Applicant
US5682309(A)	1997-10-01	Bartusiak et al.	Applicant
US5687077(A)	1997-11-01	Gough, Jr.	Examiner
US5865665(A)	1999-02-01	Yueh	Applicant
US5918200(A)	1999-06-01	Tsutsui et al.	Applicant
US5953229(A)	1999-09-01	Clark et al.	Examiner
US6092033(A)	2000-07-01	Uhlmann	Applicant
US6115640(A)	2000-09-01	Tarumi	Examiner
US6163730(A)	2000-12-01	Hayner	Applicant
US6285971(B1)	2001-09-01	Shah et al.	Applicant
US6519498(B1)	2003-02-01	Jevtic et al.	Examiner
US6584369(B2)	2003-06-01	Patel et al.	Examiner
US6633782(B1)	2003-10-01	Schleiss et al.	Examiner
US2002/0026249(A1)	2002-02-01	Rasmussen et al.	Examiner
EP1052558(A1)	2000-11-01		Applicant

Non-Patent Literature (11)

H. Mortazavian. Supervisory control with partial information on controllability and observability. IEEE, 348-351,1993.Applicant
K. J. Astrom and B. Wittenmark. Real-time parameter estimation. 59-99, 1989.Applicant
J. A. Wilson and L.F.M. Zorzetto. A generalized approach to process the estimation using hybrid artificial neural network/mechanistic models. Computers Chem. Engng. 21(9):951-963, 1997.Applicant
E. Del Castillo and J. Yeh An Adaptive run-to-run optimizing controller for linear and nonlinear semiconductor processes. IEEE Transactions on Semiconductor Manufacturing, 11(2):285-295, 1998.Applicant
J. S. Baras and N. S. Patel. A framework for robust run by run control with lot delayed measurements. Transactions on Semiconductor Manufacturing, 10(1):75-83, IEEE, 1997.Applicant
G. C. Goodwin and D. Q. Mayne. A parameter estimation perspective of continuous time model reference adaptive control. Automactica, 23(1):57-70, 1987.Applicant
G. M. Stanley and R. S. H. Mah, Observability and redundancy in process data estimation. Chemical Engineering Science, 36:259-272,1981.Applicant
C. Rao and J. Rawlings, Nonlinear moving horizon state estimation. International Symposium on Nonlinear Model Predictive Control: Assessment and Future Directions,146-163,1998.Applicant
Z. Ning, J. R. Moyne, T. Smith, D. Boning, E. Del Castillo, J. Yeh, and A. Hurwitz. A comparative analysis of run-to-run control algorithms in the semiconductor manufacturing industry. In Proceedings of the Advanced Semiconductor Manufacturing Conference, pp. 375-381. IEEE/SEMI, 1996.Applicant
K. S. Tsakalis. Performance limitations of adaptive parameter estimation and system identification algorithms in the absence of excitation. Automatica, 32(4):549-560, 1996.Applicant
International Search Report dated Aug. 6, 2003 (PCT/US 02/28872; TT5213-PCT).Applicant

US 6,738,682 B1Grant

Method and apparatus for scheduling based on state estimation uncertainties

Issue Date:2004-05-18

•36 Claims

•18 Drawing Sheets

Abstract

Metadata

Assignee

Advances Micro Devices, Inc.

Inventor

Alexander J. Pasadyn

Application Information

Application Number:US 10/210,753

Filing Date:2002-07-31

Priority Date:2001-09-13

Art Unit:7

Classifications

IPC:

G06F 1900G05B 1304

Field of Search:

700 44700 51700 52700 96700 97700103700100705 8705 9706 48

Patent Drawings (18 sheets)

Description

Background of the Invention

[0003] 1. Field of the Invention

[0004] This invention relates generally to the field of semiconductor device manufacturing and, more particularly, to a method and apparatus for scheduling based on state estimation uncertainties.

[0005] 2. Description of the Related Art

\begin{matrix} \min_{u} f (x, u, t) & (1) \end{matrix}

g_i(x,u,f)≧0 (2)

[0025] {tilde over (x)}_k+1=λx_k−1+(1−λ){tilde over (x)}_k, (3)

[0026] where x is the measured value, and {tilde over (x)} is the estimate.

[0031] Consider a process that can be modeled linearly as a simple example,

[0032] x=rt. (4)

[0036] x_k+1=Ax_k+Bu_k (5)

[0037] The process state x is mapped to the product state y using the output equation

[0038] y_k=Cx_k. (6)

[0040] r=r₀k_p. (7)

[0043] To estimate r₀and k_pfrom the data (r), the previous equation may be used with a Taylor series approximation,

[0044] Δr=r₀×Δk_p+k_p×Δr₀. (8)

[0046] One simple method of distributing the error is to apply a linear filter to each parameter.

[0047] r_0.new=r_0.measλ_r+r_0.last(1−λ_r) (9)

[0048] k_p.new=k_p.measλ_k+k_p.last(1−λ_k) (10)

[0056] The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.

Summary of the Invention

Brief Description of the Drawings

[0060] FIG. 1 is a simplified block diagram of a manufacturing system in accordance with one illustrative embodiment of the present invention;

[0061] FIG. 2 is a simplified block diagram of a portion of the manufacturing system of FIG. 1;

[0062] FIGS. 3A and 3B are graphs of exemplary probability density functions;

[0063] FIGS. 4 through 29 a graphs illustrating the performance of a controller of FIG. 1 to under various scenarios; and

[0064] FIG. 30 represents a block diagram on a system including a process controller and a scheduling controller in accordance with another embodiment of the present invention; and

[0065] FIG. 31 represents a simplified flow diagram of a method for scheduling activities in a manufacturing system in Accordance with yet another embodiment of the present invention.

Detailed Description of Specific Embodiments

[0077] Using a linearized form and assuming that there is a single “nominal” point for all combinations, the deviations from nominal removal for each context can be described by the equations

[0078] y_1A=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_At₀ (11)

[0079] y_1B=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_Bt₀ (12)

[0080] y_1C=r₀𝑓₀t+r₁𝑓₀t₀+r₀𝑓_Ct₀ (13)

[0081] y_2A=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_At₀ (14)

[0082] y_2B=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_Bt₀ (15)

[0083] y_2C=r₀𝑓₀t+r₂𝑓₀t₀+r₀𝑓_Ct₀, (16)

[0084] where the subscript “1” refers to the process tool 200, and the subscript “2” refers to the process tool 210.

[0085] The entire system can be combined into a single state-space model,

\begin{matrix} {[\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k + 1} = {[\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k} + {[\begin{matrix} r_{0} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] [t]}_{k} & (17) \\ {[\begin{matrix} y_{1 A} \\ y_{1 B} \\ y_{1 C} \\ y_{2 A} \\ y_{2 B} \\ y_{2 C} \end{matrix}]}_{k} = {[\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k}, & (18) \end{matrix}

[0087] The observability test calculated here,

\begin{matrix} O^{T} = [\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 0 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \end{matrix}], & (19) \end{matrix}

[0089] In the example above, tool qualifications would appear as two new cases described by the following equations.

[0090] y₁=r₁ (20)

[0091] y₂=r₂, (21)

\begin{matrix} {[\begin{matrix} y_{1 A} \\ y_{1 B} \\ y_{1 C} \\ y_{2 A} \\ y_{2 B} \\ y_{2 C} \\ y_{1} \\ y_{2} \end{matrix}]}_{k} = {[\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} x_{adj} \\ r_{1} \\ r_{2} \\ f_{A} \\ f_{B} \\ f_{C} \end{matrix}]}_{k} & (23) \end{matrix}

[0093] The observability matrix for this new system is

\begin{matrix} O^{T} = [\begin{matrix} 1 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 1 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 1 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 1 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} & 0 \\ 0 & f_{0} t_{0} & 0 & 0 & 0 & r_{0} t_{0} \\ 0 & 0 & f_{0} t_{0} & r_{0} t_{0} & 0 & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & r_{0} t_{0} & 0 \\ 0 & 0 & f_{0} t_{0} & 0 & 0 & r_{0} t_{0} \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}] & (24) \end{matrix}

\begin{matrix} f (x) = \frac{1}{\sqrt{2 π σ}} \exp (- \frac{{(x - \overline{x})}^{2}}{2 σ}), & (25) \end{matrix}

[0103] where {overscore (x)} is the mean and σ²is the variance. A plot of this function is shown in FIG. 3A.

[0104] For an n-vector of random variables, the probability density is given by

\begin{matrix} f (x) = \frac{1}{\sqrt{{(2 π)}^{″}} \det V} \exp (- \frac{1}{2} {(x - \overline{x})}^{T} V^{- 1} (x - \overline{x})), & (26) \end{matrix}

[0105] where {overscore (x)} is the vector of means and V is the covariance matrix given by

[0106] V=E((x−{overscore (x)})(x−{overscore (x)})^T). (27)

\begin{matrix} x = [\begin{matrix} x_{1} \\ x_{2} \end{matrix}] & (28) \end{matrix}

[0109] and an output equation given by

[0110] y=Cx, (29)

[0111] where

\begin{matrix} C = [\begin{matrix} a_{1} & a_{2} \\ b_{1} & b_{2} \end{matrix}] . & (30) \end{matrix}

\begin{matrix} f (x) = \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) . & (31) \end{matrix}

[0114] {tilde over (y)}₁=a₁{circumflex over (x)}₁+a₂{circumflex over (x)}₂. (32)

[0115] If a measurement of y_l,mis obtained for y_l, then the prediction error is

[0116] e_y=ŷ₁−y_l,m. (33)

[0117] The observer component 134 distributes this error between the states x₁and x₂. This distribution can be accomplished since a line l implied by the measurement,

[0118] y_l,m=a₁x₁+a₂x₂, (34)

\begin{matrix} \min_{x1, x2} {(x_{1} - {\hat{x}}_{1})}^{2} + {(x_{2} - {\hat{x}}_{2})}^{2} & (35) \end{matrix}

a₁x₁+a₂x₂=y_l,m. (36)

[0121] If a₂0, then

\begin{matrix} - \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} = x_{2} . & (37) \end{matrix}

[0122] Substituting this into Equation 35 yields

\begin{matrix} \min_{x1, x2} {(x_{1} - {\hat{x}}_{1})}^{2} + {(- \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} - {\hat{x}}_{2})}^{2} . & (38) \end{matrix}

[0123] Setting the derivative with respect to x₁to zero yields

\begin{matrix} 2 (x_{1} - {\hat{x}}_{1}) + 2 (- \frac{a_{1} x_{1}}{a_{2}} + \frac{y_{1, m}}{a_{2}} - {\hat{x}}_{2}) \frac{- a_{1}}{a_{2}} = 0. & (39) \end{matrix}

[0124] Grouping the x₁terms yields

\begin{matrix} x_{1} (1 + \frac{a_{1}^{2}}{a_{2}^{2}}) - {\hat{x}}_{1} - \frac{a_{1} y_{1}}{a_{2}^{2}} + \frac{a_{1} {\hat{x}}_{2}}{a_{2}} - 0. & (40) \end{matrix}

[0125] Therefore,

\begin{matrix} x_{1} = \frac{{\hat{x}}_{1} + \frac{a_{1} y_{1}}{a_{2}^{2}} - \frac{a_{1} {\hat{x}}_{2}}{a_{2}}}{1 + \frac{a_{1}^{2}}{a_{2}^{2}}} \frac{a_{2}^{2}}{a_{2}^{2}} = \frac{a_{2}^{2} {\hat{x}}_{1} + a_{1} y_{1} - a_{1} a_{2} {\hat{x}}_{2}}{a_{1}^{2} + a_{2}^{2}} . & (41) \end{matrix}

[0126] By symmetry,

\begin{matrix} x_{2} = \frac{a_{1}^{2} {\hat{x}}_{2} + a_{2} y_{1} - a_{2} a_{1} {\hat{x}}_{1}}{a_{1}^{2} + a_{2}^{2}} . & (42) \end{matrix}

[0127] So,

\begin{matrix} (x_{1.0}, x_{2.0}) = (\frac{a_{2}^{2} {\hat{x}}_{1} + a_{1} y_{1} - a_{1} a_{2} {\hat{x}}_{2}}{a_{1}^{2} + a_{2}^{2}}, \frac{a_{1}^{2} {\hat{x}}_{2} + a_{2} y_{1} - a_{2} a_{1} {\hat{x}}_{1}}{a_{1}^{2} + a_{2}^{2}}) & (43) \end{matrix}

[0128] The line, l, can be parameterized in t by

[0129] x₁(t)=x_1,0+a₂t (44)

[0130] x₂(t)=x_2,0−a₁t (45)

[0131] Now, the unnormalized integral, k_l, of the probability density function along line l may be defined by

\begin{matrix} k_{l} = \int_{l} \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ l, or & (46) \\ k_{l} = \int_{- \infty}^{\infty} \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} (t) - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} (t) - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ t . & (47) \end{matrix}

[0132] Then, the expected value of t is given by

\begin{matrix} t_{\exp} = \frac{1}{k_{l}} \int_{- \infty}^{\infty} t \frac{1}{\sqrt{4 π^{2} σ_{1} σ_{2}}} \exp (- \frac{{(x_{1} (t) - {\hat{x}}_{1})}^{2}}{2 σ_{1}^{2}} - \frac{{(x_{2} (t) - {\hat{x}}_{2})}^{2}}{2 σ_{2}^{2}}) ⅆ t, & (48) \end{matrix}

[0133] and the expected values of the states are given by

[0134] x₁=x_1,0+a₂t_exp (49)

[0135] x₂=x_2,0−a₁t_exp. (50)

[0138] Consider a system where {overscore (x)} is the current vector of state estimates, P is the error covariance matrix for the state estimates, and y is a vector of measurements described by

[0139] y=Cx+v, (51)

[0140] where v represents random measurement error with zero mean and covariance matrix R.

[0141] Given the system described above, the discrete Kalman filter essentially minimizes the performance index

\begin{matrix} J = \frac{1}{2} ({(x - \overline{x})}^{T} P^{- 1} (x - \overline{x}) + {(y - Cx)}^{T} R^{- 1} (y - Cx)), & (52) \end{matrix}

[0142] over x to arrive at the new state estimate vector.

[0145] dJ=dx^TP⁻¹(x−{overscore (x)})−(Cdx)^TR⁻¹(y−Cx). (53)

[0146] Thus,

[0147] 0=dx^T[P⁻¹(x−{overscore (x)})−C^TR⁻¹(y−Cx)]. (54)

[0148] Since dx can vary arbitrarily, the term in brackets must be zero, and it is possible to solve for the optimal x algebraically.

[0149] 0=P⁻¹x−P⁻¹{overscore (x)}−C^TR⁻¹y+C^TR⁻¹Cx (55)

[0150] 0=(P⁻¹+C^TR⁻¹C)x−P⁻¹{overscore (x)}−C^TR⁻¹y (56)

[0151] (P⁻¹+C^TR⁻¹C)x=P⁻¹{overscore (x)}+C^TR⁻¹y+C^TR⁻¹{overscore (x)}−C^TR⁻¹{overscore (x)} (57)

[0152] (P⁻¹+C^TR⁻¹C)x=(P⁻¹+C^TR⁻¹C){overscore (x)}+C^TR⁻¹y−C^TR⁻¹C{overscore (x)} (58)

[0153] x={overscore (x)}+(P⁻¹+C^TR⁻¹C)⁻¹C^TR⁻¹(y−C{overscore (x)}). (59)

[0154] In the two-variable case described above,

[0155] C=[a₁a₂] (60)

[0156] and

\begin{matrix} P = [\begin{matrix} σ_{1}^{2} & 0 \\ 0 & σ_{2}^{2} \end{matrix}] . & (61) \end{matrix}

[0157] Since there is only one measurement, the matrix R is simply the single term R. So for this case

\begin{matrix} x = \overline{x} + {([\begin{matrix} \frac{1}{σ_{1}^{2}} & 0 \\ 0 & \frac{1}{σ_{2}^{2}} \end{matrix}] + [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [\begin{matrix} a_{1} & a_{2} \end{matrix}])}^{- 1} [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] . & (62) \end{matrix}

[0158] Equation 62 can be further simplified by

\begin{matrix} x = \overline{x} + {[\begin{matrix} \frac{σ_{1}^{2} a_{1}^{2} + R}{σ_{1}^{2} R} & \frac{a_{1} a_{2}}{R} \\ \frac{a_{1} a_{2}}{R} & \frac{σ_{2}^{2} a_{2}^{2} + R}{σ_{2}^{2} R} \end{matrix}]}^{- 1} [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] & (63) \\ x = \overline{x} + \frac{σ_{1}^{2} σ_{2}^{2} R}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} \frac{σ_{2}^{2} a_{2}^{2} + R}{σ_{2}^{2} R} & - \frac{a_{1} a_{2}}{R} \\ - \frac{a_{1} a_{2}}{R} & \frac{σ_{1}^{2} a_{1}^{2} + R}{σ_{1}^{2} R} \end{matrix}] [\begin{matrix} a_{1} \\ a_{2} \end{matrix}] [\frac{1}{R}] [y - C \overline{x}] & (64) \\ x = \overline{x} + \frac{σ_{1}^{2} σ_{2}^{2} R}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} \frac{a_{1}}{σ_{2}^{2} R} \\ \frac{a_{2}}{σ_{1}^{2} R} \end{matrix}] [y - C \overline{x}] & (65) \\ x = \overline{x} + \frac{1}{σ_{1}^{2} a_{1}^{2} + σ_{2}^{2} a_{2}^{2} + R} [\begin{matrix} a_{1} σ_{1}^{2} \\ a_{2} σ_{2}^{2} \end{matrix}] [y - C \overline{x}] . & (66) \end{matrix}

[0159] This result demonstrates how the uncertainties in the state estimates and the measurement affect the update.

[0161] x={overscore (x)}+(P⁻¹+C_r^TR_r⁻¹C_r)⁻¹C_r^TR_r⁻¹(y_r−C_r{overscore (x)}). (67)

[0164] The evolution of x in time is given by

[0165] x_k+1=A_kx_k+B_ku_k+G_kw_k (68)

[0166] where u_kis the process input and w_kis a random process error with zero mean and covariance matrix Q. As above, the measurement taken is given by

[0167] y_k=C_kx_k+v_k, (69)

[0168] where v represents random measurement error with zero mean and covariance matrix R.

[0169] Any time the process is run, the state estimates and error covariance are updated using the following equations:

[0170] x_new=Ax_old+Bu (70)

[0171] P_new=AP_oldA^T+GQG^T (71)

[0173] x_new=x_old+(P_old⁻¹+C^TR⁻¹C)⁻¹C^TR⁻¹(y−Cx_old) (72)

[0174] P_new=(P_old⁻¹+C^TR⁻¹C)⁻¹. (73)

[0178] In the nonlinear case, the model equations are a more general relation between the current and future state values.

[0179] x_k+1=f(x_k,u_k) (74)

[0180] y_k=h(x_k) (75)

[0181] At a given time step, these equations can be linearized to create the corresponding terms from the linear model.

\begin{matrix} A \approx [\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \frac{\partial f_{1}}{\partial x_{2}} & \dots \\ \frac{\partial f_{2}}{\partial x_{1}} & \frac{\partial f_{2}}{\partial x_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (76) \\ B \approx [\begin{matrix} \frac{\partial f_{1}}{\partial u_{1}} & \frac{\partial f_{1}}{\partial u_{2}} & \dots \\ \frac{\partial f_{2}}{\partial u_{1}} & \frac{\partial f_{2}}{\partial u_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (77) \\ C \approx [\begin{matrix} \frac{\partial h_{1}}{\partial x_{1}} & \frac{\partial h_{1}}{\partial x_{2}} & \dots \\ \frac{\partial h_{2}}{\partial x_{1}} & \frac{\partial h_{2}}{\partial x_{2}} & \dots \\ ⋮ & ⋮ & ⋰ \end{matrix}] & (78) \end{matrix}

TABLE 1

Process Events: Case 1

TABLE 2

Process Events: Case 2

TABLE 3

Controller Internal History (Events 2-4)

TABLE 4

Controller Internal History (Events 2-5)

TABLE 5

Controller Internal History (Events 6-7)

[0209] The process model for a particular tool and product can be written

[0210] y=x_t+x_p+u, (79)

[0212] A traditional discrete time state space model is used, including the terms for process and metrology noise,

[0213] x_k+1=A_k+B_ku_k+G_kw_k, (80)

[0214] y_k=C_kx_k+v_k. (81)

[0215] So, for a system with m tools and n products, a state vector is constructed as

[0216] x=[x_adjx_tx_t. . . x_tx_px_p. . . x_p]^T (82)

[0218] The state transition matrix is a square matrix of size m+n+1 and is given by

\begin{matrix} A = [\begin{matrix} 0 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \end{matrix}], & (83) \end{matrix}

[0219] which shows that all the tool and product parameters are nominally stationary. The process input is assumed to affect only x_adj, so it is of size m+n+1 by 1 with an effect given by

[0220] B=[1 0 . . . 0]^T. (84)

[0221] The complete output matrix (of size mn+m by m+n+1) for the process is given by

\begin{matrix} C = [\begin{matrix} 1 & 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \\ 1 & 1 & 0 & \dots & 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 1 & 0 & \dots & 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 1 & \dots & 0 & 1 & 0 & \dots & 0 \\ 1 & 0 & 1 & \dots & 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 1 & \dots & 0 & 0 & 0 & \dots & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 1 & 0 & \dots & 0 \\ 1 & 0 & 0 & \dots & 1 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & 0 & \dots & 0 & 0 & 0 & \dots & 0 \\ 1 & 0 & 1 & \dots & 0 & 0 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋰ & ⋮ & ⋮ & ⋮ & ⋰ & ⋮ \\ 1 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 0 \end{matrix}], & (85) \end{matrix}

[0222] which results in an observable system. In each simulation run, only one row from the output matrix is active. This reduced subset of the output matrix is denoted by C_eff.

[0239] δ_k(t)=0, t<k (86)

[0240] δ_k(t)=1, t>k (87)

[0276] The equation,

[0277] y_k+1=𝑓(y_k,b_k,u_k)=y_k+b_ku_k, (88)

[0278] where b_kis the unknown gain (effective at time k) and u_kis the applied input, describes the process.

\begin{matrix} {[\begin{matrix} x \\ b \end{matrix}]}_{k + 1} \approx {[\begin{matrix} \frac{δ f}{δ x} & \frac{δ f}{δ b} \\ 0 & 1 \end{matrix}] [\begin{matrix} x \\ b \end{matrix}]}_{k} + {[\begin{matrix} \frac{δ f}{δ u} \\ 0 \end{matrix}] [u]}_{k} & (89) \\ {[y]}_{k} = {[\begin{matrix} 1 & 0 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} . & (90) \end{matrix}

[0280] Note that

\frac{δ f}{δ x_{k}} = 1, \frac{δ f}{δ b_{k}} = u_{k}, and \frac{δ f}{δ u_{k}} = b_{k} .

[0281] For this system, the observability test matrix is given by

\begin{matrix} O = [\begin{matrix} 1 & 1 \\ 0 & u_{k} \end{matrix}] . & (91) \end{matrix}

[0299] P_new=APA^T+GQG^T. (92)

[0300] When a measurement is taken (using a particular C_rand R_r, the error covariance is updated according to

[0301] P_new=(P_old⁻¹+C^TR⁻¹C)⁻¹. (93)

[0304] A very simple example system illustrates these ideas. Consider a nominally stationary process with two states and two measurements as described by the equations below.

\begin{matrix} {[\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k + 1} = {[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (94) \\ {[\begin{matrix} y_{1} \\ y_{2} \end{matrix}]}_{k} = {[\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (95) \end{matrix}

\begin{matrix} {[y_{1}]}_{k} = C_{r} x_{k} = {[\begin{matrix} 1 & 0 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} & (96) \\ {[y_{2}]}_{k} = C_{r} x_{k} = {[\begin{matrix} 1 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}]}_{k} . & (97) \end{matrix}

\begin{matrix} O = [C^{T}] [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}] . & (98) \end{matrix}

TABLE 6

Processing Order Dependence Results

[0318] Maximize throughput (minimize time).

[0319] Minimize use of raw materials.

[0320] Minimize mean-squared deviation from inline targets.

[0321] Minimize the number of gross outliers from inline targets.

\begin{matrix} \min_{u} f_{n} (u) & (99) \\ \sum_{i = 1}^{n} u_{i} \leq c & (100) \end{matrix}

u_i∈{0,1}. (101)

[0333] The vector u that solves the optimization problem minimizes the uncertainty in the parameter estimates while satisfying the constraint on the maximum number of measurements.

\begin{matrix} \min_{u} f_{n} (u) & (102) \end{matrix}

u_i∈{0,1,2, . . . , n} (103)

[0338] u_i≠u_j(i≠j). (104)

\begin{matrix} \min_{u} f_{n} (u) & (105) \end{matrix}

u_i∈{0,1,2, . . . , k} (106)

TABLE 7

Process Decision Base Case Run Summary

\begin{matrix} \frac{n!}{(n - c)! c!} . & (107) \end{matrix}

TABLE 8

Summary of Sampling Optimization Tests

TABLE 9

Summary of Order Optimization Tests

TABLE 10

Tool Allocation Run Summary