Optimal one-wafer scheduling of single-arm multi-cluster tools with tree-like topology
10001773 ยท 2018-06-19
Assignee
Inventors
Cpc classification
Y02P90/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
International classification
G05B19/41
PHYSICS
Abstract
The scheduling problem of a multi-cluster tool with a tree topology whose bottleneck tool is process-bound is investigated. A method for scheduling the multi-cluster tool to thereby generate an optimal one-wafer cyclic schedule for this multi-cluster tool is provided. A Petri net (PN) model is developed for the multi-cluster tool by explicitly modeling robot waiting times such that a schedule is determined by setting the robot waiting times. Based on the PN model, sufficient and necessary conditions under which a one-wafer cyclic schedule exists are derived and it is shown that an optimal one-wafer cyclic schedule can be always found. Then, efficient algorithms are given to find the optimal cycle time and its optimal schedule. Examples are used to demonstrate the scheduling method.
Claims
1. A method for controlling robots of a tree-like multi-cluster tool in wafer processing, the multi-cluster tool comprising K single-cluster tools denoted as C.sub.i, i=1, 2, . . . , K, the single-cluster tool C.sub.i having a robot R.sub.i for wafer handling, the multi-cluster tool being decomposable into a plurality of cluster-tool-chains (CTCs) each having a serial topology, an individual CTC consisting of single-cluster tools C.sub.i, C.sub.i+1, . . . C.sub.i being denoted as CTC[i, i], processing steps performed by C.sub.i being indexed from 0 to n[i], a first processing step of C.sub.i having an index 0 and being a step of loading a wafer from a loadlock or a buffer module of C.sub.i to R.sub.i, the method comprising: determining values of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], wherein .sub.ij is a robot waiting time for R.sub.i to wait at a j-th step in C.sub.i before unloading the wafer from a process module used for performing the j-th step in C.sub.i; for any i{1, 2, . . . , K} and any j{0, 1, . . . , n[i]}, when R.sub.i arrives at the process module for the j-th step for unloading the wafer therefrom in the j-th step performed in C.sub.i, waiting, by R.sub.i, for the robot waiting time of .sub.ij; after the robot waiting time of .sub.ij expires, unloading, by R.sub.i, the wafer from the process module for the j-th step; after the wafer is unloaded from the process module for the j-th step, transporting, by R.sub.i, the wafer to the process module for a next step that is either a (j+1)th step, or a zeroth step when j=n[i]; and after the wafer arrives at the process module for the next step, loading, by R.sub.i, the wafer to the second process module; wherein the determining of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], comprises: determining candidate values of .sub.ij for the single-cluster tools in an individual CTC by performing a CTC-Check algorithm under a constraint that is equal to a lower bound of cycle time of the multi-cluster tool, the lower bound of cycle time of the multi-cluster tool being a fundamental period of a bottleneck tool among the K single-cluster tools; responsive to finding that the candidate .sub.ij values for the individual CTC are non-negative, setting the candidate .sub.ij values as the determined values of .sub.ij for the individual CTC; and responsive to finding that at least one of the candidate .sub.ij values for the individual CTC is negative, performing: determining a minimum cycle time for the individual CTC; and determining the values of .sub.ij for the individual CTC as the candidate values of .sub.ij obtained by performing the CTC-Check algorithm under a revised constraint that the determined minimum cycle time for the individual CTC; wherein the CTC-Check algorithm for CTC[f, l] is configured to compute the candidate values of .sub.ij such that .sub.i(n[i]) is minimized for each value of i selected from N.sub.[f, l1], and the CTC-Check algorithm comprises the steps of: setting .sub.ij=min{(4.sub.l+3.sub.l+.sub.l(j+1)), 2(n[l]+1)(.sub.l+.sub.l).sub.m.sub.
.sub.i(b[i]1)=min{.sub.(i+1)0(4.sub.i+3.sub.i), 2(n[i]+1)(.sub.i+.sub.i)};
.sub.ij=min{(4.sub.i+3.sub.i+.sub.i(j+1)), .sub.02(n[i]+1)(.sub.i+.sub.i).sub.m.sub.
.sub.i(n[i])=2(n[i]+1)(.sub.i+.sub.i).sub.m=0.sup.n[i]1.sub.im; and
.sub.i0=.sub.i0, where: b[l] is an index denoting a step of putting the wafer in C.sub.l to a buffer module shared by C.sub.l and C.sub.l+1; .sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1), iN.sub.K and jN.sub.n[i]; .sub.i0=.sub.i0+4.sub.i+3.sub.i+.sub.i(n[i]), iN.sub.K; is a cycle time of the multi-cluster tool; .sub.ij is a time taken in processing the wafer at the j-th step in C.sub.i; .sub.ij is a wafer sojourn time at the j-th step in C.sub.i; .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; N.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 robots R.sub.i, i=1, 2, . . . , K, are single-arm.
3. A method for controlling robots of a tree-like multi-cluster tool in wafer processing, the multi-cluster tool comprising K single-cluster tools denoted as C.sub.i, i=1, 2, . . . , K, the single-cluster tool C.sub.i having a robot R.sub.i for wafer handling, the multi-cluster tool being decomposable into a plurality of cluster-tool-chains (CTCs) each having a serial topology, an individual CTC consisting of single-cluster tools C.sub.i, C.sub.i+1, . . . C.sub.i being denoted as CTC[i, i], processing steps performed by C.sub.i being indexed from 0 to n[i], a first processing step of C.sub.i having an index 0 and being a step of loading a wafer from a loadlock or a buffer module of C.sub.i to R.sub.i, the method comprising: determining values of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], wherein .sub.ij is a robot waiting time for R.sub.i to wait at a j-th step in C.sub.i before unloading the wafer from a process module used for performing the j-th step in C.sub.i; for any i{1, 2, . . . , K} and any j{0, 1, . . . , n[i]}, when R.sub.i arrives at the process module for the j-th step for unloading the wafer therefrom in the j-th step performed in C.sub.i, waiting, by R.sub.i, for the robot waiting time of .sub.ij; after the robot waiting time of .sub.ij expires, unloading, by R.sub.i, the wafer from the process module for the j-th step; after the wafer is unloaded from the process module for the j-th step, transporting, by R.sub.i, the wafer to the process module for a next step that is either a (j+1)th step, or a zeroth step when j=n[i]; and after the wafer arrives at the process module for the next step, loading, by R.sub.i, the wafer to the second process module; wherein the determining of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], comprises: identifying an L-CTC set consisting of first individual CTCs each having a leaf tool therein, whereby one or more second individual CTCs not in the L-CTC set are also identified; for each of the first individual CTCs, determining a minimum cycle time and then determining the values of .sub.ij by performing a CTC-Check algorithm under a constraint that is equal to the determined minimum cycle time; for each second individual CTC, determining candidate values of .sub.ij for each single-cluster tool therein by performing the CTC-Check algorithm under an initial constraint that is equal to a maximum value of the minimum cycle times already determined for the first individual CTCs; responsive to finding that the candidate .sub.ij values for the second individual CTC are non-negative, setting the candidate .sub.ij values as the determined values of .sub.ij for the second individual CTC; and responsive to finding that at least one of the candidate .sub.ij values for the second individual CTC is negative, performing: determining a minimum cycle time for the second individual CTC; and determining the values of .sub.ij for the second individual CTC as the candidate values of .sub.ij obtained by performing the CTC-Check algorithm under a revised constraint that is equal to the determined minimum cycle time for the second individual CTC; wherein the CTC-Check algorithm for CTC[f, l] is configured to compute the candidate values of .sub.ij such that .sub.i(n[i]) is minimized for each value of i selected from N.sub.[f, l1], and the CTC-Check algorithm comprises the steps of: setting .sub.ij=min{(4.sub.l+3.sub.l+.sub.l(j+1)), 2(n[l]+1)(.sub.l+.sub.l).sub.m.sub.
.sub.i(b[i]1)=min{.sub.(i+1)0(4.sub.i+3.sub.i), 2(n[i]+1)(.sub.i+.sub.i)};
.sub.ij=min{(4.sub.i+3.sub.i+.sub.i(j+1)), .sub.02(n[i]+1)(.sub.i+.sub.i).sub.m.sub.
.sub.i(n[i])=2(n[i]+1)(.sub.i+.sub.i).sub.m=0.sup.n[i]1.sub.im; and
.sub.i0=.sub.i0, where: b[l] is an index denoting a step of putting the wafer in C.sub.l to a buffer module shared by C.sub.l and C.sub.l+1; .sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1), iN.sub.K and jN.sub.n[i]; .sub.i0=.sub.i0+4.sub.i+3.sub.i+.sub.i(n[i]), iN.sub.K; is a cycle time of the multi-cluster tool; .sub.ij is a time taken in processing the wafer at the j-th step in C.sub.i; .sub.ij is a wafer sojourn time at the j-th step in C.sub.i; .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; N.sub.L={1, 2, . . . , L} for a positive integer L; and .sub.L=N.sub.L{0}.
4. The method of claim 3, wherein the robots R.sub.i, i=1, 2, . . . , K, are single-arm.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1)
(2)
(3)
(4)
DETAILED DESCRIPTION
(5) Since a one-wafer cyclic schedule is easy to implement and understand by a practitioner, it gives rise to a question if there exists a one-wafer cyclic schedule for a tree-like multi-cluster tool and how such a schedule can be found if it exists. The present work provides a solution of schedulability and a method for scheduling the tree-like multi-cluster tool with the one-wafer cyclic schedule. Since the robot task time is much shorter than the wafer processing time in practice [Kim et al., 2003; and Lopez and Wood, 2003], it is reasonable to assume that the bottleneck tool of a multi-cluster tool is process-bound, or it is process-dominant. Hence, we address a process-dominant tree-like multi-cluster tool in this work. The key for scheduling a K-cluster tool is to coordinate the activities of the multiple robots in accessing the BMs. In scheduling single-cluster tools, Wu et al. [2008] and Wu and Zhou [2010a] find that it is crucial to determine when a robot should wait and how long it should wait if necessary. By following this idea, the present work develops a PN model for a tree-like multi-cluster tool with the robot waiting being explicitly modeled. With the model, a schedule for the system is parameterized by the robot waiting time. For a process-dominant tree-like multi-cluster tool, necessary and sufficient conditions under which a one-wafer cyclic schedule exists are derived. It is then shown that there is always a one-wafer cyclic schedule. An efficient algorithm is developed and disclosed herein to find the minimal cycle time and the one-wafer cyclic schedule.
(6) A. System Modeling by Petri Net
(7) A.1. Tree-like Multi-cluster Tool
(8) The configuration of a tree-like multi-cluster tool is illustrated in
(9) As done in [Chan et al. 2011b], for a K-tree-cluster tool, we assume: 1) the root has two LLs; 2) a BM shared by two adjacent tools can hold one wafer at a time without a processing function; 3) a PM can process one wafer at a time; 4) all the wafers in a cassette should be processed in an identical sequence specified in the recipe and visit a PM no more than once (except for a BM); 5) the loading, unloading, moving time of the robots, and the processing time of a wafer at a PM are deterministic and known; 6) the loading and unloading time of a robot is same, and the robot moving time from a PM to another is also same regardless of whether it carries a wafer or not; and 7) there is no parallel module, or only one PM is configured for each processing step.
(10) With two LLs, while one lot of wafers in one LL is being processed, the other LL can be used for loading/unloading another lot of wafers. In this way, a multi-cluster tool can work consecutively without interruption. Thus, it operates in a steady state at most of time and there are always wafers to be processed. This is equivalent to that the LLs have infinite capacity.
(11) A.2. Operation Process
(12) The wafer fabrication process can be illustrated by the 5-tree-cluster tool shown in
(13) In C.sub.i, iN.sub.K\{1}, the BM denoted as PM.sub.i0 can be viewed as a virtual LL for injecting wafers from an upstream tool, while the other BM(s) PM.sub.ij (j>0) can be viewed as a virtual process module(s). The BM shared by adjacent tools C.sub.i and C.sub.j is called an outgoing buffer for C.sub.i and an incoming one for C.sub.j. The LLs in C.sub.1 can be treated as an incoming buffer with infinite capacity. There are a number of processing steps in each individual tool and a BM connecting two tools is treated as a processing step with processing time being zero. Let denote the index set of leaf tools and DI(C.sub.i) the index set of the immediate downstream tools of C.sub.i (i.Math.). We have DI(C.sub.i)= if i. Further, let PM.sub.i(b[i,k]) denote the BM shared by C.sub.i and C.sub.k, kDI(C.sub.i), with PM.sub.k0 being the incoming buffer or virtual LL for C.sub.k. It is called Step b[i,k] for C.sub.i and Step 0 for C.sub.k, respectively. Assume that, except the incoming buffer, there are n[i] steps in C.sub.i. Then, there are n[i]+1 steps in C.sub.i denoted as PS.sub.i0, PS.sub.i1, . . . , PS.sub.i(n[i]) with PS.sub.i0 and PS.sub.i(b[i,k]) being the incoming and outgoing steps. Let R.sub.i denote the robot in C.sub.i. As discussed above, at most of time, a multi-cluster tool operates in a steady state. Under such a state, for a process-dominant multi-cluster tool, a backward strategy [Dawande 2002] is optimal for each individual tool.
(14) A.3. Modeling the Wafer Flow
(15) We model a multi-cluster tool system by extending the resource-oriented PN (ROPN) proposed in [Wu, 1999; Wu et al., 2008a and 2008b; and Wu and Zhou, 2009]. It is a finite capacity PN=(P, T, I, O, M, K), where P is a finite set of places; T is a finite set of transitions, PT, and PT=; I:PT.fwdarw.N={0, 1, 2, . . . } is an input function; O:PT.fwdarw.N is an output function; M:P.fwdarw.N is a marking denoting the number of tokens in P with M.sub.0 being the initial marking; and K:P.fwdarw.N\{0} is a capacity function with K(p) being the number of tokens that p can hold at a time. The basic concept, transition enabling and firing rules of Petri nets (PN) can be found in [Zhou et al., 1998; Wu and Zhou, 2009].
(16) To model a multi-cluster tool, one needs to model the individual tools and the BMs. The behavior of Step j in C.sub.i is modeled as follows. The PM for Step j in C.sub.i with i1 and j0 is modeled by timed place p.sub.ij with K(p.sub.ij)=1. Place p.sub.10 models the LLs in C.sub.1 with K(p.sub.10)=. Places z.sub.ij and d.sub.ij model R.sub.i's holding a wafer (token) for loading into p.sub.ij and moving from Steps j to j+1 (or Step 0 if j=n[i]), respectively. Place q.sub.ij models R.sub.i's waiting at Step j for unloading a wafer there. Transitions t.sub.ij and u.sub.ij model R.sub.i's loading and unloading a wafer into and from PM.sub.ij, respectively. Then, with arcs (z.sub.ij, t.sub.ij), (t.sub.ij, p.sub.ij), (p.sub.ij, u.sub.ij), (q.sub.ij, u.sub.ij), and (u.sub.ij, d.sub.ij), of the PN model for Step j in C.sub.i is obtained as shown in
(17) With the model for a step as a module, tool C.sub.i is modeled as follows. Place r.sub.i models R.sub.i with K(r.sub.i)=1, meaning that, with only one arm, the robot can hold one wafer at a time. Timed y.sub.ij with arcs (r.sub.i, y.sub.ij) and (y.sub.ij, q.sub.ij) for connecting r.sub.i and q.sub.ij, representing that R.sub.i moves from Steps j+2 to j, j=0, 1, . . . , n[i]2 (y.sub.i(n[i]1) for moving from Steps 0 to n[i]1, and y.sub.i(n[i]) for moving from Steps 1 to n[i]). Finally, x.sub.ij, j=0, 1, 2, . . . , n[i]1, are added between d.sub.ij and z.sub.i(j+1) with arcs (d.sub.ij, x.sub.ij) and (x.sub.ij, z.sub.i(j+1)); and x.sub.i(n[i]) is added between d.sub.i(n[i]) and z.sub.i0 with arcs (d.sub.i(n[i]), x.sub.i(n[i])) and (x.sub.i(n[i]), z.sub.i0). In this way, the modeling of C.sub.i is completed as shown in
(18) A BM linking C.sub.i and C.sub.a, aDI(C.sub.i), is denoted by PM.sub.i(b[i,a]) in C.sub.i and PM.sub.a0 in C.sub.a. Thus, p.sub.i(b[i,a]) and p.sub.a0 with p.sub.i(b[i,a])=p.sub.a0 are used to model the BM. Then, Step b[i,a] for C.sub.i is modeled by {p.sub.i(b[i,a]), q.sub.i(b[i,a]), z.sub.i(b[i,a]), d.sub.i(b[i,a]), t.sub.i(b[i,a]), u.sub.i(b[i,a])} and Step 0 for C.sub.a by {P.sub.a0, q.sub.a0, z.sub.a0, d.sub.a0, t.sub.a0, u.sub.a0}, respectively. Thereafter, when we refer to Step b[i,a] in C.sub.i, we use p.sub.i(b[i,a]), whereas for Step 0 in C.sub.a we use p.sub.a0. It should be pointed out that Step 0 in C.sub.1 (the LLs) is not shared with any other tool and there is no outgoing buffer in a leaf tool C.sub.L. The PN model for the BM linking C.sub.i and C.sub.a is shown in
(19) With the PN structure developed, marking M.sub.0 is set as follows. To describe the idle state of the system, a special type of token called V-token representing a virtual wafer is introduced. As mentioned above, there is a process-bound bottleneck tool in the system. Hence, in the steady state, if there is a wafer being processed in every PM.sub.ij with j0, the system reaches its maximal throughput. Let denote the index set of non-leaf tools N.sub.K= with =. Then, M.sub.0 is set as follows. For C.sub.i, iN.sub.K, set M.sub.0(p.sub.ij)=1 for j1 with a V-token, M.sub.0(p.sub.ij)=0, j=1, and M.sub.0(p.sub.10)=n; M.sub.0(q.sub.ij)=M.sub.0(z.sub.ij)=M.sub.0(d.sub.ij)=0 for any j; and M.sub.0(r.sub.i)=1. It is assumed that the token in p.sub.i(b[i,a]) enables u.sub.a0, where aDI(C.sub.i).
(20) It is easy to show that the obtained PN is deadlock-prone. To make it deadlock-free, let .sub.n=N.sub.n{0}, a control policy on y.sub.ij's is defined as follows.
(21) Definition 1: At marking M, y.sub.ij, iN.sub.K and j.sub.n[i]1, is said to be control-enabled if M(p.sub.i(j+1))=0; y.sub.1(n[i]) is control-enabled if M(p.sub.1(n[i]))=1; and y.sub.i(n[i]), iN.sub.K\{1}, is control-enabled if M(p.sub.i0)=0.
(22) With Definition 1, the PN for an individual tool is shown to be deadlock-free [Wu et al., 2008a]. Thereafter, it is assumed that the PN is controlled by the policy given in Definition 1.
(23) In the PN model for a BM shared by C.sub.i and C.sub.a shown in
(24) Definition 2: Define the unique color of transition t.sub.i as C(t.sub.i)={c.sub.i}.
(25) By Definition 2, the colors for u.sub.i(b[i,a]) and u.sub.a0 are c.sub.i(b[i,a]) and c.sub.a0, respectively. Then, the color for a token in p.sub.i(b[i,a]) or p.sub.a0 is defined as follows.
(26) Definition 3: For i, aDI(C.sub.i), a token entering p.sub.i(b[i,a]) by firing t.sub.i(b[i,a]) in C.sub.i has color c.sub.a0, while a token entering p.sub.a0 by firing t.sub.a0 in C.sub.a has color c.sub.i(b[i,a]).
(27) It is easy to check that, by Definitions 2 and 3, the model is conflict-free. The obtained model can also describe the behavior of initial and final transient processes as explained as follows. At M.sub.0, y.sub.i0 is enabled and fires leading to M.sub.1(q.sub.i0)=1. By starting from M.sub.1, transition u.sub.10 fires and W.sub.1 representing the first wafer is unloaded from p.sub.10. In this way, every time when u.sub.10 fires, a token for a real wafer is delivered into p.sub.11. With the transition enabling and firing rules, the model evolves to reach a marking M such that every V-token is removed from the model and is replaced by a token for a real wafer, or a steady state is reached. The evolution from M.sub.0 to M presents the initial transient process. Similarly, when the system needs to stop working, every time when u.sub.10 fires, a V-token is delivered into p.sub.11, the model can evolve back to marking M.sub.0, which describes the final transient process.
(28) A.4. Modeling Activity Time
(29) To describe the temporal aspect, time is associated with both transitions and places. It follows from Kim et al. [2003] and Lee and Lee [2006] that the time for the robot to move from one step to another is a constant, and so is the time for the robot to load/unload a wafer into/from a PM. The symbols and time durations for places and transitions are listed in TABLE 1.
(30) TABLE-US-00001 TABLE 1 The time durations associated with transitions and places (iN.sub.n, j.sub.n[i]). Transition or Time Symbol place Actions required .sub.i u.sub.ijT Robot R.sub.i unloads a wafer from p.sub.ij Constant .sub.i t.sub.ijT Robot R.sub.i loads a wafer into p.sub.ij .sub.i y.sub.ijT Robot R.sub.i moves from a step to Constant .sub.i another x.sub.ijT .sub.ij p.sub.ijP Wafer processing in p.sub.ij Constant .sub.ij .sub.ij p.sub.ijP Wafter sojourn in p.sub.ij .sub.ij .sub.ij q.sub.ijP Robot R.sub.i waits before unloading a [0, ) wafer from p.sub.ij z.sub.ij, d.sub.ijP No time is associated 0
B. Properties Of Scheduling A K-Cluster Tool
(31) This section recalls the properties of scheduling an individual tool in [Zhu et al., 2013]. For a process-dominant K-tree-cluster tool, since a backward strategy is optimal for each individual tool, with the PN model shown in
.sub.i=2(n[i]+1)(.sub.i+.sub.i)+.sub.j=0.sup.n[i].sub.ij=.sub.i1+.sub.i2, iN.sub.K,(1)
where .sub.i1=2(n[i]+1)(.sub.i+.sub.i) is R.sub.i's task time and is a constant, and .sub.i2=.sub.j=0.sup.n[i].sub.ij is the robot waiting time in a cycle.
(32) With robot waiting as an event, the time taken for completing a wafer at Step j in C.sub.i, iN.sub.K, is given by [Wu et al., 2008]
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1), iN.sub.K and jN.sub.n[i],(2)
and
.sub.i0=4.sub.i+3.sub.i+.sub.i(n[i]), iN.sub.K.(3)
(33) Note that, since a BM has no processing function, we have .sub.i0=.sub.i(b[i,a])=0, aDI(C.sub.i). With .sub.ij, .sub.i, and .sub.i being constants and .sub.ij's being variable, if .sub.ij is set to be zero, the shortest time taken for completing a wafer at Step j in C.sub.i is
.sub.ij=.sub.ij+4.sub.i+3.sub.i, iN.sub.K and j.sub.n[i].(4)
(34) A cluster tool may be scheduled such that a wafer stays in PM.sub.ij for some time after its completion, or .sub.ij.sub.ij, where .sub.ij is the wafer sojourn time in PM.sub.ij. For Step j{0, b[i,a]}, aDI(C.sub.i), or a BM, the wafer unloaded from PS.sub.ij by the f-th firing of u.sub.ij is not the one that is loaded into PS.sub.ij by the f-th firing of t.sub.ij. However, for scheduling purpose, we concern only the time needed for completing the tasks in accessing a BM but not if they are the same wafer. Hence, the virtual wafer sojourn time for Step j{0, b[i, a]}, aDI(C.sub.i), is introduced as follows. Let .sub.1 and .sub.2 be the end time point of the k-th firing of t.sub.ij and the start time point of the k-th firing of u.sub.ij, respectively. The virtual wafer sojourn time is defined as .sub.ij=.sub.2.sub.1. In this way, for all steps in C.sub.i, .sub.ij has the same meaning. Then, by replacing .sub.ij with .sub.ij in (2) and (3), the cycle time at Step j in C.sub.i is given by
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1), iN.sub.K and jN.sub.n[i],(5)
and
.sub.i0=.sub.i0+4.sub.i+3.sub.i+.sub.i(n[i]), iN.sub.K.(6)
Let .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i]), .sub.i1}. If .sub.i=.sub.i1, C.sub.i is transport-bound, otherwise it is process-bound. The manufacturing process in C.sub.i is a serial one and C.sub.i should be scheduled such that
.sub.i=.sub.i0=.sub.i1= . . . =.sub.i(n[i]) and .sub.ij.sub.ij, iN.sub.K and j.sub.n[i](7)
where .sub.i is the cycle time of C.sub.i. To find a feasible schedule, .sub.i.sub.i must hold. Given .sub.i for C.sub.i, R.sub.i should be scheduled such that .sub.i=.sub.i. Thus, .sub.i2=.sub.i.sub.i1 is the R.sub.i's waiting time in a cycle, or the schedule is a function of R.sub.i's waiting time. This implies that a one-wafer cyclic schedule for a multi-cluster tool is determined by the robots' waiting time. The key here is how to determine the minimal .sub.i's.
(35) Let denote the cycle time of a K-tree-cluster tool and .sub.i the cycle time of C.sub.i, iN.sub.K. From [Zhu et al., 2013b], it can easily show that, to obtain a one-wafer cycle schedule for a K-tree-cluster tool, .sub.1=.sub.2= . . . =.sub.K= should hold. Let C.sub.h, 1hK, be the bottleneck tool in a K-tree-cluster tool and .sub.h be its FP. Then, .sub.1=.sub.2= . . . =.sub.K=.sub.h must hold. Hence, to obtain a one-wafer cycle schedule for a K-tree-cluster tool, every individual tool should have the same cycle time and, at the same time, the multiple robots should be coordinated such that all the individual tools operate in a paced way.
(36) Assume that C.sub.i, iN.sub.K. It is scheduled to have a cycle time . Examine C.sub.i and C.sub.a, i.Math. and aDI(C.sub.i). If the system is scheduled such that, every time after R.sub.i loads a wafer into PS.sub.i(b[i, a]) by firing t.sub.i(b[i, a]), u.sub.a0 fires immediately to unload this wafer by R.sub.a, then C.sub.i and C.sub.a can operate in a paced way. If a K-tree-cluster tool is scheduled such that, any pair of C.sub.i and C.sub.a can operate in such a way, a one-wafer cyclic schedule is obtained. We then examine how C.sub.i and C.sub.a, i.Math. and aDI(C.sub.i), can be scheduled to operate in a paced way. Let .sub.i0 be the start time point for firing u.sub.i0 in C.sub.i. Between the firings of u.sub.i0 and t.sub.i(b[i, a]), the following transition firing sequence is executed: .sub.i=firing u.sub.i0 (with time.sub.i).fwdarw.x.sub.i0(.sub.i).fwdarw.t.sub.i1(.sub.i).fwdarw.y.sub.i(n[i])(.sub.i).fwdarw.robot waiting in q.sub.i(n[i])(.sub.i(n[i])).fwdarw.u.sub.i(n[i])(.sub.i).fwdarw.x.sub.i(n[i])(.sub.i).fwdarw.t.sub.i0(.sub.i).fwdarw. . . . .fwdarw.y.sub.i(b[i, a]1)(.sub.i).fwdarw.robot waiting in q.sub.i(b[i, a]1)(.sub.i(b[i, a]1)).fwdarw.u.sub.i(b[i, a]1)(.sub.i).fwdarw.x.sub.i(b[i, a]1)(.sub.i).fwdarw.t.sub.i(b[i, a])(.sub.i)
. Given a schedule for C.sub.i by setting .sub.ij's, the time taken by .sub.i is .sub.i={(n[i]+1)(b[i, a]2)}(2.sub.i+2.sub.i).sub.i+.sub.j=b[i,a]1.sup.n[i].sub.ij, if b[i, a]>1; and .sub.i=2.sub.i+.sub.i, if b[i, a]=1. Then, u.sub.a0 starts to fire at .sub.a0=.sub.i0+.sub.i, i.Math.. In other words, to make C.sub.i and C.sub.a operate in a paced way with a cycle time , u.sub.a0 should fire .sub.i time units later than the firing of u.sub.i0.
(37) With the PN model, the above requirement can be implemented by properly scheduling C.sub.i and C.sub.a as follows. At M.sub.0 that is set as above discussed, u.sub.10 fires and W.sub.1 representing the first real wafer released into the system is unloaded from p.sub.10. Then, for an mDI(C.sub.1), transition firing sequence .sub.1=firing u.sub.10(.sub.1).fwdarw.x.sub.10(.sub.1).fwdarw.t.sub.11(.sub.1).fwdarw.y.sub.1(n[1])(.sub.1).fwdarw.robot waiting in q.sub.1(n[1])(.sub.1(n[1])).fwdarw.u.sub.1(n[i])(.sub.1).fwdarw.x.sub.1(n[1])(.sub.1).fwdarw.t.sub.10(.sub.1).fwdarw. . . . .fwdarw.y.sub.1(b[1, m]1)(.sub.1).fwdarw.robot waiting in q.sub.1(b[1, m]1)(.sub.1(b[1, m]1)).fwdarw.u.sub.1(b[1, m]1)(.sub.1).fwdarw.x.sub.1(b[1, m]1)(.sub.1).fwdarw.t.sub.1(b[1, m])(.sub.1)
is executed in C.sub.1. By firing t.sub.11, W.sub.1 is loaded into PS.sub.11. After firing t.sub.1(b[1,m]), u.sub.m0 is enabled and fires. The time taken by .sub.1 is .sub.1={(n[1]+1)(b[1, m]2)}(2.sub.1+2.sub.1).sub.1+.sub.j=b[1,m]1.sup.n[1].sub.ij such that .sub.m0=.sub.10+.sub.1. Then, in C.sub.1, t.sub.1(b[1, m]) fires again after a cycle. Meanwhile, in C.sub.m, a cycle is also completed. Since the cycle time is for both C.sub.1 and C.sub.m, u.sub.m0 fires again just after t.sub.1(b[1, m]) fires. During this cycle, W.sub.2 is released into the system.
(38) By starting from the firing of u.sub.m0, transition firing sequence .sub.m=u.sub.m0(.sub.m).fwdarw.x.sub.m0(.sub.m).fwdarw.t.sub.m1(.sub.m).fwdarw.y.sub.m(n[m])(.sub.m).fwdarw.robot waiting in q.sub.m(n[m])(.sub.m(n[m])).fwdarw.u.sub.m(n[m])(.sub.m).fwdarw.x.sub.m(n[m])(.sub.m).fwdarw.t.sub.m0(.sub.m).fwdarw. . . . .fwdarw.y.sub.m(b[m, d]1)(.sub.m).fwdarw.robot waiting in q.sub.m(b[m, d]1)(.sub.m(b[m, d]1)).fwdarw.u.sub.m(b[m, d]1)(.sub.m).fwdarw.x.sub.m(b[m, d]1)(.sub.m).fwdarw.t.sub.m(b[m, d])(.sub.m)
is executed in C.sub.m, dDI(C.sub.m). After firing t.sub.m(b[m, d]), u.sub.d0 is enabled and fires. The time taken by .sub.m is .sub.m such that .sub.d0=.sub.m0+.sub.m. This process can be performed for every pair of C.sub.m and C.sub.d, dDI(C.sub.m), such that every tool in the system acts in a paced way. Notice that, after each cycle in C.sub.1, a V-token is removed from the system. When all V-tokens are removed, the steady state is reached and the system operates according to the backward one-wafer cycle schedule.
(39) Notice that, to perform the above process for C.sub.m and C.sub.d, dDI(C.sub.m), it requires that: 1) when R.sub.m arrives at p.sub.m(b[m, d]) for firing u.sub.m(b[m, d]) (t.sub.m(b[m, d])), there is a token in p.sub.m(b[m,d]) (p.sub.m(b[m, d]) is emptied); and 2) when R.sub.d arrives at p.sub.d0 for firing u.sub.d0 (t.sub.d0), there is a token in p.sub.d0 (p.sub.d0 is emptied). To make these requirements satisfied, we have the following theorem.
(40) Theorem 1: Given .sub.h as cycle time for a process-dominant K-tree-cluster tool, a one-wafer cyclic schedule exists if and only if, for any pair of C.sub.i and C.sub.a, aDI(C.sub.i), the following conditions are satisfied by determining .sub.ij's and .sub.af's:
.sub.ij=.sub.af=, j.sub.n[i] and f.sub.n[a],(8)
.sub.i(b[i, a])4.sub.a+3.sub.a+.sub.a(n[a])(9)
and
.sub.a04.sub.i+3.sub.i+.sub.i(b[i, a]1).(10)
(41) The proof of Theorem 1 is similar to that in [Zhu et al., 2013b] and omitted. By Theorem 1, to find a one-wafer cyclic schedule, the key is to determine such that (8)-(10) are satisfied by setting .sub.ij's and .sub.af's. This issue is discussed next.
(42) C. One-Wafer Cyclic Scheduling
(43) C.1. Scheduling of a Cluster-tool-chain
(44) By viewing an individual tool as a vertex, the topology of a K-tree-cluster tool is a tree (directed graph) [Cormen et al., 2001]. Let (i, j) denote the index set of the tools on the path from C.sub.i to C.sub.j, including i and j, and |(i, j)| be its cardinality. The length of the path from C.sub.i to C.sub.j is defined as the number of arcs connecting two adjacent tools on a path and is denoted by Len(C.sub.i, C.sub.j)=|.sub.(i, j)|1. If there is a path from C.sub.i to C.sub.j and Len(C.sub.1, C.sub.i)<Len(C.sub.1, C.sub.j), C.sub.i is an upstream tool of C.sub.j and C.sub.j is a downstream one of C.sub.i. Let O-Deg(C.sub.i) denote the number of downstream tools immediately adjacent to C.sub.i. C.sub.i is called a fork tool if O-Deg(C.sub.i)2. For example, in the 5-tree-cluster tool shown in
(45) A multi-cluster tool with serial topology can be seen as a cluster-tool-chain (CTC). Then, a K-tree-cluster tool can also be seen to be formed by a number of CTCs. A CTC that starts from C.sub.f and ends at C.sub.l is denoted as CTC[f, l]. Note that a CTC can be formed by a single tool and in this case we have f=l. Let UI(C.sub.i) denote the index of the immediate upstream tool of C.sub.i. Since C.sub.1 has no upstream tool, we set UI(C.sub.1)=0. Then, we divide a K-tree-cluster tool into a number of CTCs such that, for a CTC[f, l], we have O-Deg(C.sub.j)2, j=UI(C.sub.f) and f1; either O-Deg(C.sub.l)2 or O-Deg(C.sub.l)=0; and O-Deg(C.sub.l)=1, i.sub.(i, j), if, and il. For a K-tree-cluster tool, the individual tools can be labeled such that the tools on each CTC[f, l] are labeled with consecutive numbers in an increasing order from f to l. That is, the immediate upstream and downstream tools of C.sub.i are C.sub.i1 and C.sub.i+1, respectively. For example, the 5-tree-cluster tool shown in
(46) Given CTC[f, l], there is only one BM shared by C.sub.i and C.sub.i+1, iN.sub.[f, l1]={f, f+1, . . . , l1}. Hence, for the simplicity of presentation, for a CTC, we can use PS.sub.i(b[i]) for the BM in C.sub.i instead of PS.sub.i(b[i,i+1]). Let .sub.i(b[i])=4.sub.i+3.sub.i+.sub.i(b[i]1) and .sub.i0=4.sub.i+3.sub.i+.sub.i(n[i]). Examining the conditions given in Theorem 1, one can find that, to schedule CTC[f, l] from C.sub.l to C.sub.f such that these conditions are satisfied, one needs to set the robots' waiting time such that: 1) .sub.l(n[l]) is as small as possible; and 2) .sub.i(n[i]) and .sub.i(b[i]1), iN.sub.[f, l1], are as small as possible. Given cycle time .sub.h, this can be implemented as follows: (1) set .sub.ij=min{(4.sub.l+3.sub.l+.sub.l(j+1)), 2(n[l]+1)(.sub.l+.sub.l).sub.m.sub.
.sub.i(b[i]1)=min{.sub.(i+1)0(4.sub.i+3.sub.i), 2(n[i]+1)(.sub.i+.sub.i)},(11)
.sub.ij=min{(4.sub.i+3.sub.i+.sub.i(j+1)), .sub.02(n[i]+1)(.sub.i+.sub.i).sub.m.sub.
.sub.i(n[i])=2(n[i]+1)(.sub.i+.sub.i).sub.m=0.sup.n[i]1.sub.im(13)
and
.sub.i0=.sub.i0.(14)
(47) If iN.sub.[f, l1], .sub.i(b[i]1)0, the conditions given in Theorem 1 are satisfied. That is, given .sub.h, a one-wafer cyclic schedule is found for CTC[f, l] by setting the .sub.ij's. However, iN.sub.[f, l1], .sub.i(b[i]1)<0 may happen. Since 2(n[i]+1)(.sub.i+.sub.i)0 always holds. .sub.i(b[i]1)<0 implies that .sub.(i+1)0(4.sub.i+3.sub.i)<0, leading to .sub.(i+1)0<(4.sub.i+3.sub.i), i.e., the conditions in Theorem 1 are violated. Thus, the above procedure can be used to not only schedule a CTC if a feasible one-wafer schedule exists for the given cycle time , it also can be used to check the existence of a one-wafer cyclic schedule for CTC[f, l] and this procedure is called CTC-Check.
(48) Note that, in the above procedure, for iN.sub.[f, l1], .sub.i2 is assigned .sub.ij's, j.sub.n[i]1} as much as possible. In this way, .sub.i(n[i]) and .sub.i0=4.sub.i+3.sub.i+.sub.i(n[i]) are minimized.
(49) C.2. Minimal Cycle Time of a CTC
(50) Given .sub.h for CTC[f, l], if .sub.i(b[i]1)<0, iN.sub.[f, l1], happens by using CTC-Check, one cannot find a one-wafer schedule with cycle time . However, a one-wafer cyclic schedule still exists and such a schedule can be found by increasing . The key is how to determine the minimal cycle time and this issue is discussed as follows.
(51) For CTC[f, l] and given , .sub.(k+1)0<(4.sub.k+3.sub.k), kN.sub.[f, l1], we assume that .sub.(i+1)0(4.sub.i+3.sub.i), iN.sub.[k+1, l1], that is, the conditions given in Theorem 1 are satisfied for C.sub.i, iN.sub.[k+1, l1], but not satisfied for C.sub.k. Since 4.sub.k+3.sub.k is a constant, to make .sub.(k+1)0(4.sub.k+3.sub.k) satisfied, the only way is to increase .sub.(k+1)0. Since .sub.(k+1)0=(4.sub.k+1+3.sub.k+1+.sub.(k+1)(n[k+1])) and (4.sub.k+1+3.sub.k+1) is a constant, to increase .sub.(k+1)0, one needs to increase and reduce .sub.(k+1)(n[k+1]). By examining the CTC-Check procedure, one can find that, by increasing , one can assign more part of .sub.(k+1)2 into .sub.(k+1)j, j.sub.n[k+1]1\{n[k+1]}, such that .sub.(k+1)(n[k+1]) is reduced. In this way, .sub.(k+1)0 can be increased by increasing and reducing .sub.(k+1)(n[k+1]) simultaneously.
(52) By increasing , to obtain a one-wafer cyclic schedule, the cycle time for any C.sub.i in a K-tree-cluster tool should be increased as well such that every tool has the same cycle time. Hence, by increasing for C.sub.i, iN.sub.[k+2, l], .sub.i(n[i]) is reduced. Then, by the CTC-Check procedure, this leads to the decrease of .sub.(i1)(n[i1]). Finally, the increase of for C.sub.i, iN.sub.[k+2, l1], can result in the decrease of .sub.(k+1)(n[k+1]). This implies that, with the increase of , .sub.(k+1)(n[k+1]) can be reduced by scheduling C.sub.k+1 and its downstream tools. However, given , if CTC[f, l] is scheduled by the CTC-Check procedure such that .sub.i(n[i])=0, iN.sub.[k+2, l], the increase of for C.sub.i and its downstream tools has no effect on .sub.(k+1)(n[k+1]), since .sub.i(n[i]) cannot be reduced any more. Thus, the effect of scheduling downstream tools on .sub.(k+1)(n[k+1]) should be taken into account in finding the minimal cycle time.
(53) Note that C.sub.l is either a leaf or a fork. If it is a fork, it has multiple outgoing BMs. This means that CTC[f, l] has multiple downstream CTCs. As above discussed, with the increase of , scheduling tool C.sub.i in a downstream CTC of CTC[f, l] can result in the reduction of .sub.(k+1)(n[k+1]). Also, given , if a schedule for tool C.sub.i in a downstream CTC is obtained by the CTC-Check procedure such that .sub.i(n[i])=0, then, with the increase of , scheduling C.sub.i and its downstream tools has no effect on .sub.(k+1)(n[k+1]).
(54) With the above discussion, we present how to find the minimal cycle time and schedule the system as follows. Given , for CTC[f, l], every time if .sub.k(b[k]1)<0, kN.sub.[f, l1] is returned by the CTC-Check procedure, the cycle time is increased by , i.e. +, such that .sub.(k+1)0=(4.sub.k+3.sub.k). The key is how to determine . To do so, define D[i]={PM.sub.ij|j.sub.n[i]1\{b[i]1, n[i]}} be the set of steps in C.sub.i and B[i]=|D[i]|, and B*[i]=B[i] if il, and B*[l]=n[l]1.
(55) Given , for CTC[f, l], when .sub.k(b[k]1)<0, kN.sub.[f, l1], is returned by the CTC-Check procedure, for every C.sub.i, iN.sub.[k, l], or in the downstream CTCs of CTC[f, l], the robot waiting time is set by the CTC-Check procedure. To find , for C.sub.i, iN.sub.[k, l], or in the downstream CTCs of CTC[f, l], let A.sub.ij=.sub.ij and .sub.ij=.sub.ij, j.sub.n[i], and =4.sub.k+3.sub.k.sub.(k+1)0=4.sub.k+3.sub.k((4.sub.k+1+3.sub.k+1+.sub.(k+1)(n[k+1])))=4.sub.k+3.sub.k+4.sub.k+1+3.sub.k+1+.sub.(k+1)(n[k+1]).
(56) To take the effect of tools in the downstream CTCs of CTC[f, l] into account, we use DsI(C.sub.i), i.Math., to denote the index set of all the downstream tools of C.sub.i and LeafDsI(C.sub.i), the index set of leaf tools in DsI(C.sub.i). Further, define E(k)={g.sub.(k, m)|mLeafDsI(C.sub.k), .sub.j(n[j])>0, j.sub.(h, g) and h=DI(C.sub.k), and .sub.(g+1)(n[g+1])=0, g.Math.LeafDsI(C.sub.k)}. Further, let Y(k)={.sub.(h, s)|sE(k) and h=DI(C.sub.k)}. Then, is determined as follows. For gY(k), let .sub.g=.sub.g(n[g])/.sub.jY(g)B*[j], .sub.k=/(1+.sub.jY(k)B*[j]), and Q(k)={a.sub.(k, d)|dE(k)}. Then, let =min.sub.hQ(k).sub.h and there are two cases.
(57) Case 1: If =.sub.k, let +. For iDsI(C.sub.a) and aE(k), set .sub.i0=A.sub.i0+, .sub.i0=.sub.i0+, and .sub.i(m1)=.sub.i(m1)+ with mBI(C.sub.i), when C.sub.i is not a leaf tool. For iY(k)\E(k), .sub.ij=A.sub.ij+, j.sub.n[i]\{{j1|jBI(C.sub.i)}{n[i]}}, .sub.i(b[m, d]1)=A.sub.i(b[m, d]1)+.sub.j{.sub.
(58) Case 2: If .sub.k, let =.sub.g=min.sub.hQ(k).sub.h, +. Then, for sE(k) and iDsI(C.sub.s), .sub.i0=A.sub.i0+, .sub.i0=.sub.i0+, and .sub.i(m1)=.sub.i(m1)+, mBI(C.sub.i), when C.sub.i is not a leaf tool. For iY(k), .sub.ij=A.sub.ij+, j.sub.n[i]\{{j1|jBI(C.sub.i)}{n[i]}}, .sub.i(m1)=A.sub.i(m1)+.sub.jY(i)B*[j]+, mBI(C.sub.i); .sub.i(n[i])=A.sub.i(n[i]).sub.j{.sub.
(59) Finally the cycle time is increased by such that .sub.(k+1)0=(4.sub.k+3.sub.k) and Conditions (9)-(10) for any pair of C.sub.i and C.sub.i+1, iN.sub.[f, l], are satisfied. In addition, since .sub.(k+1)0=(4.sub.k+3.sub.k), a cycle time increase that is less than must result in .sub.(k+1)0<(4.sub.k+3.sub.k). For a CTC without downstream CTCs, a method is presented to find the minimal cycle time and its optimal one-wafer cyclic schedule in [Zhu et al., 2013b]. Since such method is somehow similar to the one disclosed herein, we do not go into too much detail and please refer to [Zhu et al., 2013b] for detail.
(60) In the above development, each individual tool is scheduled such that, for any C.sub.i, .sub.i(n[i]) is minimized. Thus, it follows from .sub.1=.sub.2= . . . =.sub.K= that .sub.i0, iN.sub.[f, l], in CTC[f,l] is minimized. The above development is summarized as Algorithm 1, where inputs and .sub.h represent the index set of the individual cluster tools in a CTC and the given cycle time, respectively. Assume that all .sub.ij, .sub.i, .sub.i of the K-cluster tool are known constants to Algorithm 1. Its output is the CTC's minimal cycle time.
(61) TABLE-US-00002 Algorithm 1: Scheduling CTC[f, l] for given denoted as SCH(CTC[f, l], ) Input:, N.sub.[f, l]. Output: .sub.ij for C.sub.i, i N.sub.[f, l] and in the downstream CTCs, j.sub.n[i], .sub.f0, , . 1. Initialization: 1.1. lf+1, AD UI(f) 2. Set .sub.ij, j.sub.n[l] for R.sub.l as: 2.1. For j 0 to n[l] 1 do 2.2. .sub.lj min{ (4.sub.l +3.sub.l+.sub.l(j+1)), 2(n[l] + 1)(.sub.l + .sub.l) .sub.m=0.sup.j1 .sub.lm} 2.3. EndFor 2.4. .sub.l(n[l]) 2(n[l] + 1)(.sub.l + .sub.l) .sub.m=0.sup.n[l]1 .sub.lm 2.5. .sub.l0 (4.sub.l+ 3.sub.l+ .sub.l(n[l])), il 1, a 1 3. If AD = 1 Then update .sub.mj(m DsI(C.sub.i)) as 3.1. For each jE.sub.0 3.2. .sub.j0 .sub.j0 + , .sub.j0.sub.j0 + 3.3. .sub.j(m1).sub.j(m1) + , for mBI(C.sub.j) 3.4. EndFor 3.5. If E(i) Then 3.6. For each j.sub.(i+1, g)|gE(i) do 3.7. .sub.jm.sub.jm + , for m.sub.n[j] \ ({i1|jBI(C.sub.i)}{n[j]}) 3.8. .sub.mY(j) B*[m] 3.9. .sub.j(m1) .sub.j(m1)+ + , for mBI(C.sub.j) 3.10. .sub.j(n[j]) .sub.j(n[j]) 3.11. .sub.j0 .sub.j0+ + 3.12. EndFor 3.13. EndIf 3.14. a |.sub.(f,i)| 4. Set .sub.ij for R.sub.i (i.sub.(f, li), j.sub.n[i]) as: 4.1. While a1 4.2. If.sub.(i+1)0< (4.sub.i + 3.sub.i) Then 4.3. 4.sub.i + 3.sub.i .sub.(i+1)0 4.4. If .sub.(i+1)(n[i+1])= 0 Then , E(i), E.sub.0DsI(C.sub.i) 4.5. Else 4.6. Find E(i) 4.7. .sub.k .sub.k(n[k])/ .sub.mY(k) B*[m], for each kY(i) 4.8. .sub.i/(1 + .sub.mY(i) B*[m]) 4.9. min{.sub.i, .sub.k }with kY(i) 4.10.E.sub.0DsI(C.sub.g)| g E(i) 4.11.EndIf 4.12.+ 4.13.AD 1 4.14.Goto 3. 4.15.EndIf 4.16..sub.i(b[i]1) min{.sub.(i+1)0 (4.sub.i + 3.sub.i), 2(n[i] + 1)(.sub.i +.sub.i)} 4.17.For j 0 to n[i] and jb[i] 1 do 4.18..sub.ij min{ (4.sub.i +3.sub.i+.sub.i(j+1)), 2(n[i] + 1)(.sub.i + .sub.i) .sub.m.sub.
C.3. Scheduling K-Tree-Cluster Tool
(62) As above discussed, a K-tree-cluster tool is composed of a number of CTCs, to obtain the minimal cycle time of the K-tree-cluster tool, it needs to minimize .sub.i0=4.sub.i+3.sub.i+.sub.i(n[i]) for every C.sub.i in each CTC, or minimize .sub.i(n[i]). This is done as follows. Let L-CTC be the set of CTC[f, l]s with C.sub.l being a leaf tool of the K-tree-cluster tool and assume that |L-CTC|=g. Given =.sub.h, the lower bound of cycle time for a K-tree-cluster tool, as the initial cycle time, each CTC in the L-CTC is scheduled by using Algorithm 1. Assume that the minimal cycle time obtained for these g CTCs are .sub.1, . . . , .sub.g, respectively. Then, given =max{.sub.1, . . . , .sub.g} as the cycle time, for any C.sub.i in any CTC that is in L-CTC, .sub.ij's are set by the CTC-Check procedure. After that, given =max{.sub.1, . . . , .sub.g} as initial cycle time, we schedule the CTC.Math.L-CTC that is not scheduled and whose downstream CTCs are all in L-CTC. By repeating such a process, one can find a one-wafer cyclic schedule for the entire K-tree-cluster tool by minimizing .sub.i0=4.sub.i+3.sub.i+.sub.i(n[i]) for every individual tool C.sub.i. If finally the obtained minimal cycle time is =.sub.h, the lower bound of cycle time is reached by a one-wafer cyclic schedule. We present Algorithm 2 as follows to implement above sketchy procedure.
(63) TABLE-US-00003 Algorithm 2: Schedule a K-tree-cluster tool. Input: .sub.ij, .sub.i, .sub.i (i N.sub.K,j.sub.n[i]) Output: .sub.ij, 1.Initialization: .sub.h max(.sub.i), i N.sub.K, , .sub.1 2.For each i N.sub.K do 3.If (jN.sub.n[i], .sub.ij>0) Then {i} EndIf 4.EndFor 5.While 6.For each e do 7. {e}, mUI(C.sub.e) 8.While m 0 and O-Deg(C.sub.m) = 1 do
{m}, mUI(C.sub.m) EndWhile 9.f min(
) 10. i UI(C.sub.f), j the step index of PM.sub.i(b[i,f]) in C.sub.i 11. .sub.1 .sub.1 {i} 12. .sub.new max(.sub.h, max(.sub.m)|m
) 13. Call SCH(CTC[f, l], .sub.new) to set .sub.f0, , .sub.ij 14. .sub.ij .sub.f0 15. EndFor 16. 17. For each i.sub.1 do 18. If jBI(i), .sub.ij > 0 Then 19. max(.sub.ij), jBI(i), .sub.1.sub.1\{i}, and {i} 20. For jBI(i) and .sub.ij< 21. .sub.m0.sub.m0 + (.sub.ij), .sub.m0.sub.m0 + (.sub.ij), mDsI(C.sub.j) 22. EndFor 23. EndIf 24. EndFor 25. EndWhile
(64) By Algorithm 2, the CTCs in a K-tree-cluster tool are identified and they are scheduled by calling Algorithm 1 to find the minimal cycle time and set the robots' waiting time. This is done from the leaves to the root in a backward way as above discussed. Also, by Algorithm 2, if =.sub.h is returned, it implies that .sub.(i+1)0<(4.sub.i+3.sub.i), iN.sub.K, does not occur and a one-wafer cyclic schedule with the lower bound of cycle time is obtained. Therefore, Algorithm 2 can be used to decide whether the K-tree-cluster tool can be scheduled to reach the lower bound of cycle time. Thus, we have Theorem 2 immediately.
(65) Theorem 2: For a process-dominant K-tree-cluster tool, there is a one-wafer cyclic schedule such that its cycle time is the lower bound .sub.h if and only if, by Algorithm 2, =.sub.h is returned.
(66) Moreover, by the proposed method, if >.sub.h is returned, the obtained one-wafer cyclic schedule is optimal as stated by the following theorem.
(67) Theorem 3: For a process-dominant K-tree-cluster tool, by Algorithm 2, if >.sub.h is returned, the obtained one-wafer cyclic schedule is optimal in terms of cycle time.
(68) Proof. By applying Algorithm 2 to a K-tree-cluster tool, every time if .sub.(i+1)0<(4.sub.i+3.sub.i), iN.sub.K, occurs, the cycle time is increased by as + such that .sub.(i+1)0=(4.sub.i+3.sub.i). Hence, by Algorithm 2, finally a one-wafer cyclic schedule is obtained with cycle time >.sub.h, this implies that there is at least an iN.sub.K such that .sub.(i+1)0=(4.sub.i+3.sub.i). In this case, any decrease of would result in .sub.(i+1)0=(4.sub.i+3.sub.i), leading to the violation of Conditions (9)-(10). Thus, >.sub.h obtained is the minimal cycle time.
(69) Note that, for a process-dominant K-tree-cluster tool addressed in this work, each individual tool is scheduled by using a backward scheduling strategy. This implies that a backward scheduling strategy is optimal for such a K-tree-cluster tool if the proposed method is applied.
(70) D. Illustrative Examples
(71) In this section, we use two examples to show how to apply the proposed method and its effectiveness. In the examples, the time is in seconds and is omitted for simplicity.
Example 1
(72) It is from [Chan et al., 2011b]. As shown in
(73) By .sub.ij=.sub.ij+4.sub.i+3.sub.i, .sub.i1=2(n[i]+1)(.sub.i+.sub.i), and .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i]), .sub.i1}, for C.sub.1, .sub.10=.sub.10+4.sub.1+3.sub.1=0+45+32=26, .sub.11=36, .sub.12=26, .sub.13=26, .sub.14=36, and .sub.11=2(n[1]+1)(.sub.1+.sub.1)=2(4+1)(5+2)=70. We have .sub.1=70 and C.sub.1 is transport-bound. For C.sub.2, we have that .sub.20=15, .sub.21=85, .sub.22=85, .sub.23=73, .sub.24=20, and .sub.21=40. Thus we have .sub.2=85 and C.sub.2 is process-bound. For C.sub.3, we have that .sub.30=15, .sub.31=20, .sub.32=73, .sub.33=85, .sub.34=85, and .sub.31=40. Then we have .sub.3=85 and C.sub.3 is process-bound. Since .sub.2=.sub.3>.sub.1, and C.sub.2 and C.sub.3 are process-bound, the 3-tree-cluster is process-dominant.
(74) With the lower bound of cycle time being .sub.h=.sub.2=.sub.3=85, set =.sub.h=85 as initial cycle time, we have .sub.12=.sub.11=15, .sub.22=.sub.21=40, and .sub.32=.sub.21=40. By Algorithm 2 that calls Algorithm 1, .sub.ij's are set as .sub.20=.sub.21=0, .sub.22=12, .sub.23=33, .sub.24=0, .sub.30=45, .sub.31=.sub.32=.sub.33=.sub.34=0, .sub.10=.sub.11=.sub.12=.sub.13=0 and .sub.14=15 such that =.sub.h=85 is returned. Hence, a one-wafer cyclic schedule with the lower bound of cycle time =85 is obtained, which verifies Theorem 2.
(75) With this topology of this example, by changing the activity time, four other cases are generated and studied in [Chan et al., 2011b] by using the method proposed there. For each of these cases, a multi-wafer cyclic schedule is obtained. These cases are also studied by the proposed method and a one-wafer cyclic schedule is obtained for each of the cases with the cycle time being less than that obtained in [Chan et al., 2011b].
Example 2
(76) It is a 5-tree-cluster tool composed of five single-arm cluster tools as shown in
(77) By .sub.ij=.sub.ij+4.sub.i+3.sub.i, .sub.i1=2(n[i]+1)(.sub.i+.sub.i), and .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i]), .sub.i1}, for C.sub.1, .sub.10=.sub.10+4.sub.1+3.sub.1=0+45+32=26, .sub.11=36, .sub.12=26, .sub.13=26, .sub.14=36, and .sub.11=70. We have .sub.1=70 and C.sub.1 is transport-bound. For C.sub.2, we have that .sub.20=15, .sub.21=85, .sub.22=85, .sub.23=73, .sub.24=20, and .sub.21=40. Then we have .sub.2=85 and C.sub.2 is process-bound. For C.sub.3, we have that .sub.30=35, .sub.31=69s, .sub.32=35, .sub.33=66, .sub.34=39, and .sub.31=90. Thus we have .sub.3=90 and C.sub.3 is transport-bound. For C.sub.4, we get .sub.40=7s, .sub.41=107, .sub.42=7s, .sub.43=107, .sub.44=105s, and .sub.41=20. Therefore, we have .sub.4=107 and C.sub.4 is process-bound. For C.sub.5, it is found that .sub.50=7s, .sub.51=107, .sub.52=107, .sub.53=107, .sub.54=107, and .sub.51=20. Hence we have .sub.5=107 and C.sub.5 is process-bound. Since .sub.4=.sub.5.sub.i, iN.sub.3, and C.sub.4 and C.sub.5 are process-bound, the 5-tree-cluster is process-dominant.
(78) With the lower bound of cycle time being .sub.4=.sub.5=107, set =107 as initial cycle time. By .sub.i2=.sub.i1, we have .sub.12=37, .sub.22=67, .sub.32=17, .sub.42=87, and .sub.52=87. By applying Algorithm 2 to CTC[3, 5], the cycle time is increased as ++((4.sub.3+3.sub.3).sub.40)/(1+B*[4]+B*[5])=107+(3521)/(1+3+3)=107+2=109. Then, =109 is set for scheduling CTC[2, 2] and CTC[1, 1]. Then, given =109, by applying Algorithm 2 to CTC[2, 2] and CTC[1, 1] sequentially, the cycle time =109 is returned and .sub.ij's are set as: .sub.30=19, .sub.31=.sub.32=.sub.33=.sub.34=0, .sub.40=2, .sub.41=14, .sub.42=2, .sub.43=4, .sub.44=67, .sub.50=.sub.51=.sub.52=.sub.53=2, .sub.54=81, .sub.10=39, .sub.11=.sub.12=.sub.13=.sub.14=0, .sub.20=24, .sub.21=22, .sub.22=23, .sub.23=0, and .sub.24=0. Hence, an optimal one-wafer cyclic schedule with cycle time =109 is obtained.
(79) E. The Present Invention
(80) The present invention is developed based on the theoretical development in Sections A-C above.
(81) An aspect of the present invention is to provide a computer-implemented method for scheduling a tree-like multi-cluster tool to generate a one-wafer cyclic schedule. The multi-cluster tool comprises K single-cluster tools C.sub.i's. The multi-cluster tool is decomposable into a plurality of CTCs each having a serial topology.
(82) Exemplarily, the method makes use of the finding given by Theorem 1. In particular, the method comprises determining values of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], such that (8)-(10) are satisfied for any pair of C.sub.i and C.sub.a, in which i, aN.sub.K, C.sub.a being an immediate downstream tool of C.sub.i.
(83) In determining the aforesaid values of .sub.ij, preferably a CTC-Check algorithm for computing candidate values of .sub.ij under a constraint on . The computation of the candidate .sub.ij values is performed for at least one individual CTC. The CTC-Check algorithm for CTC[f, l] is configured to compute the candidate .sub.ij values such that .sub.i(n[i]) is minimized for each value of i selected from N.sub.[f, l1]. In one embodiment, the CTC-Check algorithm as used in the disclosed method is the one given by Section C.1.
(84) Based on the CTC-Check algorithm, the values of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], are determined as follows according to one embodiment of the present invention. First, the candidate values of .sub.ij for the single-cluster tools in an individual CTC are determined by performing the CTC-Check algorithm under the constraint that is equal to a lower bound of cycle time of the multi-cluster tool. This lower bound is a FP of a bottleneck tool among the K single-cluster tools, and is given by .sub.h. If the candidate .sub.ij values for the individual CTC are non-negative, then the candidate .sub.ij values are set as the determined values of .sub.ij for the individual CTC. If at least one of the candidate .sub.ij values for the individual CTC is negative, a minimum cycle time for the individual CTC is first determined and then the values of .sub.ij for the individual CTC are determined by performing the CTC-Check algorithm under a revised constraint that is the determined minimum cycle time for the individual CTC.
(85) More particularly, it is preferable and advantageous that the values of .sub.ij, i=1, 2, . . . , K, and j=0, 1, . . . , n[i], are determined according to the procedure given in Section C.3, where the procedure is embodied in Algorithms 1 and 2 detailed above. A summary of this procedure is given as follows. First identify an L-CTC set consisting of first individual CTCs each having a leaf tool therein. It follows that one or more second individual CTCs not in the L-CTC set are also identified. For each of the first individual CTCs, a minimum cycle time is determined, followed by determining the values of .sub.ij by performing the CTC-Check algorithm under the constraint that is equal to the determined minimum cycle time. For each second individual CTC, candidate values of .sub.ij for each single-cluster tool therein are determined by performing the CTC-Check algorithm under an initial constraint that is equal to a maximum value of the minimum cycle times already determined for the first individual CTCs. If the candidate .sub.ij values for the second individual CTC are non-negative, then the candidate .sub.ij values are set as the determined values of .sub.ij for the second individual CTC. If, on the other hand, at least one of the candidate .sub.ij values for the second individual CTC is negative, then the following two-step procedure is performed. First, determine a minimum cycle time for the second individual CTC. Second, determine the values of .sub.ij for the second individual CTC by performing the CTC-Check algorithm under a revised constraint that is equal to the determined minimum cycle time for the second individual CTC.
(86) 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.
(87) In particular, the method disclosed herein can be implemented in a tree-like multi-cluster cluster tool if the multi-cluster tool includes one or more processors. The one or more processors are configured to execute a process of generating a one-wafer cyclic schedule according to one of the embodiments of the disclosed method.
(88) 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.