Petri net-based optimal one-wafer cyclic scheduling of treelike hybrid multi-cluster tools

Abstract

Since single and dual-arm tools behave differently, it is difficult to coordinate their activities in a hybrid multi-cluster tool that is composed of both single- and dual-arm tools. Aiming at finding an optimal one-wafer cyclic schedule for a treelike hybrid multi-cluster tool whose bottleneck tool is process-bound, the present work extends a resource-oriented Petri net to model such system. By the developed Petri net model, to find a one-wafer cyclic schedule is to determine robot waiting times. By doing so, it is shown that, for any treelike hybrid multi-cluster tool whose bottleneck tool is process-bound, there is always a one-wafer cyclic schedule. Then, computationally efficient algorithms are developed to obtain the minimal cycle time and the optimal one-wafer cyclic schedule. Examples are given to illustrate the developed method.

Claims

1. A computer-implemented method for scheduling a treelike hybrid K-cluster tool with a plurality of branches, sub-trees (ST) and extended sub-trees (EST) to generate a one-wafer cyclic schedule, the treelike hybrid K-cluster tool having K single-cluster tools denoted as C.sub.1, C.sub.2, . . . , C.sub.K, with C.sub.1 being a head tool of the treelike hybrid K-cluster tool, the single-cluster tool C.sub.k, k.sub.K, having a robot R.sub.k for wafer handling, being the cycle time for all the branches as iteratively calculated with a maximum fundamental period being a given initial cycle time, where the one-wafer cyclic schedule of the treelike hybrid K-cluster tool cannot be found with the given initial cycle time, the method comprising: determining fundamental periods (FP) .sub.1, .sub.2, . . . , .sub.K for the single-cluster tools C.sub.1, C.sub.2, . . . , C.sub.K and applying a maximum fundamental period =max{.sub.1, .sub.2, . . . , .sub.K} as the given initial cycle time ; determining a one-wafer cyclic schedule for each of the ST (ST.sub.i) by increasing the cycle time by , wherein the ST comprises one or more branches; wherein the determining of one-wafer cyclic schedule for each of the ST comprises: determining the k such that C.sub.k is an upstream adjacent tool of C.sub.j; determining a one-wafer cyclic schedule for each of the EST (EST.sub.j) based on a generating algorithm by increasing the cycle time by if C.sub.k is not a fork tool, wherein the EST comprises one or more ST and the generating algorithm further comprises: (S1.1) determining, responsive for finding that k.Math.F and A.sub.i(n[i])0, a time increment m according to:
.sub.m=A.sub.m(n[m])/.sub.pS.sub.mB[p] if m>i and ${}_m={}_i=\{\begin{array}{cc}{}_i\left(S,S\right)-A_{i\left(n\left[i\right]\right)}& \mathrm{for}\mathrm{Condition}1,\\ \frac{{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}& \mathrm{for}\mathrm{Condition}2,\\ \frac{{}_i\left(D,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}& \mathrm{for}\mathrm{Condition}3,\end{array}\mathrm{if}m=i,$ (S1.2) computing, responsive for finding that =min{.sub.p|pS.sub.i}=.sub.i, (S1.2.1) in EST.sub.i or B.sub.i, for p.Math.S.sub.i: responsive for finding that p.Math.L, .sub.p((b[p].sub._.sub.1)1)=A.sub.p((b[p].sub._.sub.1)1)+; responsive for finding that pL, .sub.p0=A.sub.p0+; (S1.2.2) in EST.sub.i or B.sub.i, responsive for finding that pS.sub.i and p.Math.F: further responsive for finding that pL, .sub.pj=A.sub.pj+Y for jD[p], or for j.sub.n[p]\{n[p]}; further responsive for finding that pL, .sub.p((b[p].sub._.sub.1)1=A.sub.p((b[p].sub._.sub.1)1+.sub.qS.sub.p.sub.\{p}B[q]A.sub.i(n[i])/(.sub.pS.sub.iB[p])+, or .sub.p0=A.sub.p0+; and .sub.p(n[p])=A.sub.p(n[p]).sub.qS.sub.pB[q]Y; (S1.2.3) in EST.sub.i, responsive for finding that pS.sub.i and pF: ${}_{\mathrm{pj}}=A_{\mathrm{pj}}+Y,jD\left[p\right];$ ${}_{p\left(\left(b\left[p\right]\_1\right)-1\right)}=A_{p\left(\left(b\left[p\right]\_1\right)-1\right)}+\underset{q{S}_{p\_1}}{.Math.}B\left[q\right]Y+;$ ${}_{p\left(\left(b\left[p\right]\_d\right)-1\right)}=A_{p\left(\left(b\left[p\right]\_d\right)-1\right)}+\left(\underset{q{S}_{p\_d}}{.Math.}B\left[q\right]+1\right)Y,d\left\{2,3,\mathrm{.Math.},f\left[p\right]\right\};\mathrm{and}$ ${}_{p\left(n\left[p\right]\right)}=A_{p\left(n\left[p\right]\right)}-\underset{q{S}_p}{.Math.}B\left[q\right]Y;$ (S1.3) responsive for finding that =min{.sub.p|pS.sub.i}=.sub.f.sub.i, performing the Steps (S1.2.1), (S1.2.2) and (S1.2.3) with Y=.sub.f, followed by repeating the Steps (S1.1), (S1.2) and (S1.3); and the generating algorithm is implemented by a wafer handling robot in a wafer processing device in a semiconductor manufacturing industry for determining the one-wafer cyclic schedule for each of the EST, an optimized schedule is obtained with an optimal cycle time for the treelike hybrid K-cluster tool; where: Condition 1 is that $0<A_{i\left(n\left[i\right]\right)}\frac{{.Math.}_{p{S}_i}B\left[p\right]{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}$ and an S-S case is considered, Condition 2 is that $A_{\left(i+1\right)\left(n\left[i+1\right]\right)}\frac{{.Math.}_{p{S}_i}B\left[p\right]{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}$ and the S-S case is considered, Condition 3 is that a D-S case is considered; Y=.sub.i(S,S)A.sub.(i(n[i]) when the Condition 1 is satisfied; $Y=\frac{{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}$ when the Condition 2 is satisfied; $Y=\frac{{}_i\left(D,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}$ when the Condition 3 is satisfied; L denotes an index set of leaf tools in the treelike hybrid K-cluster tool; F denotes an index set of fork tools in the treelike hybrid K-cluster tool; ST.sub.j denotes a ST with C.sub.j being a fork tool and a root node of the ST, and EST.sub.i is an EST of ST.sub.j with none of C.sub.i, C.sub.i+1, . . . , C.sub.j2, C.sub.j1 being a fork tool; B.sub.i, starting from C.sub.i and ends at C.sub.m, mL, denotes a linear multi-cluster tool in the treelike K-cluster tool; .sub.ij is a robot waiting time of R.sub.i at Step j as obtained after the cycle time is increased by , j.sub.n[i], n[i] being an index of a last processing step of C.sub.i; A.sub.kj is a robot waiting time at Step j for R.sub.k as determined for the cycle time ; S.sub.i is a set of single-cluster tools connected to C.sub.i and selected from the K single-cluster tools; B[k]=n[k]1; b[p]_d is an index denoting a d-th outgoing module of C.sub.p; D[p] be a set of processing steps in C.sub.p; f[i], 1f[i]n[i], denotes the number of outgoing modules in C.sub.i, i.Math.L; .sub.i+1(S,S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+4.sub.i+3.sub.i when C.sub.i and C.sub.i+1 are S-S, and .sub.i+1(D, S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+.sub.i, when C.sub.i and C.sub.i+1 are D-S; .sub.i is a time taken by R.sub.i to load or unload a wafer in C.sub.i; .sub.i is a time taken by R.sub.i to move between process modules of C.sub.i for transiting from one processing step to another; .sub.L={1, 2, . . . , L} for a positive integer L; and .sub.L=N.sub.L{0}.

2. The method of claim 1, wherein the generating algorithm further comprises the steps of: (S2) responsive for finding the optimal cycle time for EST.sub.k or ST.sub.k, k.Math.F and A.sub.i(n[i])=0, where the one-wafer cyclic schedule cannot be found with the given initial cycle time, performing: updating with a value computed by +.sub.i=+.sub.i(S, S) for S-S case, or +.sub.i=+.sub.i(D, S) for D-S case; and based on the updated value of , recomputing the robot waiting times for the robots in EST.sub.k or ST.sub.k, so that the part of the schedule for EST.sub.k or ST.sub.k is generated and thereby the performing of the generating algorithm is completed; (S3) responsive for finding the optimal cycle time for EST.sub.k or ST.sub.k, and kF, where the one-wafer cyclic schedule cannot be found with the given initial cycle time, performing Steps (S3.1), (S3.2) and (S3.3); (S3.1) finding the optimal cycle time +.sub.q for C.sub.k with EST.sub.k.sub._.sub.q or ST.sub.k.sub._.sub.q, q.sub.f[k], by performing the Steps (S.1) and (S.2); (S3.2) updating with a value computed by +max{.sub.1, .sub.2, . . . , .sub.f[k]}; and (S3.3) finding the part of the schedule for ST.sub.k by recomputing the robot waiting times with the updated cycle time ; where: EST.sub.k.sub._.sub.q or ST.sub.k.sub._.sub.q is the EST or the ST having the single-cluster tool C.sub.i and a branch thereof, B.sub.i.sub._.sub.q.

3. The method of claim 2, further comprising: identifying, in the treelike hybrid K-cluster tool, ST.sub.j with j=max.sub.lF{l}, and one or more ESTs of ST.sub.j, the one or more ESTs being denoted as EST.sub.j1, EST.sub.j2 down to EST.sub.i such that an upstream adjacent tool of C.sub.i is a fork tool; determining a first part of the schedule for ST.sub.j by performing the generating algorithm; determining a second part of the schedule for EST.sub.j1 based on the first part of the schedule; and repeating determining one part of the schedule EST.sub.jm based on a determined part of the schedule for EST.sub.jm+1 until the one or more ESTs are scheduled.

4. The method of claim 2, wherein R.sub.k is single-arm or double-arm.

5. The method of claim 1, further comprising: identifying, in the treelike hybrid K-cluster tool, ST.sub.j with j=max.sub.lF{l}, and one or more ESTs of ST.sub.j, the one or more ESTs being denoted as EST.sub.j1, EST.sub.j2 down to EST.sub.i such that an upstream adjacent tool of C.sub.i is a fork tool; determining a first part of the schedule for ST.sub.j by performing the generating algorithm; determining a second part of the schedule for EST.sub.j1 based on the first part of the schedule; repeating determining one part of the schedule EST.sub.jm based on a determined part of the schedule for EST.sub.jm+1 until the one or more ESTs are scheduled.

6. The method of claim 1, wherein R.sub.k is single-arm or double-arm.

7. The method of claim 1, wherein the one-wafer cyclic schedule cannot achieve a lower bound of cycle time.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 depicts a treelike hybrid 9-cluster tool as an example for illustration.

(2) FIG. 2 depicts a PN model for a single-arm tool C.sub.i as an illustrative example.

(3) FIG. 3 depicts, as an example, a PN model for a dual-arm tool C.sub.i.

(4) FIG. 4 depicts examples of a PN model for the BM between C.sub.k and C.sub.i for: (a) a D-D case; (b) a S-D case, (c) a D-S case; and (d) a S-S case.

(5) FIG. 5 provides an illustration of the proof of Theorem 2.

(6) FIG. 6 depicts a Gantt chart for the optimal schedule of Example 1.

(7) FIG. 7 depicts a Gantt chart for the optimal schedule of Example 2.

DETAILED DESCRIPTION

(8) Based on the results obtained in [Yang et al., 2015], the present work confirms that an O.sup.2CS exists for a treelike hybrid multi-cluster tool. To do so, a Petri net (PN) model is developed to describe the dynamic behavior of the system. By this model, one shows that there is always a one-wafer cyclic schedule. Then, algorithms are designed to obtain the O.sup.2CS by setting the robot waiting time. The method as disclosed herein is shown to be computationally efficient.

(9) Hereinafter, the notation .sub.K, K being a positive integer, denotes a set containing positive integers from 1 to K, i.e. .sub.K={1, 2, . . . , K}. Let .sub.K={0}.sub.K.

A. Petri Net Modeling

(10) By following Chan et al. [2011a and b], for the system, one assumes that: 1) the capacity of a BM is one and has no processing function; 2) only one PM is configured for each step, that is, there is no parallel module, and only one wafer can be processed in a PM at a time; 3) only one type of wafers that have the identical recipe is processed, and they visit a PM only once except entering a BM at least twice; 4) the activity time is a known constant; and 5) in each individual tool except the fork and leaf (to be defined later) tool, besides BM(s), there is at least one PM. The fork tool may have no PM and the leaf tool has at least two PMs.

(11) Let C.sub.i, i.sub.K, denote the i-th cluster tool, where C.sub.1 that has two loadlocks is called the head tool; C.sub.i, i1, is called a leaf tool if it connects to only one tool; and if C.sub.i, i.sub.K, connects to at least three adjacent tools, it is called a fork tool. Denote R.sub.i as the robot in C.sub.i. As shown in FIG. 1, C.sub.3, C.sub.7, and C.sub.9 are leaf tools, while C.sub.2 and C.sub.5 are fork ones. Let L={i|C.sub.i is a leaf tool} denote the index set of leaf tools. The tools are numbered such that, for any two adjacent tools C.sub.k and C.sub.i, k.Math.L and i{1}, with C.sub.k/C.sub.i being the upstream/downstream one, one has i>k [Chan et al. 2011b]. However, k and i may not be in a consecutive order.

(12) A BM connecting C.sub.k and C.sub.i is seen as the outgoing module (OM) for C.sub.k and the incoming module (IM) for C.sub.i, respectively, and this IM is numbered as the Step 0 for C.sub.i. Let n[i] be the index for the last step in C.sub.i, i.sub.K. Then, there are n[i]+1 steps in C.sub.i, including the OM(s) and IM(s). Let f[i], 1f[i]n[i], denote the number of OM(s) in C.sub.i, i.Math.L. If f[i]>1, C.sub.i is a fork tool; otherwise if f[i]=1, it is not. Let PS.sub.ij denote Step j (except the BM(s)) in C.sub.i, i.sub.K and j.sub.n[i], with PS.sub.10 denoting the loadlocks in C.sub.1. Further, let PS.sub.i(b[i].sub._.sub.1), PS.sub.i(b[i].sub._.sub.2), . . . , and PS.sub.i(b[i].sub._.sub.f[i]) with b[i]_1<b[i]_2< . . . <b[i]_f[i], denote the OM(s). Note that b[i]_1, b[i]_2, . . . and b[i]_f[i] are not necessary in a consecutive order, in other words, b[i]_2=b[i]_1+1 may not hold. The IM for C.sub.i is denoted as PS.sub.i0. Then, the n[i]+1 steps in C.sub.i are denoted as PS.sub.i0, PS.sub.i1, . . . , PS.sub.i(b[i].sub._.sub.1), . . . , PS.sub.i(b[i].sub._.sub.2), . . . , PS.sub.i(n[i]), respectively. Notice that b[i]_1=1 if it is Step 1 and b[i]_f[i]=n[i] if it is the last step. By this way, the route of a wafer in FIG. 1 can be denoted as: PS.sub.10.fwdarw.PS.sub.11.fwdarw. . . . .fwdarw.PS.sub.1(b[1].sub._.sub.1) (PS.sub.20).fwdarw.PS.sub.2(b[2].sub._.sub.1) (PS.sub.30).fwdarw.PS.sub.31.fwdarw. . . . .fwdarw.PS.sub.30 (PS.sub.2(b[2].sub._.sub.1)).fwdarw. . . . .fwdarw.PS.sub.2(b[2].sub._.sub.2) (PS.sub.40).fwdarw. . . . .fwdarw.PS.sub.4(b[4].sub._.sub.1) (PS.sub.50).fwdarw. . . . .fwdarw.PS.sub.50 (PS.sub.4(b[4].sub._.sub.1)).fwdarw. . . . .fwdarw.PS.sub.40 (PS.sub.2(b[2].sub._.sub.2)).fwdarw. . . . .fwdarw.PS.sub.20 (PS.sub.1(b[1].sub._.sub.1)).fwdarw.PS.sub.10.

(13) The present work extends the resource-oriented PN developed in [Wu, 1999; and Wu and Zhou, 2001 and 2009] to model a treelike hybrid K-cluster tool. The basic concept of the PN used in the present work is based on [Zhou and Venkatesh, 1998; Wu, 1999; and Wu and Zhou 2009]. As a kind of finite capacity PN, it is defined as PN=(P, T, I, O, M, ), where P={p.sub.1, p.sub.2, . . . , p.sub.m} is a finite set of places and T={t.sub.1, t.sub.2, . . . , t.sub.n} is a finite set of transitions; I/O is the input/output functions; M(p) is a marking representing the number of tokens in place p with M.sub.0(p) being the initial marking in p; and is a capacity function with (p) being the largest number of tokens that p can hold at a time. Transition t's preset is the set of all input places to t, namely, .sup..circle-solid.t={p: pP and I(p, t)>0}. Its postset is the set of all output places from t, namely, t.sup..circle-solid.={p: pP and O(p, t)>0}. Similarly, one has p's preset .sup..circle-solid.p={tT: O(p, t)>0} and postset p.sup..circle-solid.={tT: I(p, t)>0}. For the transition enabling and firing rules, one can refer to [Wu, 1999; Wu and Zhou, 2001 and 2010c].

(14) A.1. PN for Hybrid K-Cluster Tools

(15) To model a hybrid K-cluster tool, one adopts the PN models developed in [Yang et al., 2015] with the backward and swap strategies for the single and dual-arm tool as shown in FIGS. 2 and 3, respectively. A brief introduction to them is presented for self-completeness as follows. Note that for convenience, a token and a wafer are often used without difference.

(16) For C.sub.i, i.sub.K, regardless of whether it is a single or dual-arm tool, transition x.sub.ij, j.sub.n[i], models R.sub.i's moving from Steps j to j+1 (or Step 0 if j=n[i]) with a wafer hold, and places r.sub.i and p.sub.ij, model R.sub.i and PS.sub.ij, j.sub.n[i], respectively. Note that (p.sub.ij)=1 indicating that there is only one PM for a step; and (r.sub.i)=1 if C.sub.i is a single-arm tool and (r.sub.i)=2 if C.sub.i is a dual-arm tool. For a single-arm tool C.sub.i, i.sub.K, as shown in FIG. 2, place q.sub.ij with (q.sub.ij)=1 models R.sub.i's waiting before unloading a wafer (token) from p.sub.ij, j.sub.n[i]. Places d.sub.ij and z.sub.ij with (d.sub.ij)=(z.sub.ij)=1 model that R.sub.i holds a wafer for moving from Steps j to j+1 (or Step 0 if j=n[i]) and loading a wafer into p.sub.ij, j.sub.n[i], respectively. Transitions u.sub.ij and t.sub.ij model that R.sub.i removes a wafer from p.sub.ij, and drops a wafer into p.sub.ij, j.sub.n[i], respectively. Transition y.sub.ij, j.sub.n[i]\{0, 1}, models R.sub.i's moving from Steps j+2 to j (or to n[i]1 if j=0, or to n[i] if j=1), without carrying a wafer.

(17) For a dual-arm tool C.sub.i, i.sub.K, as shown in FIG. 3, places d.sub.ij and z.sub.ij with (d.sub.ij)=(z.sub.ij)=1 model the state that a swap ends and R.sub.i's waiting before unloading a wafer from p.sub.ij, j.sub.n[i], respectively. Place q.sub.ij with (q.sub.ij)=2 models that both arms of R.sub.i hold a wafer and wait during swap at p.sub.ij, j.sub.n[i]. Transitions t.sub.ij and u.sub.ij model R.sub.i's loading and unloading a wafer into and from p.sub.ij, j.sub.n[i], respectively. By firing u.sub.ij, two tokens enter q.sub.ij, implying that both arms hold a wafer and wait. For more details, the readers can refer to [Wu et al., 2008] and [Wu and Zhou, 2010b].

(18) For a BM that connects C.sub.k and C.sub.i, k.Math.L, i.Math.{1}, with C.sub.k being the upstream one, there are four different cases:

(19) 1) both C.sub.k and C.sub.i are dual-arm tools (herein referred to as a D-D case in short);

(20) 2) C.sub.k is a single-arm tool and C.sub.i is a dual-arm one (herein referred to as a S-D case in short);

(21) 3) C.sub.k is a dual-arm tool and C.sub.i is a single-arm one (herein referred to as a D-S case in short); and

(22) 4) both are single-arm tools (herein referred to as a S-S case in short).

(23) As the BM linking C.sub.k and C.sub.i can be treated as a step denoted by PS.sub.k(b[k].sub._.sub.q) for C.sub.k, or the q-th OM, 1qf[k], in C.sub.k, and it is also seen as PS.sub.i0 in C.sub.i. Hence, this BM is modeled by p.sub.k(b[k].sub._.sub.q) and p.sub.i0 for C.sub.k and C.sub.i, respectively, with p.sub.k(b[k].sub._.sub.q)=p.sub.i0 and (p.sub.k(b[k].sub._.sub.q))=(p.sub.i0)=1. The PN models of the four cases are shown in FIG. 4. For the S-S case, Step b[k]_q for C.sub.k is modeled by z.sub.k(b[k].sub._.sub.q), t.sub.k(b[k].sub._.sub.q), p.sub.k(b[k].sub._.sub.q), q.sub.k(b[k].sub._.sub.q), u.sub.k(b[k].sub._.sub.q), and d.sub.k(b[k].sub._.sub.q) together with arcs (z.sub.k(b[k].sub._.sub.q), t.sub.k(b[k].sub._.sub.q)), (t.sub.k(b[k].sub._.sub.q), p.sub.k(b[k].sub._.sub.q)), q.sub.k(b[k].sub._.sub.q), u.sub.k(b[k].sub._.sub.q)), (q.sub.k(b[k].sub._.sub.q), u.sub.k(b[k].sub._.sub.q), and (u.sub.k(b[k].sub._.sub.q), d.sub.k(b[k].sub._.sub.q)). Step 0 for C.sub.i is modeled by z.sub.i0, t.sub.i0, p.sub.i0, q.sub.i0, u.sub.i0, and d.sub.i0 together with arcs (z.sub.i0, t.sub.i0), (t.sub.i0, p.sub.i0), (p.sub.i0, u.sub.i0), (q.sub.i0, u.sub.i0), and (u.sub.i0, d.sub.i0) as shown in FIG. 4(d). Similarly, one can obtain the models for the other cases.

(24) With the developed PN, the initial marking M.sub.0 of the PN model can be set by putting a V-token representing a virtual wafer (not real one) as follows.

(25) For C.sub.1, set M.sub.0(p.sub.10)=n, representing that there are always wafers to be processed. If C.sub.1 is a single-arm tool, set M.sub.0(r.sub.1)=0; M.sub.0(p.sub.1(b[i].sub._.sub.1))=0 and M.sub.0(p.sub.1j)=1, j.sub.n[1]\{b[1]_1}; M.sub.0(z.sub.1j)=M.sub.0(d.sub.1j)=0, j.sub.n[1]; M.sub.0(q.sub.1j)=0, j.sub.n[1]\{(b[1]_1)1}, and M.sub.0(q.sub.1((b[1].sub._.sub.1)1))=1, implying that R.sub.1 is waiting at PS.sub.1((b[1].sub._.sub.1)1)) for unloading a wafer there. If C.sub.1 is a dual-arm tool, set M.sub.0(r.sub.1)=1; M.sub.0(p.sub.1j)=1, j.sub.n[1]; M.sub.0(q.sub.ij)=M.sub.0(d.sub.1j)=0, j.sub.n[1]; M.sub.0(z.sub.1j)=0, j.sub.n[1]\{[b1]_1} and M.sub.0(z.sub.1(b[1].sub._.sub.1))=1, implying that R.sub.1 is waiting at PS.sub.1(b[i].sub._.sub.1) for unloading a wafer there.

(26) For a single-arm tool C.sub.i, i.sub.K\{1}, M.sub.0(r.sub.i)=0; M.sub.0(z.sub.ij)=M.sub.0(d.sub.ij)=0, j.sub.n[i]; M.sub.0(p.sub.i1)=0 and M.sub.0(p.sub.ij)=1, j.sub.n[i]\{1}; M.sub.0(q.sub.ij)=0, j.sub.n[i], and M.sub.0(q.sub.i0)=1, representing that R.sub.i is waiting at PS.sub.i0 for unloading a wafer there. For a dual-arm tool C.sub.i, i.sub.K\{1}, set M.sub.0(r.sub.i)=1; M.sub.0(p.sub.ij)=1, j.sub.n[i]; M.sub.0(q.sub.ij)=M.sub.0(d.sub.ij)=0, j.sub.[n]; M.sub.0(z.sub.ij)=0, j.sub.n[i], and M.sub.0(z.sub.i0)=1, representing that R.sub.i is waiting at PS.sub.i0 for unloading a wafer there. It should be pointed out that, at M.sub.0, for any adjacent C.sub.k and C.sub.i, the token in p.sub.i0 is assumed to enable u.sub.k(b[k].sub._.sub.q), but not u.sub.i0.

(27) In FIG. 4, for place p.sub.i0 (p.sub.k(b[k].sub._.sub.q)), there are two output transitions u.sub.k(b[k].sub._.sub.q) and u.sub.i0, leading to a conflict. However, a token entering p.sub.i0 by firing t.sub.k(b[k].sub._.sub.q) should enable u.sub.i0, while the one entering p.sub.i0 by firing t.sub.i0 should enable u.sub.k(b[k].sub._.sub.q). To avoid such a conflict, one introduces colors into the model. one first defines the color for the transition as follows.

(28) Definition 1:

(29) The color of a transition t.sub.i is defined as C(t.sub.i)={c.sub.i}.

(30) By Definition 1, the colors for u.sub.i0 and u.sub.k(b[k].sub._.sub.q) are c.sub.i0 and c.sub.k(b[k].sub._.sub.q), respectively. Then, one can define the color for a token as follows.

(31) Definition 2:

(32) If a token in p.sup..circle-solid.t.sub.i enables t.sub.i, it has the same color of t.sub.i, i.e. {c.sub.i}.

(33) With Definition 2, a token entering p.sub.i0 by firing t.sub.k(b[k].sub._.sub.q) has color c.sub.i0 and enables u.sub.i0 only, and the token entering p.sub.i0 by firing t.sub.i0 has color c.sub.k(b[k].sub._.sub.q) and enables u.sub.k(b[k].sub._.sub.q) only. By this way, the PN becomes conflict-free. One more issue is that although the model for a dual-arm tool is deadlock-free, the model for a single-arm one is deadlock-prone [Yang et al. 2015]. A control policy defined in [Yang et al. 2015] is applied to solve this problem.

(34) Definition 3 [Yang et al. 2015]:

(35) In the PN model of a treelike hybrid K-cluster tool, for a single-arm tool C.sub.i, i.sub.K, at marking M, y.sub.ij, j.sub.n[i]\{n[i], (b[i]_q)1} and q.sub.f[i], is control-enabled if M(p.sub.i(j+1))=0; y.sub.i(n[i]) is control-enabled if transition t.sub.i1 has just been executed, and y.sub.i((b[i].sub._.sub.q)1) is control-enabled if transition t.sub.i((b[i].sub._.sub.q)+1) has just been executed.

(36) Thereafter, it is assumed that the PN is always controlled by the control policy given in Definition 3 such that the model is deadlock-free.

(37) A.2. Modeling Activity Time

(38) In the developed PN model, the time related activities are modeled by both transitions and places and time should be associated with both of them. As pointed out by Kim et al. [2003] and Lee and Lee [2006], for both single (S) and dual-arm (D) tools, the time for the robot to move from one step to another with or without carrying a wafer is identical, so is the time for the robot to unload/load a wafer from/into a PM. By following [Wu et al., 2008; and Wu and Zhou, 2010b], the activity time is modeled as shown in TABLE 1.

(39) TABLE-US-00001 TABLE 1 Time duration associated with transitions and places for tool C.sub.i. Tran- sitions/ Time Tool Symbol places Action duration type .sub.i t.sub.ij/ R.sub.i loads/unloads a wafer into/from .sub.i S u.sub.ij T Step j, j .sub.n[i] .sub.i u.sub.ij and R.sub.i Swaps at Step j, j .sub.n[i] .sub.i D t.sub.ij T .sub.i x.sub.ij T R.sub.i moves from a step to another .sub.i Both with a wafer carried .sub.i y.sub.ij T R.sub.i moves from a step to another .sub.i S without a wafer carried .sub.ij p.sub.ij P A wafer is been processed in p.sub.ij, j .sub.ij Both .sub.n[i] .sub.ij p.sub.ij P A wafer is been processed and is .sub.ij Both waiting in p.sub.ij , j .sub.n[i] .sub.ij q.sub.ij P R.sub.i waits before unloading a wafer 0 S from Step j, j .sub.n[i] .sub.ij z.sub.ij P R.sub.i waits at p.sub.ij, j .sub.n[i] 0 D .sub.ij1 q.sub.ij P R.sub.i waits during swap at p.sub.ij, j .sub.n[i] 0 D d.sub.ij P No robot activity is associated 0 Both z.sub.ij P No robot activity is associated 0 S

B. Timeliness Analysis of Individual Tools

(40) With the above developed PN model, this section presents the temporal properties for individual tools to parameterize a schedule by robot waiting time. According to Wu et al. [2008], for a single-arm tool C.sub.i, i.sub.K, the time taken for processing a wafer at Step j, j.sub.n[i], is
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1)(1)
For Step 0, as .sub.i0=0, one has
.sub.i0=4.sub.i+3.sub.i+.sub.i(n[i])(2)
With the robot waiting time being removed, the time needed for completing a wafer at Step j is
.sub.ij=.sub.ij+4.sub.i+3.sub.i,j.sub.n[i].(3)
To be feasible, a wafer should stay in PM.sub.ij for .sub.ij (.sub.ij) time units. By replacing .sub.ij with .sub.ij, the cycle time at Step j in C.sub.i is computed by
.sub.ij.sub.ij=+4.sub.i+3.sub.i+.sub.i(j1),jN.sub.n[i](4)
and
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j01),j.sub.n[i].(4)
The robot cycle time for a single-arm tool C.sub.i is

