Petri Net-based Scheduling of Time Constrained Single-arm Cluster Tools with Wafer Revisiting

Abstract

It is very difficult to schedule a single-arm cluster tool with wafer revisiting such that wafer residency time constraints are satisfied. The present invention conducts a study on this challenging problem for a single-arm cluster tool with atomic layer deposition (ALD) process. With a so called p-backward strategy being applied, a Petri net model is developed to describe the dynamic behavior of the system. Based on the model, existence of a feasible schedule is analyzed, schedulability conditions are derived, and scheduling algorithms are presented if there is a schedule. A schedule is obtained by simply setting the robot waiting time if schedulable and it is very computationally efficient. The obtained schedule is shown to be optimal. Illustrative examples are given to demonstrate the proposed approach.

Claims

1. A computer-implemented method for scheduling a cluster tool, the cluster tool comprising a single-arm robot for wafer handling, a wafer-processing system comprising four process modules including PM.sub.1, PM.sub.2, PM.sub.3, and PM.sub.4, each for performing a wafer-processing step with a wafer residency time constraint where the ith process module, i{1, 2, . . . , 4}, is used for performing Step i of the wafer-processing steps for each wafer, and a wafer flow pattern having (PM.sub.1, (PM.sub.2, PM.sub.3).sup.h, PM.sub.4) with (PM.sub.2, PM.sub.3).sup.h being the revisiting process and h2, the method comprising: obtaining, by a processor, a lower bound z.sub.iL of a production cycle of Step i,i{1, 2, . . . , 4}, as follows:
.sub.1L=.sub.1+3+4;
.sub.2L=2.sub.2+.sub.3+5+8;
.sub.3L=2.sub.3+.sub.2+5+8; and
.sub.4L=.sub.4+3+4; obtaining, by a processor, an upper bound .sub.iU of a production cycle of Step i, i{1, 2, . . . , 4}, as follows:
.sub.1U=.sub.1+3+4;
.sub.2U=2.sub.2+.sub.3+5+8;
.sub.3U=2.sub.3+.sub.2+5+8; and
.sub.4U=.sub.4+3+4; obtaining, by a processor, a maximum lower bound .sub.Lmax as follows:
.sub.Lmax=max{.sub.iL,i custom-character .sub.4}; obtaining, by a processor, a minimum upper bound .sub.Umin as follows:
.sub.Umin=min{.sub.iU,i.sub.4}; determining, by a processor, a robot task time .sub.1 in a cycle as follows:
.sub.1=14+12+.sub.2+.sub.3; determining, by a processor, a robot waiting time .sub.i of Step i as follows:
if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U] and .sub.1<.sub.Lmax, then setting .sub.0=.sub.1=.sub.2=.sub.3=0, and setting .sub.4=.sub.Lmax.sub.1;
else if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U] and .sub.Lmax.sub.1.sub.Umin, then setting .sub.0=.sub.1=.sub.2=.sub.3=0;
else if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U]= and .sub.Lmax.sub.1.sub.Umin, then setting .sub.i,i.sub.3 by $_{i - 1} = {\begin{matrix} 0, & i F \\ _{Lmax} -_{i} -_{i} - 4 .Math. - 3 .Math., & i E .Math. {1, 4} \\ _{Lmax} - 2 .Math._{2} -_{2} -_{3} - 5 .Math. - 8 .Math., & i E .Math. {2} \\ _{Lmax} - 2 .Math._{3} -_{3} -_{2} - 5 .Math. - 8 .Math., & i E .Math. {3} \end{matrix} .Math. .Math. and .Math. .Math. setting .Math. .Math._{4} =_{Lmax} -_{1} - {.Math.}_{i = 0}^{3} .Math. .Math._{i};$ wherein: .sub.i, i custom-character .sub.4, is a time that a wafer is processed in the ith process module; .sub.i i.sub.4, is a longest time that a wafer stays in the ith process module after being processed; is a time that a wafer is loaded or unloaded by the robot from Step i; is a time that a wafer is moved by the robot from Step i to Step j; E={i|.sub.iU>.sub.Lmax, i custom-character .sub.4}; and F=.sub.4\E.

2. The method of claim 1, further comprising: determining a production cycle of the system.

3. The method of claim 1, wherein the determination of the robot waiting time is based on a Petri Net model.

4. The method of claim 1, wherein the h is 2.

5. A non-transitory computer-readable medium whose contents cause a computing system to perform a computer-implemented method for scheduling a cluster tool, the cluster tool comprising a single-arm robot for wafer handling, a wafer-processing system comprising four process modules including PM.sub.1, PM.sub.2, PM.sub.3, and PM.sub.4, each for performing a wafer-processing step with a wafer residency time constraint where the ith process module, i{1, 2, . . . 4}, is used for performing Step i of the wafer-processing steps for each wafer, and a wafer flow pattern having (PM.sub.1, (PM.sub.2, PM.sub.3).sup.h, PM.sub.4) with (PM.sub.2, PM.sub.3).sup.h being the revisiting process and h2, the method comprising: obtaining, by a processor, a lower bound z.sub.iL of a production cycle of Step i,i{1, 2, . . . 4}, as follows:
.sub.1L=.sub.1+3+4;
.sub.2L=2.sub.2+.sub.3+5+8;
.sub.3L=2.sub.3+.sub.2+5+8; and
.sub.4L=.sub.4+3+4; obtaining, by a processor, an upper bound .sub.iU of a production cycle of Step i, i{1, 2, . . . , 4}, as follows:
.sub.1U=.sub.1+3+4;
.sub.2U=2.sub.2+.sub.3+5+8;
.sub.3U=2.sub.3+.sub.2+5+8; and
.sub.4U=.sub.4+3+4; obtaining, by a processor, a maximum lower bound .sub.Lmax as follows:
.sub.Lmax=max{.sub.iL,i custom-character .sub.4}; obtaining, by a processor, a minimum upper bound .sub.Umin as follows:
.sub.Umin=min{.sub.iU,i.sub.4}; determining, by a processor, a robot task time .sub.1 in a cycle as follows:
.sub.1=14+12+.sub.2+.sub.3; determining, by a processor, a robot waiting time .sub.i of Step i as follows:
if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U] and .sub.1<.sub.Lmax, then setting .sub.0=.sub.1=.sub.2=.sub.3=0, and setting .sub.4=.sub.Lmax.sub.1;
else if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U] and .sub.Lmax.sub.1.sub.Umin, then setting .sub.0=.sub.1=.sub.2=.sub.3=0;
else if [.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U]= and .sub.Lmax.sub.1.sub.Umin, then setting .sub.i,i.sub.3 by $_{i - 1} = {\begin{matrix} 0, & i F \\ _{Lmax} -_{i} -_{i} - 4 .Math. - 3 .Math., & i E .Math. {1, 4} \\ _{Lmax} - 2 .Math._{2} -_{2} -_{3} - 5 .Math. - 8 .Math., & i E .Math. {2} \\ _{Lmax} - 2 .Math._{3} -_{3} -_{2} - 5 .Math. - 8 .Math., & i E .Math. {3} \end{matrix} .Math. .Math. and .Math. .Math. setting .Math. .Math._{4} =_{Lmax} -_{1} - {.Math.}_{i = 0}^{3} .Math. .Math._{i};$ wherein: .sub.i, i custom-character .sub.4, is a time that a wafer is processed in the ith process module; .sub.i i.sub.4, is a longest time that a wafer stays in the ith process module after being processed; is a time that a wafer is loaded or unloaded by the robot from Step i; is a time that a wafer is moved by the robot from Step i to Step j; E={i|.sub.iU<.sub.Lmax, i custom-character .sub.4}; and F=.sub.4\E.

6. The non-transitory computer-readable medium of claim 5, wherein the method further comprises: determining a production cycle of the system.

7. The non-transitory computer-readable medium of claim 5, wherein the determination of the robot waiting time is based on a Petri Net model.

8. The non-transitory computer-readable medium of claim 5, wherein the h is 2.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0060] Embodiments of the present invention are described in more detail hereinafter with reference to the drawings, in which:

