# US 9,227,318 B1 · Optimal buffer space configuration and scheduling for single-arm multi-cluster tools

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,227,318 B1
- Document ID: US9227318B1
- Status: Granted
- Kind: B1
- Application number: 14/639,137
- Filed: 2015-03-05
- Granted: 2016-01-05
- Earliest claimed: 2015-01-12
- Assignees: Macau University of Science and Technology
- Applicants: Macau University of Science and Technology
- Inventors: Liping Bai; Naiqi Wu; Zhiwu Li; Mengchu Zhou
- Web page: https://patentgrep.com/patent/US9227318B1

## CPC

- B25J 9/009: {being mechanically linked with one another at their distal ends}
- G05B 19/41865: {characterised by job scheduling, process planning, material flow}
- H10P 72/0461: {characterised by the presence of two or more transfer chambers}
- H10P 72/0612: {Production flow monitoring, e.g. for increasing throughput}
- G05B 2219/45032: Wafer manufacture; interlock, load-lock module
- G06F 30/22: using Petri net models
- Y10S 901/02: Arm motion controller
- Y10S 901/41: Tool
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- H10P: GENERIC PROCESSES OR APPARATUS FOR THE MANUFACTURE OR TREATMENT OF DEVICES COVERED BY CLASS H10
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method for scheduling single-arm multi-cluster tools is provided. The present invention studies the scheduling problem of a single-arm multi-cluster tool with a linear topology and process-bound bottleneck individual tool. Its objective is to find a one-wafer cyclic schedule such that the lower bound of cycle time is reached by optimally configuring spaces in buffering modules that link individual cluster tools. A Petri net model is developed to describe the dynamic behavior of the system by extending resource-oriented Petri nets such that a schedule can be parameterized by robots' waiting time. Based on this model, conditions are presented under which a one-wafer cyclic schedule with lower bound of cycle time can be found. With the derived conditions, an algorithm is presented to find such a schedule and optimally configure the buffer spaces.

## Claims

### Claim 1

A computer implemented method for scheduling single-arm multi-cluster tools with optimal buffer space configuration, comprising:
obtaining, by a processor, a wafer processing time, a robot wafer loading and unloading time, and a robot moving time;
calculating, by a processor, a shortest time for completing a wafer based on the wafer processing time, the robot wafer loading and unloading time, and the robot moving time;
calculating, by a processor, a robot cycle time based on the robot wafer loading and unloading time, and the robot moving time;
determining, by a processor, a fundamental period based on selecting a maximum value among the shortest time for completing the wafer and the robot cycling time;
determining, by a processor, a type of cluster tool by:
if the fundamental period is a value of the shortest time for completing the wafer, the type of cluster tool is process-bound;
otherwise the type of cluster tool is a transport-bound;
determining, by a processor, the multi-cluster tools to be process-bound, or transport-bound based on the type of cluster tool having a maximum value of the fundamental period;
determining, by a processor, a lower bound of cycle time based on the maximum value of the fundamental period;
determining, by a processor, an algorithm for scheduling and buffer space configuration based on a petri net model; and
calculating, by a processor, a robot waiting time based on the algorithm;
calculating, by a processor, a wafer sojourn time based on the algorithm and the lower bound of cycle time;
determining, by a processor, a buffer space for buffer module based on the wafer sojourn time and the robot waiting time; and
obtaining, by a processor, a schedule based on the buffer space for buffer module and the lower bound of cycle time.

### Claim 2 (depends on 1)

The method of claim 1, wherein the shortest time for completing the wafer is calculated by:
ζij=αij+4λi+3μi,i∈K and j∈n[i]
ζij denotes a shortest time for completing a wafer for a cluster tool i at step j;
αij denotes a wafer processing time for a cluster tool i at step j;
λi denotes a robot wafer loading and unloading time for a cluster tool i;
μi denotes a robot moving time for a cluster tool i;
K denotes a total number of cluster tools; and
n[i] denotes a total number of steps for a cluster tool i.

### Claim 3 (depends on 1)