(41) $\begin{array}{cc}{}_i=2\left(n\left[i\right]+1\right)\left({}_i+{}_i\right)+\underset{j=0}{\overset{n\left[i\right]}{.Math.}}{}_{\mathrm{ij}}={}_{i1}+{}_{i2}& \left(6\right)\end{array}$
where .sub.i1=2(n[i]+1)(.sub.i+.sub.i) is the robot's activity time in a cycle without waiting and it is a known constant, while .sub.i2=.sub.j=0.sup.n[i].sub.ij is the robot waiting time in a cycle.

(42) For a dual-arm tool C.sub.i, i.sub.K, according to Wu et al. [2010a], the time needed for processing a wafer at Step j, j.sub.n[i], is
.sub.ij=.sub.ij+.sub.i.(7)
Similarly, by replacing .sub.ij with .sub.ij in (7), the cycle time at Step j, j.sub.n[i], is
.sub.ij=.sub.ij+.sub.i.(8)
The robot cycle time for a dual-arm tool C.sub.i is

(43) $\begin{array}{cc}{}_i=\left(n\left[i\right]+1\right)\left({}_i+{}_i\right)+\underset{j=0}{\overset{n\left[i\right]}{.Math.}}{}_{\mathrm{ij}}={}_{i1}+{}_{i2}& \left(9\right)\end{array}$
where .sub.i1=(n[i]+1)(.sub.i+.sub.i) is the robot cycle time in a cycle without waiting and .sub.i2=.sub.j=0.sup.n[i].sub.ij is the robot's waiting time in a cycle.