[0061] FIG. 1 depicts cluster tools: (a) single-arm robot and (b) dual-arm robot; and

[0062] FIG. 2 depicts a PN model for the system with wafer flow pattern (PM.sub.1, (PM.sub.2, PM.sub.3).sup.h, PM.sub.4).

DETAILED DESCRIPTION

[0063] In the following description, a method for scheduling time constrained single-arm cluster tools with wafer revisiting is set forth as preferred examples. It will be apparent to those skilled in the art that modifications, including additions and/or substitutions may be made without departing from the scope and spirit of the invention. Specific details may be omitted so as not to obscure the invention; however, the disclosure is written to enable one skilled in the art to practice the teachings herein without undue experimentation.

[0064] The aim of the present invention is to cope with this challenging problem for a single-arm cluster tool. The problem is modeled by a Petri net by using a p-backward strategy explained later. With the model, analysis on the existence of a feasible schedule is carried out and conditions under which a schedule exists are presented. If it is schedulable, a schedule is very efficiently obtained by simply setting the robot waiting time. The obtained schedule is shown to be optimal in terms of cycle time.

[0065] In Section A, the present invention develops the PN model for the system. Based on it, Section B carries out the schedulability analysis, establishes the schedulability conditions, and presents scheduling algorithms to obtain the optimal schedule. Illustrative examples are used to demonstrate the proposed method in Section C.

A. MODELING BY PETRI NET

[0066] Petri nets (PNs) are recognized as a powerful tool for dealing with concurrent activities and resource allocation. They are widely used for modeling, analysis, and control of manufacturing systems [Wu et al., 2008a, and 2011, 2013; and Kim et al., 2003 and 2013]. The present invention adopts PN to model the dynamic behavior of a single-arm cluster tool with both wafer residency time constraints and wafer revisiting.

A.1 Finite-Capacity PN

[0067] Scheduling a cluster tool is to effectively allocate its limited resources to tasks. To do so, the present invention adopts the resource-oriented PN (ROPN) to model the system. It is a finite capacity PN and its basic concept is based on [Murata, 1989, Wu, 1999; and Wu and Zhou, 2001, and 2009]. It is denoted as PN=(P, T, I, O, M, K), where P=(p.sub.1, p.sub.2, . . . , p.sub.m) and T=(t.sub.1, t.sub.2, . . . , t.sub.n) are finite sets of places and transitions with PT= and PT; I: PT.fwdarw.N={0, 1, 2, . . . } and O: PT.fwdarw.N describe the relation from P to T and T to P, respectively; M: P.fwdarw.N is a marking with M(p) being the number of tokens in place p and M.sub.0 being the initial marking; K: P.fwdarw.{1, 2, 3, . . . } is a capacity function with K(p) representing the maximum number of tokens that can be held by p at a time.

[0068] Let .sup.t={p: pP and I(p, t)>0} be the preset of transition t and t.sup.={p: pP and O(p, t)>0} be its postset. Similarly, p's preset .sup.p={tT: O(p, t)>0} and postset p.sup.={tT: I(p, t)>0}. Then, the transition enabling and firing rules are defined as follows.

[0069] Definition 2.1: A transition tT in a finite capacity PN is said to be enabled if following conditions are satisfied.

M(p)I(p,t),pP(2.1)

K(p)M(p)I(p,t)+O(p,t),pP(2.2)

[0070] By Definition 2.1, when (2.1) is met, t is said to be process-enabled, and when (2.2) is met, t is said to be resource-enabled. Thus, t is enabled if it is both process and resource-enabled.

[0071] An enabled tT at marking M can fire. The firing oft transforms the PN from M to M according to

M(p)=M(p)I(p,t)+O(p,t),pP(2.3)

A.2 Modeling Activity Sequences

[0072] In wafer fabrication, ALD is a typical revisiting process and, as done in [Wu et al., 2011], the present invention focuses on the ALD process. In ALD, a wafer visits Step 1 first and then it goes to Steps 2 and 3 sequentially for processing. After being processed by Step 3, it goes back to Step 2 and the Step 3. This process is repeated for several times. To control the quality, every time the wafer visits Steps 2 and 3, the exact same processing environment is required. To ensure the processing environment requirement, each step is configured with only one PM. One assumes that PM, is configured for Step i. Thus, as presented in [Wu et al., 2011], the wafer flow pattern for this process can be denoted as (PM.sub.1, (PM.sub.2, PM.sub.3).sup.h, PM.sub.4) with (PM.sub.2, PM.sub.3).sup.h being the revisiting process and h2. For the simplicity of presentation, the present invention focuses on the case when h=2. Notice that the obtained results with h=2 can be extended to cases with h>2. Then, a single-arm cluster tool with both wafer residency time constraints and wafer revisiting is modeled by an ROPN as follows.

[0073] Let N.sub.n{1, 2, 3, . . . , n} and .sub.n=N.sub.n{0}. As shown in FIG. 2, timed place p.sub.n, nN.sub.4, models the PM for Step n with K(p.sub.n)=1 representing that there is only one PM. The loadlocks are treated as a processing step with the processing time being zero. They are modeled by p.sub.0 with K(p.sub.0)= representing that the loadlocks can hold all wafers in a tool. Timed place q.sub.n2 with K(q.sub.n2)=1, n.sub.4, models the robot waiting before unloading a wafer from p.sub.n. Non-timed places q.sub.n1 and q.sub.n3 with K(q.sub.n1)=K(q.sub.n3)=1, n.sub.4, are used to connect two neighboring steps. Place r with K(r)=1 models the robot (R). When M(r)=1, the robot is idle and ready for performing a task.

[0074] With the resources in the system being modeled, transitions are used to model the material flows. Timed transition t.sub.ij, i, j.sub.4, models the activity that the robot moves from p.sub.i to p.sub.j with a wafer being carried. Timed transition y.sub.ij, i, j.sub.4, models the activity that the robot moves from p.sub.i to p.sub.j without carrying a wafer. Transitions s.sub.n1 and s.sub.n2 represent the robot tasks that load and unload a wafer into and from p.sub.n, n.sub.4, respectively. By doing so, the structure of the model is formed.

[0075] With the developed PN structure, by putting a V-token representing a virtual wafer, the initial marking M.sub.0 is set as follows. Set M.sub.0(p.sub.i)=1, iN.sub.4\{1}, M.sub.0(p.sub.1)=0, and M.sub.0(p.sub.0)=n to indicate that, there are always wafers in the loadloacks to be processed; M.sub.0(r)=0; M.sub.0(q.sub.ij)=0, i custom-character .sub.4 and j.sub.3, and M.sub.0(q.sub.02)=1, indicating that the robot is waiting at the loadlocks for unloading a wafer there.

