Scheduling method for single-arm cluster toolsof wafer fabrications with residency and continuous reentrancy

Zhou Binghai Wang Zhu Chen Jia

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

With the rapid development of the semiconductor manufacturing technology, especially the diameter of wafers expanding to 300 mm, cluster tools are adopted widely in the modern semiconductor industry. Cluster tools have diverse scheduling requirements such as complex wafer flow patterns, wafer residency time constraints, and resource constraints, etc. It is difficult to solve their scheduling problems. How to improve the scheduling performance is of great significance to reduce cost and shorten the cycle time of semiconductor wafer fabrications.

Venkatesh et al.[1]studied how to schedule robotic tasks of single-arm cluster tools, but their methods are based on the assumption of wafer processing without residency time constraints. Currently, there is some related literature on scheduling problems of single-arm cluster tools with residency time constraints. Lee et al.[2-3]studied the scheduling problem of the minimum period under the steady state and established an algorithm to search for the minimum period, but the calculation is too complex. Rostami et al.[4-5]studied the schedulability problem of cluster tools and considered residency time constraints.They presented a linear programming-based method to find an optimal periodic schedule with a buffer module. However, the method only considered the scheduling problem of a single wafer product type. Yoon and Lee[6]established a scheduling model with residency time constraints and put forward a kind of online scheduling algorithm with different product types. The literature mentioned above has not considered continuous reentrant processing requirements.

Perkinson et al.[7]presented an analysis model of the effect of redundant processing chambers and chamber reentrant process sequences on steady-state throughput. Lee et al.[8]used Petri net models to develop deadlock avoidance conditions and built a mixed integer programming model. However, the mathematical method is not suitable for solving large-scale scheduling problems with reentrant wafer flows. Zuberek et al.[9-10]developed timed Petri nets to model and analyze scheduling problems of cluster tools with chamber reentrancy. Nevertheless, only the static scheduling problem of robot operations is considered. Jung et al.[11]proposed a mixed integer programming model to minimize the cycle time of timed Petri net models of cluster tools with various scheduling requirements. Wu et al.[12-13]developed resource-oriented Petri net models with colors and time introduced to describe the operations of cluster tools. Kim et al.[14]determined the cycle time of a cluster tool with the timed event graph model. Wu et al.[15]developed a formal Petri net model to address the real-time operational problem with residency time constraints. These methods are applicable to various reentrant processing types, but none addresses residency time constraints.

The methods mentioned above cannot fully adapt to the practical applications when residency time and reentrancy constraints are separately considered to study the scheduling problem of single-arm cluster tools. At present, there are only a few works on scheduling problems of single-arm cluster tools with residence time and reentrancy constraints. In this paper, the scheduling problem of single-arm cluster tools is explored with residency time constraints, continuous reentrancy constraints and diverse wafer product types.

1 Problem Formulations

A single-arm cluster tool consists of several process modules (PMs), a transport module (TM), and loadlocks (LLs). The logic chart is shown in Fig.1. The PMs execute wafer processes. The LLs are used for storing the unprocessed and processed wafers. The TM unloads a wafer from one LL to the PM, loads it back to the other LL, and moves the wafer from one PM to another PM.

Fig.1 Single-arm cluster tool logic chart

To effectively formulate a scheduling problem domain, the following assumptions are given:

1) The TM is a single-arm robot, which can pick, place or transport only one wafer at a time; the time of loading, unloading and transporting a wafer among different PMs and LLs can be variable.

2) Each PM only processes one wafer at a time.

3) There exists the phenomenon of consecutive reentrant processing between two adjacent PMs, i.e., the same wafer returning to the same two consecutive PMs.

4) There are residency time constraints for wafers in PMs. The time interval of residency in PMs is (a,b), and (0,∞) in the LLs. If the actual residency time of a wafer exceeds the upper limit of the time interval, the wafers should be considered as being of bad quality.

5) Residency time and processing time for each wafer within each PM can be different.

6) A wafer lot is scheduled at the moment of arriving at the LL.

7) There is no buffer among PMs. A cluster tool of three PMs is considered in this paper.

(1)

(2)

(3)

According to assumption 2), a PM only processes one wafer at a time such that the PM must be free before a new wafer is inserted. Namely,

(4)

As mentioned above, this paper addresses the scheduling with continuous reentrancy. Two adjacent PMs which process a wafer more than one time should satisfy the following requirements:

(5)

(6)

(7)

(8)

To make full use of the equipment, the processing operation begins once a wafer is loaded in the PM. The details are described as