(44) Since the production process is serial for each tool C.sub.i, i.sub.K, the productivity for each step is identical. Thus, C.sub.i should be scheduled such that
.sub.i=.sub.i0=.sub.i1= . . . =.sub.i(n[i])=.sub.i.(10)
Due to the fact that both .sub.i and .sub.i are functions of .sub.ij's, the schedule for each tool C.sub.i, i.sub.K, is parameterized by robots' waiting time. With this observation in mind, the key for scheduling a treelike hybrid K-cluster tool is to determine .sub.ij's such that the activities of the multiple robots are coordinated to act in a paced way.

C. Scheduling the Overall System

(45) C.1. Schedule Properties

(46) Let .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i]), .sub.(n[i])} denote the fundamental period (FP) of C.sub.i, i.sub.K. If .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i])}, C.sub.i is process-bound. Let =max{.sub.1, .sub.2, . . . .sub.K}=.sub.h, 1hK, or C.sub.h is the bottleneck tool. Since, by assumption, a treelike hybrid K-cluster tool addressed here is process-dominant, C.sub.h must be process-bound. Let be the cycle time of the system. Then, with .sub.i being the cyclic time of C.sub.i, to obtain a one-wafer cyclic schedule for the system, each individual tool must have an identical cycle time that is equal to for the entire system, i.e.
=.sub.i,i.sub.K.(11)
From [Yang et al. 2015], each individual tool can be scheduled to be paced, if and only if, for any adjacent pair C.sub.k and C.sub.i, k.Math.L and i.Math.{1}, linked by PS.sub.k(b[k].sub._.sub.q), 1qf[k], at any marking M, one has: 1) whenever R.sub.i (R.sub.k) is scheduled to load a token into p.sub.i0 (p.sub.k(b[k].sub._.sub.q)), M(p.sub.i0)=0 (M(p.sub.k(b[k].sub._.sub.q))=0); and 2) whenever R.sub.i (R.sub.k) is scheduled to unload a token from p.sub.i0 (p.sub.k(b[k].sub._.sub.q)), M(p.sub.i0)=1 (M(p.sub.k(b[k].sub._.sub.q))=1). In [Yang et al. 2015], the existence of a one-wafer cyclic schedule with the LB of cycle time, i.e. OSLB for short, is discussed and conditions under which an OSLB exists are derived. Algorithm is developed to find it if it exists. This work conducts a study on the case that there is no OSLB and presents a method to find an O.sup.2CS with >.
C.2. Optimal One-Wafer Cyclic Scheduling