[0076] With wafer revisiting process, there are two ways for a token in q.sub.33 to go, one is to q.sub.21 by firing t.sub.32 and the other is to q.sub.41 by firing t.sub.34, leading to a conflict. To eliminate such a conflict, colors are introduced to the model to form a colored PN as follows.

[0077] Definition 2.2: Transition t.sub.i in the PN is defined to have a unique color C(t.sub.i)=c.sub.i.

[0078] By Definition 2.2, the color of t.sub.32 and t.sub.34 are C.sub.32 and c.sub.34, respectively. Let W.sub.d(g) be the d-th wafer released into the system and being processed for the g-th time by a PM. Then, one can define the color of a token as follows.

[0079] Definition 2.3: Define the color of a token W.sub.d in q.sub.33 as C(q.sub.33, W.sub.d)=c.sub.3, if it will go to step j for processing when it leaves q.sub.33.

[0080] By Definition 2.3, one has C(q.sub.33, W.sub.d(q))=C(t.sub.32)=e.sub.32, 1q<h, and (q.sub.33, W.sub.d(h))=C(t.sub.34)=c.sub.34. Notice that, in the model, only q.sub.33 has multiple output transitions. Hence, by Definitions 2.2 and 2.3, conflict is eliminated. Besides conflict, deadlock is an important issue for operating a single-arm tool with wafer revisiting. To avoid deadlock, one presents a control policy by the following definition.

[0081] Definition 2.4: At any marking M, transitions y.sub.20 is control-enabled only if the transition firing sequence t.sub.12.fwdarw.s.sub.21 has just performed; y.sub.03 is control-enabled only if s.sub.01 has just fired; y.sub.14 is control-enabled only if s.sub.11 has just fired; y.sub.42 is control-enabled only if s.sub.41 has just fired; y.sub.22 is control-enabled only if the transition firing sequence t.sub.32.fwdarw.s.sub.21 has just performed; y.sub.33 is control-enabled only if the transition firing sequence y.sub.42.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31 has just fired; and y.sub.31 is enabled only if the transition firing sequence t.sub.32.fwdarw.s.sub.21.fwdarw.y.sub.22.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31 has just performed.

[0082] Let M=(S.sub.1, S.sub.2, S.sub.3, S.sub.4) represent the marking of the system, where S.sub.i represents the state at Step i, iN.sub.4. S.sub.i={W.sub.d(g)} representing that the d-th wafer is being processed at Step i for the g-th time, or {V.sub.d(g)} representing that the d-th virtual wafer is being processed at Step i for the g-th time, or {null} representing that Step i is idle. In this way, as above discussed, one has M.sub.0=({null}, {V.sub.3(1)}, {V.sub.2(2)}, {V.sub.1(1)}). Then, by Definition 2.4, at M.sub.0, the only enabled transition is s.sub.02. After s.sub.02 fires, R performs task sequence <t.sub.01.fwdarw.s.sub.11.fwdarw.y.sub.14.fwdarw.s.sub.42.fwdarw.t.sub.40.fwdarw.s.sub.01.fwdarw.y.sub.03.fwdarw.s.sub.32.fwdarw.t.sub.34 (according to its color).fwdarw.s.sub.41.fwdarw.y.sub.42.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31.fwdarw.y.sub.33 waiting for the completion of the wafer at Step 3.fwdarw.s.sub.32.fwdarw.t.sub.32 (according to its color).fwdarw.s.sub.21.fwdarw.y.sub.22.fwdarw.waiting for the completion of the wafer at Step 2.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31.fwdarw.y.sub.31.fwdarw.s.sub.12.fwdarw.t.sub.12.fwdarw.s.sub.21.fwdarw.y.sub.20.fwdarw.s.sub.02> such that a cycle is completed and there is no deadlock. This implies that, by the control policy given in Definition 2.4, the model is deadlock-free. It can be verified that this control policy is necessary and sufficient.

A.3 Task Time Modeling

[0083] In order to schedule the process, it is necessary to model the time taken for performing each activity. From the PN model, both transitions and places represent tasks that take time. As done in [Lee and Lee, 2006; and Wu et al, 2011], one assumes that the time taken for each activity is deterministic and known. The time taken for the robot to move from Step i to j, ij, with or without holding a wafer is assumed to be same [Kim et al., 2003] and denoted by , i.e., it takes time units to fire t.sub.ij and y.sub.ij. Note that in the revisiting process, after loading a wafer into p.sub.3/p.sub.2, the robot waits there for the completion of the wafer and it does nothing and takes no time. Similarly, the time taken for the robot to unload (firing s.sub.i2)/load (firing s.sub.i1) a wafer from/into a step is assumed to be the same as well and it is denoted by . The time taken for processing a wafer in p.sub.i, i.sub.4, is .sub.i with .sub.i>0, i0, and .sub.0=0.

[0084] Let .sub.i be the longest time for which a wafer can stay in a PM at Step i without being scrapped after being processed. Then, with wafer residency time constraints, the wafer sojourn time at Step i should be within [.sub.i, .sub.i+.sub.i], i.e., a token should stay in PM.sub.i for at least .sub.i time units and no more than .sub.i+.sub.i time units. One uses .sub.i and .sub.4 to denote the wafer sojourn time at Steps 1 and 4, respectively; and .sub.2j and .sub.3j, jN.sub.2 to denote the wafer sojourn time for the j-th visiting Steps 2 and 3, respectively. Notice that no wafer residency time constraint is imposed on Step 0. The symbols and explanation are summarized in Table I.

TABLE-US-00001 TABLE I TIME DURATIONS ASSOCIATED WITH TRANSITIONS AND PLACES. Transition Symbol or place Actions Allowed time duration s.sub.i1 T Robot loads a wafer into Step i, i.sub.4 s.sub.i2 T Robot unloads a wafer from Step i, i.sub.4 t.sub.ij T Robot moves from Steps i to j with a wafer carried, i, j.sub.4 y.sub.ij T Robot moves from Steps i to j without If ij, fixed as , carrying a wafer, i, j.sub.4 otherwise, 0 .sub.1 and p.sub.1 and A wafer is being processed and waiting [.sub.i, .sub.i + .sub.i] .sub.4 p.sub.4 P in p.sub.1 and p.sub.4 .sub.2j and p.sub.2j and p.sub.3j A wafer being processed and waiting in [.sub.i, .sub.i + .sub.i] .sub.3j P p.sub.2j and p.sub.3j, j = 1, 2 .sub.i q.sub.i2P Robot waits before unloading a wafer 0 from PM.sub.i, i.sub.4 .sub.i q.sub.i3 P Robot waits after unloading a wafer 0 from PM.sub.i, i.sub.4 .sub.i q.sub.i1 P Robot waits before loading a wafer from 0 PM.sub.i, i.sub.4

[0085] From the above analysis, for a single-arm cluster tool with wafer revisiting and residency time constraints, according to [Wu et al., 2008; and Wu and Zhou, 2010b], one has the following schedulability definition.

[0086] Definition 2.5 [Wu et al., 2008; and Wu and Zhou, 2010b]: Given the wafer sojourn time interval [.sub.i, .sub.i+.sub.i] for Step i, i custom-character .sub.4, if there exists a schedule such that whenever s.sub.i2, i{1, 4}, fires, .sub.i.sub.i.sub.i+.sub.i holds, and whenever s.sub.i2, i{2, 3}, fires, .sub.i.sub.ij.sub.i+.sub.i, +jN.sub.2, holds, then, a single-arm cluster tool with wafer revisiting and residency time constraints is schedulable.

[0087] With the PN model, one discusses the scheduling problem next.

