System and method for determining an optimized schedule of a production line
10101721 ยท 2018-10-16
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
Y10S901/09
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/04
PHYSICS
G05B19/418
PHYSICS
G05B19/41
PHYSICS
Abstract
A method determines an optimized production schedule of a production line including a hybrid multi-cluster tool formed by a plurality of single-arm tools and dual-arm tools interconnected with each other. The method includes determining time for individual operations of a robotic arm and a processing module in the plurality of single-arm tools and dual-arm tools; determining robot waiting time of the single-arm tools and dual-arm tools based on the time for individual operations and different connection relationships of the plurality of single-arm tools and dual-arm tools; determining whether the optimized production schedule exists using the determined waiting time, wherein the optimized production schedule only exists if the hybrid multi-cluster tool is process-dominant where the robot activity time of the plurality of single-arm tools and dual-arm tools is substantially shorter than processing time at the processing module; and determining the optimized production schedule if the optimized production schedule exists.
Claims
1. A method for determining an optimized production schedule of a production line including a hybrid multi-cluster tool formed by a plurality of single-arm tools and dual-arm tools interconnected with each other; wherein each single-arm tool includes one robotic arm for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object, and each dual-arm tool includes two robotic arms for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object; each single-arm tool and dual arm tool are connected with each other through at least one buffering module; the method comprising the steps of: determining time for individual operations of the robotic arm and the processing module in the plurality of single-arm tools and dual-arm tools; determining waiting time of the single-arm tools and dual-arm tools based on the time for individual operations and different connection relationships of the plurality of single-arm tools and dual-arm tools; determining whether the optimized production schedule exists using the determined waiting time, wherein the optimized production schedule only exists if the hybrid multi-cluster tool is process-dominant where the robot activity time of the plurality of single-arm tools and dual-arm tools is shorter than processing time at the processing module; and determining the optimized production schedule if the optimized production schedule exists, wherein the hybrid multi-cluster tool has a non-cyclic treelike structure with at least one of the single-arm tools and dual-arm tools being connected with three or more adjacent single-arm tools and dual-arm tools.
2. The method in accordance with claim 1, wherein the step of determining the time for individual operations of the robotic arm and the processing module in the plurality of single-arm tools and dual-arm tools comprises the step of determining one or more of: a time required for the robotic arm of the single-arm tool to load or unload the object; a time required for the robotic arms of the dual-arm tool to swap; a time required for the robotic arm of the single-arm tool or the dual-arm tool to move while holding the object; a time required for the robotic arm of the single-arm tool to move without holding the object; a time required for processing the object in the processing module of the single-arm tool or the dual-arm tool; a time required for resting the object in the processing module of the single-arm tool or the dual-arm tool; a time required for the robotic arm of the single-arm tool to wait before unloading the object; a time required for the robotic arms of the dual-arm tool to wait at the processing module of the dual-arm tool; and a time required for the robotic arms of the dual-arm tool to wait during swap at the processing module of the dual arm tool.
3. The method in accordance with claim 2, wherein the different connection relationships comprise: an upstream downstream relationship that includes an upstream single-arm tool and downstream single-arm tool connection, an upstream single-arm tool and a downstream dual-arm tool connection, an upstream dual-arm tool and a downstream single-arm tool connection, or an upstream dual-arm tool and a downstream dual-arm tool connection; and a number relationship that includes a number of adjacent single-arm or the dual-arm tools of which the respective single-arm tool or the dual-arm tool is connected to.
4. The method in accordance with claim 3, wherein the step of determining whether the optimized production schedule exists using the time for individual operations and the waiting time comprises: calculating an robot activity time of each of the single-arm tools and dual-arm tools in a production cycle without waiting using the time for individual operations; calculating a period of each of the single-arm tools and dual-arm tools using the time for individual operations; determining a maximum period from the calculated periods; determining a robot waiting time of each of the plurality of single-arm tools and dual-arm tools using the maximum period; evaluating the robot waiting time determined so as to determine if the optimized production schedule exists.
5. The method in accordance with claim 4, wherein the step of determining the optimized production schedule comprises setting an optimal robot waiting time for each of the plurality of single-arm tools and dual-arm tools based on the determination results without interfering with the operation of the buffering modules.
6. The method in accordance with claim 1, wherein the object is a semiconductor and the production line is a semiconductor manufacturing line.
7. The method in accordance with claim 1, wherein the optimized production schedule comprises a shortest time for completion of a cycle of production of the object.
8. A computerized system arranged to determine an optimized production schedule of a production line including a hybrid multi-cluster tool formed by a plurality of single-arm tools and dual-arm tools interconnected with each other; wherein each single arm tool includes one robotic arm for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object, and each dual-arm tool includes two robotic arms for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object; each single-arm tool and dual-arm tool are connected with each other through at least one buffering module; the computerized system comprising: a Petri-Net (PN) model computation module arranged for: determining time for individual operations of the robotic arm and the processing module in the plurality of single arm tools and dual arm tools; determining robot waiting time of the single-arm tools and dual-arm tools based on the time for individual operations and different connection relationships of the plurality of single arm tools and dual arm tools; determining whether the optimized production schedule exists using the determined robot waiting time, wherein the optimized production schedule only exists if the hybrid multi-cluster tool is process-dominant where the robot activity time of the plurality of single-arm tools and dual-arm tools is shorter than processing time at the processing module; and determining the optimized production schedule if the optimized production schedule exists, wherein the hybrid multi-cluster tool has a non-cyclic treelike structure with at least one of the single-arm tools and dual-arm tools being connected with three or more adjacent single-arm tools and dual-arm tools.
9. The computerized system in accordance with claim 8, wherein determining the time for individual operations of the robotic arm and the processing module in the plurality of single arm tools and dual arm tools comprises determining one or more of: a time required for the robotic arm of the single-arm tool to load or unload the object; a time required for the robotic arms of the dual-arm tool to swap; a time required for the robotic arm of the single-arm tool or the dual-arm tool to move while holding the object; a time required for the robotic arm of the single-arm tool to move without holding the object; a time required for processing the object in the processing module of the single-arm tool or the dual arm tool; a time required for resting the object in the processing module of the single-arm tool or the dual arm tool; a time required for the robotic arm of the single-arm tool to wait before unloading the object; a time required for the robotic arms of the dual-arm tool to wait at the processing module of the dual arm tool; and a time required for the robotic arms of the dual-arm tool to wait during swap at the processing module of the dual arm tool.
10. The computerized system in accordance with claim 9, wherein the different connection relationships comprise: an upstream downstream relationship that includes an upstream single-arm tool and downstream single-arm tool connection, an upstream single-arm tool and a downstream dual-arm tool connection, an upstream dual-arm tool and a downstream single-arm tool connection, or an upstream dual-arm tool and a downstream dual-arm tool connection; and a number relationship that includes a number of adjacent single-arm or the dual-arm tools of which the respective single-arm tool or the dual-arm tool is connected to.
11. The computerized system in accordance with claim 10, wherein the Petri-Net (PN) model computation module is arranged to determine whether the optimized production schedule exists using the time for individual operations and the waiting time by: calculating an activity time of each of the single-arm tools and dual-arm tools in a production cycle without robot waiting using the time for individual operations; calculating a period of each of the single-arm tools and dual-arm tools using the time for individual operations; determining a maximum period from the calculated periods; determining a robot waiting time of each of the plurality of single-arm tools and dual-arm tools using the maximum period; evaluating the robot waiting time determined so as to determine if the optimized production schedule exists.
12. The computerized system in accordance with claim 11, wherein the Petri-Net (PN) model computation module is arranged to determine the optimized production schedule by setting an optimal robot waiting time for each of the plurality of single-arm tools and dual-arm tools based on the determination results without interfering with the operation of the buffering modules.
13. The computerized system in accordance with claim 8, wherein the optimized production schedule comprises a shortest time for completion of a cycle of production of the object.
14. The computerized system in accordance with claim 8, wherein the object is a semiconductor and the production line is a semiconductor manufacturing line.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1) Embodiments of the present invention will now be described, by way of example, with reference to the accompanying drawings in which:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
(10) Multi-cluster tools generally comprise a number of single-cluster tools connected by buffering modules with a capacity of one or two, and they may have linear or non-cyclic treelike topology. A multi-cluster tool with K (2) individual cluster tools is generally referred to as a K-cluster tool. Furthermore, if these individual tools include both single and dual-arm tools, then the multi-cluster tool is of a hybrid type.
(11) An exemplary treelike hybrid 9-cluster tool 100 linked by buffering modules 106 is illustrated in
(12) In the present invention, a Petri net (PN) model has been developed for determining and evaluating an optimized schedule of a production line formed by a treelike hybrid multi-cluster tool, such as that shown in
(13) In one embodiment, the present invention provides a method for determining an optimized production schedule of a production line, the production line comprises a hybrid multi-cluster tool formed by a plurality of single-arm tools and dual-arm tools interconnected with each other; wherein each single-arm tool includes one robotic arm for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object, and each dual-arm tool includes two robotic arms for manipulating an object and at least one processing module for processing the object or a buffering module for holding the object; the single-arm tools and dual-arm tools are connected with each other through at least one buffering module; the method comprising the steps of: determining time for individual operations of the robotic arm and the processing module in the plurality of single-arm tools and dual-arm tools; determining waiting time of the single-arm tools and dual-arm tools based on the time for individual operations and different connection relationships of the plurality of single-arm tools and dual-arm tools; determining whether the optimized production schedule exists using the determined waiting time, wherein the optimized production schedule only exists if the hybrid multi-cluster tool is process-dominant where the robot activity time of the plurality of single-arm tools and dual-arm tools is substantially shorter than processing time at the processing module; and determining the optimized production schedule if the optimized production schedule exists.
(14) Petri Net (PN) Modeling
(15) The following assumptions are made in the embodiment of the present invention: 1) a buffering module has no processing function and its capacity is one; 2) for each step, only one process module is configured for product (e.g., semiconductor wafer) processing and, only one product can be processed in a process module at a time; 3) only one type of product is processed with an identical recipe, and they visit a process module only once except entering a buffering module at least twice; 4) the robots' task time is constant; and 5) besides buffering module, there is at least one processing step in each individual tool except the fork and leaf tool. The fork tool may have no processing step and the leaf tool has at least two process modules.
(16) Let .sub.n={1, 2, . . . , n}, .sub.n={0}
.sub.n, and C.sub.i and R.sub.i, i
.sub.K, denote the i-th cluster tool and its robot, respectively, where C.sub.1 with load-locks is the head tool, C.sub.i, i1 is the leaf tool if it connects with only one adjacent tool, and C.sub.i, i1 is the fork tool if it connects at least three adjacent tools. Further, let L={i|C.sub.i is a leaf tool} be the index set of leaf tools. For the tool shown in
.sub.K\{1}, with C.sub.k/C.sub.i being the upstream/downstream one where i>k. It should be noted that, however, k and i are not necessary in a consecutive order as shown in
.sub.K and j
.sub.r.
(17) A buffering module connecting C.sub.k and C.sub.i can be considered as the outgoing module for C.sub.k and the incoming module for C.sub.i, respectively. Let n[i] represent the index for the last step in C.sub.i, i.sub.K. Then, the number of steps in C.sub.i, including the incoming and outgoing steps, is n[i]+1. Further, let f[k] (1f[k]n[k]) denote the number of outgoing modules in C.sub.k, k.Math.L, and these outgoing modules are denoted as PS.sub.k(b[k].sub._.sub.1), PS.sub.k(b[k].sub._.sub.2), . . . , and PS.sub.k(b[k].sub._.sub.f[k]) with b[k]_1<b[k]_2< . . . <b[k]_f[k]. When f[k]>1, C.sub.k is a fork tool, otherwise it is not. It should be pointed out that b[k]_1, b[k]_2, . . . and b[k]_f[k] may not be in a consecutive order, in other words, b[k]_2=b[k]_1+1 may not hold. The incoming module for C.sub.i is denoted as PS.sub.i0. In this way, the n[k]+1 steps in C.sub.k are denoted as PS.sub.k0, PS.sub.k1, . . . , PS.sub.k(b[k].sub._.sub.1), PS.sub.k((b[k].sub._.sub.1)+1), . . . , PS.sub.k(b[k].sub._.sub.2), . . . , PS.sub.k(n[k]), respectively. Notice that b[k]_1 can be 1 if it is Step 1 and b[k]_f[k] can be n[k] if it is the last step. Hence, the route of a product in
(18) A. Petri Net (PN) for Hybrid K-Cluster Tools
(19) To model a hybrid K-cluster tool, the behavior of individual tools and buffering modules need to be modeled. Since the behavior of a single-arm tool is different from that of a dual-arm tool, their models are presented separately.
(20) For C.sub.i, regardless of whether it is a single or dual-arm tool, places r.sub.i and p.sub.ij model R.sub.i and PS.sub.ij, i.sub.K, j.sub.n[i], respectively. For a single-arm tool C.sub.i, as shown in
(21) For a dual-arm tool C.sub.i, as shown in
(22) For a buffering module that links C.sub.k and C.sub.i, k.Math.L, i.sub.K\{1}, with C.sub.i being the downstream one, there are four different cases: 1) both C.sub.k and C.sub.i are dual-arm tools (D-D); 2) C.sub.k and C.sub.i are single and dual-arm tools, respectively (S-D); 3) C.sub.k and C.sub.i are dual and single-arm tools, respectively (D-S); and 4) both C.sub.k and C.sub.i are single-arm tools (S-S). As discussed above, the buffering module connecting C.sub.k and C.sub.i can be denoted as PS.sub.k(b[k].sub._.sub.q) for C.sub.k, or the q-th OM, 1qf[k], in C.sub.k. This buffering module can be also denoted as PS.sub.i0 in C.sub.i. Then, it 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 K(p.sub.k(b[k].sub._.sub.q))=K(p.sub.i0)=1. The PN models of these four different cases are shown in
(23) With the PN structure developed, by putting a V-token representing a virtual product (not real one), the initial marking M.sub.0 of the PN model is set as follows.
(24) If C.sub.1 is a single-arm tool, set M.sub.0(r.sub.1)=0; M.sub.0(p.sub.10)=n, representing that there are always products to be processed; M.sub.0(p.sub.1(b[1].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, meaning that R.sub.1 is waiting at PS.sub.1((b[1].sub._.sub.1)1) for unloading a product there.
(25) If C.sub.1 is a dual-arm tool, set M.sub.0(r.sub.1)=1; M.sub.0(P.sub.10)=n; M.sub.0(p.sub.1j)=1, j.sub.n[1]; M.sub.0(q.sub.1j)=M.sub.0(d.sub.1j)=0, j.sub.n[1]; M.sub.0(z.sub.1j)=0, j.sub.n[i]\{b[1]_1}; and M.sub.0(z.sub.1(b[1].sub._.sub.1))=1, meaning that R.sub.1 is waiting at PS.sub.1(b[1].sub._.sub.1) for unloading a product there.
(26) For C.sub.i, i.sub.K\{1}, if it is a single-arm tool, set 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, implying that R.sub.i is waiting at PS.sub.i0 for unloading a product there. If C.sub.i, i
.sub.K\{1}, is a dual-arm tool, 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[i]; M.sub.0(z.sub.ij)=0, j
.sub.n[i]; and M.sub.0(z.sub.i0)=1, implying that R.sub.i is waiting at PS.sub.i0 for unloading a product there. It should be pointed out that, for any adjacent C.sub.k and C.sub.i, k
.sub.K-1, at M.sub.0, it is assumed that the token in p.sub.i0 enables u.sub.k(b[k].sub._.sub.q), but not u.sub.i0.
(27) In
(28) Definition 2.1: Define the color of a transition t.sub.i as C(t.sub.i)={c.sub.i}. From Definition 2.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, the color for a token can be defined as follows.
(29) Let .circle-solid.t.sub.i be the set of places of transition t.sub.i. We present the following definition.
(30) Definition 2.2: A token in p.circle-solid.t.sub.i that enables t.sub.i has the same color of t.sub.i's, i.e., {c.sub.i}. For example, a token that enters p.sub.i0 by firing t.sub.k(b[k].sub._.sub.q) has color c.sub.i0, while the one that enters p.sub.i0 by firing t.sub.i0 has color c.sub.k(b[k].sub._.sub.q). In this way, the PN is made conflict-free.
(31) Based on the above discussion, the PN model for a dual-arm fork tool C.sub.i is deadlock-free but the PN model for a single-arm non-fork tool C.sub.i is deadlock-prone. To make the model deadlock-free, the following control policy is introduced.
(32) Definition 2.3: For the PN model of a single-arm tool C.sub.i, i.sub.K, at marking M, transition y.sub.ij, j.sub.n[i]\{n[i], (b[i]_q)1}, q
.sub.f[i], is control-enabled if M(p.sub.i(j+1))=0; 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; y.sub.i(n[i]) is control-enabled if transition t.sub.i1 has just been executed.
(33) By using this control policy, the PN for a single-arm non-fork tool C.sub.i is deadlock-free. For a single-arm fork tool C.sub.i, assume that, at M, u.sub.i0 is enabled. After u.sub.i0 fires, R.sub.i performs the following activities: x.sub.i0.fwdarw.t.sub.i1.fwdarw.y.sub.i(n[i]).fwdarw.u.sub.i(n[i]).fwdarw.x.sub.i(n[i]).fwdarw.t.sub.i0.fwdarw.y.sub.i(n[i]1)(M(p.sub.i(n[i]))=0).fwdarw. . . . .fwdarw.y.sub.i((b[i]).sub._.sub.q) (M(p.sub.i((b[i].sub._.sub.q)+1)))=0).fwdarw.u.sub.i((b[i]).sub._.sub.q).fwdarw.x.sub.i((b[i]).sub._.sub.q).fwdarw.t.sub.i((b[i].sub._.sub.q)+1).fwdarw.y.sub.i((b[i].sub._.sub.q)1)) (t.sub.i((b[i].sub._.sub.q)+1) has just been executed).fwdarw. . . . y.sub.i0(M(p.sub.i1)=0).fwdarw.u.sub.i0.fwdarw.x.sub.i0
. In this way, a cycle is completed and this process can be repeated. Thus, there is no deadlock. This implies that, by the control policy, the PN for the system is made deadlock-free.
(34) B. Modeling Activity Time
(35) In the PN model developed above, with transitions and places representing activities that take time, time is associated with both transitions and places. Since the activity time taken by single-arm and dual-arm tool is different, it should be modeled for both tools. For both types of tools, the robot activity time is modeled such that the time for the robot to move from one step to another is same, so is the time for the robot to load/unload a product into/from a process module. In the present invention, the activity time is modeled as shown in Table I.
(36) TABLE-US-00001 TABLE I Time duration associated with transitions and places in C.sub.i. Transition Time Tool Symbol or place Action duration type .sub.i t.sub.ij/u.sub.ij T R.sub.i loads/unloads a product .sub.i Single- into/from Step j, j .sub.n[i] arm .sub.i u.sub.ij and R.sub.i Swaps at Step j, j .sub.n[i] .sub.i Dual- t.sub.ij T arm .sub.i x.sub.ij T R.sub.i moves from a step to another .sub.i Both with a product hold .sub.i y.sub.ij T R.sub.i moves from a step to another .sub.i Single- without a product hold arm .sub.ij p.sub.ij P A product is being processed .sub.ij Both in p.sub.ij, j .sub.n[i] .sub.ij p.sub.ij P A product is being processed .sub.ij Both and waiting in p.sub.ij, j .sub.n[i] .sub.ij q.sub.ij P R.sub.i waits before unloading a [0, ) Single- product from Step j, j .sub.n[i] arm .sub.ij z.sub.ij P R.sub.i waits p.sub.ij, j .sub.n[i] [0, ) Dual- arm .sub.ij1 q.sub.ij P R.sub.ij waits during swap at p.sub.ij, j 0 Dual- .sub.n[i] arm d.sub.ij P No robot activity is associated 0 Both z.sub.ij P No robot activity is associated 0 Single- arm
Timeliness Analysis of Individual Tools
(37) With the PN model, the following presents the temporal properties of individual tools such that a schedule can be parameterized by robot waiting time. For a single-arm tool C.sub.i, i.sub.K, the time taken for processing a product at Step j, j
.sub.n[i], is
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1).(3.1)
For Step 0, as .sub.i0=0,
.sub.i0=.sub.i0+4.sub.i+3.sub.i+.sub.i(n[i])=4.sub.i+3.sub.i+.sub.i(n[i]).(3.2)
(38) With the robot waiting time being removed, the time taken for completing a product at Step j is:
.sub.ij=.sub.ij+4.sub.i+3.sub.i, j.sub.n[i].(3.3)
(39) To make a schedule feasible, a product should stay at process module PM.sub.ij for .sub.ij (.sub.ij) time units and, by replacing .sub.ij with .sub.ij, the cycle time at Step j in C.sub.i is:
.sub.ij=.sub.ij+4.sub.i+3.sub.i+.sub.i(j1), j.sub.n[i].(3.4)
and
.sub.i0=.sub.i0+4.sub.i+3.sub.i+.sub.i(n[i]).(3.5)
(40) The robot cycle time for a single-arm tool C.sub.i is:
.sub.i=2(n[i]+1)(.sub.i+.sub.i)+.sub.j=0.sup.n[i].sub.ij=.sub.i1+.sub.i2.(3.6)
where .sub.i1=2(n[i]+1) (.sub.i+.sub.i) is the robot's activity time in a cycle without waiting and .sub.i2=.sub.j=0.sup.n[i].sub.ij is the robot waiting time in a cycle.
(41) For a dual-arm tool C.sub.i, i.sub.K, is the time needed for completing a product at Step j, j.sub.n[i], in C.sub.i is:
.sub.ij=.sub.ij+.sub.i.(3.7)
Similarly, by replacing .sub.ij with .sub.ij in (3.7), the cycle time at Step j, j.sub.n[i], in C.sub.i is:
.sub.ij=.sub.ij+.sub.i.(3.8)
(42) The robot cycle time for a dual-arm tool C.sub.i is:
.sub.i=(n[i]+1)(.sub.i+.sub.i)+.sub.j=0.sup.n[i].sub.ij=.sub.i1+.sub.i2.(3.9)
where .sub.i1=(n[i]+1)(.sub.i+.sub.i) is the robot cycle time without waiting and .sub.i2=.sub.j=0.sup.n[i].sub.ij is the robot's waiting time in a cycle.
(43) As the manufacturing process in each C.sub.i, i.sub.K, is serial, in the steady state, the productivity for each step must be same. Thus, C.sub.i should be scheduled such that
.sub.i=.sub.i0=.sub.i1= . . . =.sub.i(n[i])=.sub.i.(3.10)
(44) Notice that both .sub.i and .sub.i are functions of .sub.ij's, which means that the schedule for C.sub.i, i.sub.K, is parameterized by robots' waiting time. Based on the schedule for C.sub.i, i
.sub.K, to schedule a treelike hybrid K-cluster tool, the key is to determine .sub.ij's such that the activities of the multiple robots are coordinated to act in a paced way.
(45) Scheduling the Overall System
(46) A. Schedule Properties
(47) Let .sub.i=max{.sub.i0, .sub.i1, . . . , .sub.i(n[i]), .sub.i1} be 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; otherwise it is transport-bound. Let =max{.sub.1, .sub.2, . . . , .sub.K} and assume that =.sub.h, 1hK, or C.sub.h is the bottleneck tool. As mentioned above, C.sub.h is process-bound in a process-dominant treelike hybrid K-cluster tool. Let denote the cycle time for the system. With .sub.i being the cycle time of C.sub.i, to obtain a one-product cyclic schedule for a process-dominant treelike hybrid multi-cluster tool, every individual tool must have the same cycle time and it should be equal to the cycle time of the system, i.e.,
=.sub.i, i.sub.K.(4.1)
(48) Based on (4.1), to find a one-product cyclic schedule is to schedule the individual tools such that they can act in a paced way. Since both .sub.i and .sub.i are functions of .sub.ij's, given () as cycle time, a one-product cyclic schedule can be obtained by determining .sub.ij's for each tool C.sub.i, i.sub.K, j
.sub.n[i]. The individual tools are scheduled to be paced, if and only if for any adjacent pair C.sub.k and C.sub.i, k.Math.L, i.Math.{1}, linked by PS.sub.k(b[k].sub._.sub.q), 1qf[k], at any marking M: 1) whenever R.sub.i (R.sub.k) is scheduled to load a product (token) into p.sub.i0 (p.sub.k(b[k].sub._.sub.q)), t.sub.i0 (t.sub.k(b[k].sub._.sub.q)) is enabled; and 2) whenever R.sub.i (R.sub.k) is scheduled to unload a product (token) from p.sub.i0 (p.sub.k(b[k].sub._.sub.q)), .sub.i0 (.sub.k(b[k].sub._.sub.q)) is enabled. Given =, if a one-product cyclic schedule is found, the lower bound of cycle time is achieved.
(49) B. Existence of a One-Product Cyclic Schedule with the Lower Bound of Cycle Time (OSLB)
(50) For a process-dominant linear hybrid K-cluster tool, the conditions under which an OSLB exists are given as follows.
(51) Lemma 4.1: For a process-dominant linear hybrid K-cluster tool, an OSLB exists, if and only if, for any adjacent tool pair C.sub.i and C.sub.i+1, i.sub.K-1, the following conditions are satisfied by determining .sub.ij's and .sub.(i+1)l's, j.sub.n[i] and l.sub.n[i+1].
.sub.ij=.sub.(i+1)l=, j.sub.n[i] and l.sub.n[i+1].(4.2)
If C.sub.i and C.sub.i+1 are D-S case
.sub.i4.sub.i+1+3.sub.i+1+.sub.(i+1)(n[i+1]).(4.3)
If C.sub.i and C.sub.i+1 are S-S case
(4.sub.i+3.sub.i+.sub.i((b[i].sub._.sub.1)1))4.sub.i+1+3.sub.i+1.sub.(i+1)(n[i+1]).(4.4)
(52) Lemma 4.1 states that, to check the existence of an OSLB, one needs to examine the D-S and S-S cases only. By Lemma 4.1, given =, if conditions (4.2)-(4.4) are satisfied, a linear hybrid K-cluster tool can be scheduled such that the individual tools are paced. Notice that Condition (4.2) says that the cycle time of each individual tool is same, while Conditions (4.3) and (4.4) involve the operations of buffering modules only. Hence, although a treelike hybrid K-cluster tool is structurally different from a linear hybrid K-cluster tool, the similar conditions can be obtained for the existence of an OSLB. The following result are obtained.
(53) Theorem 4.1: 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}, linked 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].(4.5)
If C.sub.k and C.sub.i are D-S case
.sub.k4.sub.i+3.sub.i+.sub.i(n[i]).(4.6)
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]).(4.7)
(54) Proof: With the fact that a linear hybrid K-cluster tool is a special case of a treelike hybrid K-cluster tool, it follows from Lemma 4.1 that Conditions (4.5)-(4.7) must be necessary. Thus, it is necessary to show the if part only. If a C.sub.k in a treelike hybrid K-cluster tool is not a fork, it acts just as an individual tool in a linear hybrid K-cluster tool. Thus, it is only necessary to examine the fork tools.
(55) Assume that C.sub.k is a single-arm fork tool and C.sub.k.sub._.sub.1, C.sub.k.sub._.sub.2, . . . , C.sub.k.sub._.sub.f[k] are the set of its adjacent downstream tools. Based on M.sub.0, it can be assumed that the tool is at marking M with M(r.sub.k)=0; M(z.sub.kj)=M(d.sub.kj)=0, j.sub.n[k]; M(p.sub.k(b[k].sub._.sub.1))=0 and M(p.sub.kj)=1, j.sub.n[k]\{b[k]_1}; M(q.sub.kj)=0,j.sub.n[k]\{(b[k]_1)1}; and M(q.sub.k((b[k].sub._.sub.1)1))=1, implying that R.sub.k is waiting at PS.sub.k((b[k].sub._.sub.1)1)for unloading a product there. Then, if (4.5) holds, the tool can be scheduled as follows. For C.sub.k, R.sub.k unloads (firing .sub.k((b[k].sub._.sub.1)1)) a product from PS.sub.k((b[k].sub._.sub.1)1)), and then moves (x.sub.k((b[k].sub._.sub.1)1)) to PS.sub.k(b[k].sub._.sub.1) and loads (t.sub.k(b[k].sub._.sub.1)) the product into it. After firing t.sub.k(b[k].sub._.sub.1), u.sub.(k.sub._.sub.1)0 fires immediately. Then, with a backward strategy, after some time, R.sub.k comes to PS.sub.k((b[k].sub._.sub.f[k])1) and u.sub.k((b[k].sub._.sub.f[k])1) fires to unload the product in PS.sub.k((b[k].sub._.sub.f[k])1). Then, R.sub.k moves (x.sub.k((b[k].sub._.sub.f[k])1) to PS.sub.k(b[k].sub._.sub.f[k]) and loads (t.sub.k(b[k].sub._.sub.f[k])) the product into it. After firing t.sub.k(b[k].sub._.sub.f[k]), u.sub.k.sub._.sub.f[k])0 fires immediately. Similarly, the tool can be scheduled such that after firing t.sub.k(b[k].sub._.sub.q), q=2, 3, . . . f[k]1, ends, u.sub.(k.sub._.sub.q) 0 fires immediately. In this way, when R.sub.k comes to q.sub.k(b[k].sub._.sub.1) again, if C.sub.k.sub._.sub.1 is a single-arm tool and (4.7) is satisfied, C.sub.k.sub._.sub.1 can be scheduled such that firing t.sub.(k.sub._.sub.1)0 ends before R.sub.k comes to q.sub.k(b[k].sub._.sub.1), or u.sub.k(b[k].sub._.sub.1) is enabled when R.sub.k comes to q.sub.k(b[k].sub._.sub.1). If C.sub.k.sub._.sub.1 is a dual-arm tool, according to [Yang et al., 2014a], C.sub.k.sub.
(56) Notice that the conditions given in Theorem 4.1 are the functions of robots' waiting time of single-arm tools and have nothing to do with dual-arm tools. Thus, to schedule a treelike hybrid K-cluster tool is to determine .sub.ij's for single-arm tools C.sub.i, i.sub.K, j.sub.n[i], only. By this observation, for a dual-arm tool C.sub.i, i
.sub.K, simply set .sub.i0=.sub.i2=.sub.i1. Observe (4.6) and (4.7), it can be concluded that, for a single-arm tool C.sub.i, i
.sub.K, to make the conditions given in Theorem 4.1 satisfied, it is necessary to set .sub.ij's such that .sub.i((b[i].sub._.sub.q)1), q
.sub.f[i], and .sub.i(n[i]) are as small as possible. With this as a rule, the following discussion covers how to determine .sub.ij's for the single-arm tools sequentially from the leaves to the head one to find an OSLB.
(57) To ease the presentation, let h(z) be an arbitrary function and define .sub.x.sup.yh(z)=0 if x>y. It follows from the discussion of the last section that, for a single-arm tool C.sub.i, it is necessary to assign R.sub.i's idle time .sub.i2=2(n[i]+1)(.sub.i+.sub.i) into .sub.ij's. For a dual-arm tool C.sub.i, iL, set .sub.ij=0,j.sub.n[i], and .sub.i0=.sub.i2=.sub.i1. For a single-arm tool C.sub.i, iL, set .sub.ij=min{(4.sub.i+3.sub.i+.sub.i(j+1)), .sub.i1.sub.d=0.sup.j1 .sub.id}, j.sub.n[i]1 such that .sub.i(n[i])=.sub.i1.sub.j=0.sup.n[i]1.sub.ij is minimized. Then, for the adjacent upstream tool C.sub.k of C.sub.i with C.sub.k and C.sub.i being linked by PS.sub.k(b[k].sub._.sub.q), there are altogether four cases.
(58) For Case 1), C.sub.k is a dual-arm non-fork tool, check if .sub.k4.sub.i3.sub.i.sub.i(n[i])0. If not, there is no OSLB, otherwise for j.sub.n[k], set .sub.kj=0 and .sub.k0=.sub.k2=.sub.k1.
(59) For Case 2), C.sub.k is a single-arm non-fork tool, check if (4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i]))0. If not, there is no OSLB, otherwise set .sub.k[(b[k].sub._.sub.1)1]=min{(4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i])), .sub.k1}, .sub.kj=min{(4.sub.k+3.sub.k+.sub.k(j+1)), .sub.k1.sub.k((b[k].sub._.sub.1)1).sub.d=0.sup.j1.sub.kd (d(b[k]_1)1)}, j.sub.n[k]\{n[k], (b[k]_1)1}, and .sub.k(n[k])=.sub.k1.sub.k((b[k].sub._.sub.1)1).sub.j=0.sup.n[k]1 .sub.kj (j(b[k]_1)1).
(60) For Case 3), C.sub.k is a single-arm fork tool, check if (4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i]))0. If not, there is no OSLB, otherwise set .sub.k((b[k].sub._.sub.q)1)=min{(4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i]), .sub.k1.sub.d=1.sup.q1.sub.k((b[k].sub._.sub.d)1)}, .sub.kj=min{(4.sub.k+3.sub.k+.sub.k(j+1)), .sub.k1.sub.d=1.sup.f[k].sub.k((b[k].sub._.sub.d)1).sub.n=0.sup.j1 .sub.kn (n.Math.{(b[k]_h)1|h.sub.f[k]})}, j.sub.n[k]\{n[k]}\{(b[k]_h)1|h
.sub.f[k]}, and .sub.k(n[k])=.sub.k1.sub.d=1.sup.f(k).sub.k((b[k].sub._.sub.d)1).sub.j=0.sup.n[k]1.sub.kj (j.Math.{(b[k]_h)1|h
.sub.f[k]}).
(61) For Case 4), C.sub.k is a dual-arm fork tool, check if .sub.k4.sub.i3.sub.i.sub.i(n[i])0. If not, there is no OSLB, otherwise set .sub.kj=0, j.sub.n[k], and .sub.k0=.sub.k2=.sub.k1.
(62) Then, do the same for the adjacent upstream tool of C.sub.k and this process is repeated till C.sub.1 such that an OSLB is obtained if it exists, or the process terminates at a C.sub.k with no such a schedule. Based on the above discussion, let Q be a binary variable indicating the existence of an OSLB. Then, the present invention utilises the following algorithm to test the existence of an OSLB and find it if it exists.
(63) Algorithm 4.1: Test the existence of an OSLB for a treelike hybrid K-cluster tool
(64) Step 1: Initialization: Q=1, calculate .sub.i1 and .sub.i, i.sub.K, and =max {.sub.1, .sub.2, . . . , .sub.K}.
(65) Step 2: When iL:
(66) 2.1. If C.sub.i is a single-arm tool 2.2.1. .sub.ij=min{(4.sub.i+3.sub.i+.sub.i(j+1)), .sub.i1.sub.d=0.sup.j1.sub.id}, j.sub.n[i]1, and .sub.i(n[i])=.sub.i1.sub.j=0.sup.n[i]1 .sub.ij; 2.2.2. For its adjacent upstream tool C.sub.k, if it is a fork tool, go to Step 7; 2.2.3. Otherwise if it is a single-arm tool, go to Step 3, and if it is a dual-arm tool, Step 4;
(67) 2.2. If C.sub.i is a dual-arm tool 2.2.4. .sub.ij=0, .sub.i0=.sub.i2=.sub.i1, j.sub.n[i]; 2.2.5. For its adjacent upstream tool C.sub.k, if it is a fork tool, go to Step 7; 2.2.6. Otherwise if it is a single-arm tool, go to Step 6, and if it is a dual-arm tool, Step 5;
(68) Step 3: Determine .sub.kj for R.sub.k if C.sub.k and C.sub.i are S-S.
(69) 3.1. If (4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i]))<0, Q=0 and go to Step 8;
(70) 3.2. Else, .sub.k((b[k].sub._.sub.1)1)=min{(4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i])), .sub.k1};
(71) 3.3 .sub.kj=min{(4.sub.k+3.sub.k+.sub.k(j+1)), .sub.k1.sub.k((b[k].sub._.sub.1)1).sub.d=0.sup.j1.sub.kd(d(b[k]_1)1)}, j.sub.n[k]\{n[k], (b[k]_1)1};
(72) 3.4. .sub.k(n[k])=.sub.k1.sub.k((b[k].sub._.sub.1)1).sub.j=0.sup.n[k]1 .sub.kj (j(b[k]_1)1);
(73) 3.5. i=k with C.sub.k being its adjacent upstream tool. If k=0 go to Step 8, else if C.sub.k is a fork tool, go to Step 7; otherwise if it is a single-arm tool, go to Step 3.1, and if it is a dual-arm, go to Step 4;
(74) Step 4: Determine .sub.kj for R.sub.k if C.sub.k and C.sub.i are D-S.
(75) 4.1. If .sub.k(4.sub.i+3.sub.i+.sub.i(n[i]))<0, let Q=0 and go to Step 8;
(76) 4.2. Else, .sub.kj=0 and .sub.k0=.sub.k2=.sub.k1, j.sub.n[k];
(77) 4.3. i=k with C.sub.k being its adjacent upstream tool. If k=0 go to Step 8, else if C.sub.k is a fork tool, go to Step 7; otherwise, if it is a single-arm tool go to Step 6, and if it is a dual-arm one go to Step 5;
(78) Step 5: Determine .sub.kj for R.sub.k if C.sub.k and C.sub.i are D-D.
(79) 5.1. .sub.kj=0 and .sub.k0=.sub.k2=.sub.k1, j.sub.n[k];
(80) 5.2. i=k with C.sub.i being its adjacent upstream tool. If k=0 go to Step 8, else if C.sub.k is a fork tool go to Step 7; otherwise, if it is a single-arm tool go to Step 6, and if it is a dual-arm one go to Step 5.1;
(81) Step 6: Determine .sub.kj for R.sub.k if C.sub.k and C.sub.i are S-D.
(82) 6.1. .sub.k[(b[k].sub._.sub.1)1]=min{(4.sub.k+3.sub.k).sub.i, .sub.k1};
(83) 6.2. .sub.kj=min{(4.sub.k+3.sub.k+.sub.k(j+1)), .sub.k1.sub.k((b[k].sub._.sub.1)1).sub.d=0.sup.j1.sub.kd (d(b[k]_1)1)}, j.sub.n[k]\{n[k], (b[k]_1)1};
(84) 6.3. .sub.k(n[k])=.sub.k1.sub.k((b[k].sub._.sub.1)1).sub.j=0.sup.n[k]1 .sub.kj (j(b[k]_1)1);
(85) 6.4. i=k with C.sub.k being its adjacent upstream tool. If k=0 go to Step 8, else if C.sub.k is a fork tool go to Step 7; otherwise, if it is a single-arm tool go to Step 3, and if it is a dual-arm one go to Step 4;
(86) Step 7: Determine .sub.kj for R.sub.k if C.sub.k is a fork tool.
(87) 7.1. If C.sub.k is a single-arm fork tool 7.1.1. For C.sub.k and C.sub.i, when it is S-S, if (4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i]))<0, let Q=0 and go to Step 8; otherwise, .sub.k[(b[k].sub._.sub.q)1]=min{(4.sub.k+3.sub.k)(4.sub.i+3.sub.i+.sub.i(n[i])), .sub.k1.sub.d=1.sup.q1.sub.k((b[k].sub._.sub.d)1)}). When it is S-D case, .sub.k((b[k].sub._.sub.q)1)=min{(4k+3.sub.k).sub.i, .sub.k1.sub.d=1.sup.q1.sub.k((b[k].sub._.sub.d)1)}); 7.1.2. .sub.kj=min{(4.sub.k+3.sub.k+.sub.k(j1)), .sub.k1.sub.d=1.sup.f[k].sub.k((b[k].sub._.sub.d)1).sub.n=0.sup.j1.sub.kn(n.Math.{(b[k]_h)1|h.sub.f[k]})}, j.sub.n[k]\{n[k]}\{(b[k]_h)1|h
.sub.f[k]}; 7.1.3. .sub.k(n[k]).sub.k1.sub.d=1.sup.f[k].sub.k((b[k].sub._.sub.d)1).sub.j=0.sup.n[k]1 .sub.kj(j.Math.{(b[k]_h)1|h
.sub.f[k]}); 7.1.4. i=k with C.sub.k being its adjacent upstream tool. If k=0 go to Step 8, else if C.sub.k is a fork tool, go back to Step 7; otherwise, if it is a single-arm tool go to Step 3, and if it is a dual-arm one go to Step 4;
(88) 7.2. If C.sub.k is a dual-arm fork tool 7.2.1. For C.sub.k and C.sub.i, when it is D-S case, if .sub.k(4.sub.i+3.sub.i+.sub.i(n[i]))<0, let Q=0 and go to Step 8, otherwise, .sub.kj=0 and .sub.k0=.sub.k2=.sub.k1, j.sub.n[k]; 7.2.2. When it is D-D case, .sub.kj=0 and .sub.k0=.sub.k2=.sub.k1, j
.sub.n[k]; 7.2.3. i=k with C.sub.k being its adjacent upstream cluster. If k=0 go to Step 8, else if C.sub.k is a fork tool, go back to Step 7; otherwise, if it is a dual-arm tool go to Step 5, and if it is a single-arm tool, go to Step 6.
(89) Step 8: End and return Q.
(90) Using Algorithm 4.1, if Q=1 is returned, an OSLB is found for a process-dominant treelike hybrid K-cluster tool, otherwise there is no such a schedule. Based on Algorithm 4.1, to check if LB of cycle time can be achieved for a treelike hybrid K-cluster tool, it is necessary to set the robot waiting time from the leaf to the head one by one. In the worst case when Q=1 is returned, it is only necessary to set the robot waiting time for each individual tool once and check condition 4.6 or 4.7 for each buffering module once. Let H=max(n[1]+1, n[2]+1, . . . , n[K]+1). Since it is necessary need to set .sub.ij for each Step j in C.sub.i, i.sub.K, j.sub.n[i], there are at most HK operations in setting the robot waiting time. Meanwhile, there are K1 buffering modules for checking Condition 4.6 or 4.7. Hence, there are at most (H+1)K1 operations altogether. With H and K being bounded to known constants, the computational complexity of Algorithm 4.1 is bounded by a constant and thus it is very efficient.
EXAMPLE 1
(91) Example 1 is a treelike hybrid 3-cluster tool, where dual-arm tool C.sub.1 is a fork tool and its adjacent downstream tools are single-arm tools C.sub.2 and C.sub.3. In this example, their activity time is as follows. For C.sub.1, (.sub.10, .sub.11, .sub.12, .sub.13, .sub.1, .sub.1)=(0, 77, 0, 0, 13, 1); for C.sub.2, (.sub.20, .sub.21, .sub.22, .sub.2, .sub.2)=(0, 65, 69, 4, 1); for C.sub.3, (.sub.30, .sub.31, .sub.32, .sub.3, .sub.3)=(0, 61, 55, 6, 1).
(92) For C.sub.1, .sub.10=13 s, .sub.11=90 s, .sub.12=13 s, .sub.13=13 s, .sub.11=(n[1]+1)(.sub.1+.sub.1)=414=56 s, .sub.1=90 s and it is process-bound. For C.sub.2, .sub.20=19 s, .sub.21=84 s, .sub.22=88 s, .sub.21=2(n[2]+1)(.sub.2+.sub.2)=65=30 s and .sub.2=88 s. For C.sub.3, .sub.30=27 s, .sub.31=88 s, .sub.32=82 s, .sub.31=2(n[3]+1)(.sub.3+.sub.3)=67=42 s and .sub.3=88 s. This 3-cluster tool is process-dominant with .sub.1>.sub.2=.sub.3 and let =.sub.1=.sub.1=.sub.2=.sub.3=90 s. By Algorithm 4.1, the robots' waiting time is set as .sub.20=6 s, .sub.21=2 s, and .sub.22=.sub.21.sub.20.sub.21=903062=52 s; .sub.30=2 s, .sub.31=8 s, and .sub.32=.sub.31.sub.30.sub.31=904228=38 s. Then, for C.sub.1, as (4.sub.2+3.sub.2+.sub.22).sub.1=90(19+52)13=6>0 and, (4.sub.3+3.sub.3+.sub.32).sub.1=90(27+38)13=12>0, from Algorithm 4.1, a cyclic schedule with lower bound of cycle time can be obtained by setting .sub.10=34 s, .sub.11=.sub.12=.sub.13=0. Simulation is used to verify the correctness of the schedule as shown in Table II.
(93) From Table II, it can be seen that, by firing u.sub.20 immediately after R.sub.1's swap operation at p.sub.12, when R.sub.2 (R.sub.1) is scheduled to unload a product from p.sub.20(p.sub.12), M(p.sub.20)=1(M(p.sub.12)=1); when R.sub.2(R.sub.1) is scheduled to load a product into p.sub.20(p.sub.12), M(p.sub.20)=0(M(p.sub.12)=0). Similarly, R.sub.3(R.sub.1) can act as scheduled without being delayed by a buffering module if u.sub.30 fire immediately after R.sub.1's swap operation at p.sub.13. The Gantt chart for the schedule obtained is shown in
(94) TABLE-US-00002 TABLE II The simulation result for example 1. C.sub.1 C.sub.2 C.sub.3 Time Time Robot Time NO. interval(s) Robot action NO. interval(s) action NO. interval(s) Robot action 1 0-13 Swap 1 13-17 Unload 1 27-33 Unload at p.sub.12 from p.sub.20 from p.sub.30 2 13-14 Move 2 17-18 Move to 2 33-34 Move to to p.sub.13 p.sub.21 p.sub.31 3 14-27 Swap 3 18-22 Load 3 34-40 Load at p.sub.13 into p.sub.23 into p.sub.31 4 27-28 Move 4 22-23 Move to 4 40-41 Move to to p.sub.10 p.sub.22 p.sub.32 5 28-62 Wait at 5 23-75 Wait at 5 41-79 Wait at p.sub.10 p.sub.22 p.sub.32 6 62-75 Swap 6 75-79 Unload 6 79-85 Unload at p.sub.10 from p.sub.22 from p.sub.32 7 75-76 Move 7 79-80 Move to 7 85-86 Move to to p.sub.11 p.sub.20 p.sub.30 8 76-89 Swap 8 80-84 Load 8 86-92 Load at p.sub.11 into p.sub.20 into p.sub.30 9() 89-90 Move 9 84-85 Move to 9 92-93 Move to to p.sub.12 p.sub.21 p.sub.31 10 90-103 Swap 10 85-87 Wait at 10 93-101 Wait at at p.sub.12 p.sub.21 p.sub.31 11 103-104 Move 11 87-91 Unload 11 101-107 Unload to p.sub.13 from p.sub.21 from p.sub.31 12 104-117 Swap 12 91-92 Move to 12 107-108 Move to at p.sub.13 p.sub.22 p.sub.32 13 117-118 Move 13 92-96 Load 13 108-114 Load to p.sub.10 into p.sub.22 into p.sub.32 14 118-152 Wait at 14 96-97 Move to 14 114-115 Move to p.sub.10 p.sub.20 p.sub.30 15 152-165 Swap 15() 97-103 Wait at 15() 115-117 Wait at at p.sub.10 p.sub.20 p.sub.30
EXAMPLE 2
(95) Example 2 is a treelike hybrid 5-cluster tool, where C.sub.2 is a fork tool and its adjacent tools are C.sub.1, C.sub.3 and C.sub.5. C.sub.5 and C.sub.4 that is adjacent to C.sub.3 are leaf tools. Furthermore, C.sub.1 is a dual-arm tool and the others are all single-arm tools. Their activity time is as follows: for C.sub.1, (.sub.10, .sub.11, .sub.1, .sub.1)=(0, 61.5, 0, 28.5, 0.5); for C.sub.2, (.sub.20, .sub.21, .sub.22, .sub.2, .sub.2)=(0, 0, 0, 10, 1); for C.sub.3, (.sub.30, .sub.31, .sub.32, .sub.33, .sub.3, .sub.3)=(0, 56, 0, 58, 7, 1); for C.sub.4, (.sub.40, .sub.41, .sub.42, .sub.43, .sub.4, .sub.4)=(0, 56, 66, 65, 5, 1); and for C.sub.5, (.sub.50, .sub.51, .sub.52, .sub.5, .sub.5)=(0, 48, 50, 6, 1).
(96) For C.sub.1, .sub.10=28.5 s, .sub.11=90 s, .sub.12=28.5 s, .sub.11, .sub.11=(n[1]+1)(.sub.1+.sub.1)=329=87 s, .sub.1=90 s, and it is process-bound. For C.sub.2, .sub.20=43 s, .sub.21=43 s, .sub.22=43 s, .sub.21=2(n[2]+1)(.sub.2+.sub.2)=2311=66 s, and .sub.2=66 s. For C.sub.3, .sub.30=31 s, .sub.31=87 s, .sub.32=31 s, .sub.33=89 s, .sub.31=2(n[3]+1)(.sub.3+.sub.3)=248=64 s, and .sub.3=89 s. For C.sub.4, .sub.40=23 s, .sub.41=79 s, .sub.42=89 s, .sub.43=88 s, .sub.41=2(n[4]+1)(.sub.4+.sub.4)=246=48 s, and .sub.4=89 s. For C.sub.5, .sub.50=27 s, .sub.51=75 s, .sub.52=77 s, .sub.51=2(n[5]+1)(.sub.5+.sub.5)=237=42 s, and .sub.5=77 s. This is shown that it is process-dominant with =.sub.1=90 s. Next, let =.sub.1=.sub.2=.sub.3=.sub.4=.sub.5=90 s.
(97) By Algorithm 4.1, for C.sub.4, .sub.40=11 s, .sub.41=1 s, .sub.42=2 s, and .sub.43=.sub.41.sub.40.sub.41.sub.42=90481112=28 s. For C.sub.5, .sub.50=15 s, .sub.51=13 s, and .sub.52=.sub.51.sub.50.sub.51=90421513=20 s. For C.sub.3, since (4.sub.4+3.sub.4+.sub.43)(4.sub.3+3.sub.3)=90(23+28)31=8>0, set .sub.31=min{8,.sub.31}=min{8,26}=8 s, .sub.30=min{90.sub.31,.sub.31.sub.31}=min{3,268}=3 s, .sub.32=min{90.sub.33,.sub.31.sub.31.sub.30}=min{1,2683}=1 s, and .sub.33=.sub.31.sub.30.sub.32=26831=14 s. For C.sub.2, (4.sub.3+.sub.3+.sub.33)(4.sub.2+3.sub.2)=90(31+14)43=2>0, set .sub.20=min{2,.sub.21}=min{2,24}=2 s. With (4.sub.5+3.sub.5+.sub.52)(4.sub.2+3.sub.2)=90(27+20)43=0, set .sub.21=min{0,.sub.21.sub.20}=min{0,22}=0. At last, set .sub.22=.sub.21.sub.20.sub.21=2420=22 s. For C.sub.1 and C.sub.2, since (4.sub.2+3.sub.2+.sub.22).sub.1=90(43+22)28.5=3.5<0, or condition (4.6) is violated, i.e., there is no one-product cyclic schedule to achieve its lower bound and this result can also be verified by simulation.
(98) The embodiments of the present invention are particularly advantageous as it provides a solution for scheduling a treelike multi-cluster tool with a complex topology which is process-bound. By developing a Petri net model to describe the system based mainly on the buffering modules, the necessary and sufficient conditions under which a one-wafer cyclic schedule with the lower bound of cycle time can be found. The present invention also proposes an efficient algorithm to test whether such a schedule exists and to find it if it exists.
(99) Although not required, the embodiments described with reference to the Figures can be implemented as an application programming interface (API) or as a series of libraries for use by a developer or can be included within another software application, such as a terminal or personal computer operating system or a portable computing device operating system. Generally, as program modules include routines, programs, objects, components and data files assisting in the performance of particular functions, the skilled person will understand that the functionality of the software application may be distributed across a number of routines, objects or components to achieve the same functionality desired herein.
(100) It will also be appreciated that where the methods and systems of the present invention are either wholly implemented by computing system or partly implemented by computing systems then any appropriate computing system architecture may be utilized. This will include stand-alone computers, network computers and dedicated hardware devices. Where the terms computing system and computing device are used, these terms are intended to cover any appropriate arrangement of computer hardware capable of implementing the function described.
(101) It will be appreciated by persons skilled in the art that numerous variations and/or modifications may be made to the invention as shown in the specific embodiments without departing from the spirit or scope of the invention as broadly described. The present embodiments are, therefore, to be considered in all respects as illustrative and not restrictive.
(102) Any reference to prior art contained herein is not to be taken as an admission that the information is common general knowledge, unless otherwise indicated.