(47) For a process-dominant treelike hybrid K-cluster tool, the conditions under which an OSLB can be found are given as follows [Yang, et al., 2015].

(48) Lemma 1:

(49) For a process-dominant treelike hybrid K-cluster tool, an OSLB exists, if and only if, for any adjacent pair C.sub.k and C.sub.i, k.Math.L, i.Math.{1}, connected by PS.sub.k(b[k].sub._.sub.q), the following conditions are satisfied by determining .sub.kj's and .sub.il's, j.sub.n[k] and l.sub.n[i] such that:
.sub.kj=.sub.il=,j.sub.n[k] and l.sub.n[i];(12)
if C.sub.k and C.sub.i are D-S case,
4.sub.k4.sub.i+3.sub.i+.sub.i(n[i]);(13)
and if C.sub.k and C.sub.i are S-S case,
(4.sub.k+3.sub.k+.sub.k((b[k].sub._.sub.q)1))4.sub.i+3.sub.i+.sub.i(n[i]);(14)

(50) Based on Lemma 1, an efficient algorithm is developed in [Yang, et al., 2015] to test the existence of an OSLB and find it if it exists. In the sequel, for a process-dominant treelike K-cluster tool, one shows that there is always a one-wafer cyclic schedule and present an efficient algorithm to find the minimal cycle time > and O.sup.2CS. In the following discussion, one focuses on the situation that there is no OSLB for the system.

(51) Let B.sub.i denote a linear multi-cluster tool in a treelike K-cluster tool called a branch that starts from C.sub.i and ends at C.sub.m, mL. For simplicity, one assumes that the tools in B.sub.i is labeled consecutively as C.sub.i, C.sub.i+1, . . . , C.sub.m. Assume that, with = as the cycle time, the conditions given in Lemma 1 are violated for a pair of C.sub.i and C.sub.i+1 in B.sub.i. Then, let A.sub.kj=.sub.kj, k=i+1, i+2, . . . , m, j.sub.n[k], where .sub.kj is R.sub.k's waiting time obtained by the algorithm given in [Yang, et al., 2015] with cycle time =. Define .sub.i+1(S, S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+4.sub.i+3.sub.i, when C.sub.i and C.sub.i+1 are S-S, and .sub.i+1(D, S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+.sub.i, when C.sub.i and C.sub.i+1 are D-S. If A.sub.(i+1)(n[i+1])=0, it follows from [Yang et al., 2014b] that an O.sup.2CS with cycle time =+.sub.i+1(S, S) (or +.sub.i+1(D, S) if C.sub.i is a dual-arm tool) can be found for B.sub.i. Otherwise, if A.sub.(i+1)(n[i+1])0, assume that, for g[i+1, m], A.sub.k+1)(n[k+1])>0, ikg1, and A.sub.(g+1)(n[g+1])=0, or C.sub.g+1 is a dual-arm one, or gL. Define D[k]={PM.sub.kj|j(b[k]_1)1 and jn[k]} be the set of steps in C.sub.k, and B[k]=n[k]1, k=i+1, i+2, . . . , m. Then, let .sub.g=.sub.g(n[g])/B[g], .sub.g1=A.sub.(g1)(n[g1])/(B[g1]+B[g]), .sub.g2=A.sub.(g2)(n[g2])/(B[g2]+B[g1]+B[g]), . . . , .sub.i+2=A.sub.(i+2) (n[i+2])/(B[i+2]+B[i+3]+ . . . +B[g]), .sub.i+1 is defined by (15) below if C.sub.i is a single-arm tool, where =(B[i+1]+B[i+2]+ . . . +B[g]).