B. SYSTEM SCHEDULING

[0088] In [Wu et al., 2011], a p-backward strategy is proposed to schedule a single-arm cluster tool for the ALD process without taking wafer residency time constrains into account. Based on the PN model, the present invention adopts this strategy to explore the schedulability and scheduling problem of a single-arm cluster tool with residency time constraints for the ALD process. If schedulable, efficient algorithm is developed to find an optimal schedule.

B.1 P-Backward Scheduling

[0089] To make the scheduling analysis, one needs to present the p-backward scheduling strategy for a single-arm cluster tool with wafer revisiting. Based on the PN model, one shows how a p-backward strategy works. Since a single-arm cluster tool with wafer revisiting is deadlock-prone, to avoid deadlock, the system must start from a proper state. One assumes that the system starts from Marking M.sub.1=({null}, {W.sub.3(1)}, {W.sub.2(2)}, {W.sub.1(1)}) and, at the same time, the robot is idle, or M.sub.1(r)=1. Notice that this marking is consistence with M.sub.0 that is set in the last section and can be reached by applying a p-backward strategy. By starting from M.sub.1 with a p-backward strategy being applied, the system evolves as follows. [0090] Step 1: Transition firing sequence .sub.1=<firing y.sub.20.fwdarw.s.sub.02.fwdarw.t.sub.01.fwdarw.s.sub.11> (the robot goes to the loadlocks from PM.sub.2.fwdarw.waits in q.sub.02.fwdarw.unloads W.sub.4 there moves to PM.sub.1.fwdarw.loads W.sub.4 into PM.sub.1) is performed such that W.sub.4(1) is put into Step 1. By doing so, it transforms the system from M.sub.1 to M.sub.2=({W.sub.4(1)}, {W.sub.3(1)}, {W.sub.2(2}, {W.sub.1(1)}). [0091] Step 2: Transition firing sequence .sub.2=<firing y.sub.14.fwdarw.waiting in q.sub.42.fwdarw.s.sub.42.fwdarw.t.sub.40.fwdarw.s.sub.01> is performed such that M.sub.3=({W.sub.4(1)}, {W.sub.3(1)}, {W.sub.2(2)}, {null}) is reached. [0092] Step 3: Transition firing sequence .sub.3=<firing y.sub.03.fwdarw.waiting in q.sub.32.fwdarw.s.sub.32.fwdarw.t.sub.34.fwdarw.s.sub.41> is performed such that M.sub.4=({W.sub.4(1)}, {W.sub.3(1)}, {null}, {W.sub.2(1)}) is reached. [0093] Step 4: Transition firing sequence .sub.4=<firing y.sub.42.fwdarw.waiting in q.sub.22.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31> is performed such that M.sub.5=({W.sub.4(1)}, {null}, {W.sub.3(1)}, {W.sub.2(1)}) is reached. [0094] Step 5: Transition firing sequence .sub.5=<firing y.sub.33.fwdarw.waiting q.sub.32.fwdarw.s.sub.32.fwdarw.t.sub.32.fwdarw.s.sub.21> is performed such that M.sub.6=({W.sub.4(1)}, {W.sub.3(2)}, {null}, {W.sub.2(1)}) is reached. [0095] Step 6: Transition firing sequence .sub.6=<firing y.sub.22.fwdarw.waiting q.sub.22.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31> is performed such that M.sub.7=({W.sub.4(1)}, {null}, {W.sub.3(2)}, {W.sub.2(1)}) is reached. [0096] Step 7: Transition firing sequence .sub.7=<firing y.sub.31.fwdarw.waiting in q.sub.12.fwdarw.s.sub.12.fwdarw.t.sub.12.fwdarw.s.sub.21> is performed such that M.sub.8=({null}, {W.sub.4(1)}, {W.sub.3(2)}, {W.sub.2(1)}) is reached.

[0097] Note that Marking M.sub.8 is equivalent to M.sub.1 in the sense of dynamic behavior of PN. Hence, by transforming M.sub.1 to M.sub.8, a cycle is completed. This is what a p-backward strategy does.

B.2 Cycle Time Analysis

[0098] With the above discussion, one can analyze the cycle time for the system. Let .sub.j be the time taken for the robot to perform .sub.j, jN.sub.7. Then, from the time modeling, one can easily obtain .sub.1=+.sub.0+++=2+2+.sub.0. Similarly, for .sub.2-7, one has .sub.2=2+2+.sub.4, .sub.3=2+2+.sub.3; .sub.4=2+2+.sub.2; .sub.5=+2+.sub.3; .sub.6=+2+.sub.2; and .sub.7=2+2+.sub.1.

[0099] Since .sub.1-7 form a robot cycle, the robot cycle time is

[00002] $\begin{matrix} = {.Math.}_{i = 1}^{7} .Math. .Math._{i} = (14 .Math. + 12 .Math. + a_{2} + a_{3}) + {.Math.}_{i = 0}^{4} .Math. .Math._{i} =_{1} +_{2} & (3.1) \end{matrix}$

where .sub.1=14+12+.sub.2+.sub.3 is the robot task time in a cycle and

[00003] $_{2} = {.Math.}_{i = 0}^{4} .Math. .Math._{i}$

is the robot waiting time in a cycle. Notice that .sub.1 is constant and known in advance and .sub.0-4 in .sub.2 should be determined by a schedule.

[0100] Based on the fact that the cycle time of the entire system must be equal to the robot cycle time [Wu. et. al., 2008], with the robot cycle time obtained, one can analyze the wafer sojourn time at each Step. It follows from the above analysis that the wafer sojourn time at Step 1 is equal to the robot cycle time minus the time taken for performing .sub.1 and the time for firing s.sub.12, t.sub.12, and s.sub.21 in .sub.7, i.e., one has

.sub.1=(2+2+.sub.0)(+2)=34.sub.0(3.2)

[0101] Similarly, for Step 4, one has

.sub.4=34.sub.3(3.3)

[0102] For Step 2, the sojourn time taken for a wafer to visit the step for the first time is different from that for a wafer to visit the step for the second time. One uses .sub.21 and .sub.22 to denote them, respectively. It follows from the above transition firing analysis that .sub.21 is equal to the robot cycle time minus the time taken for .sub.5-7 and the time taken for firing s.sub.22, t.sub.23, and s.sub.31 in .sub.4. Thus, one has

[00004] $\begin{matrix} \begin{matrix} _{21} = .Math. - (_{5} +_{6} +_{7}) - (+ +) \\ = .Math. - (+ 2 .Math. +_{3}) - (+ 2 .Math. +_{2}) - (2 .Math. + 2 .Math. +_{1}) - \\ .Math. (2 .Math. +) \\ = .Math. - 5 .Math. - 8 .Math. -_{3} -_{2} -_{1} \end{matrix} & (3.4) \end{matrix}$

[0103] When a wafer visits Step 2 for the second time, the robot loads it into PM.sub.2 and waits here for its completion. Thus, one has

.sub.22=.sub.2(3.5)

[0104] Similarly, one can calculate the wafer sojourn time for Step 3 and one has

.sub.31=.sub.3(3.6)

.sub.32=58.sub.3.sub.2.sub.2(3.7)

[0105] With wafer residency time constraints, to make a schedule feasible, the cycle time for each step should be in a permissive range. Thus, one analyzes such a range for each step as follows. For Step 1, it follows from the above analysis that, to complete a wafer requires three robot moving tasks between steps (t.sub.01, t.sub.12, and y.sub.21), two wafer unloading tasks (s.sub.02 and s.sub.12), and two wafer loading tasks (s.sub.11 and s.sub.21). Thus, with the wafer staying time in Step 1, the time taken for this process is

.sub.1=.sub.1+3+4+.sub.0(3.8)

[0106] To be feasible, one has .sub.1[.sub.1, .sub.1+.sub.1]. Hence, the permissive shortest cycle time at Step 1 is

.sub.1S=.sub.1+3+4+.sub.0(3.9)

and the permissive longest cycle time at Step 1 is

.sub.1L=.sub.1+.sub.1+3+4+.sub.0(3.10)

[0107] Similarly, the cycle time for completing a wafer at Step 4 is

.sub.4=.sub.4+3+4+.sub.3(3.11)

[0108] The permissive shortest cycle at Step 4 is

.sub.4S=.sub.4+3+4+.sub.3(3.12)

and the permissive longest cycle time at Step 4 is

.sub.4L=.sub.4+.sub.4+3+4+.sub.3(3.13)

[0109] For Step 2 in the revisiting process, one analyzes the wafer cycle as follows. By firing s.sub.21 (.sub.8=<s.sub.21 ()>), a wafer is loaded into Step 2 for processing for the first time, which is followed by transition firing sequence .sub.9=(y.sub.20.fwdarw.s.sub.O2.fwdarw.t.sub.01.fwdarw.s.sub.11.fwdarw.y.sub.14.fwdarw.s.sub.42.fwdarw.t.sub.40.fwdarw.s.sub.01.fwdarw.y.sub.03.fwdarw.s.sub.32.fwdarw.t.sub.34.fwdarw.s.sub.41.fwdarw.y.sub.42). During the time for performing .sub.9, the wafer just loaded into Step 2 is being processed. Hence, the time taken for performing .sub.9 is the wafer sojourn time for the first visiting Step 2, i.e., .sub.21. Then, transition firing sequence .sub.10=<t.sub.23 ().fwdarw.s.sub.31 ().fwdarw.y.sub.33 (0).fwdarw.waiting for the completion at Step 3 (.sub.3).fwdarw.s.sub.32 ().fwdarw.t.sub.32 ().fwdarw.s.sub.21 () (loading the wafer into Step 2 to be processed for the second time).fwdarw.y.sub.22 (0).fwdarw.waiting for the completion of the wafer at Step 2 (.sub.22).fwdarw.s.sub.22 ().fwdarw.t.sub.23().fwdarw.s.sub.31().fwdarw.y.sub.31().fwdarw.waiting in q.sub.12 (.sub.1).fwdarw.s.sub.12().fwdarw.t.sub.12 ()> is performed. By performing .sub.8-10, a cycle is completed at Step 2. Thus, the time taken for completing a wafer at Step 2 is

.sub.2=.sub.21+.sub.22+.sub.3+5+8+.sub.1(3.14)

[0110] With .sub.21[.sub.2, .sub.2+.sub.2] and .sub.22=.sub.2, the permissive shortest cycle at Step 2 is

.sub.2S=.sub.2+.sub.2+.sub.3+5+8+.sub.1=2.sub.2+.sub.3+5+8+.sub.1(3.15)

and the permissive longest cycle time at Step 2 is

.sub.2L=.sub.2+.sub.2+.sub.2+.sub.3+5+8+.sub.1=2.sub.2+.sub.2+.sub.3+5+8+.sub.1(3.16)

[0111] For Step 3, similar to Step 2, one analyzes the process as follows. One has the following transition firing sequence .sub.11=<s.sub.31 (a wafer is loaded into Step 3 to be processed for the first time, ).fwdarw.y.sub.33 (0).fwdarw.waiting for the completion of the wafer at Step 3 (.sub.31).fwdarw.s.sub.32 ().fwdarw.t.sub.32 ().fwdarw.s.sub.21 ().fwdarw.y.sub.22 (0).fwdarw.waiting for the completion of the wafer at Step 2 (.sub.2).fwdarw.s.sub.22 ().fwdarw.t.sub.23 ().fwdarw.s.sub.31 ()>. Then, transition firing sequence .sub.12=<y.sub.31.fwdarw.s.sub.12.fwdarw.t.sub.12.fwdarw.s.sub.21.fwdarw.y.sub.20.fwdarw.s.sub.02.fwdarw.t.sub.01.fwdarw.s.sub.11.fwdarw.y.sub.14.fwdarw.s.sub.42.fwdarw.t.sub.40.fwdarw.s.sub.01.fwdarw.y.sub.03> is performed. During the time for performing .sub.12, a wafer for its second visiting of Step 3 is completed. Thus, the time taken for doing so is .sub.32. Finally, to complete a cycle, transition firing sequence .sub.13=<s.sub.32 ().fwdarw.t.sub.34().fwdarw.s.sub.41().fwdarw.y.sub.42().fwdarw.waiting in q.sub.22 (.sub.2).fwdarw.s.sub.22().fwdarw.t.sub.23 ()> is performed. Thus, the cycle time for Step 3 is

.sub.3=.sub.31+.sub.32+.sub.2+5+8+.sub.2(3.17)

[0112] With .sub.31=.sub.3 and .sub.32[.sub.3, .sub.3+.sub.3], the permissive shortest cycle at Step 3 is

.sub.3S=2.sub.3+.sub.2+5+8+.sub.2(3.18)

and the permissive longest cycle time at Step 3 is

.sub.3L=2.sub.3+.sub.3+.sub.2+5+8+.sub.2(3.19)

[0113] With the above timeliness analysis, one discusses the scheduling problem next. Notice that the above derived expressions are functions of robot waiting time. Hence, the scheduling problem is to decide the robot waiting time .sub.i's to obtain a schedule if it exists.

B.3 Schedulability and Scheduling Algorithm

[0114] Let be the production cycle of the system. Then, the production rate for all the steps must be . Also, the robot cycle should be equal to the production rate too, i.e., one has

=.sub.1=.sub.2=.sub.3=.sub.4=(3.20)

[0115] Based on the above analysis, to make (3.20) hold, one needs to decide .sub.i's in .sub.2. Also, to schedule a cluster tool, the production rate should be maximized, which requires to minimize .sub.2. Furthermore, with wafer residency time constraints, schedule feasibility is essential. To be feasible, a schedule should ensure that .sub.i is in an acceptable interval. Let .sub.iL and .sub.iU denote the lower and upper bounds of .sub.i. It follows from the above analysis that when .sub.0=.sub.1=.sub.2=.sub.3=.sub.4=0, .sub.iS and .sub.iL are the lower and upper bounds of .sub.i, respectively. Thus, by removing the robot waiting time from (3.9), (3.10), (3.12), (3.13), (3.15), (3.16), (3.18), and (3.19), one has the following lower and upper bounds of .sub.i.

.sub.1L=.sub.1+3+4(3.21)

.sub.1U=.sub.1+.sub.1+3+4(3.22)

.sub.2L=2.sub.2+.sub.3+5+8(3.23)

.sub.2U=2.sub.2+.sub.2+.sub.3+5+8(3.24)

.sub.3L=2.sub.3+.sub.2+5+8(3.25)

.sub.3U=2.sub.3+.sub.3+.sub.2+5+8(3.26)

.sub.4L=.sub.4+3+4(3.27)

.sub.4U=.sub.4+.sub.4+3+4(3.28)

[0116] Let .sub.Lmax=max {.sub.iL,iN.sub.4} and .sub.Umin=min{.sub.iU, iN.sub.4}, one has the following lemma.

[0117] Lemma1: If .sub.1>.sub.Umin, the system is not schedulable.

[0118] Proof:

[0119] It follows from the above discussion that =.sub.1. When =.sub.1, one has .sub.0.sub.1=.sub.2=.sub.3=.sub.4=0. In this case, if .sub.Umin=.sub.kU, k{1, 4}, by (3.2) and (3.3), one has .sub.k=.sub.134>.sub.kU34=.sub.k+.sub.k+3+434=.sub.k+.sub.k. This implies that the wafer residency time constraints are violated for Step k, k{1, 4}. If .sub.Umin=.sub.2U, by (3.4), one has .sub.21=.sub.158.sub.3.sub.2>.sub.2U58.sub.3.sub.2=2.sub.2+.sub.2+.sub.3+5+858.sub.3.sub.2=.sub.2+.sub.2. Hence, the wafer residency time constraints are violated for Step 2. If .sub.Umin=.sub.3U, by (3.4), one has .sub.32=.sub.158.sub.3.sub.2>.sub.3U58.sub.3.sub.2=2.sub.3+.sub.3+.sub.2+5+858.sub.3.sub.2=.sub.3+.sub.3. The wafer residency time constraints are violated for Step 3.

[00005] $_{2} = -_{1} = {.Math.}_{i = 0}^{4} .Math. .Math._{i}$

[0120] Then, one discusses the case when >.sub.1. In this case, one has and .sub.i.sub.1, i.sub.4. If .sub.Umin=.sub.kU, k{1, 4}, by (3.2) and (3.3), one has .sub.k=34.sub.k-134(.sub.1.sub.1)=.sub.134>.sub.kU34=.sub.k+.sub.k+3+434=.sub.k+.sub.k. The residency time constraints are violated for Step k, k{1, 4}. If .sub.Umin=.sub.2U, by (3.4), one has .sub.21=58.sub.3.sub.2.sub.158.sub.3.sub.2(.sub.1)=.sub.158.sub.3.sub.2>.sub.2U58.sub.3.sub.2=2.sub.2+.sub.3+5+858.sub.3.sub.2=.sub.2+.sub.2. The residency time constraints are violated for Step 2. If .sub.Umin=.sub.3U, by (3.4), one has .sub.32=58.sub.3.sub.2.sub.258.sub.3.sub.2(.sub.1)=.sub.158.sub.3.sub.2>.sub.3U58.sub.3.sub.2=2.sub.3+.sub.2+5+858.sub.3.sub.2=.sub.3+.sub.3. The residency time constraints are violated for Step 3. Thus, in any case, no matter how .sub.i's are set, a feasible schedule cannot be found.

[0121] Next one discusses the schedulability and scheduling problem when .sub.1<.sub.Umin. One has the following two cases.

[.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U]{circle around (1)}

[.sub.1L,.sub.1U][.sub.2L,.sub.2U][.sub.3L,.sub.3U][.sub.4L,.sub.4U]={circle around (2)}

[0122] For Case {circle around (1)}, one has the following lemmas.

[0123] Lemma 2: If .sub.1<.sub.Lmax, let .sub.0=.sub.1=.sub.2=.sub.3=0 and .sub.4=.sub.Lmax.sub.1, the obtained schedule is feasible.

[0124] Proof By the obtained schedule, the cycle time for the tool is ==.sub.Lmax. In this case, one has .sub.iL==.sub.Lmax.sub.iU, iN.sub.4. Then, for Step i, i{1, 4}, by (3.2) and (3.3), .sub.i=.sub.Lmax34.sub.iL34=.sub.i and .sub.i=.sub.Lmax34.sub.iU34=.sub.i+.sub.i, or the wafer residency time constraints are satisfied. For Step 2, by (3.4), .sub.21=.sub.Lmax58.sub.3.sub.2.sub.2L58.sub.3.sub.2=.sub.2 and .sub.21.sub.Lmax58.sub.3.sub.2.sub.2U58.sub.3.sub.2=.sub.2+.sub.2. By (3.5), .sub.22=.sub.2. Hence, the wafer residency time constraints are satisfied for Step 2. For Step 3, by (3.6), .sub.31=.sub.3. By (3.7), .sub.32=.sub.Lmax58.sub.3.sub.2>.sub.3L58.sub.3.sub.2=.sub.3 and .sub.32=.sub.Lmax58.sub.3.sub.2.sub.3U58.sub.3.sub.2=.sub.3+.sub.3. Hence, the wafer residency time constraints are satisfied for Step 3. Therefore, the obtained schedule is feasible and the system is schedulable.

[0125] Lemma 3: If .sub.Lmax.sub.1.sub.Umin, set .sub.0.sub.2=.sub.3=.sub.4=0, the obtained schedule is feasible.

[0126] Proof:

[0127] In this case, the cycle time ==.sub.1. Then, for Step i, i{1, 4}, one has .sub.i=.sub.134.sub.iL34=.sub.i and .sub.i=.sub.134.sub.iU34=.sub.i+.sub.i. For Step 2, one has .sub.21=.sub.158.sub.3.sub.2.sub.2L58.sub.3.sub.2=.sub.2 and .sub.21.sub.158.sub.3.sub.2.sub.2U58.sub.3.sub.2=.sub.2+.sub.2, and .sub.22=.sub.2. For Step 3, one has .sub.31=.sub.3, and .sub.32=.sub.158.sub.3.sub.2.sub.3L58.sub.3.sub.2=.sub.3 and .sub.32.sub.158.sub.3.sub.2.sub.3U58.sub.3.sub.2=.sub.3+.sub.3. Thus, for all the steps, the wafer residency time constraints are satisfied and the obtained schedule is feasible.

[0128] For Case {circle around (2)}, there must exist at least one i custom-character .sub.4 such that .sub.iU<.sub.Lmax. Let E={i|.sub.iU<.sub.Lmax, i.sub.4} and F=.sub.4\E. Then, for Step i, i.sub.4, one sets .sub.i-1 as follows.

[00006] $\begin{matrix} _{i - 1} = {\begin{matrix} 0, & i F \\ _{Lmax} -_{i} -_{i} - 4 .Math. - 3 .Math., & i E .Math. {1, 4} \\ _{Lmax} - 2 .Math._{2} -_{2} -_{3} - 5 .Math. - 8 .Math., & i E .Math. {2} \\ _{Lmax} - 2 .Math._{3} -_{3} -_{2} - 5 .Math. - 8 .Math., & i E .Math. {3} \end{matrix} & (3.29) \end{matrix}$

Then, one has the following lemma.

[0129] Lemma 4: For the case of [.sub.1,L, .sub.1U][.sub.2L, .sub.2U][.sub.3L, .sub.3U]#[.sub.4L, .sub.4U]=, let

[00007] $_{4} =_{Lmax} -_{1} - {.Math.}_{i = 0}^{3} .Math. .Math._{i},$

where .sub.i, i.sub.3 is determined via (3.29). Then, if .sub.40, the obtained schedule is feasible, otherwise the system is not schedulable.

[0130] Proof:

[0131] One first shows that when .sub.40, the obtained schedule is feasible. It follows from (3.29) and

[00008] $_{4} =_{Lmax} -_{1} - {.Math.}_{i = 0}^{3} .Math. .Math._{i}$

that one has ==.sub.Lmax. Then, for Step i, i{1, 4}, if iF, .sub.i=.sub.Lmax34.sub.iL34=.sub.i and .sub.i=.sub.Lmax34.sub.iU34=.sub.i+.sub.i. If iE, .sub.i=.sub.Lmax34(.sub.Lmax.sub.i.sub.i43)=.sub.i+.sub.i. For Step 2, one has .sub.22=.sub.2. If 2F, .sub.21=.sub.Lmax58.sub.3.sub.2.sub.2L58.sub.3.sub.2=.sub.2 and .sub.21=.sub.Lmax58.sub.3.sub.2<.sub.2U58.sub.3.sub.2=.sub.2+.sub.2. If 2E, .sub.21=.sub.Lmax58.sub.3.sub.2(.sub.Lmax.sub.2.sub.2.sub.2.sub.343)=.sub.2+.sub.2. For Step 3, one has .sub.31=.sub.3. If 3F, .sub.32=.sub.Lmax58.sub.3.sub.2.sub.3L58.sub.3.sub.2=.sub.3 and .sub.32=.sub.Lmax58.sub.3.sub.2<.sub.3U58.sub.3.sub.2=.sub.3+.sub.3. If 3E, .sub.32=.sub.Lmax58.sub.3.sub.2(.sub.Lmax.sub.3.sub.3.sub.2.sub.343)=.sub.3+.sub.3. Thus, the wafer residency time constraints are satisfied for all the steps and the obtained schedule are feasible.

[0132] Now one shows that the system is not schedulable if .sub.4<0. When .sub.4<0, the obtained schedule is meaningless, or one cannot find a feasible schedule such that ==.sub.Lmax. Then, there are two choices: (1) <.sub.Lmax and (2) >.sub.Lmax.

[0133] If <.sub.Lmax, one assumes that .sub.iL=.sub.Lmax, i custom-character .sub.4. If i{1, 4}, for Step i, one has .sub.i=34.sub.i-1<.sub.Lmax34.sub.i-1=.sub.iL34.sub.i-1<.sub.i. If .sub.2L=.sub.Lmax, one has .sub.21=58.sub.3.sub.2.sub.1<.sub.Lmax58.sub.3.sub.2.sub.1=.sub.2L34.sub.1.sub.2. If .sub.3L=.sub.Lmax, one has .sub.32=58.sub.3.sub.2.sub.2<.sub.Lmax58.sub.3.sub.2.sub.2=.sub.3L34.sub.2.sub.3. This implies that the wafer residency time constraints are violated for at least one step. Thus, a feasible schedule cannot be found, it is not schedulable.

[0134] If >.sub.Lmax, one assumes that =.sub.Lmax+ and .sub.i-1=.sub.i-1+.sub.i-1, where .sub.i-1 is obtained via (3.29), iE. Then, according to (3.1), one has

[00009] $\begin{matrix} {.Math.}_{k = 1}^{4} .Math. .Math. (_{k - 1} + .Math. .Math._{k - 1}) -_{1} = (_{Lmax} -_{1}) + .Math. .Math. & (3.30) \end{matrix}$

[0135] If .sub.iL=.sub.Lmax, iE, and i{1, 4}, one has .sub.Lmax+=.sub.i+.sub.i+4+3+.sub.i-1+.sub.i-1=.sub.Lmax+.sub.i-1. If .sub.iL=.sub.Lmax, iE, and i{2, 3}, one has .sub.Lmax+=.sub.i+.sub.i+8+5+.sub.2+.sub.3+.sub.i-1+.sub.i-1=.sub.Lmax+.sub.i-1. Thus, one has =.sub.i-1=.sub.Lmax and iE. Since .sub.4<0,

[00010] $\begin{matrix} {.Math.}_{k = 1}^{4} .Math. .Math._{k - 1} >_{Lmax} -_{1} .Math. .Math. must .Math. .Math. hold, .Math. leading .Math. .Math. to .Math. .Math. the .Math. .Math. following .Math. .Math. result .Math. .Math. .Math. {.Math.}_{k = 1}^{4} .Math. .Math. (_{k - 1} + .Math. .Math._{k - 1}) -_{1} > (_{Lmax} -_{1}) + & (3.31) \end{matrix}$

This contradicts to (3.30), i.e., a feasible schedule cannot be found.

[0136] Up to now, one presents the conditions under which a feasible schedule can be found for a single-cluster tool with wafer revisiting and residency time constraints. Notice that, by above analysis, for each case, one presents a schedule, then check its feasibility. Thus, if a feasible schedule exists, a feasible schedule can be found by simply setting the robot waiting time. In summary, an algorithm is presented as follows to find a schedule if it exists.

[0137] Algorithm 1: Find a feasible schedule for a single-am cluster tool with wafer residency time constraints for an ALD process if it exists as [0138] 1) If .sub.1<.sub.Lmax, set .sub.0=.sub.1=.sub.2=.sub.3=0 and .sub.4=.sub.Lmax.sub.1 to obtain a feasible schedule; [0139] 2) If .sub.Lmax.sub.1.sub.Umin, set .sub.0=.sub.1=.sub.2=.sub.3=.sub.4=0 to obtain a feasible schedule; and [0140] 3) If [.sub.1L, .sub.1U][.sub.2L, .sub.2U][.sub.3L, .sub.3U][.sub.4L, .sub.4U]=, set .sub.i, i.sub.3, by using (3.29) and .sub.4=

