IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
757
Markovian Timed Petri Nets for Performance Analysis of Semicondu
ctor Manufacturing Systems
MuDer Jeng, Senior Member, IEEE, Xiaolan Xie, and WenYuan Hung
Abstract—A subclass of generalized stochastic Petri Nets (GSPNs) with priorities, called Markovian timed Petri nets, are proposed to model semiconductor manufacturing systems that consider process priorities, routing priorities, resource re-entrance, and nonpreemptive operations. Uniformization technique is used to establish both lower and upper bounds of the performance of interest. These bounds are computable using linear programming. Numerical experiments have been conducted to evaluate the accuracy of the bounds using models adapted from real-world systems. The experiments show that the upper bounds are very close to the simulation results. Thus, performance measures can be accurately estimated using these bounds. Index Terms—Linear programming, performance, Petri nets, semiconductor manufacturing, uniformization.
I. INTRODUCTION EMICONDUCTOR manufacturing systems are large and complex discrete event systems. The complexity arises from the large numbers of re-entrant production procedures and shared resources as well as the complicated interactions between procedures and resources. For example, a modern DRAM fabrication may require hundreds of processing steps using dozens types of machines. Because the manufacturing resources are rather expensive, system performance is especially crucial to every semiconductor plant production. To evaluate the performance of a semiconductor manufacturing system, prior work has used Petri nets models due to the advantages of their flexibility in capturing key system features [1]–[3], and their graphical representation for visualizing system dynamics. However, due to the state space explosion problem, it is computationally impractical to use analytic techniques such as those for stochastic and generalized stochastic Petri nets [6], [7], to calculate steady-state performance measures of large systems. As a result, simulation is often adopted. Although there are computationally efficient methods for computing cycle time in large timed marked graphs [9], a subclass of Petri nets, the methods are seldom used for semiconductor manufacturing systems because the systems are in general not decision-free. We notice that there has been research that calculates performance bounds of some classes of systems modeled by,
Manuscript received July 16; 2000; revised July 5, 2000. This work was supported in part by the National Science Council of Taiwan, R.O.C., under Grant NSC88-2212-E-019-013. This paper was recommended by Associate Editors M. A. Jafari and M. Zhou. M. Jeng and W. Hung are with the Department of Electrical Engineering, National Taiwan Ocean University, Keelung 202, Taiwan, R.O.C. (e-mail: jeng@celab1.ee.ntou.edu.tw). X. Xie is with the INRIA/Macsi Team, ENIM, 57045 Metz Cedex, France (e-mail: xie@loria.fr). Publisher Item Identifier S 1083-4419(00)08291-1.
S
for example, persistent and mono-T-semiflow Petri nets [11] and closed free choice synchronized queueing networks [12]. Again, these models have difficulties in representing complex semiconductor manufacturing systems. In this paper, we propose an analytic method for evaluating the performance of a class of semiconductor manufacturing systems. A subclass of generalized stochastic Petri nets (GSPN) with priorities [10], called Markovian timed Petri nets, are used to represent the systems with process priorities, routing priorities, resource re-entrance and nonpreemptive operations. The performance analysis follows the uniformization technique proposed in [4] for the performance evaluation of re-entrance production lines, an important class of semiconductor manufacturing systems. Unfortunately only preemptive operations were considered in [4] while operations are mainly nonpreemptive in most real situations. The uniformization technique was also used in [5] for the performance evaluation of stochastic timed Petri nets and the preemption was again assumed. An important feature of our approach is the consideration of nonpreemptive operations. Properties of the Petri net model are used to obtain tight lower and upper bounds of the performance of interest. These bounds are computable using linear programming. Therefore, the performance analysis proposed in this paper is based on the net structure rather than the generation of the underlying Markov chain as required for the analysis of general GSPNs. Notice also that the class of semiconductor manufacturing systems considered in this paper cannot be represented by the models proposed in [11] and [12]. The paper is organized as the follows. Section II describes basic concepts and the definition of Markovian timed Petri nets. Section III describes the uniformization technique. Section IV exploits the properties of the Petri net model to derive linear constraints for improving the uniformization technique. Computation of lower and upper bounds of the performance of interest is also addressed. Section V shows experimental results for small, medium, and large models. Conclusions are given in Section VI. II. BASIC CONCEPTS AND PROPOSED MODELS This section first briefly summarizes Petri net concepts [8] related to the discussion of this paper, and then presents the definition of Markovian timed Petri nets. A. Basic Concepts , An untimed Petri net is a four-tuple where and are finite sets of places and transitions respecis a set of directed arcs; and tively;
1083–4419/00$10.00 ? 2000 IEEE
758
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
Fig. 1.
Net modules: (a) basic module; (b) priority module; and (c) shared-resource module.
is the initial marking, where is the set of non-negative integers. The set of input (resp. output) transitions is denoted by (resp. ). The set of input of a place is denoted by (resp. (resp. output) places of a transition ). The marking indicates the number of tokens in each place. In manufacturing, tokens are interpreted as resources or system statuses. A Petri net models system dynamics using tokens and their firing rule. A transition is enabled and can be fired under a iff . The firing results in remarking moving one token from each of its input places and adding one is reachable token to each of its output places. A marking iff there exists a firing sequence of transitions from from to . This gives , where is called if the incidence matrix such that if , and , otherwise; and , called the firing count vector, is a vector whose -th entry denotes the number of denotes all occurrences of in . The reachability set the markings that are reachable from . Boundedness, liveness, and reversibility are three important properties in manufacturing. These correspond to overflow-freeness, deadlock-freeness, and re-initializability, such respectively. A Petri net is bounded iff a fixed and . is reversible that . is live iff and iff a marking reachable from such that is enabled. B. Markovian Timed Petri Nets A Markovian timed Petri net is such that: , and are places, transitions, arcs, and the initial marking, respectively, as defined in an untimed net. is the mapping of a transition to a 2) defined by an exponential probability firing rate , or to zero firing time, where density function 1)
Fig. 2. Place and arcs denoting the availability of buffer rooms.
is the set of nonnegative real numbers. A transition with zero firing time is called an immediate transition. is the mapping of a transition to a priority. 3) is the mapping of arcs (from places to 4) transitions) to switching probabilities. , is constructed by com5) The net structure, i.e., posing modules as defined below. The proposed class of Markovian timed nets model semiconductor manufacturing systems where each operation uses exactly one resource. This feature is typical in many real-world applications, e.g., the etching process of DRAM [2]. As shown in Fig. 1, the modules proposed in the present work to build Markovian timed nets are described as follows: 1) Basic module: this subnet models an operation that uses a dedicate machine. Two transitions respectively denote setup and processing of an operation, denoted by an operation place. Two buffer places represent that input and output buffer rooms are occupied, respectively. Note that it is assumed there is one global buffer in the system. The assumption is justified in [2]. Thus, the place and arcs model the availability of buffer rooms (see Fig. 2, where is the number of buffer rooms) are not shown in the models of this paper for clarity. 2) Priority module: Basic module can be transformed into this module if an operation can be performed in more than
JENG et al.: MARKOVIAN TIMED PETRI NETS
759
Fig. 3. Building a net by linking modules.
one machine, i.e., it has routing flexibility. In this case, the buffer places of the basic modules are merged, and in Fig. 2(b), the dotted blocks are basic modules. The routing priority is indicated in the setup transitions. 3) Shared-resource module: two or more of the above modules can be combined into this module if they share a common machine. That is, the resource place is merged, and in Fig. 2(c), the dotted blocks are basic modules. The resource priority can be defined in the setup transitions. Fig. 3 shows how a net is built by combining modules through merging the buffer places. Since an entire process in a semiconductor manufacturing system can be divided into subprocesses or layers, we summarize the model construction procedure as follows: 1) A basic module is built for each operation step. 2) All basic modules in each subprocess are connected according to the precedence order of the operations by merging the buffer places (as in Fig. 3). 3) Each subprocess net is refined, if necessary, by converting basic modules into priority and shared resource modules. 4) A source and a sink transitions are added to each subprocess net as shown in Fig. 4. Note that subprocess nets may share common modules (see the large model in Section V). C. An Example Fig. 5 shows a net that consists of three subprocesses, A, B, and . Each subprocess and C, and two types of resources, has exactly one operation. An alternative operation is denoted by setup and processing transitions, and an operation place (dotted blocks in Fig. 5). The input and output places of setup and processing transitions are buffer places. with C, and A also shares with In the model, A shares B. B and C have the higher priority of using resources. If A has and for use, it will use . The two available resources on and are set as follows: . routing priorities of and are both available, a token in will That is, when choose to fire. The process priorities of sharing resources on , and are set as follows: and . In and have tokens, a token in other words, when both will cause to fire. Similarly, we will fire if , and are all marked. As mentioned above, we say process priorities for priorities concerning the sharing of resources among different subproD. Assumptions In order to simplify the performance evaluation, we present several assumptions on the model: 1) There are no local processing cycles within a subprocess. Thus, there are no preventive maintenance (PM) on resources and rework. 2) There is one unit of each resource type. This implies that the resources are different one from another. 3) Higher priority subprocesses have only one resource type to use, i.e., no routing flexibility. 4) Each type of resources is shared by at most two processes. 5) Firing times of setup transitions, processing transitions and sink transitions are exponentially distributed random variables. 6) Source transitions are immediate transitions, i.e., with zero firing time. products in the system. When a 7) There are at most product leave the system, i.e., a sink transition fires, a new
Fig. 4. Net constructed by combining subprocess nets.
Fig. 5.
Simple model.
cesses, and routing priorities for choosing different possible resources for the same operation.
760
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
product is loaded into the system after an exponentially distributed random delay. 8) When a new product is loaded into the system, it chooses a process with respect to given routing probabilities. 9) The system is ergodic and it is initially in a steady state. Assumptions 7 and 8 can be represented in the Petri net models by adding an interface place and a transition , as illustrated in Fig. 6. It has been proven in [2] that the final Petri net model is greater than or equal to is live, bounded and reversible if the maximal number of resources that can perform the same operation. We notice that in our model, only resource setups are preemtpive and the operations are not preemptive. As a result, by choosing setup times small enough, our model provides a good approximation of nonpreemptive manufacturing systems. This is one of the advantage of using Petri net models since the joint consideration of job priority and uniformization has not been possible using classical queueing approaches [4]. Notice that in real-world semiconductor manufacturing, the setup times are relatively small compared to the operation times (e.g., 1–10). Nevertheless, a complete ignorance of setup times may not be feasible. Thus, we do not assign the setup transitions in our models to be immediate (i.e., with zero firing time). and the source tranNote that the subnet composed of sitions can be equivalently represented by a so-called switching transition as illustrated in Fig. 7. However, we should be aware that the forward function of the new transition, i.e., tokens generated by its firing, is random. We use in the following the compact representation for the performance evaluation. III. UNIFORMIZATION ANALYSIS In this section, we follow the uniformization technique proposed in [4] for the performance evaluation of re-entrant production lines. Special structure of our semiconductor manufacturing systems will be taken into account in the next section. The following notation will be used throughout the paper. Firing rate of transition . Incidence matrix of the Petri net. Expected value of . Marking at time . Set of buffer places. OP Set of operation places. Set of resource places. Set of input (output) places of . Set of input (output) transitions of . Set of processing transitions. OUT Set of sink transitions. SETUP Set of setup transitions. INV Set of minimal -invariants. Priority level of . Let us rescale time so that . The uniformization is a method for transforming a continuous time Markov process into an equivalent discrete time Markov chain by sampling the system at a constant rate higher than the maximal rate of leaving a state. In the case of Petri nets, it can be interpreted as follows. We can imagine that every (timed) transition is always under a firing process. If it is actually not enabled, we say that the tran-
Fig. 6. Interface place and interface transition.
Fig. 7. Equivalent representation.
sition is under a virtual firing process. As a result, the transition . Let be the sequence firings occur at rate denote the -field of such random sampling times, and let generated by the events up to time . be the marking of the Petri net at time . Let Let if transition is firable with regard to both the and the priority structure, and otherwise. marking and to represent the Furthermore, we use marking and the firability indicators after the -th event. , an event occurs. The event is an At the sampling time actual firing or a virtual firing of transition with probability . As a result, the following state transition will be observed: if if where is the transition fired at time Taking expectation by conditioning on . gives (1)
JENG et al.: MARKOVIAN TIMED PETRI NETS
761
Taking expectation of the new equation leads to
where . Furthermore, since for any processing transition (6)
Since the system is in a steady state, As a result, we obtain the following flow balance equation:
. B. Firability of Setup Transitions (2) Each setup transition has one buffer input place and one resource input place. As a result
is the utilization ratio of transition . where Considering now the second moments of the marking, i.e., for all . For , conditional expectation of (1) gives
Hence
and (7) C. -Invariants It is well known that for any -invariant . As a result (8) Taking expectation of the above equation (9) D. Process Priority in a Consider two transitions and and a resource place such that and has higher priority, i.e., (see Fig. 8). It is obvious that cannot fire if is marked, i.e., which implies (10) E. Routing Priority (4) where . Consider two transitions and and a buffer place such that and has the higher priority, i.e., (see Fig. 9). It is obvious that cannot fire if is marked, i.e., which implies (11) A resource is said to be nonidling if it cannot stay idle provided that at least one of its input place is not empty. Due to the priority structure, some resources may not be nonidling. For example, for the buffer place of Fig. 9, even if all three places and are marked, the lower priority transition cannot is not nonidling. fire and resource F. Number of Tokens in Buffer Places in a lower priority process, let For each buffer place be the resource corresponding to the output transition of
where Since
. the steady state, . Furthermore, . Combining these facts with (2) leads to (3) system is
Similarly, for all
, we have
IV. SPECIFIC CONSTRAINTS AND PERFORMANCE EVALUATION A. Firability of Single Input Transitions We notice that the interface transition, the processing transitions and the sink transitions have only one input place each. For any such transition , it is firable if and only if the input place is marked. That is,
where
is the set of input places of . Taking expectation gives (5)
762
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
TABLE I EXPERIMENT RESULT FOR A SIMPLIFIED MODEL
Fig. 8.
Process priority.
Fig. 9.
Routing priority.
G. Additional Constraints By definition, which implies that (13)
H. Performance Evaluation Equations (2)–(13) define a linear system of real nonnega, and . If the performance of interest tive numbers can be expressed as a linear function of these quantities such . Then a lower bound and an upper bound can as be obtained by solving the following linear programming problems:
Fig. 10. Simplified system for wafer etching.
with the highest routing priority. Thanks to assumptions 3 and is nonidling. As a result 4 of Section II,
(2)–(13) hold (2)–(13) hold Finally,
For each buffer place in a higher priority process, let be the resource related to the output transition of . Thanks to cannot be idle if assumptions 3 and 4 of Section II, . As a result
Typical performance of interest includes the throughput , the utilization ratio of a rerate , the average buffer level source , etc. V. EXPERIMENTAL RESULTS In order to evaluate the proposed method, we conduct several different experiments on a PentiumII-350 PC with 128 MB RAM running Windows 4.0 NT. LINDO, a commercial linear programming package, is used to compute upper and lower bounds of performance measures. Visual SimNet is adopted to obtain the simulation results for comparison.
As a result (12)
JENG et al.: MARKOVIAN TIMED PETRI NETS
763
Fig. 11.
Difference ratios of upper bounds.
Fig. 12.
Difference ratios of lower bounds.
Fig. 13.
Computation times of upper bounds.
This section contains three parts. First, we evaluate the performance bounds of a simplified semiconductor manufacturing model and compare the results with simulated ones. We also experiment the contributions of the constraints to the solution quality using this model since its performance bounds can be obtained fairly quickly under all constraints proposed in this paper. However, performance bounds of large models can be obtained within reasonable computation time only if we remove some of the constraints. That is, the number of constraints is too large for a large model. Since constraints (3) and (4), i.e., the
second moment flow balance constraints, constitute the largest portion of all constraints, we partially or completely remove these constraints in the present paper. Of course, as for which constraints should be removed such that good results are still retained, we leave it as a future research. Therefore, in the second and third parts of this section, we experiment a medium and a large etching area models adapted from a real-world system by partially and completely removing constraints (3) and (4), respectively. For all these models, mean setup and processing times are randomly assigned with a ratio of about 1:15.
764
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
Fig. 14.
Computation times of lower bounds.
Fig. 15.
Performance result without constraints (5).
Fig. 16.
Performance result without constraints (6).
Fig. 17.
Performance result without constraints (7).
JENG et al.: MARKOVIAN TIMED PETRI NETS
765
Fig. 18.
Performance result without constraints (12).
Fig. 19.
Performance result without constraints (13).
A. A Simplified Model Fig. 10 is a simplified net model for wafer etching where (i.e., the maximal number of wafer lots). It contains seven resource types and five subprocesses: CC, SW, AC, 3C, and PV. There are four resource types shared: pv cc, sw cc, aei2, and aei3. Resource pv cc is shared by CC and PV, and the pri. Resource sw cc is shared by CC and SW, and ority is . CC also has two routing choices such the priority is . We set the switching probathat the priority is bilities as 0.1, 0.1, 0.2, 0.2, and 0.4 for the five subprocesses, respectively. Table I shows the experimental result, where UB and LB mean the upper bound and the lower bound, respectively. We notice that the upper bounds of the resource utilization ratios and the throughput rate are very closed to the simulation results. Most differences are below 8%. The lower bounds are fair. Most difference ratios are below 35%. In the following, we discuss the effectiveness of constraints (2)–(13) on the solution quality: 1) Experiments show that constraints (2) are very important for computing accurate performance bounds. The number of flow balance equations in constraints (3) and (4) is the largest among all the constraints. Thus, it is natural to assume that such equations contribute to a large percentage of solution time. In order to know the effectiveness of constraints (3) and (4), we do two experiments. In one experiment, we only keep those of constraints (3) and (4) where the corresponding places and transitions are directly connected. In the second experiment, we remove all constraints (3) and (4). Figs. 11 and 12 show
Fig. 20.
Modified simple model.
the difference ratios. Thus, we know that constraints (3) and (4) have more influence on lower bounds than upper bounds. Even if we remove all constraints (3) and (4), the upper bounds of the performance are still very closed to the simulation results. The computation times are shown in Figs. 13 and 14. It is worth mentioning that almost the same upper bounds can still be obtained while the computation time is decreased drastically. However, the quality of lower bounds is reduced.
766
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
Fig. 21.
Upper bounds for different switching probabilities.
6)
7)
8)
Fig. 22.
Medium model for wafer etching.
9)
there is no information about how many tokens in the model. Constraints (11) are for routing priority. Experiments show that comparing to other constraints, the routing constraints seem to contribute less on the solution quality. This is because there are . The routing constraints only constitute a small percentage of them, and are bounded between 0 and the initial marking. most We leave the enhancement of the constraints on routing priority as a future research. Constraints (10) are for process priority. Experiments show that comparing to other constraints, the process constraints also seem to contribute less on the solution quality. The reason is similar to the above discussion on routing priority. However, the process constraints are stronger than the routing constraints. This is because a resource utilization is the sum of the utilizations for the transitions that are directly connected to the resource, and the transitions contain both the lower-priority and higher-priority transitions. Thus, a less accurate performance bound for one transition can be compensated by a more accurate one for another transition. Another experiment to test constraints (12) is shown in Fig. 18. These constraints are as important as constraints (5), and contribute to a lot of solution quality. Some solution quality is reduced when we remove constraints (13). Fig. 19 shows the result.
2) Constraints (5) concern the firability of single input transitions. We remove all constraints (5), and compare the computation results with those that keep all constraints (5). Fig. 15 shows that if we remove the constraints, the lower bounds of the resource utilization and throughput are all 0. In addition, some of the upper bounds are not good. From the experiment, we know constraints (5) are very important for obtaining good solutions. 3) We remove all constraints (6) (i.e., ones for processing transitions) and calculate the performance again. Fig. 16 shows that small solution quality is lost when we remove all constraints (6). 4) Fig. 17 shows if we remove all constraints (7) (i.e., ones for setup transitions), small solution quality is lost. 5) Constraints (8) and (9) concern the initial marking of the model. These constraints can not be ignored. Otherwise,
Beside the above experiments, it is well-known that equality constraints are more important than inequality constraints. As discussed above, the constraints for routing priority seem to contribute less to obtain good performance bounds. In the following experiment, we assign different switching probabilities to each subprocess, and compute the performance bounds. In order to understand the influence of switching probabilities on each subprocess, we simplify Fig. 10 into the model shown in Fig. 20, where all resources except those for CC, i.e., the subprocess with routing and choices, are nonshared. The priorities are: . Fig. 21 shows the result for upper bounds with three switching probability assignments. One assigns an equal probability to each subprocess, i.e., CC, SW, AC, and PV are all 0.25. Another assigns high probabilities to high-priority subprocesses, i.e.,
JENG et al.: MARKOVIAN TIMED PETRI NETS
767
Fig. 23. Performance result for a medium model.
Fig. 24.
Difference ratios of performance bounds for a medium model.
Fig. 25.
Modified medium model.
Fig. 26.
Performance result for a modified medium model.
we set the probabilities as 0.1, 0.3, 0.3, and 0.3 for CC, SW, AC, and PV, respectively. The third assigns high probabilities to low-priority processes, i.e., we set the probabilities as 0.5, 0.1, 0.3, and 0.1 for CC, SW, AC, and PV, respectively. We can see that when the lower-priority subprocess CC with routing choices is assigned with a lower switching probability, the result is the best.
B. A Medium Model Fig. 22 is a medium model for wafer etching where . It contains fifteen resource types and ten subprocesses: CC, SW, AC, 3C, PV, METAL, TUNGSTEN, 3P, 2P, and NITRIDE RMV. There are six resource types shared: pv cc, sw cc, aei2, aei3, web aei1 and 3p 2p. Resource pv cc is shared by CC and
768
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
Fig. 27.
Difference ratios of performance bounds for a modified medium model.
Fig. 28. Etching area model.
PV, and the priority is . Resource sw cc is shared . CC also has by CC and SW, and the priority is . two routing choices such that the priority is Resource web aei1 is shared by METAL and TUNGSTEN, and . Resource 3p 2p is the priority is . shared by 3P and 2P, and the priority is To gain computational efficiency, we remove some of constraints (3) and (4) where the corresponding places and transitions are not directly connected. Fig. 23 shows the experimental result where the numbers at the horizontal axis correspond to the resource utilization ratios and the throughput. Note that we set the switching probabilities as 0.01, 0.01, 0.1, 0.12, 0.12, 0.12, 0.05, 0.12, 0.05, 0.3, for the ten subpro-
cesses, respectively. The difference ratios of upper and lower bounds are shown in Fig. 24. We observe that the upper bounds of the resource utilization ratios and the throughput are very closed to the simulation results. Most differences are below 14%. The lower bounds are not as good as those for the previous model since only partial constraints (3) and (4) are kept. Each computation takes on an average about 30 minutes. Therefore, we know that if a lower-priority subprocess with routing choices is assigned with a lower switching probability, most of the upper bounds are very closed to the simulated ones. In order to know the effectiveness of routing priority on this model, we perform another experiment without routing priority.
JENG et al.: MARKOVIAN TIMED PETRI NETS
769
Fig. 29. Resource utilization ratios and throughput for a large model.
Fig. 30.
Difference ratios of upper bounds for a large model.
We convert CC in Fig. 22 to CC1 and CC2 in Fig. 25, i.e., we use switching probabilities (0.025, 0.025, 0.05, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.2 for the eleven subprocesses) to replace the routing priority. The experiment result is shown in Fig. 26. Fig. 27 shows the difference ratios of performance bounds. We notice that almost all upper bounds are almost equal to the simulation results. Thus, if each route is determined by a probability instead of a priority, more accurate bounds can be obtained. C. A Large Etching Area Model We consider a model that is adapted from a real-world . etching area [2]. The model is shown in Fig. 28, where It contains 38 resource types and 15 subprocesses: CC, SW, AC, 3C, PV, METAL, TUNGSTEN, 3P, 2P, NITRIDE RMV, EDGE POLY RMV, 4P, 1P, AC WIDTH, and UV/03 ASHING. There are seven resource types shared: pv cc, sw cc, aei2, aei3, web aei1, 3p 2p, and 4p 1p. Resource pv cc is shared by CC . Resource sw cc is shared and PV, and the priority is . CC also has by CC and SW, and the priority is . two routing choices such that the priority is Resource web aei1 is shared by METAL and TUNGSTEN, . Resource 3p 2p and the priority is . 3P also is shared by 3P and 2P, and the priority is . has two routing choices such that the priority is Resource 4p 1p is shared by 4P and 1P and the priority is
. 1P also has two routing choices such that the priority . For computational efficiency, in this experiment we remove all constraints (3) and (4). Fig. 29 shows the experimental result of upper bounds where the numbers at the horizontal axis correspond to the resource utilization ratios and the throughput. We set the probabilities as 0.008, 0.008, 0.05, 0.1, 0.05, 0.1, 0.05, 0.004, 0.008, 0.13, 0.13, 0.1, 0.008, 0.13, 0.124 for the 15 subprocesses, respectively. The difference ratios of upper bounds are shown in Fig. 30. Again, we notice that the upper bounds of the resource utilization ratios and the throughput are very closed to the simulation results. Most differences are below 5%. Note that some of the difference rations for upper bounds are slightly below zero. This may be due to the simulation error since exact performance may not be obtained. Because of removing all constraints (3) and (4), the lower bounds are all 0. The computation times are shown in Fig. 31. In Fig. 30, two resources have high difference ratios. One is 4p 1p, and its difference ratio is 36.95% (resource #14). The other is pv cc, and its difference ratio is 17.43% (resource #3). These two resources have the same characteristics that they serve subprocesses with routing choices, and the priorities of the served routes are low. This effect has been discussed in the first experiment about routing priority. In addition, consider the fashion where we assign the switching probabilities. Thus, is
770
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 30, NO. 5, OCTOBER 2000
Fig. 31.
Computation times for a large model.
as in the experiments for the previous models, we also obtain the conclusion that if a lower-priority subprocess with routing choices is assigned with a lower switching probability, most of the upper bounds are very closed to the simulated ones. Thus, if a system model conform to such a condition, we can estimate a performance measure very accurately by its upper bound.
Preliminary results on the effectiveness of the constraints proposed in this paper have been obtained. More thorough study should be done in the future. Another future direction is the improvement of lower bounds. Again, this also concerns the addition and removal of constraints as described above.
ACKNOWLEDGMENT VI. CONCLUSION A technique has been proposed for calculating lower and upper bounds of performance measures for a class of semiconductor manufacturing systems. A system is modeled as a Markovian timed Petri net. The net model can represent a system with process priorities, routing priorities, resource re-entrance, and nonpreemptive operations. In particular, the last feature is more realistic than prior work [4] that only considers preemptive operations. The performance bounds are computable using the uniformization technique and linear programming. We have conducted experiments for small, medium, and large models that are adapted from a real-world system for wafer etching. For the small model, the upper bounds are very close to the simulated performances of interest. The lower bounds are fair although not as good as the upper bounds. For the medium model, since we partially remove the second moment flow balance constraints to gain computational efficiency, the lower bounds are not as good as those for the small model. Nevertheless, the upper bounds are still very close to the simulated results. The former are closer to the latter if a lower-priority subprocess with routing choices is assigned with a lower switching probability. This argument also holds in the experiment for the large model even if we remove all the second moment flow balance constraints. Thus, if a system model conform to such a condition, we can estimate a performance measure very accurately by its upper bound. Currently, we are investigating the relaxation of the assumptions made in this paper. This includes the extension of the proposed method to systems with rework, preventive maintenance, and general time distribution. Future research may consider the addition of further constraints to increase the accuracy of performance bounds while removing unimportant constraints that contribute less to the solution quality to cope with large models. The authors would like to thank Dr. W. Garbe for the use of the Visual SimNet package.
REFERENCES
[1] C. Feng and W.-C. Hung, “Modeling and simulation of a Petri netsbased diffusion cell controller in an IC CIM system,” in Proc. 1997 IEEE Int. Conf. Syst., Man, Cybern., Orlando, FL, Oct. 12–15, 1997, pp. 1180–1185. [2] M. D. Jeng, X. L. Xie, and S. W. Chou, “Modeling, qualitative analysis, and performance evaluation of the etching area in an IC wafer fabrication system using Petri nets,” IEEE Trans. Semicond. Manufact., vol. 11, pp. 358–373, Aug. 1998. [3] J. Kim and A. A. Desrochers, “Modeling and analysis of semiconductor manufacturing plants using time Petri net models: COT business case study,” in Proc. 1997 IEEE Int. Conf. Syst., Man, Cybern., Orlando, FL, Oct. 12–15, 1997, pp. 3227–3232. [4] S. Kumar and P. R. Kumar, “Performance bounds for queueing networks and scheduling policies,” IEEE Trans. Automat. Contr., vol. 39, pp. 1600–1611, 1994. [5] Z. Liu, “Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach,” INRIA, France, Research Report, no. 2642, 1995. [6] M. A. Marsan, G. Balbo, and G. Conte, “A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor system,” ACM Trans. Comput. Syst., vol. 2, pp. 93–122, 1984. [7] M. K. Molloy, “Performance analysis using stochastic Petri nets,” IEEE Trans. Comput., vol. C–23, pp. 913–917, 1982. [8] T. Murata, “Petri nets: Properties, analysis, and applications,” Proc. IEEE, vol. 77, pp. 541–580, 1989. [9] M. C. Zhou and M. D. Jeng, “Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems: A Petri net approach,” IEEE Trans. Semicond. Manufact., vol. 11, pp. 333–357, Aug. 1998. [10] G. Chiola, M. A. Marsan, G. Balbo, and G. Conte, “Generalized stochastic Petri nets: A definition at the net level and its implications,” IEEE Trans. Softw. Eng., vol. 19, no. 2, pp. 89–107, 1993. [11] J. Campos, G. Chiola, and M. Silva, “Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector,” IEEE Trans. Softw. Eng., vol. 17, no. 2, pp. 117–125, 1991. [12] , “Properties and performance bounds for closed free choice synchronized monoclass queueing networks,” IEEE Trans. Automat. Contr., vol. 36, no. 12, pp. 1368–1382, 1991.
JENG et al.: MARKOVIAN TIMED PETRI NETS
771
MuDer Jeng (S’89-M’92-SM’96) received the B.S. and M.S. degrees in electrical engineering from National Cheng Kung University, Tainan, Taiwan, R.O.C., in 1983 and 1985, respectively, and the Ph.D. degree in computer and systems engineering from Rensselaer Polytechnic Institute, Troy, NY, in 1992. He is currently Professor of Electrical Engineering at National Taiwan Ocean University, Keelung. He was a Visiting Scientist at INRIA (Institut National de Recherche en Informatique et en Automatique) Lorraine, France, during the summers of 1999 and 2000. His research interests include Petri nets, discrete event systems, computer integrated manufacturing, semiconductor manufacturing systems, multimedia systems, neural networks, and underwater robotics. In the above areas, he has over 80 publications in journals, books, and conference proceedings. Dr. Jeng received Franklin V. Taylor Outstanding Paper Award from IEEE Systems, Man and Cybernetics (SMC) Society in 1993. He has annually been granted Research Award by National Science Council, Taiwan since 1994. He has been a program committee member of: 1994, 1998, and 1999 IEEE SMC Conferences; 1997 and 1999 IEEE International Conferences on Emerging Technologies and Factory Automation; 1998 and 2000 IEEE International Symposia on Industrial Electronics; and 2001 IEEE International Conference on Robotics and Automation. He organized and chaired/co-chaired over 20 sessions in major international conferences. He guest-edited a 1998 special section on “Petri Nets in Semiconductor Manufacturing” for IEEE TRANSACTIONS ON SEMICONDUCTOR MANUFACTURING, and is currently a Guest Editor for a 2001 special issue on “Semiconductor Manufacturing Systems: Modeling, Analysis, and Control” for IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION. He is listed in Who’s Who in the World, Who’s Who in Science and Engineering, and Who’s Who in Asia and the Pacific Nations.
Xiaolan Xie received the Ph.D. degree from University of Nancy I, Nancy, France, in 1989, and the Habilitation à Diriger des Recherches degree from University of Metz, Metz, France, in 1995. He was a Senior Research Scientist at the Institut National de Recherche en Informatique et en Automatique (INRIA) from 1990 to 1999. Since 1999, he has been a Full Professor at the Ecole Nationale d’Ingénieurs de Metz (ENIM), a French engineering school. His research interests include modeling, performance evaluation, management, and design of manufacturing systems. He is coauthor of a book on Petri nets and has authored/coauthored over 30 journal papers in related fields. He has served as a Guest Editor of a 2000 Special Issue of International Journal of Production Research on modeling, specification, and analysis of manufacturing systems, and a 2001 Special Issue of IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION on semiconductor manufacturing systems.
WenYuan Hung received the M.S. degree in electrical engineering from National Taiwan Ocean University, Keelung, Taiwan, R.O.C. in 1999. He currently serves in the R.O.C. Marines. His research interests include Petri nets and performance evaluation of semiconductor manufacturing systems.