Patent Document ID: 20170083009
Application ID: 14919720
Patent Flag: 0

Claim One:
1. A computer-implemented method for scheduling a treelike hybrid K-cluster tool to generate a one-wafer cyclic schedule, the treelike hybrid K-cluster tool having K single-cluster tools denoted as C 1 , C 2 ,. .. , C K , with C 1 being a head tool of the treelike hybrid K-cluster tool, the single-cluster tool C k , k∈ K , having a robot R k for wafer handling, the method comprising: given a value of cycle time, generating a part of the schedule for a section of the K-cluster tool by performing a generating algorithm, the section of the K-cluster tool being either an extended sub-tree (EST) or a sub-tree (ST); wherein the generating algorithm for EST k or ST k , with C i being a downstream adjacent tool of C k and with Θ being the given value of cycle time for EST i , ST i or B i , comprises the steps of: (S1) if Θ is not an optimal cycle time for EST k or ST k , and if k∉F and A i(n[i]) ≠0, then performing Steps (S1.1), (S1.2) and (S1.3); (S1.1) for m∈S i , calculating Δ m 's according to 
 Δ m =A m(n[m]) /Σ p∈S m B[p ] if m>i and Δ m = Δ i = { Φ i ( S , S ) - A i ( n [ i ] ) for Condition 1 , Φ i ( S , S ) 1 + ∑ p ∈ S i B [ p ] for Condition 2 , Φ i ( D , S ) 1 + ∑ p ∈ S i B [ p ] for Condition 3 , if m = i , where Condition 1 is that 0 < A i ( n [ i ] ) ≤ ∑ p ∈ S i B [ p ] × Φ i ( S , S ) 1 + ∑ p ∈ S i B [ p ] and S-S case is considered, Condition 2 is that A ( i + 1 ) ( n [ i + 1 ] ) ≥ ∑ p ∈ S i B [ p ] × Φ i ( S , S ) 1 + ∑ p ∈ S i B [ p ] and S-S case is considered, and Condition 3 is that D-S case is considered; (S1.2) if Δ=min{Δ p |p∈S i }=Δ i , then performing Steps (S1.2.1), (S1.2.2) and (S1.2.3) with: Y=Φ i (S,S)−A i(n[i]) when Condition 1 is satisfied; Y = Φ i ( S , S ) 1 + ∑ p ∈ S i B [ p ] when Condition 2 is satisfied; and Y = Φ i ( D , S ) 1 + ∑ p ∈ S i B [ p ] when Condition 3 is satisfied; (S1.2.1) in EST i or B i , for p∉S i , if p∉L, then setting ω p((b[p] _ 1)-1) =A p((b[p] _ 1)-1) +Δ, else setting ω p0 =A p0 +Δ; (S1.2.2) in EST i or B i , if p∈S i and p∉F, then setting: 
 ω pj =A pj +Y for j∈D[p ], or for j∈ n[p] {n[p ]} if p∈L; 
 ω p((b[p] _ 1)-1) =A p((b[p] _ 1)-1) +Σ q∈S p {p} B[q]×A i(n[i]) /(Σ p∈S i B[p ])+Δ, or ω p0 =A p0 +Δ if p∈L ; and 
 ω p(n[p]) =A p(n[p]) −Σ q∈S p B[q]×Y; (S1.2.3) in EST i , if p∈S i and p∈F, then setting: 
 ω pj =A pj +Y,j∈D[p ]; 
 ω p((b[p] _ 1)−1) =A p((b[p] _ 1)−1) +∈ q∈S p−1 B[q]×Y+Δ; 
 ω p((b[p] _ 1)−1) =A p((b[p] _ 1)−1) +∈ q∈S p−1 B[q]+Y,d∈{ 2 , 3 ,. .. ,f[p]}; and 
 ω p(n[p]) =A p(n[p]) −Σ q∈S p B[q]×Y; (S1.3) if Δ=min{Δ p |p∈S i }=Δ f ≠Δ i , then performing the Steps (S1.2.1), (S1.2.2) and (S1.2.3) with Y=Δ f followed by repeating the Steps (S1.1), (S1.2) and (S1.3); where: L denotes an index set of leaf tools in the treelike hybrid K-cluster tool; F denotes an index set of fork tools in the treelike hybrid K-cluster tool; ST j denotes a ST (sub-tree) with C j being a fork tool, and EST i is an EST (extended sub-tree) of ST j with none of C i , C i+1 ,. .. , C j-2 , C j-1 being a fork tool; B i , starting from C i and ends at C m , m∈L, denotes a linear multi-cluster tool in the treelike K-cluster tool; ω ij is a robot waiting time of R i at Step j, j∈Ω n[i] , n[i] being an index of a last processing step of C i ; A kj is a robot waiting time at Step j for R k , computed under an assumption that Θ=Π, Π being a fundamental period of a bottleneck tool among the K single-cluster tools; S i is a set of single-cluster tools connected to C i and selected from the K single-cluster tools; B[k]=n[k]−1; b[p]_d is an index denoting a d-th outgoing module of C p ; D[p] be a set of processing steps in C y ; f[i], 1≦f[i]≦n[i], denotes the number of outgoing modules in C i , i∉L; Φ i+1 (S, S)=4λ i+1 +3μ i+1 +A (i+1)(n[i+1]) −Θ+4λ i +3μ i when C i and C i+1 are S-S, and Φ i+1 (D, S)=4λ i+1 +3μ i+1 +A (i+1)(n[i+1]) −Θ+λ i , when C i and C i+1 are D-S; λ i is a time taken by R i to load or unload a wafer in C i ; μ i is a time taken by R i to move between process modules of C i for transiting from one processing step to another; L ={1, 2,. .. , L} for a positive integer L; and Ω L = L ∪{0}.