[00011] $_{Lmax} -_{1} - {.Math.}_{i = 0}^{3} .Math. .Math._{i} .$

Then, if .sub.40, a feasible schedule is obtained.

[0141] By Algorithm 1, only simple calculation is needed such that the proposed method is computationally very efficient. Another issue for scheduling problem is its productivity. The following theorem shows the optimality of the proposed method.

[0142] Theorem 1: If the system is schedulable, the obtained schedule by methods given in Lemmas 2 to 4 is optimal in terms of productivity.

[0143] Proof Let .sub.iL=.sub.Lmax, i custom-character .sub.4. According to Lemmas 2 and 4, if the system is scheduled such that =<.sub.Lmax, from (3.2)-(3.7), one has .sub.i<.sub.i, if .sub.iL=.sub.Lmax and i{1, 4}; .sub.21<.sub.2, if .sub.2L=.sub.Lmax, and .sub.32<.sub.3, if .sub.3L=.sub.Lmax. In other words, the obtained schedule is not feasible. Thus, by the algorithms given in Lemmas 2 and 4, the obtained schedule has a minimal cycle time, or maximal productivity.

C. ILLUSTRATIVE EXAMPLES

[0144] This section uses examples with wafer flow pattern (PM.sub.1, (PM.sub.2, PM.sub.3).sup.2, PM.sub.4) to show the proposed method.