(52) $\begin{array}{cc}{}_{i+1}=\{\begin{array}{c}{}_{i+1}\left(S,S\right)-A_{\left(i+1\right)\left(n\left[i+1\right]\right)},\mathrm{if}{A}_{\left(i+1\right)\left(n\left[i+1\right]\right)}<{}_{i+1}\left(S,S\right)/\left(+1\right)\\ {}_{i+1}\left(S,S\right)/\left(+1\right),\mathrm{if}{A}_{\left(i+1\right)\left(n\left[i+1\right]\right)}{}_{i+1}\left(S,S\right)/\left(+1\right)\end{array}.& \left(15\right)\end{array}$
If C.sub.i is a dual-arm tool, .sub.i+1=.sub.i+1(D, S)/(+1). Then, one has Lemmas 2-3 [Yang, et al., 2014b].

(53) Lemma 2:

(54) For B.sub.i that is composed of two tools, there is an O.sup.2CS and its minimal one-wafer cycle time is =+, where is determined by

(55) 0$\begin{array}{cc}=\{\begin{array}{c}\begin{array}{c}{}_2\left(S,S\right)-A_{2\left(n\left[2\right]\right)},\mathrm{if}{A}_{2\left(n\left[2\right]\right)}[0,\left(n\left[2\right]-1\right){}_2\left(S,S\right)/n\left[2\right])\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ \begin{array}{c}{}_2\left(S,S\right)/n\left[2\right],\mathrm{if}{A}_{2\left(n\left[2\right]\right)}\left[\left(n\left[2\right]-1\right){}_2\left(S,S\right)/n\left[2\right],\right)\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ {}_2\left(D,S\right)/n\left[2\right],\mathrm{for}D-S\mathrm{case}\end{array}.& \left(16\right)\end{array}$

(56) With Lemma 2, a method is proposed to find the minimal cycle time and the O.sup.2CS for a B.sub.i composed of two tools in [Yang, et al., 2014b].

(57) Lemma 3:

(58) For a B.sub.i in a treelike hybrid K-cluster tool, if, by the algorithm in [Yang, et al., 2015], a one-wafer cyclic schedule with cycle time () is found, a feasible one-wafer cyclic schedule is obtained with cycle time (+) by setting .sub.g((b[g].sub._.sub.1)1)=A.sub.g((b[g].sub._.sub.1)+, g[i, m1], and .sub.m0=A.sub.m0+ where mL and >0.

(59) Let ST.sub.i denote a sub-tree in a treelike hybrid K-cluster tool that starts from C.sub.i with C.sub.i being a fork tool. Let ST.sub.i and ST.sub.j be two STs, and ST.sub.i can be contained by ST.sub.j, and such a relation is denoted as ST.sub.i<ST.sub.j or ST.sub.j>ST.sub.i. In a treelike hybrid K-cluster tool, the individual tools can be numbered such that ST.sub.j>ST.sub.i only if j<i. However, j<i does not necessarily mean ST.sub.j>ST.sub.i, for they may be independent of each other. Such a relation is denoted as ST.sub.jvST.sub.i. Then, one can discuss the one-wafer cyclic scheduling problem. One has the following result.

(60) Theorem 1:

(61) For an ST.sub.i composed of three tools, there is an O.sup.2CS and its minimal cycle time is =+=+max{.sub.1, .sub.2}, where .sub.1 and .sub.2 are obtained by the method given in Lemma 2.

(62) Proof:

(63) An ST.sub.i composed of three tools must contain a fork tool denoted by C.sub.i and two downstream tools denoted by C.sub.i+1 and C.sub.i+2. It follows from Lemma 2 that one can schedule both C.sub.i and C.sub.i+1 such that their cycle time is =+.sub.1 to obtain an O.sup.2CS for tool pair of C.sub.i and C.sub.i+1. Similarly, both C.sub.i and C.sub.i+2 can be scheduled such that their cycle time is =+.sub.2 to obtain an O.sup.2CS for tool pair of C.sub.i and C.sub.i+2. Thus, for ST.sub.i composed of C.sub.i, C.sub.i+1, and C.sub.i+2, one can schedule the three tools such that their cycle time is =max{+.sub.1, +.sub.2}=+max{.sub.1, .sub.2} to obtain an O.sup.2CS.

(64) The ST discussed in Theorem 1 is the simplest one. A fork tool C.sub.i with f[i] adjacent downstream tools C.sub.i.sub._.sub.1, C.sub.i.sub._.sub.2, . . . , and C.sub.i.sub._.sub.f[i] may contain no ST but only branches and these branches are B.sub.i.sub._.sub.1, B.sub.i.sub._.sub.2, . . . , B.sub.i.sub._.sub.f[i]. By the method presented in [Yang, et al., 2014b], one can find O.sup.2CSs for B.sub.i.sub._.sub.q, q.sub.f[i]. Assume that the cycle time for the branch composed of C.sub.i and B.sub.i.sub._.sub.q is +.sub.q. Then, based on Theorem 1, one has the following corollary immediately.

(65) Corollary 1:

(66) For an ST.sub.i composed of C.sub.i and its downstream branches B.sub.i.sub._.sub.1, B.sub.i.sub._.sub.2, . . . , B.sub.i.sub._.sub.f[i], there is an O.sup.2CS and its minimal one-wafer cycle time is =+max{.sub.1, .sub.2, . . . , .sub.f[i]}, where +.sub.q is the cycle time for the branch composed of C.sub.i and B.sub.i.sub._.sub.q, q.sub.f[i].

(67) Then, an O.sup.2CS for a treelike hybrid K-cluster tool can be found as follows. Let C.sub.j be a fork tool. There must be a ST.sub.j. Assume that there are tools C.sub.i, C.sub.i+1, . . . , C.sub.j2, C.sub.j1, and none of them is a fork tool. Then, one calls the multi-cluster tool formed by C.sub.i and all its downstream tools an extended sub-tree denoted as EST.sub.i. Note that C.sub.i is not a fork tool. If EST.sub.i contains ST.sub.j, one calls EST.sub.i is an extended sub-tree of ST.sub.j. Let F={l/C.sub.i is a fork tool} be the index set of fork tools. Assume that jF has the largest value, i.e. j=max.sub.lF{l}. Then, ST.sub.j must contain no ST and its O.sup.2CS can be found based on Corollary 1. There may be more than one EST of ST.sub.j. Thus, with the O.sup.2CS for ST.sub.j found, one needs to find the O.sup.2CSs for all its ESTs. Then, let FF\{j}. If F, find h such that it has the largest value in F, i.e., h=max.sub.lF{l}. If ST.sub.hvST.sub.j, or they are independent of each other, it can be dealt with just as ST.sub.j. Otherwise, ST.sub.j can be contained in ST.sub.h or one has ST.sub.h>ST.sub.j. In this case, one needs to find the O.sup.2CS for ST.sub.h and its ESTs. Then, let FF\{h} and repeat the above procedure. In this way, with the decreasing order of the indices in F, one finds the O.sup.2CSs for all the STs and their ESTs. When C.sub.1 is reached, one finds the O.sup.2CS for the treelike hybrid K-cluster tool. The key is how to find an O.sup.2CS for a ST or an extended one. By the definition of an EST.sub.k, if B.sub.i.sub._.sub.q in Corollary 1 is replaced by EST.sub.i.sub._.sub.q, the result must also hold.

(68) In the following, one first shows how to find the O.sup.2CS for an EST that contains only one fork tool and then present a method for finding the O.sup.2CS for the whole system. Assume that j=max.sub.lF{l} and EST.sub.i is an extended sub-tree of ST.sub.j. Further, assume that for tool pair C.sub.i and C.sub.i+1, i+1j, there is no one-wafer cyclic schedule with cycle time . Notice that, based on the O.sup.2CS for ST.sub.j that can be found based on Corollary 1, Condition (13) or (14) is not satisfied for tool pair C.sub.i and C.sub.i+1, i+1j, only.

(69) Let A.sub.pj=.sub.pj, p.sub.K\N.sub.i, j.sub.n[p], where .sub.pj's are obtained by the algorithm in [Yang, et al., 2015] with cycle time , and define D[l]={PM.sub.1j|jn[l] and j(b[l]_d)1, df[l]} and B[l]=n[l]1, l.sub.K. Let .sub.i+1(S, S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+4.sub.i+3.sub.i for the S-S case and .sub.i+1(D, S)=4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])=+4.sub.i+3.sub.i for the D-S case. It follows from [Yang, et al., 2014b] that, if A.sub.(i+1)(n[i+1])=0, to make (13) or (14) satisfied for C.sub.i and C.sub.i+1, needs to be increased by .sub.i+1(D, S) and .sub.i+1(S, S) time units, respectively. If A.sub.(i+1)(n[i+1])0, one needs to check if A.sub.j(n[j])=0. If yes, the optimal cycle time can still be found by the methods in [Yang, et al., 2014b]. If A.sub.j(n[j])0 and there is a dual-arm tool in the tools C.sub.i+1, C.sub.i+2, C.sub.j, or there is at least one A.sub.p(n[p])=0, i+1<p<j, one can still find the optimal cycle time by the methods in [Yang, et al., 2014b]. However, when A.sub.p(n[p])>0, i+1pj, one cannot find the optimal cycle time by the methods in [Yang, et al., 2014b]. In this situation, one discusses how to find the optimal cycle time as follows.

(70) Assume that C.sub.j has f[j] downstream tools such that ST.sub.j has f[j] branches. Then, for C.sub.j.sub._.sub.q in B.sub.j.sub._.sub.q, q.sub.f[j] one first checks whether A.sub.(j.sub._.sub.q)(n[q])>0. If so, find g such that A.sub.((j.sub._.sub.q)+z)(n[(j.sub._.sub.q)+z])>0, 0zg, and A.sub.(j.sub._.sub.q)+z+1)(n[(j.sub._.sub.q)+z+1])>0 or C.sub.(j.sub._.sub.q)+g+1 is a dual-arm one, or (j_q)+gL. Then, let A.sub.((j.sub._.sub.q)+g)=A.sub.((j.sub._.sub.g)(n[(j.sub._.sub.q)+g])/B[(j_q)+g], .sub.((j.sub._.sub.q)+g1)=A.sub.((j.sub._.sub.q)+g1)(n[j.sub._.sub.q)+g1])/(B[(j_q)+g1]+B[(j_q)+g]), .sub.(j.sub._.sub.q)+g2)=A.sub.((j.sub._.sub.q)+g2)(n[j.sub._.sub.q)+g2])/B[(j_q)+g2]+B[(j_q)+g1]+B[(j_q)+g]), . . . , and .sub.j.sub._.sub.q)=A.sub.(j.sub._.sub.q)(n[j.sub._.sub.q])/B[j_q]+B[(j_q)+1]+ . . . +B[(j_q)+g]). Further, let j_q=(B[j_q]+B[(j_q)+1]+ . . . +B[(j_q)+g]), q.sub.f[j], and .sub.j=.sub.j.sub._.sub.1+.sub.j.sub.2+ . . . +.sub.j.sub._.sub.f[j]. It should be noted that, if A.sub.(j.sub._.sub.q)(n[j.sub._.sub.q])=0, one has .sub.j.sub._.sub.q=0. Then, define .sub.j=A.sub.j(n[j])/[.sub.j+B[j]], .sub.j1=A.sub.(j1)(b[j1])/(.sub.j+B[j]+B[j1]), . . . , .sub.i+2=A.sub.(i+2)(n[i+2])/(.sub.j+B[j]+B[j1]+ . . . +B[i+2]). Let =.sub.j+B[j]+B[j1]+ . . . +B[i+1], =min{.sub.i+1, .sub.i+2, . . . , .sub.j, .sub.(j.sub._.sub.q)+z)} and =argmin{.sub.i+1, .sub.i+2, . . . , .sub.j, .sub.(j.sub._.sub.q)+z)} with q.sub.f[j] and 0zg, where .sub.i+1 is defined by

(71) $\begin{array}{cc}{}_{i+1}=\{\begin{array}{cc}{}_{i+1}\left(S,S\right)-A_{\left(i+1\right)\left(n\left[i+1\right]\right)},& \begin{array}{c}\mathrm{if}0<A_{\left(i+1\right)\left(n\left[i+1\right]\right)}<\frac{{}_{i+1}\left(S,S\right)}{1+}\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ \frac{{}_{i+1}\left(S,S\right)}{1+},& \begin{array}{c}\mathrm{if}{A}_{\left(i+1\right)\left(n\left[i+1\right]\right)}\frac{{}_{i+1}\left(S,S\right)}{1+}\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ \frac{{}_{i+1}\left(D,S\right)}{1+},& \mathrm{for}D-S\mathrm{case}\end{array}.& \left(17\right)\end{array}$
Then, one has the following results.

(72) Theorem 2:

(73) Assume that: 1) j=max.sub.lF {l}; 2) for an EST.sub.i of ST.sub.j, by the algorithm in [Yang, et al., 2015] with cycle time , Condition (14) is violated for tool pair C.sub.i and C.sub.i+1, i+1j, only; and 3) =.sub.=A.sub.i+1. Then, for EST.sub.i, an O.sup.2CS with cycle time + can be found, where is given by (17).

(74) Proof:

