Petri Net-Based Optimal One-Wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools

摘要

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

主权项

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 C1, C2, . . . , CK, with C1 being a head tool of the treelike hybrid K-cluster tool, the single-cluster tool Ck, k∈K, having a robot Rk 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 ESTk or STk, with Ci being a downstream adjacent tool of Ck and with Θ being the given value of cycle time for ESTi, STi or Bi, comprises the steps of: (S1) if Θ is not an optimal cycle time for ESTk or STk, and if k∉F and Ai(n[i])≠0, then performing Steps (S1.1), (S1.2) and (S1.3); (S1.1) for m∈Si, calculating Δm's according to
Δm=Am(n[m])/Σp∈SmB[p] if m>i andΔm=Δi={Φi(S,S)-Ai(n[i])forCondition1,Φi(S,S)1+∑p∈SiB[p]forCondition2,Φi(D,S)1+∑p∈SiB[p]forCondition3,ifm=i, where Condition 1 is that0Y=Φi(S,S)−Ai(n[i]) when Condition 1 is satisfied;Y=Φi(S,S)1+∑p∈SiB[p]  when Condition 2 is satisfied; andY=Φi(D,S)1+∑p∈SiB[p]  when Condition 3 is satisfied; (S1.2.1) in ESTi or Bi, for p∉Si, if p∉L, then setting ωp((b[p]_1)-1)=Ap((b[p]_1)-1)+Δ, else setting ωp0=Ap0+Δ; (S1.2.2) in ESTi or Bi, if p∈Si and p∉F, then setting:
ωpj=Apj+Y for j∈D[p], or for j∈n[p]/{n[p]} if p∈L; ωp((b[p]_1)-1)=Ap((b[p]_1)-1)+Σq∈Sp/{p}B[q]×Ai(n[i])/(Σp∈SiB[p])+Δ, or ωp0=Ap0+Δ if p∈L; andωp(n[p])=Ap(n[p])−Σq∈SpB[q]×Y; (S1.2.3) in ESTi, if p∈Si and p∈F, then setting:
ωpj=Apj+Y,j∈D[p];ωp((b[p]_1)−1)=Ap((b[p]_1)−1)+∈q∈Sp−1B[q]×Y+Δ;ωp((b[p]_1)−1)=Ap((b[p]_1)−1)+∈q∈Sp−1B[q]+Y,d∈{2,3, . . . ,f[p]}; andωp(n[p])=Ap(n[p])−Σq∈SpB[q]×Y; (S1.3) if Δ=min{Δp|p∈Si}=Δ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; STj denotes a ST (sub-tree) with Cj being a fork tool, and ESTi is an EST (extended sub-tree) of STj with none of Ci, Ci+1, . . . , Cj-2, Cj-1 being a fork tool; Bi, starting from Ci and ends at Cm, m∈L, denotes a linear multi-cluster tool in the treelike K-cluster tool; ωij is a robot waiting time of Ri at Step j, j∈Ωn[i], n[i] being an index of a last processing step of Ci; Akj is a robot waiting time at Step j for Rk, computed under an assumption that Θ=Π, Π being a fundamental period of a bottleneck tool among the K single-cluster tools; Si is a set of single-cluster tools connected to Ci 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 Cp; D[p] be a set of processing steps in Cy; f[i], 1≦f[i]≦n[i], denotes the number of outgoing modules in Ci, i∉L; Φi+1(S, S)=4λi+1+3μi+1+A(i+1)(n[i+1])−Θ+4λi+3μi when Ci and Ci+1 are S-S, and Φi+1(D, S)=4λi+1+3μi+1+A(i+1)(n[i+1])−Θ+λi, when Ci and Ci+1 are D-S; λi is a time taken by Ri to load or unload a wafer in Ci; μi is a time taken by Ri to move between process modules of Ci for transiting from one processing step to another; L={1, 2, . . . , L} for a positive integer L; and ΩL=L∪{0}.