Patent Document ID: 10073444
Application ID: 14919720
Patent Flag: 1

Claim One:
1. A computer-implemented method for scheduling a treelike hybrid K-cluster tool with a plurality of branches, sub-trees (ST) and extended sub-trees (EST) to generate a one-wafer cyclic schedule, the treelike hybrid K-cluster tool having K single-cluster tools denoted as C 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, Θ being the cycle time for all the branches as iteratively calculated with a maximum fundamental period Π being a given initial cycle time, where the one-wafer cyclic schedule of the treelike hybrid K-cluster tool cannot be found with the given initial cycle time, the method comprising: determining fundamental periods (FP) Π 1 , Π 2 ,. .. , Π K for the single-cluster tools C 1 , C 2 ,. .. , C K and applying a maximum fundamental period Π=max{Π 1 , Π 2 ,. .. , Π K } as the given initial cycle time Θ; determining a one-wafer cyclic schedule for each of the ST (ST i ) by increasing the cycle time Θ by Δ, wherein the ST comprises one or more branches; wherein the determining of one-wafer cyclic schedule for each of the ST comprises: determining the k such that C k is an upstream adjacent tool of C j ; determining a one-wafer cyclic schedule for each of the EST (EST j ) based on a generating algorithm by increasing the cycle time Θ by Δ if C k is not a fork tool, wherein the EST comprises one or more ST and the generating algorithm further comprises: (S1.1) determining, responsive for finding that k∉F and A i(n[i]) ≠0, a time increment Δm 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 , (S1.2) computing, responsive for finding that Δ=min{Δ p |p∈S i }=Δ i , (S1.2.1) in EST i or B i , for p∉S i : responsive for finding that p∉L, ω p((b[p] _ 1)−1) =A p((b[p] _ 1)−1) +Δ; responsive for finding that p∈L, ω p0 =A p0 +Δ; (S1.2.2) in EST i or B i , responsive for finding that p∈S i and p∉F: further responsive for finding that p∈L, ω pj =A pj +Y for j∈D[p], or for j∈ n[p] {n[p]}; further responsive for finding that 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 +Δ; and ω p(n[p]) =A p(n[p]) −Σ q∈S p B[q]×Y; (S1.2.3) in EST i , responsive for finding that p∈S i and p∈F: ω 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 ] ⁢ ⁢ _ ⁢ ⁢ d ) - 1 ) = A p ⁡ ( ( b ⁡ [ p ] ⁢ ⁢ _ ⁢ ⁢ d ) - 1 ) + ( ∑ q ∈ S p ⁢ ⁢ _ ⁢ ⁢ d ⁢ B ⁡ [ q ] + 1 ) × Y , ⁢ d ∈ { 2 , 3 , … ⁢ , f ⁡ [ p ] } ; and ω p ⁡ ( n ⁡ [ p ] ) = A p ⁡ ( n ⁡ [ p ] ) - ∑ q ∈ S p ⁢ B ⁡ [ q ] × Y ; (S1.3) responsive for finding that Δ=min{Δ p |p∈S i }=Δ f ≠Δ i , 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); and the generating algorithm is implemented by a wafer handling robot in a wafer processing device in a semiconductor manufacturing industry for determining the one-wafer cyclic schedule for each of the EST, an optimized schedule is obtained with an optimal cycle time Θ for the treelike hybrid K-cluster tool; where: Condition 1 is that 0 < A i ⁡ ( n ⁡ [ i ] ) ≤ ∑ p ∈ S i ⁢ B ⁡ [ p ] × Φ i ⁡ ( S , S ) 1 + ∑ p ∈ S i ⁢ B ⁡ [ p ] and an 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 the S-S case is considered, Condition 3 is that a D-S case is considered; Y=Φ i (S,S)−A (i(n[i]) when the Condition 1 is satisfied; Y = Φ i ⁡ ( S , S ) 1 + ∑ p ∈ S i ⁢ B ⁡ [ p ] when the Condition 2 is satisfied; Y = Φ i ⁡ ( D , S ) 1 + ∑ p ∈ S i ⁢ B ⁡ [ p ] when the Condition 3 is satisfied; L denotes an index set of leaf tools in the treelike hybrid K-cluster tool; F denotes an index set of fork tools in the treelike hybrid K-cluster tool; ST j denotes a ST with C j being a fork tool and a root node of the ST, and EST i is an EST 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 as obtained after the cycle time is increased by Δ, 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 as determined for the cycle time Θ; 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 p ; 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 =N L ∪{0}.