(75) Since (14) is violated for tool pair C.sub.i and C.sub.i+1 only, they should be S-S. It follows from (17) that if 0<A.sub.(i+1)(n[i+1]).sub.i+1(S, S)/(+1) and =.sub.i+1=.sub.i+1(S, S)A.sub.(i+1)(n[i+1]), one has (+1)A.sub.(i+1)(n[i+1]).sub.i+1(S, S)A.sub.(i+1)(n[i+1])<(.sub.i+1(S, S)A.sub.(i+1)(n[i+1]))A.sub.(i+1)(n[i+1])/<.sub.i+1(S, S)A.sub.(i+1)(n[i+1])=. By A.sub.(i+1)(n[i+1])>0, one has >0, or it is feasible in the sense of that the time is set to be positive value. Let +. Then, for B.sub.(j.sub._.sub.q)+g+1) (if it exists) in B.sub.j.sub._.sub.q q.sub.f[j], reset the robots' waiting time as given by Lemma 3. Meanwhile, for C.sub.((j.sub._.sub.q)+g), set .sub.((j.sub._.sub.q)+g)l=A.sub.((j.sub._.sub.q)+g)l+A.sub.(i+1)(n[i+1])/, lD[(j_q)+g] (or l.sub.n[j.sub._.sub.q)+g]\{n[(j_q)+g]} if (j_q)+gL), .sub.(j.sub._.sub.q)+g)((b[(j.sub._.sub.q)+g].sub._.sub.1)1)=A.sub.(j.sub._.sub.q)+g)((b[(j.sub._.sub.q)+g].sub._.sub.1)1)+ (or .sub.(j.sub._.sub.q)+g)0=A.sub.((j.sub._.sub.q)+g)0+ if (j_q)+gL), and .sub.(j.sub._.sub.q)+g)(n[j.sub._.sub.q)+g])=A.sub.(j.sub._.sub.q)+g)(n[j.sub._.sub.q)+g])B[(j_q)+g]A.sub.(i+1)(n[i+1])/>A.sub.((j.sub._.sub.q)+g)(n[j.sub._.sub.q)+g])B[(j_q)+g]>A.sub.((j.sub._.sub.q)+g)(n[(j.sub._.sub.q)+g])B[(j_q)+g].sub.(j.sub._.sub.q)+g=0. It follows from the discussion in the last section that it is feasible for C.sub.(j.sub._.sub.q)+g. For C.sub.(j.sub._.sub.q)+g1, set .sub.((j.sub._.sub.q)+g1)((b[(j.sub._.sub.q)+g1].sub._.sub.1)1)=A.sub.((j.sub._.sub.q)+g1)((b[(j.sub._.sub.q)+g1].sub._.sub.1)1)+B[(j_q)+g]A.sub.(i+1)(n[i+1])/+, .sub.((j.sub._.sub.q)+g1)l=A.sub.((j.sub._.sub.q)+g1)l+A.sub.(i+1)(n[i+1])/, lD[(j_q)+g1], and .sub.(j.sub._.sub.q)+g1)(n[(j.sub._.sub.q)+g1])=A.sub.(j.sub._.sub.q)+g1)(n[(j.sub._.sub.q)+g1])(B[(j_q)+g]+B[(j_q)+g1])A.sub.(i+1)(n[i+1])/>0. It is also feasible for C.sub.(j.sub._.sub.q)+g1. Then, set the robot waiting time for C.sub.(j.sub._.sub.q)+g2, . . . , C.sub.(j.sub._.sub.q)+2, C.sub.(j.sub._.sub.q)+1, and C.sub.j.sub._.sub.q in a similar way. For C.sub.j.sub._.sub.q, one has .sub.(j.sub._.sub.q)((b[j.sub._.sub.q].sub._.sub.1)1)=A.sub.(j.sub._.sub.q)((b[j.sub._.sub.q].sub._.sub.1)1)+(B[(j_q)+g]+B[(j_q)+g1]+ . . . +B[(j_q)+1])A.sub.(i+1)(n[i+1])/+, .sub.(j.sub._.sub.q)l=A.sub.(j.sub._.sub.q)l+A.sub.(i+1)(n[i+1])/, lD[j_q], and .sub.(j.sub._.sub.q)(n[j.sub._.sub.q])=A.sub.(j.sub._.sub.q)(n[j.sub._.sub.q])(B[(j.sub._.sub.q)+g]+B[(j.sub._.sub.q)+g1]+ . . . +B[j_q])A.sub.(i+1)(n[i+1])/>0. It is feasible for C.sub.j.sub._.sub.q too. For the fork tool C.sub.j, set .sub.j((b[j].sub._.sub.d)1)=A.sub.j((b[j].sub._.sub.d)1)+(B[(j_q)+g]+B[(j_q)+g1]+ . . . +B[j_q]+1)A.sub.(i+1)(n[i+1])/, d{2, 3, . . . , f[j]}; .sub.j((b[j].sub._.sub.1)1)=A.sub.j((b[j].sub._.sub.1)1)+(B[j_q)+g]+B[(j_q)+g1]+ . . . +B[j_q])A.sub.(i+1)(n[i+1])+; and .sub.jl=A.sub.jl+A.sub.(i+1)(n[i+1])/, lD[j]. At last, set .sub.j(n[j])=A.sub.j(n[j])(.sub.j+B[j])A.sub.(i+1)(n[i+1])/>0. Similarly, set the robot waiting time for C.sub.j1, C.sub.j2, . . . , till to C.sub.i+1. In this way, for C.sub.i+1, one has .sub.(i+1)((b[i+1].sub._.sub.1)1)=A.sub.(i+1)(b[i+1].sub._.sub.1)1)+(B[i+1])A.sub.(i+1)(n[i+1])/+, .sub.(i+1)l=A.sub.(i+1)l+A.sub.(i+1)(n[i+1])/, jD[i+1], and .sub.(i+1)(n[i+1])=A.sub.(i+1)(n[i+1]).sub.(i+1)(n[i+1])/=0. By doing so, one has +(4.sub.i+1+3.sub.i+1)=+4.sub.i+1+3.sub.i+1+A.sub.(i+1)(n[i+1])+4.sub.i+3.sub.i)A.sub.(i+1)(n[i+1])(4.sub.i+1+3.sub.i+1)=4.sub.i+3.sub.i. This implies that a one-wafer cyclic schedule is found for EST.sub.i with cycle time +. Notice that one has +(4.sub.i+1+3.sub.i+1)=4.sub.i+3.sub.i, implying that any decrease of cycle time would result in +(4.sub.i+1+3.sub.i+1)<4.sub.i+3.sub.i, or the schedule obtained is optimal in the sense of cycle time.

(76) If A.sub.(i+1)(n[i+1]).sub.i+1(S, S)/(+1) and =.sub.i+1(S, S)/(+1)>0. Let +, and set the robot waiting time as done above with both A.sub.(i+1)(n[i+1])/ and =.sub.i+1(S, S)A.sub.(i+1)(n[i+1]) being replaced by =.sub.i+1(S, S)/(+1). Eventually, for C.sub.i+1, one has .sub.(i+1)((b[i+1].sub._.sub.1)1)=A.sub.(i+1)((b[i+1].sub._.sub.1)1)+(B[i+1])+, .sub.(i+1)l=A.sub.(i+1)l+, lD[i+1], and .sub.(i+1)(n[i+1])=A.sub.(i+1)(n[i+1])0. Similar to the above case, the obtained schedule can be shown to be a feasible and optimal one-wafer cyclic schedule.

(77) The result given by Theorem 2 can be illustrated by FIG. 5. At time zero, R.sub.i in C.sub.i completes its firing for loading a wafer into p.sub.i(b[i])(p.sub.(i+1)0). Meanwhile, R.sub.i+1 in C.sub.i+1 starts to unload a wafer from p.sub.i(b[i])(p.sub.(i+1)0) As shown in FIG. 5, .sub.1=(4.sub.i+3.sub.i) is the time point when R.sub.i is scheduled to unload a wafer from p.sub.i(b[i])(p.sub.(i+1)0) and .sub.2=4.sub.i3.sub.i+1+A.sub.(i+1)(n[i+1]) is the time point when R.sub.i+1 is scheduled to load a wafer into p.sub.i(b[i])(p.sub.(i+1)0). With .sub.1<.sub.2, the schedule for C.sub.i is unrealizable. Let .sub.i+1(S, S)=.sub.2.sub.1. Then, by Theorem 2, the cycle time is increased by such that +, with =.sub.i+1 being given by (17). From (17), with C.sub.i and C.sub.i+1 being S-S, there are two cases. For Case 1, A.sub.(i+1)(n[i+1]).sub.i+1(S, S)/(+1), and =.sub.i+1=.sub.i+1(S, S)A.sub.(i+1)(n[i+1]). Then, with cycle time , X.sub.1=.sub.1+ is the time point when R.sub.i is scheduled to unload a wafer from p.sub.i(b[i])(p.sub.(i+1)0) and X.sub.2=.sub.2A.sub.(i+1)(n[i+1]) is the time point when R.sub.i+1 is scheduled to load a wafer into p.sub.i(b[i]) (p.sub.(i+1)0) Since X.sub.1=X.sub.2 as illustrated in FIG. 5, the schedules for both C.sub.i and C.sub.i+1 are realizable and a one-wafer cyclic schedule is obtained for EST.sub.i. For Case 2, A.sub.(i+1)(n[i+1]).sub.i+1(S, S)/(+1), and =.sub.i+1(S, S)/(+1). Then, with cycle time , one has X.sub.1=.sub.1+=X.sub.2=.sub.2.sub.i+1(S, S)+. Hence, a one-wafer cyclic schedule is obtained for EST.sub.i too.

(78) If C.sub.i and C.sub.i+1 are D-S, one has the following result.

(79) Theorem 3:

(80) Assume that: 1) j=max.sub.lF{l}; 2) for an EST.sub.i of ST.sub.j, by the algorithm in [Yang, et al., 2015] with cycle time , Condition (13) is violated for adjacent tool pair C.sub.i and C.sub.i+1, i+1j, only; and 3) =.sub.=.sub.i+1. Then, for EST.sub.i, an O.sup.2CS with cycle time + can be found, where is given by (17).

(81) Proof:

(82) Since (13) is violated for adjacent tool pair C.sub.i and C.sub.i+1 only, it should be D-S. It follows from (17) that =.sub.i+1(D, S)/(+1)>0. Let +, and set the robot waiting time as done for Case 1 in Theorem 2 with both A.sub.(i+1)(n[i+1])/ and =.sub.i+1(S, S)A.sub.(i+1)(n[i+1]) being replaced by =.sub.i+1(S, S)/(+1)>0. At last, for C.sub.i+1, set .sub.(i+1)((b[i+1].sub._.sub.1)1)=A.sub.(i+1)((b[i+1].sub._.sub.1)1)+(B[i+1])+, .sub.(i+1)l=A.sub.(i+1)l+, lD[i+1], and .sub.(i+1)(n[i+1])=A.sub.(i+1)(n[i+1])=A.sub.(i+1)(n[i+1]).sub.i+1(D, S)/(+1). By the assumption in Section A, for each tool C.sub.p, p.sub.K, n[p]2 holds. Hence, for single-arm tool C.sub.i+1, one has =.sub.i=.sub.l=0.sup.n[i+1]A.sub.(i+1)l+2(n[i+1]+1)(.sub.i+1+.sub.i+1).sub.l=0.sup.n[i+1]A.sub.(i+1)l+6(.sub.i+1+.sub.i+1)6(.sub.i+1)4.sub.i+1+3.sub.i+1<4(.sub.i+1+.sub.i+1)(). For dual-arm tool C.sub.i, one has =.sub.i=.sub.l=0.sup.n[i]A.sub.kl+(n[i]+1)(.sub.i+.sub.i).sub.l=0.sup.n[i]A.sub.kl+3(.sub.i+.sub.i)3.sub.i<2<33.sub.i()<.sub.i. Thus, one has 4.sub.i+1+3.sub.i+1<()<.sub.i4.sub.i+1+3.sub.i+1(.sub.i)+A.sub.(i+1)(n[i+1])<A.sub.(i+1)(n[i+1]) A.sub.(i+1)(n[i+1])>.sub.i+1(D, S)=4.sub.i+1+3.sub.i+1(.sub.i)+A.sub.(i+1)(n[i+1]). This implies that .sub.(i+1)(n[i+1])=A.sub.(i+1)(n[i+1]).sub.i+1(D, S)/(+1)>0, i.e. it is feasible. Similar to Theorem 2, the schedule obtained is optimal.

(83) The idea of Theorem 3 is the same as that of Theorem 2. In Theorems 2 and 3, it is assumed that =i+1. When =argmin{.sub.i+1, .sub.i+2, . . . , .sub.j, .sub.(j.sub._.sub.q)+z)}i+1, q.sub.f[j], 0zg, the following result presents how to find an O.sup.2CS for EST.sub.i.

(84) Theorem 4:

(85) Assume that: 1) j=max.sub.lF{l}; 2) in EST.sub.i of ST.sub.j, by the algorithm in [Yang, et al., 2015] with cycle time , Condition (13) or (14) is violated for tool pair C.sub.i and C.sub.i+1, i+1j, only; 3) =.sub..sub.i+1. Then, there is an O.sup.2CS with cycle time + for EST.sub.i, where is defined as above.