(9)

(10)

(11)

According to assumption 3), two PMs processing each wafer with continuous reentrancy must satisfy the following equation:

(12)

Fig.2 Wafer reentrant flow pattern

LetLibe thei-th TM operation path, andZibe the state of each PM under periodic scheduling when pathLiis adopted,Zi={L1,L2,…,Ln}. Thei-th PM has two statesΟandΘ.ΟandΘdenote that the PM is empty and occupied, respectively. A set of five TM operational paths under the steady period isZi={L1,Θ,…,L5}. They areL1=(R1→R2→R3→R4→R5→R6),L2=(R1→R6→R2→R4→R3→R5),L3=(R6→R1→R2→R4→R3→R5),L4=(R1→R6→R2→R3→R4→R5),L5=(R1→R2→R3→R4→R6→R5).

(13)

Consequently, the scheduling problem contains the objective function (13) and the constraints (1) to (12).

2 Scheduling Algorithm

The core of the proposed scheduling algorithm is to adopt the pull strategy[1]. Due to many kinds of deadlocks caused by reentrant processes, all the possible TM paths satisfying reentrancy constraints must be listed so that feasible paths can be found out. The task of processing a wafer lot both in the initial state and the intermediate state must satisfy residency time and reentrancy constraints. The makespan of the feasible scheduling solution is calculated. Finally, the minimal makespan solution is determined.

The proposed path search scheduling method includes the following two parts: The first part is to find out each scheduling pathLiwhich can satisfy all residency time and reentrancy constraints during each wafer’s operations in turn; the second part is to calculate the corresponding makespan and obtain an optimal scheduling path. The algorithm procedure is described in details as follows:

Step1Determine whetherL2is a feasible sequence path or not. If the path meets the constraints, calculate the system makespan, otherwise determine the next path.

1) Leti=1;j=0.

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

Step2Determine whetherL3is a feasible sequence path or not. If the path meets the constraints, calculate the system makespan, otherwise determine the next path.

1) Leti=i+1 andk=0.

(29)

(30)

(31)

(32)

Step3Determine whetherL4is a feasible sequence path. If the path meets the constraints, calculate the system makespan, otherwise determine the next path.

1) Leti=i+1 andk=0.

(33)

(34)

(35)

(36)

(37)

Step4Determine whetherL5is a feasible sequence path or not. If the path meets the constraints, calculate the system makespan, otherwise determine the next path.

1) Leti=i+1 andk=0.

(38)

(39)

(40)

(41)

(42)

(43)

(44)

(45)

Step5Calculate the makespan by scheduling pathL1, and find out the best scheduling path in all the possible sequence paths:

(46)

Step6The algorithm ends.

3 Example Analysis

Fig.3 Gantt chart for L5

Fig.3 shows that the reentrancy of the third process module makes other two process modules’ utilization reduced, but the phenomena will not cause deadlocks. Meanwhile, pathL5can make residency time that is spent in the third process module very short, only 1 s, and also make other process modules have no residency. The example indicates that we can find out an optimal robot scheduling path with the proposed algorithm.

4 Simulation and Analyses

To effectively evaluate the system performance of the proposed approach, some variables are defined as follows:

We program the heuristic scheduling algorithm in Visual C++ language and run it on a computer. Based on the experimental results, the following analyses are given.

4.1 Analysis of general running time of the algorithm

Fig.4 Running time of the algorithm vs. number of wafers

Fig.4 indicates that the running time of the algorithm increases along with the increase in the number of wafers. But it is obvious that the running time of our algorithm is very short. The running time is 45 ms when the number of wafers is 100. The proposed algorithm is suitable for carrying out a real-time scheduling of the wafers.

4.2 Algorithm performance under impact of BR

Fig.5 BR vs. Rs

Fig.5 indicates that the makespan calculated by the proposed algorithm becomes smaller, andRskeeps improving. When the standard deviation of the residency time increases, the general variation tendency ofRsis very small. The standard deviation of the residency time has little influence on the performance of the proposed algorithm. The curve ofRsbecomes smooth afterBRis greater than 2, namely, the performance becomes relatively steady. In practice, the transport time is always very small relative to the maximum processing time, and the proposed algorithm is feasible and valid to schedule cluster tools with residency time and continuous reentrancy constraints.

4.3 Impact of T on algorithm performance

Fig.6 Rx vs. number of wafers and processing time AVG