Example 1

[0145] The wafer processing time at PM.sub.1-4 is .sub.1=120 s, .sub.2=40 s, .sub.3=45 s, and .sub.4=125 s, respectively. After a wafer is completed, it can stay in PM.sub.1-4 for at most .sub.1=30 s, .sub.2=20 s, .sub.3=20 s, and .sub.4=30 s, respectively. The robot task time is ==3 s.

[0146] For this example, one has .sub.1L=141 s, .sub.1U=171 s, .sub.2L=164 s, .sub.2U=184 s, .sub.3L=169 s, .sub.3U=189 s, .sub.4L=146 s, .sub.1U=176 s, .sub.Lmax=169 s, and .sub.1=163 s. One can check that [.sub.1L, .sub.1U][.sub.2L, .sub.2U][.sub.3L, .sub.3U][.sub.4L, .sub.4U] and .sub.1.sub.Lmax. Then, according to Lemma 2, one sets .sub.0=.sub.1=.sub.2=.sub.3=0 and .sub.4=.sub.Lmax.sub.1=6 s and a feasible schedule is obtained with cycle time ==.sub.Lmax=169 s.

Example 2

[0147] The wafer processing time at PM.sub.1-4 is .sub.1=95 s, .sub.2=35 s, .sub.3=30 s, and .sub.4=100 s, respectively. After a wafer is completed, it can stay in PM.sub.1-4 for at most .sub.1=30 s, .sub.2=20 s, .sub.3=20 s, and .sub.4=30 s respectively. The robot task time is ==3 s.