(86) Proof:

(87) Assume =p, or =min{.sub.i+1, A.sub.i+2, . . . , .sub.j, .sub.(j.sub._.sub.q)+z)}=.sub.p, q.sub.f[j], 0zg, and p[j_1, (j_1)+g]. Let + and, for EST.sub.i, set the robots' waiting time as done for Case 1 in Theorem 2 with both A.sub.(i+1)(n[i+1])/ and =.sub.i+1(S, S)A.sub.(i+1)(n[i+1]) being replaced by =.sub.p such that .sub.p(n[p])=A.sub.p(n[p])(B[p]+B[p+1]+ . . . +B[g])(A.sub.p(n[p])/(B[p]+B[p+1]+ . . . +B[g]))=0. Then let g=p1 and calculate again. If =.sub.q, q[j_1, (j_1)+g], let + and repeat the above process. If p[j_q, (j_q)+g], q=2, 3, . . . , f[j], or pargmin{.sub.i+1, A.sub.i+2, . . . , .sub.j}, set the robots' waiting time for EST.sub.i in the same way. In this way, finally, =A.sub.i+1 must occur and then an O.sup.2CS for EST.sub.i is found by using Theorem 2 (or Theorem 3 when C.sub.i is a dual-arm one).

(88) By Theorems 2-4, to find an O.sup.2CS for an EST.sub.i of ST.sub.j, it requires that j is the largest one in F, and such an EST.sub.i contains only one fork tool. This is not enough for one to find the O.sup.2CS for a treelike hybrid K-cluster tool. However, based on Theorems 2-4, one can obtain the O.sup.2CS for an arbitrary EST.sub.k as follows. Assume that for an EST.sub.k that may contain more than one fork tool. Then Condition (13) or (14) is violated for C.sub.k and C.sub.i only with C.sub.i being the downstream adjacent tool of C.sub.k. A path from C.sub.k to a downstream C.sub.l is called a shortest path if there are the fewest nodes (tools) on the path. Then, for an EST.sub.k, one says that C.sub.l is connected to C.sub.k if: 1) there are only single-arm tools on the shortest path from C.sub.k to C.sub.l; and 2) for each tool C.sub.p on the path, .sub.p(n[p])'s>0. By default, C.sub.k is connected to itself. Let S.sub.k={p|C.sub.p is connected to C.sub.k}. Further, as is done above, let .sub.1(S, S)=4.sub.i+3.sub.i+A.sub.i(n[i])+4.sub.k+3.sub.k for the S-S case and .sub.i(D, S)=4.sub.i+3.sub.i+A.sub.i(n[i])+.sub.k (for the D-S case. Then, for an arbitrary EST.sub.k with C.sub.i being the downstream adjacent tool of C.sub.k, to find the minimal one-wafer cycle time, .sub.m can be calculated as follows. One has that
.sub.m=A.sub.m(n[m])/(.sub.pS.sub.mB[p]),m>i,(18)
and if m=i, then one has