The method of claim 1, wherein the robot cycle time is calculated by:
ψi=2(n[i]+1)(λi+μi)+Σj=0n[i]ωij,i∈K
ψi denotes a robot cycle time for a cluster tool i;
λi denotes a robot wafer loading and unloading time for a cluster tool i;
μi denotes a robot moving time for a cluster tool i;
Σj=0n[i]ωij denotes a waiting time in a cycle for a cluster tool i; and
K denotes a total number of cluster tools.

### Claim 4 (depends on 1)

The method of claim 1, wherein the fundamental period is determined by:
πi=max{ζi0,ζi1, . . . ,ζi(n[i]),ψi1}
πi denotes a fundamental period for a cluster tool i;
ζi0, ζi1, . . . , ζi(n[i]) denote shortest times for a cluster tool i at different steps; and
ψi1 denotes a robot cycle time for a cluster tool i.

### Claim 5 (depends on 1)

The method of claim 1, wherein the maximum value of the fundamental period π is determined by:
π=max{π1,π2, . . . ,πK}
π1, π2, . . . , πK denote different fundamental periods for different cluster tools.

### Claim 6

A non-transitory computer-readable medium whose contents cause a computing system to perform a computer implemented method for scheduling single-arm multi-cluster tools with optimal buffer space configuration, the method comprising:
obtaining, by a processor, a wafer processing time, a robot wafer loading and unloading time, and a robot moving time;
calculating, by a processor, a shortest time for completing a wafer based on the wafer processing time, the robot wafer loading and unloading time, and the robot moving time;
calculating, by a processor, a robot cycle time based on the robot wafer loading and unloading time, and the robot moving time;
determining, by a processor, a fundamental period based on selecting a maximum value among the shortest time for completing the wafer and the robot cycling time;
determining, by a processor, a type of cluster tool by:
if the fundamental period is a value of the shortest time for completing the wafer, the type of cluster tool is process-bound;
otherwise the type of cluster tool is a transport-bound;
determining, by a processor, the multi-cluster tools to be process-bound, or transport-bound based on the type of cluster tool having a maximum value of the fundamental period;
determining, by a processor, a lower bound of cycle time based on the maximum value of the fundamental period;
determining, by a processor, an algorithm for scheduling and buffer space configuration based on a petri net model; and
calculating, by a processor, a robot waiting time based on the algorithm;
calculating, by a processor, a wafer sojourn time based on the algorithm and the lower bound of cycle time;
determining, by a processor, a buffer space for buffer module based on the wafer sojourn time and the robot waiting time; and
obtaining, by a processor, a schedule based on the buffer space for buffer module and the lower bound of cycle time.

### Claim 7 (depends on 6)

The non-transitory computer-readable medium of claim 6, wherein the shortest time for completing the wafer is calculated by:
ζij=αij+4λi+3μi,i∈K and j∈n[i]
ζij denotes a shortest time for completing a wafer for a cluster tool i at step j;
αij denotes a wafer processing time for a cluster tool i at step j;
λi denotes a robot wafer loading and unloading time for a cluster tool i;
μi denotes a robot moving time for a cluster tool i;
K denotes a total number of cluster tools; and
n[i] denotes a total number of steps for a cluster tool i.

### Claim 8 (depends on 6)

The non-transitory computer-readable medium of claim 6, wherein the robot cycle time is calculated by:
ψi=2(n[i]+1)(λi+μi)+Σj=0n[i]ωij,i∈K
ψi denotes a robot cycle time for a cluster tool i;
λi denotes a robot wafer loading and unloading time for a cluster tool i;
μi denotes a robot moving time for a cluster tool i;
Σj=0n[i]ωij denotes a waiting time in a cycle for a cluster tool i; and
K denotes a total number of cluster tools.

### Claim 9 (depends on 6)

The non-transitory computer-readable medium of claim 6, wherein the fundamental period is determined by:
πi=max{ζi0,ζi1, . . . ,ζi(n[i]),ψi1}
πi denotes a fundamental period for a cluster tool i;
ζi0, ζi1, . . . , ζi(n[i]) denote shortest times for a cluster tool i at different steps; and
ψi1 denotes a robot cycle time for a cluster tool i.

### Claim 10 (depends on 6)

The non-transitory computer-readable medium of claim 6, wherein the maximum value of the fundamental period π is determined by:
π=max{π1,π2, . . . ,πK}
π1, π2, . . . , πK denote different fundamental periods for different cluster tools.