[0148] One has .sub.1L=116 s, .sub.1U=146 s, .sub.2L=139 s, .sub.2U=159 s, .sub.3L=134 s, .sub.3U=154 s, .sub.4L=121 s, .sub.4U=151 s, .sub.Lmax=139 s, and .sub.1=143 s. Thus, [.sub.1L, .sub.1U][.sub.2L, .sub.2U][.sub.3L, .sub.3U][.sub.4L, .sub.4U]# and .sub.Lmax.sub.1.sub.Umin hold, and it is schedulable. Then, according to the algorithm given in Lemma 3, one sets .sub.0=.sub.1=.sub.2=.sub.3=.sub.4=0 s and a feasible schedule is obtained with cycle time ==.sub.1=143 s.

Example 3

[0149] The wafer processing time at PM.sub.1-4 is .sub.1=115 s, .sub.2=40 s, .sub.3=45 s, and .sub.4=125 s, respectively. After a wafer is completed, it can stay at PM.sub.1-4 for at most .sub.1=30 s, .sub.2=20 s, .sub.3=20 s, and .sub.4=30 s, respectively. The robot task time is ==3 s.

[0150] For this example, one has .sub.1L=136 s, .sub.1U=166 s, .sub.2L=164 s, .sub.2U=184 s, .sub.3L=169 s, .sub.3U=189 s, .sub.4L=146 s, .sub.4U=176 s, .sub.Lmax=169 s, and .sub.1=163 s. It can be checked that [.sub.1L, .sub.1U][.sub.2L, .sub.2U][.sub.3L, .sub.3U][.sub.4L]= and E={1}. According to Lemma 4, one sets .sub.0=3, .sub.1=.sub.2=.sub.3=0, and .sub.4=3. Since .sub.4>0, the system is schedulable and the obtained schedule is feasible with cycle time ==.sub.Lmax=169 s. Based on the PN model, one shows how this schedule is implemented as follows. According to the system modeling, one has M.sub.0=({null}, {V.sub.3(1)}, {V.sub.2(2)}, {V.sub.1(1)}) and one assumes the starting time is .sub.0=0. Then, the system evolves as follows.