(89) $\begin{array}{cc}{}_m={}_i=\{\begin{array}{cc}{}_i\left(S,S\right)-A_{i\left(n\left[i\right]\right)},& \begin{array}{c}\mathrm{if}0<A_{i\left(n\left[i\right]\right)}\frac{{.Math.}_{p{S}_i}B\left[p\right]{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ \frac{{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]},& \begin{array}{c}\mathrm{if}{A}_{\left(i+1\right)\left(n\left[i+1\right]\right)}\frac{{.Math.}_{p{S}_i}B\left[p\right]{}_i\left(S,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]}\\ \mathrm{for}S-S\mathrm{case}\end{array}\\ \frac{{}_i\left(D,S\right)}{1+{.Math.}_{p{S}_i}B\left[p\right]},& \mathrm{for}D-S\mathrm{case}\end{array}.& \left(19\right)\end{array}$
Clearly, (19) is the extension of (17) for an EST.sub.k containing one or more fork tools. Thus, based on (18) and (19), one can find the O.sup.2CS for an EST.sub.k if (13) or (14) is violated for C.sub.k and C.sub.i only with C.sub.i being the downstream adjacent tool of C.sub.k. With the O.sup.2CS for an EST.sub.j, the O.sup.2CS for a ST.sub.k that contains a number of EST.sub.j's can be obtained by using Corollary 1. One presents the following algorithm.

(90) Algorithm 1:

(91) Given an O.sup.2CS with cycle time for EST.sub.i (or ST.sub.i, or B.sub.i), find the O.sup.2CS for EST.sub.k (or ST.sub.k) with C.sub.i being the downstream adjacent tool of C.sub.k.

(92) Step 1:

(93) Given cycle time , check if is the optimal cycle time for EST.sub.k (or ST.sub.k) by the algorithm in [Yang, et al., 2015]. If yes, go to Step 5.

(94) Step 2:

(95) If k.Math.F and A.sub.i(n[i])=0, then:

(96) 2.1. +.sub.i=+.sub.i(S, S) (or .sub.i(D, S) if it is D-S case);

(97) 2.2. Reset the robots' waiting time by the algorithm in [Yang, et al., 2015] with cycle time , then go to Step 5.

(98) Step 3:

(99) If k.Math.F and A.sub.i(n[i])0, then:

(100) 3.1. For mS.sub.i, calculate .sub.m's, by (18) or (19).

(101) 3.2. If =min{.sub.p|pS.sub.i}=.sub.i, do:

(102) 3.2.1. If it belongs to the first case in (19), then:

(103) 3.2.1.1. In EST.sub.i or B.sub.i, for p.Math.S.sub.i, if p.Math.L, .sub.p((b[p].sub._.sub.1)1)=A.sub.p((b[p].sub._.sub.1)1)+, otherwise .sub.p0=A.sub.p0+.

(104) 3.2.1.2. In EST.sub.i or B.sub.i, if pS.sub.i and p.Math.F, set .sub.pj=A.sub.pj+A.sub.i(n[i])/(.sub.pS.sub.iB[p]), j D[p] (or j.sub.n[p]\{n[p]} if pL), .sub.p((b[p].sub._.sub.1)1)=A.sub.p((b[p].sub._.sub.1)1)+.sub.qS.sub.p.sub.{p}B[q]A.sub.i(n[i])/(.sub.pS.sub.iB[p])+ (or .sub.p0=A.sub.p0+ if pL), and .sub.p(n[p])=A.sub.p(n[p]).sub.qS.sub.pB[q]A.sub.i(n[i])/(.sub.pS.sub.iB[p]).

(105) 3.2.1.3. In EST.sub.i, if pS.sub.1 and pF, set .sub.pj=A.sub.pj+A.sub.i(n[i]/(.sub.pS.sub.iB[p]), jD[p], .sub.p((b[p].sub._.sub.1)1)=A.sub.p((b[p].sub._.sub.1)1)+

(106) ${}_{\mathrm{pj}}=A_{\mathrm{pj}}+A_{i\left(n\left[i\right]\right)}/\left(\underset{p{S}_i}{.Math.}B\left[p\right]\right),jD\left[p\right],{}_{p\left(\left(b\left[p\right]\_1\right)-1\right)}=A_{p\left(\left(b\left[p\right]\_1\right)-1\right)}+\underset{q{S}_{p\_1}}{.Math.}B\left[q\right]A_{i\left(n\left[i\right]\right)}/\left(\underset{p{S}_i}{.Math.}B\left[p\right]\right)+,{}_{p\left(\left(b\left[p\right]\_d\right)-1\right)}=A_{p\left(\left(b\left[p\right]\_d\right)-1\right)}+\left(\underset{q{S}_{p\_d}}{.Math.}B\left[q\right]+1\right)A_{i\left(n\left[i\right]\right)}/\left(\underset{p{S}_i}{.Math.}B\left[p\right]\right),d\left\{2,3,\mathrm{.Math.},f\left[p\right]\right\},\mathrm{and}{}_{p\left(n\left[p\right]\right)}=A_{p\left(n\left[p\right]\right)}-\underset{q{S}_p}{.Math.}B\left[q\right]A_{i\left(n\left[i\right]\right)}/\left(\underset{p{S}_i}{.Math.}B\left[p\right]\right).$

(107) 3.2.1.4. Go to Step 5.

(108) 3.2.2. If it belongs to the second/third case in (19), set the robot waiting time by repeating Steps 3.2.1.1-3.2.1.4, in doing so, one needs to replace A.sub.i(n[i])/(.sub.pS.sub.iB[p]) and =.sub.i(S,S)A.sub.i(n[i]) there with =.sub.i(S,S)/(.sub.pS.sub.iB[p]+1) (or .sub.i(D,S)/(.sub.pS.sub.iB[p]+1) if it belongs to the third case).

(109) 3.3. If =min{.sub.p|pS.sub.i}=.sub.f.sub.i, set the robot waiting time by repeating Procedures in 3.2.1.1 to 3.2.1.4 with both A.sub.i(n[i])/(.sub.pS.sub.iB[p]) and =.sub.i(S,S)A.sub.i(n[i]) being replaced by =.sub.f, then, back to Step 3.1.

(110) Step 4: If kF, then:

(111) 4.1. Find the optimal cycle time +.sub.q for C.sub.k with EST.sub.k.sub._.sub.q (or ST.sub.k.sub._.sub.q), q.sub.f[k], by repeating Steps 2 and 3.

(112) 4.2. +max{.sub.1, .sub.2, . . . , .sub.f[k]}.

(113) 4.3. Find the O.sup.2CS for ST.sub.k by resetting the robot waiting time with cycle time by using the algorithm in [Yang, et al., 2015].

(114) Step 5:

(115) Stop and output the schedule.

(116) With the above analysis, one can find the O.sup.2CS for a process-dominant treelike hybrid K-cluster tool as follows. One finds the O.sup.2CS for the smallest ST, say ST.sub.j with j=max.sub.lF{l} and its ESTs first. Then, do that for the ST that is larger than ST.sub.j. Continue this process until it is done for the K-cluster tool to find the final solution. However, by Algorithm 1, it requires that, for an EST.sub.k, Condition (13) or (14) is violated for tool pair C.sub.k and C.sub.i only. This may not hold for general cases. To solve this problem, the O.sup.2CS for the ESTs of ST.sub.j can be found as follows. Based on the O.sup.2CS of ST.sub.j, for EST.sub.j1 with C.sub.j1 being not a fork, the above requirement must be satisfied. Thus, one can find the O.sup.2CS for EST.sub.j1. Thereafter, one can do that for EST.sub.j2, until to EST.sub.i such that the upstream adjacent tool of C.sub.i is a fork, and in these processes the above requirement is always satisfied. Thus, one presents the following algorithm.

(117) Algorithm 2:

(118) Find an O.sup.2CS for a process-dominant treelike hybrid K-cluster tool.

(119) Step 1:

(120) =max{.sub.1, .sub.2, . . . , .sub.K}.

(121) Step 2:

(122) Check the existence of an OSLB by the algorithm in [Yang et al., 2015]. Then:

(123) 2.1. If yes, find the schedule and go to Step 4.

(124) 2.2. Otherwise find the set F such that lF, find the fork tool C.sub.j with j=max.sub.lF{l}, and go to Step 3.

(125) Step 3:

(126) Find the O.sup.2CSs for ST.sub.j and all of its EST.sub.k's:

(127) 3.1. Find the O.sup.2CS for ST.sub.j.

(128) 3.2. Find the O.sup.2CS for all of the EST.sub.k's of ST.sub.j:

(129) 3.2.1. Find k such that C.sub.k is the upstream adjacent tool of C.sub.j.

(130) 3.2.2. If C.sub.k is a fork tool, go to Step 3.3; otherwise proceed to execute Step 3.2.3.

(131) 3.2.3. Find the O.sup.2CS for EST.sub.k by using Algorithm 1.

(132) 3.2.4. Let i=k, if i=1, go to Step 4; otherwise find k such that C.sub.k is the upstream adjacent tool of C.sub.i, and go to Step 3.2.2.

(133) 3.3. If FF\{j}, go back to Step 2.2.

(134) Step 4:

(135) End and output the schedule.

(136) Notice that, for a process-dominant treelike hybrid K-cluster tool, the number of Bs+the number of STs+the number of ESTs must be less than K. Also, any B or ST, or EST contains no more than K tools. Given any of B, ST, and EST, one needs to calculate the optimal cycle time at most (K1) times by increasing each time. Thus, the computational complexity is O(K.sup.2). With K being limited in practice, the method presented is efficient and is applicable to industrial cases.

D. Illustrative Examples

(137) This section uses two examples to show the application of the disclosed method.

Example 1

(138) It is a treelike hybrid 3-cluster tool, where C.sub.1 is a fork tool and its adjacent downstream tools are C.sub.2 and C.sub.3. Furthermore, C.sub.2 and C.sub.3 are single-arm tools, and C.sub.1 is a dual-arm tool. Their activity times are as follows. For C.sub.1, (.sub.10, .sub.11, .sub.12, .sub.13, .sub.1, .sub.1)=(0, 77, 0, 0, 23, 1); for C.sub.2, (.sub.20, .sub.21, .sub.22, .sub.2, .sub.2)=(0, 75, 79, 4, 1); and for C.sub.3, (.sub.30, .sub.31, .sub.32, .sub.3, .sub.3)=(0, 71, 69, 6, 1).

(139) For C.sub.1, one has .sub.10=23 s, .sub.11=100 s, .sub.12=23 s, .sub.13=23 s, .sub.11=(n[1]+1)(.sub.1+.sub.1)=424=96 s, and .sub.1=100 s. For C.sub.2, one has .sub.20=19 s, .sub.21=94 s, .sub.22=98 s, .sub.21=2(n[2]+1)(.sub.2+.sub.2)=65=30 s and .sub.2=98 s. For C.sub.3, one has .sub.30=27 s, .sub.31=98 s, .sub.32=96 s, .sub.31=2(n[3]+1)(.sub.3+.sub.3)=67=42 s and .sub.3=98 s. Since all the individual tools are process-bound, this 3-cluster tool is process-dominant, and one lets =.sub.1=.sub.2=.sub.3==.sub.1=100 s. By the algorithm provided in [Yang, et al., 2015], the robots' waiting time is set as .sub.20=6 s, .sub.21=2 s, and .sub.22=.sub.21.sub.20.sub.21=1003062=62 s; .sub.30=2 s, .sub.31=4 s, and .sub.32=.sub.31.sub.30.sub.31=1004224=52 s. Thus, for C.sub.1, as (4.sub.2+3.sub.2+.sub.22).sub.1=100(19+62)23=4<0 and (4.sub.3+3.sub.3+.sub.32).sub.1=100(27+52)23=2<0, or (14) is violated and there is no OSLB. Thus one needs to find an optimal cycle time by Algorithm 2.

(140) By Algorithm 2, one has .sub.2=.sub.2(D, S)/n[2]=4/2=2 s, .sub.3=.sub.3(D, S)/n[3]=2/2=1 s, =max{.sub.2, .sub.3}=2 s, and =102 s. Then, let A.sub.ij=.sub.ij, i.sub.3\{1} and j.sub.i(n[i]), where .sub.ij is obtained by the algorithm provided in [Yang, et al., 2015]. By Algorithm 2, the robot waiting time is set as .sub.30=A.sub.30+=4 s, .sub.31=A.sub.31+=6 s, .sub.32=A.sub.32=50 s, .sub.20=A.sub.20+=8 s, .sub.21=A.sub.21+=4 s, .sub.22=A.sub.22=60 s, .sub.10=A.sub.10+=6 s, and .sub.11=.sub.12=.sub.13=0. In this way, the minimal cycle time and optimal one-wafer cyclic schedule is obtained and it is shown by the Gantt chart in FIG. 6.

Example 2

(141) It is from [Yang, et al., 2015]. A treelike hybrid 5-cluster tool with C.sub.2 be a fork tool, and its adjacent downstream tools are C.sub.3 and C.sub.5. The tool C.sub.4 is the downstream tool of C.sub.3, and C.sub.2 is the downstream tool of C.sub.1. Furthermore, C.sub.1 is a dual-arm tool and the others are single-arm tools. Their activity time is as follows: for C.sub.1, one has (.sub.10, .sub.11, .sub.1, .sub.1)=(0, 61.5, 0, 28.5, 0.5); for C.sub.2, one has (.sub.20, .sub.21, .sub.22, .sub.2, .sub.2)=(0, 0, 0, 10, 1); for C.sub.3, one has (.sub.30, .sub.31, .sub.32, .sub.33, .sub.3, .sub.3)=(0, 56, 0, 58, 7, 1); for C.sub.4, one has (.sub.40, .sub.41, .sub.42, .sub.43, .sub.4, .sub.4)=(0, 56, 66, 65, 5, 1); and for C.sub.5, one has (.sub.50, .sub.51, .sub.52, .sub.5, .sub.5)=(0, 48, 50, 6, 1).

(142) From [Yang, et al., 2015], the lower bound of cycle time of the system is ==90 s. With ==90 s, the robot waiting time is set as follows. For C.sub.4, .sub.40=11 s, .sub.41=1 s, .sub.42=2 s, and .sub.43=28 s are set. For C.sub.5, .sub.50=15 s, .sub.51=13 s, and .sub.52=20 s are set. For C.sub.3, .sub.31=8 s, .sub.30=3 s, .sub.32=1 s, and .sub.33=14 s are set. For C.sub.2, .sub.20=2 s, .sub.21=0, and .sub.22=22 s are set. Then, for C.sub.1, one has (4.sub.2+3.sub.2+.sub.22).sub.1=90(43+22)28.5=3.5<0, or there is no OSLB. Therefore, one needs to find the minimal cycle time by Algorithm 2.

(143) With .sub.22=22>0, .sub.52=20>0, .sub.33=14>0, and .sub.43=28>0, one has .sub.pS.sub.2B[p]=(B[2]+B[3]+B[4]+B[5])=(1+2+2+1)=6 and .sub.2(D,S)=(4.sub.2+3.sub.2+.sub.22)+.sub.1=3.5 s. Then, .sub.2=.sub.2(D, S)/(.sub.pS.sub.2B[p]+1)=3.5/7=0.5 s, .sub.3=.sub.33/(B[3]+B[4])=14/3 s, .sub.4=.sub.43/B[4]=28/2=14 s, .sub.5=.sub.52/B[5]=20/1=20 s, =min{.sub.2, .sub.3, .sub.4, .sub.5}=0.5 s, and =+=90.5 s. Let .sub.ij=.sub.ij, i.sub.5\{1} and j.sub.i(n[i]), where .sub.ij's are obtained by the algorithm in [Yang, et al., 2015] with cycle time ==90 s as given above. Then, by Algorithm 2, the robot waiting time is set as follows. For C.sub.4, .sub.40=A.sub.40+=11.5 s, .sub.41=A.sub.41+=1.5 s, .sub.42=A.sub.42+2.5 s, and .sub.43=A.sub.43227 s; for C.sub.3, .sub.31=A.sub.31+2+=9.5 s, .sub.30=A.sub.30+=3.5 s, .sub.32=A.sub.32+=1.5 s, and .sub.33=A.sub.3322=12 s; for C.sub.5, .sub.50=A.sub.50+15.5 s, .sub.51=A.sub.51+=13.5 s, and .sub.52=A.sub.52=19.5 s; for C.sub.2, .sub.20=A.sub.20+4+=4.5 s, .sub.21=A.sub.21++=1 s, and .sub.22=A.sub.224=19 s; and for C.sub.1, .sub.10=.sub.11=3.5 s and .sub.11=.sub.12=0. In this way, an optimal one-wafer cyclic schedule is obtained and its Gantt chart is shown in FIG. 7.

E. The Present Invention

(144) The present invention is developed based on the theoretical development in Sections A-C above.

(145) An aspect of the present invention is to provide a computer-implemented method for scheduling a treelike hybrid K-cluster tool to generate a one-wafer cyclic schedule. The K-cluster tool has K single-cluster tools.

(146) The method comprises given a value of cycle time, generating a part of the schedule for a section of the K-cluster tool by performing a generating algorithm. The section of the K-cluster tool is either an EST or a ST. The generating algorithm is based on Algorithm 1 above. In particular, the generating algorithm for EST.sub.k or ST.sub.k, with C.sub.i being a downstream adjacent tool of C.sub.k and with being the given value of cycle time for EST.sub.i, ST.sub.i or B.sub.i comprises Step 3 of Algorithm 1 under a condition that the checking result of Step 1 is negative. Preferably, the generating algorithm further comprises Step 2 and Step 4 of Algorithm 1, provided that the checking result of Step 1 is negative.

(147) The method is further elaborated based on Algorithm 2 as follows. First identify ST.sub.j, with j=max.sub.lF{l}, and one or more ESTs of ST.sub.j in the K-cluster tool. The one or more ESTs are denoted as EST.sub.j1, EST.sub.j2 down to EST.sub.i such that an upstream adjacent tool of C.sub.i is a fork tool. A first part of the schedule for ST.sub.j is first determined by performing the generating algorithm. Then determine a second part of the schedule for EST.sub.j1 based on the first part of the schedule. Determining one part of the schedule EST.sub.jm based on a determined part of the schedule for EST.sub.jm+1 is repeated until the one or more ESTs are scheduled.

(148) 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.

(149) In particular, the method disclosed herein can be implemented in a treelike hybrid K-cluster tool if the K-cluster tool includes one or more processors. The one or more processors are configured to execute a process of scheduling the K-cluster tool according to one of the embodiments of the disclosed method.

(150) 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.