Fig.6 shows that under the constraints of residence,Rxchanges within a small range from 25% to 40% when the average processing timeE(T) changes. AndRxbecomes small and regressive along with the increasing number of wafers. It is an expected and perfect result. When the wafer numberiis more than 20, theRxvalue tends to stabilize.

4.4 Impact of size of wafer batch on algorithm performance

As shown in Fig.7,Rsincreases with the enlarging number of wafers. Although floating exists,Rsstill ranges from 20% to 30%.Rxdeclines but tends to be stable around 35%. And the FP is closer to the ideal FP. In practice, the number of wafers equals the result obtained by using the proposed algorithm, so our algorithm performs well in application.

Fig.7 Rx/Rs vs. number of wafers

5 Conclusion

1) The proposed algorithm can effectively solve the scheduling problem of multiple wafer types and single-arm clusters with the conflicts and deadlocks generated by residency time and continuous reentrancy constraints.

2) The feasibility and availability of the developed heuristic scheduling algorithm are verified in Visual C++language. Due to the short running time of the algorithm, the proposed algorithm can solve a real-time scheduling problem of the wafers.

3) Compared with the swap policy algorithm, the experimental results indicate that the proposed algorithm has good performance.

[1]Venkatesh S, Davenport R, Foxhoven P, et al. A steady-state throughput analysis of cluster tools: dual-blade versus single-blade robots[J].IEEETransactionsonSemiconductorManufacturing, 1997,10(4): 418-424.

[2]Lee T E, Park S H. An extended event graph with negative places and tokens for timed window constraints[J].IEEETransactionsonAutomationScienceandEngineering, 2005,2(4): 319-332.

[3]Kim J H, Lee T E, Park D B, et al. Scheduling analysis of time-constrained dual-armed cluster tools [J].IEEETransactionsonSemiconductorManufacturing, 2003,16(3): 521-534.

[4]Rostami S, Hamidzadeh B. An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints[J].IEEETransactionsonRoboticsandAutomation, 2001,17(5): 609-618.

[5]Rostami S, Hamidzadeh B. An optimal residency-aware scheduling technique for cluster tools with buffer module[J].IEEETransactionsonSemiconductorManufacturing, 2004,17(1): 68-73.

[6]Yoon H J, Lee D Y. On-line scheduling of integrated single wafer processing tools with temporal constraints[J].IEEETransactionsonSemiconductorManufacturing, 2006,18(3): 390-398.

[7]Perkinson T L, Gyurcsik R S, McLarty P K. Single-wafer cluster tool performance: an analysis of the effects of redundant chambers and revisitation sequences on throughput[J].IEEETransactionsonSemiconductorManufacturing, 1996,9(3): 384-400.

[8]Lee H Y, Lee T E. Scheduling single-arm cluster tools with reentrant wafer flows[J].IEEETransactionsonSemiconductorManufacturing, 2006,19(2): 226-240.

[9]Zuberek W M. Cluster tools with chamber revisiting-modeling and analysis using timed Petri nets[J].IEEETransactionsonSemiconductorManufacturing, 2004,17(3): 333-344.

[10]Zuberek W M. Petri net modeling and performance analysis of cluster tools with chamber revisiting[C]//The8thInternationalConferenceonEmergingTechnologiesandFactoryAutomation. Antibes-Juan les Pins, France, 2001,2: 105-112.

[11]Jung C Y, Lee T E. An efficient mixed integer programming model based on timed Petri nets for diverse complex cluster tool scheduling problems[J].IEEETransactionsonSemiconductorManufacturing, 2012,25(2): 186-199.

[12]Wu N Q, Chu F, Chu C B, et al. Petri net-based scheduling of single-arm cluster tools with reentrant atomic layer deposition processes[J].IEEETransactionsonAutomationScienceandEngineering, 2011,8(1): 42-55.

[13]Wu N Q, Chu F, Chu C B, et al. Petri net-based cycle time analysis of dual-arm cluster tools with wafer revisiting and swapping strategy[C]//2011IEEEInternationalConferenceonRoboticsandAutomation. Shanghai, China, 2011: 5499-5504.

[14]Kim D K, Jung C Y, Lee T E, et al. Cyclic scheduling of cluster tools with non-identical chamber access times[C]//Proceedingsofthe2011WinterSimulationConference. Phoenix, AZ, USA, 2011: 2068-2079.

[15]Wu N Q, Zhou M C. Schedulability analysis and optimal scheduling of dual-armed cluster tools with residency time constraint and activity time variation[J].IEEETransactionsonAutomationScienceandEngineering, 2012,9(1): 203-209.