[0151] 1) From .sub.0=0 to .sub.1=15, task sequence <y.sub.20.fwdarw.robot waits in q.sub.02.fwdarw.s.sub.02.fwdarw.t.sub.01.fwdarw.s.sub.11> such that M.sub.1=({W.sub.1(1)}, {W.sub.0(1)}, {W.sub.0(2)}, {W.sub.0(1)}) is reached. [0152] 2) From .sub.1=15 to .sub.2=30, task sequence <y.sub.14.fwdarw.robot waits in q.sub.42.fwdarw.s.sub.42.fwdarw.t.sub.40.fwdarw.s.sub.01> such that M.sub.2=({W.sub.1(1)}, {V.sub.0(1)}, {V.sub.0(2)}, {null}) is reached. [0153] 3) From .sub.2=30 to .sub.3=42, task sequence <y.sub.03.fwdarw.robot waits in q.sub.32.fwdarw.s.sub.32.fwdarw.t.sub.34.fwdarw.s.sub.41> such that M.sub.3=({W.sub.1(1)}, {V.sub.0(1)}, {null}, {V.sub.0(1)}) is reached. [0154] 4) From .sub.3=42 to .sub.4=54, task sequence <y.sub.42.fwdarw.robot waits in q.sub.22.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31> such that M.sub.4=({W.sub.1(1)}, {null}, {V.sub.0(1)}, {V.sub.0(1)}) is reached. [0155] 5) From .sub.4=54 to .sub.5=108, task sequence <y.sub.33.fwdarw.robot waits at step 3.fwdarw.s.sub.32.fwdarw.t.sub.32.fwdarw.s.sub.21> such that M.sub.5=({W.sub.1(1)}, {V.sub.0(2)}, {null}, {V.sub.0(1)}) is reached. [0156] 6) From .sub.5=108 to .sub.6=157, task sequence <y.sub.22.fwdarw.robot waits at step 2.fwdarw.s.sub.22.fwdarw.t.sub.23.fwdarw.s.sub.31> such that M.sub.6=({W.sub.1(1)}, {null}, {V.sub.0(2)}, {V.sub.0(1)}) is reached. [0157] 7) From .sub.6=157 to .sub.7=169, task sequence <y.sub.31.fwdarw.robot waits in q.sub.12.fwdarw.s.sub.12.fwdarw.t.sub.12.fwdarw.s.sub.21> such that M.sub.7=({null}, {W.sub.1(1)}, {V.sub.0(2)}, {V.sub.0(1)}) is reached.

[0158] Through the above sequence, a cycle of the system is formed, which demonstrates that the cycle time is 169 s.

[0159] The embodiments disclosed herein may be implemented using general purpose or specialized computing devices, computer processors, or electronic circuitries including but not limited to digital signal processors (DSP), application specific integrated circuits (ASIC), field programmable gate arrays (FPGA), and other programmable logic devices configured or programmed according to the teachings of the present disclosure. Computer instructions or software codes running in the general purpose or specialized computing devices, computer processors, or programmable logic devices can readily be prepared by practitioners skilled in the software or electronic art based on the teachings of the present disclosure.

[0160] In some embodiments, the present invention includes computer storage media having computer instructions or software codes stored therein which can be used to program computers or microprocessors to perform any of the processes of the present invention. The storage media can include, but is not limited to, floppy disks, optical discs, Blu-ray Disc, DVD, CD-ROMs, and magneto-optical disks, ROMs, RAMs, flash memory devices, or any type of media or devices suitable for storing instructions, codes, and/or data.

[0161] The present invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The present embodiment is therefore to be considered in all respects as illustrative and not restrictive. The scope of the invention is indicated by the appended claims rather than by the foregoing description, and all changes that come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein.

Petri Net-based Scheduling of Time Constrained Single-arm Cluster Tools with Wafer Revisiting

Inventors

Cpc classification

Classification Explorer

B25J9/1682

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G05B2219/32265

PHYSICS

Classification Explorer

G05B19/402

PHYSICS

Classification Explorer

Y10S901/02

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

Y10S901/41

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

G05B2219/32376

PHYSICS

Classification Explorer

G05B2219/45031

PHYSICS

Classification Explorer

G05B2219/32373

PHYSICS

Classification Explorer

G05B2219/40238

PHYSICS

Classification Explorer

G05B19/41865

PHYSICS

Classification Explorer

H01L21/67276

ELECTRICITY

International classification

Classification Explorer

G05B19/402

PHYSICS

Classification Explorer

B25J9/16

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B25J9/00

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B25J11/00

PERFORMING OPERATIONS; TRANSPORTING

Abstract

Claims

Description