Petri Net-based Scheduling of Time Constrained Single-arm Cluster Tools with Wafer Revisiting

A non-transitory computer-readable medium whose contents cause a computing system to perform a computer-implemented method for scheduling a cluster tool, the cluster tool comprising a single-arm robot for wafer handling, a wafer-processing system comprising four process modules including PM1, PM2, PM3, and PM4, each for performing a wafer-processing step with a wafer residency time constraint where the ith process module, iε{1, 2, . . . 4}, is used for performing Step i of the wafer-processing steps for each wafer, and a wafer flow pattern having (PM1, (PM2, PM3)h, PM4) with (PM2, PM3)h being the revisiting process and h≧2, the method comprising:

• obtaining, by a processor, a lower bound ziL of a production cycle of Step i,iε{1, 2, . . . 4}, as follows:
• π1L=α1+3μ+4λ;
• π2L=2α2+α3+5μ+8λ;
• π3L=2α3+α2+5μ+8λ;
• and
• π4L=α4+3μ+4λ;
• obtaining, by a processor, an upper bound πiU of a production cycle of Step i, iε{1, 2, . . . , 4}, as follows:
• π1U=α1+3μ+4λ;
• π2U=2α2+α3+5μ+8λ;
• π3U=2α3+α2+5μ+8λ;
• and
• π4U=α4+3μ+4λ;
• obtaining, by a processor, a maximum lower bound πLmax as follows:
• πLmax=max{πiL,iε4};
• obtaining, by a processor, a minimum upper bound πUmin as follows:
• πUmin=min{πiU,iε4};
• determining, by a processor, a robot task time η1 in a cycle as follows:
• η1=14λ+12μ+α2+α3;
• determining, by a processor, a robot waiting time ωi of Step i as follows:
• if [π1L,π1U]∩[π2L,π2U]∩[π3L,π3U]∩[π4L,π4U]≠Ø and η1<πLmax, then setting ω0=ω1=ω2=ω3=0, and setting ω4=πLmax−η1;
• else if [π1L,π1U]∩[π2L,π2U]∩[π3L,π3U]∩[π4L,π4U]≠Ø and πLmax≦η1≦πUmin, then setting ω0=ω1=ω2=ω3=0;
• else if [π1L,π1U]∩[π2L,π2U]∩[π3L,π3U]∩[π4L,π4U]=Ø and πLmax≦η1≦πUmin, then setting ωi,iεΩ3 by
• ω
• i
• -
• 1
• =
• {
• 0
• ,
• i
• ∈
• F
• π
• Lmax
• -
• α
• i
• -
• δ
• i
• -
• 4
• 
• λ
• -
• 3
• 
• μ
• ,
• i
• ∈
• E
• ⋂
• {
• 1
• ,
• 4
• }
• π
• Lmax
• -
• 2
• 
• α
• 2
• -
• δ
• 2
• -
• α
• 3
• -
• 5
• 
• μ
• -
• 8
• 
• λ
• ,
• i
• ∈
• E
• ⋂
• {
• 2
• }
• π
• Lmax
• -
• 2
• 
• α
• 3
• -
• δ
• 3
• -
• α
• 2
• -
• 5
• 
• μ
• -
• 8
• 
• λ
• ,
• i
• ∈
• E
• ⋂
• {
• 3
• }
• 
• 
• and
• 
• 
• setting
• 
• 
• ω
• 4
• =
• π
• Lmax
• -
• η
• 1
• -
• ∑
• i
• =
• 0
• 3
• 
• 
• ω
• i
• ;
• wherein:
• αi, iε4, is a time that a wafer is processed in the ith process module;
• δi iε4, is a longest time that a wafer stays in the ith process module after being processed;
• λ is a time that a wafer is loaded or unloaded by the robot from Step i;
• μ is a time that a wafer is moved by the robot from Step i to Step j;
• E={i|πiU<πLmax, iε4};
• and
• F=4\E.