Jipeng Wang,, Hesuan Hu,,Chunrong Pan,, Yuan Zhou, and Liang Li

Abstract—Accompanying the unceasing progress of integrated circuit manufacturing technology, the mainstream production mode of current semiconductor wafer fabrication is featured with multi-variety, small batch, and individual customization, which poses a huge challenge to the scheduling of cluster tools with single-wafer-type fabrication. Concurrent processing multiple wafer types in cluster tools, as a novel production pattern, has drawn increasing attention from industry to academia, whereas the corresponding research remains insufficient. This paper investigates the scheduling problems of dual-arm cluster tools with multiple wafer types and residency time constraints. To pursue an easy-to-implement cyclic operation under diverse flow patterns,we develop a novel robot activity strategy called multiplex swap sequence. In the light of the virtual module technology, the workloads that stem from bottleneck process steps and asymmetrical process configuration are balanced satisfactorily. Moreover, several sufficient and necessary conditions with closed-form expressions are obtained for checking the system’s schedulability. Finally, efficient algorithms with polynomial complexity are developed to find the periodic scheduling, and its practicability and availability are demonstrated by the offered illustrative examples.

Nomenclature

N+{1, 2, ···}.

Nn{1, 2, ···,n}.

I. Introduction

IN semiconductor manufacturing industry, cluster tools are the most fundamental equipment. For the sake of a higher tool utilization rate and a higher production yield rate, the majority of wafer manufacturers apply cluster tools in various wafer fabrication processes. Particularly in the cutting-edge fabs, about 70%~80% of the wafer fabrication procedures,such as wafer cleaning, etching, and deposition, are performed in cluster tools [1]. Owing to the interior space restriction, a typical radical-type cluster tool is generally composed of several single-wafer processing modules (PMs, also called processing chambers), a wafer transfer module (TM, also called wafer-handling robot), and two loadlocks (LLs). All these modules are mechanically connected together and manipulated by the industrial computer. PMs process wafers, TM executes wafer loading, unloading, and transportation among different modules, and LLs load/unload wafer cassettes. Depending on the robot structure, cluster tools are classified into the single- and dual-arm cluster tool (see Fig. 1). Furthermore,a couple of individual cluster tools can be interconnected through buffer modules in linear or treelike topology architecture to form a multi-cluster tool [2]–[4].

Fig. 1. Cluster tools with four PMs. (a) A single-arm cluster tool; (b) A dual-arm cluster tool.

Cluster tools are a sort of integrated equipment that provides a fully automated job shop manufacturing environment with vacuum conditions. More importantly, it is a big-ticket item ranging in price from hundreds of thousands to millions of dollars per tool [5], which consumes huge investments and production costs. Thus, it is of great necessity to operate cluster tools efficiently for reducing production costs. Great works regarding the modeling, analysis, and performance evaluation of cluster tools have been conducted [2], [3],[6]–[9]. Meanwhile, it is usually taken for granted that the nature of the operation of cluster tools is to schedule the robot activities due to its domination in PM activities [8]. An indisputable fact that the time taken for wafer processing in PMs is much longer than that for robot activities has been acknowledged by the most of the past research with regard to cluster tools. Thus under most circumstances, cluster tools operate in the process-bound region, where the robot has idle time and the wafer processing in PMs determines the system cycle time. In addition, the backward and swap sequences show their efficiencies in operating single- and dual-arm cluster tools respectively [6]. Nevertheless, the complex restrictiveness, stemming from the equipment architecture,wafer recipes, and temporal logic, poses significant challenges to the scheduling of cluster tools. Over the past decades,researchers conducted extensive prominent studies with respect to scheduling cluster tools under diverse instances,including wafer residency time constraints (WRTCs)[10]–[15], activity time variation [16]–[20], wafer revisiting processes [21]–[27], PM failures [28], [29], chamber cleaning operation [1], [30]–[32], and multi-cluster tools [33]–[42],which are thoroughly reviewed in [43]. Moreover, the latest advancements can be found in [44], [45]. Note that all the aforementioned works are dedicated to the scheduling and control problems of single-wafer-type fabrication.

With the rapid improvements of integrated circuit (IC)manufacturing technology, the wafer size has increased up to 300 mm even 450 mm; besides, main leading-edge IC fabricators have stepped into 14 nm technology node, thus facilitating the reduction of wafer lot size. To respond to the customer order as quickly as possible, wafer manufacturers have to frequently switch wafer lots with a higher rapidity. If switching wafer lots with the off-line way, there is little prospect of minimizing the system’s makespan due to the repeated equipment shutdown for computing schedules and adjusting PMs [46]. If, instead, switching wafer lots with the on-line way, it does not need to close and adjust cluster tools frequently [47]. However, it remains an inefficient methodology due to the multiple occurrences of transient processes. For the transient process scheduling, its intractability in the solvability and enforceability is aggravated by the frequent state evolution, even though there has been some corresponding studies [48]–[53]. Meanwhile,the idleness of some PMs can hardly be avoided within each switching process, and this reduces the tool’s efficiency. In addition, despite the fact that existing research has made efforts so as to switch two different wafer lots in real-time,none of them provides a feasible integrated resolution for the scenarios with more than two lots. In brief, the intractable issues outlined in above can scarcely be solved via the resolutions for cluster tools with single-wafer-type fabrication.As a consequence, to tackle with these issues, novel approaches need to be explored.

Recently, the leading fabs attempt to process several wafer types in a cluster tool concurrently. Such a novel wafer fabrication mode shows promising prospects on handling the new scheduling challenges caused by the shrinking wafer lot size. By considering that two different wafer types are processed in the cluster tool concurrently, the corresponding scheduling problems have been discussed in [54], [55]. Leeet al.[54] assume that there is no PM shared by the two wafer types, and then present efficient heuristic scheduling rules to determine the optimal robot activity sequence. A mixed integer programming model is established for minimizing the cycle time, when the developed conditions do not hold. Later,Leeet al.[55] extend their previous results in [54] to the tool environment where a single PM is shared by two different wafer types. By combining both the alternating and the conventional robot activity sequence, a heuristic algorithm is proposed for operating the robot in the general cycle. Koet al.[56] investigate the scheduling problem for the dual-arm cluster tool that concurrently processes multiple wafer types with identical flow patterns but different process times at each process step. This is a more common practice of concurrent processing in actual fabs. Looking back to the existing works[54]–[56], the commonality is that none of them takes WRTCs into consideration when addressing the concurrent processing problems. In our earlier work [46], we investigate the concurrent processing of multiple wafer types in a single-arm cluster tools. We place little restriction on the number of the entire wafer types and the flow pattern of each wafer type, i.e.,the concurrent processing of multiple wafer types conducted in [46] includes, but is not limited to, the instances that have been discussed in [54], [55]. Meanwhile, we take WRTCs as the core condition in [46]. As known, compared with singlearm cluster tools, dual-arm ones have higher productivity[5]–[8], [43]. Notwithstanding this, corresponding issues have not been extended to dual-arm cluster tools platform.However, the approach for single-arm cluster tools presented in [46] cannot be applied in dual-arm ones due to diverse differences including in the structure and resource behaviors.Thus, it remains an open problem and deserves exploring novel methodologies.

In this paper, we focus on the scheduling problems of dualarm cluster tools with multiple wafer types. To improve the effectiveness and adaptability in engineering practice, we integratedly take several constraints into consideration including WRTCs, diverse flow patterns, and quantitative proportion. Considering them together in this paper, we make threefold contributions: 1) present a novel robot operation strategy that reveals effectiveness for the simplicity of its enforcement and the flexibility of tackling with intricate combination of flow patterns; 2) derive several necessary and sufficient conditions with closed-form expressions for verifying the system’s schedulability; and 3) develop efficient algorithms with polynomial complexity for computing the optimal cyclic schedule when the system is schedulable.

The rest of this paper is organized as follows. Section II introduces necessary backgrounds on the concurrent processing of multiple wafer types in dual-arm cluster tools.Section III proposes a novel robot activity sequence to enforce cyclic operation, and then analyzes temporal properties and systematic workloads. Section IV discusses the schedulability criteria and presents efficient algorithms for finding the cyclic scheduling. Section V offers several examples to demonstrate the proposed methodology’s efficiency and its enforcement method. Finally, Section VI summarizes this paper and suggests possible extensions.

II. Problem Preliminaries

For the dual-arm cluster tool scheduling, there are alternative operation strategies, including dynamic (or realtime) and static (or off-line) dispatching rules of the robot activities. The dynamic strategy usually results in aperiodic operations, unpredictable robot activities, complex computation, and intractability in scheduling implementation,even though the corresponding optimizing issues can be heuristically performed via computer simulation. With the static strategy, a schedule can be obtained in advance based on the operation objectives and requirements. In other words,such a strategy pursues cyclic operation, i.e., the robot repeats identical work cycle and so does each PM. Cyclic operation outperforms the aperiodic one thanks to various merits, such as reduced scheduling complexity, predictable behavior, less work-in-progress inventory, improved throughput, and steady(or periodical) timing patterns. Thus, this paper is devoted to the cyclic scheduling of dual-arm cluster tools with multiple wafer types and WRTCs.

A. Problem Definition

B. Activity Description

Time is taken for both PMs and robot activities. Letαλμdenote the process time of wafer type λ at process step μ. Due to the residency time constraints, the wafer of type λ must be unloaded within βλμtime units at most after its completion in the PM at process step μ. This implies that the wafer sojourn time τλμmust fall into the time interval [αλμ, αλμ+ βλμ], i.e.,τλμ∈ [αλμ, αλμ+ βλμ]. As the fact that the loadlock has no processing function, we thus have αλ0= 0 and τλ0∈ [0, +∞).As done in [11]–[14], [21], [56], we assume that: 1) the time taken for loading a wafer is the same as that for unloading,denoted as ρ, and 2) the time taken for the robot to move among any two different modules is identical, denoted as θ.Such assumption is universally accepted since the variability of these activities is marginal, and their operation times are much shorter than the wafer processing time in practice. In addition, when the robot rotates to the process step μ of wafer type λ for performing the swap operation, the wafer may remain being processed in the PM. To make the schedule feasible, the robot may need to wait some time units before or during the swap operations, which are denoted asandrespectively. Assume that it takes π time units for performing a simple swap operation at a process step. Then,the time taken for performing Υλμis

III. Scheduling Analysis

In this section, we introduce a novel robot activity strategy for achieving the cyclic fabrication of multiple wafer types in cluster tools without difficulty. On the basis of the analysis of the process step in temporal and workload properties, we present approaches to compute corresponding cycle times and to balance systematic workloads.

A. Multiplex Swap Sequence

It follows from the discussion with respect to the concurrent processing of multiple wafer types in the single-arm cluster tool that the production processes of each wafer type are mutually independent [46], likewise in the dual-arm cluster tool. This provides a holistic perspective combining the local and global cycle to examine the fabrication processes of different wafer types. As described in the multi-type WFP, the raw wafers include two parts. One is thek?γ non-shared types, while another is the γ shared ones. Assume that the shared types enter the tool before the non-shared ones. Then,the wafer type release sequence is [the shared types] → [wafer typek?γ] → [wafer typek?γ ?1] → ··· → [wafer type 1].However, according to the structural characteristics revealed by the multi-type WFP, we can safely draw a conclusion that the shared types have shown a parallelized structure mutually from the global perspective. Therefore, based on the first-in first-out principle, the wafer type release sequence in the global cycle composed of γ subcycles is : {[the shared types]k→ [wafer typek?γ] → [wafer typek?γ ?1] → ··· → [wafer type1]}1→ {[the shared types]k?1→ [wafer typek?γ] →[wafer typek?γ ?1] → ··· → [wafer type 1]}2→ ··· → {[the shared types]k?γ+1→ [wafer typek?γ] → [wafer typek?γ ?1] → ··· → [wafer type 1]}γ, where the subscript σ, σ∈Nγ, in “[the shared types]σ” indicates that the wafer being processed in the final shared process step is the σth type.Thus, the system will evolve to its initial state afterγ subcycles.

In an arbitrary global cycle, the non-shared types are processed γ times with an identical sequence, while the shared ones require to be dynamically executed in each subcycle with different sequences. Let PSλμ, λ ∈ Nk, μ ∈ Nnλ, denote the μth process step of wafer type λ. Specially, the LLs can be treated as a process step, denoted as PSλ0. Letrepresent the process step sequence for wafer type λ from theit h tojth process steps, i.e.,. For the non-shared types, according to the swap-with-wait operation, the robot will execute process steps sequentially in each subcycle as follows:. As for the shared types, their fabrication mechanisms are more complicated. Due to the parallelized structure and identical manufacturing parameters at the shared process steps, each shared PM conducts a different wafer type and configures a permutation in the light of the first-in first-out rule. Thus, in the σth subcycle, wafers being processed from the first to the final shared process steps are W?(σ,1), W?(σ,2), ···, W?(σ,δ), ···,W?(σ,ε), respectively, where Wλindicates the wafer of the λth type. Note that ?(σ,δ)is equal tok??ε+σ?δ|γ?+1, whereis equal to γ when ε+σ?δ is divisible by γ;otherwise,is the remainder of ε+σ?δ by dividing γ. In two unbiased adjacent shared process steps, the process step chain composed of the identical wafer type satisfying the latter instance will be chosen to execute. In the σth subcycle, thus, the robot will execute the process steps of the shared types sequentially as follows:

By this point, the robot operation strategy with respect to the non-shared and shared types is demonstrated clearly within the above discussions. Then, based on the standpoint that the wafer fabrications of the non-shared and shared types(as a unit) are mutually independent, the process steps of these two parts can be concatenated and executed with the swap-

with-wait operation to construct the multiplex swap sequence

B. Temporal Analysis

According to the results in [11], [14], we can easily draw the conclusion that the time needed for completing a wafer of type λ at process step μ isIn consideration of the concurrent mechanism featured by two aspects, i.e., the parallel PMs and the parallelized structure that are formulated by the shared and non-shared PMs of the shared wafer types,we characterize such specification by introducing two coefficients:mλμand ζλμ, wheremλμis the number of parallel PMs of PSλμ; and ζλμ= 1 if λ ∈ Nk?γorotherwise,ζλμ= γ. Thus, the production cycle time of PSλμ, λ ∈ Nk, μ ∈ Nnλ,is

In accordance with the MSS, the process step sequence that will be performed is easily identified. Given the preliminary assumption along this paper, the elementary operation during each process step is performed with swap-with-wait policy.Then in the σth subcycle, the executed process step sequence

With the MSS, based on the previous analysis, when the system arrives at the steady state, the wafer fabrication process in dual-arm cluster tools presents a cyclic serial one.Hence, the cycle time for completing a wafer at each step and the robot cycle time are identical. This is unified as the system production cycle time, denoted as ψ . Thus, ? λ ∈ Nk, σ ∈ Nγ,

we have

Equations (3) and (4) present the basics for scheduling cluster tools with multiple types of wafers within the steady state, as well as the properties with respect to the temporal relationship and productivity between each pair of modules under cyclic operations. For the wafer fabrication within each process step in the steady state, as revealed by (3) and (4), one should and must keep the same production rhythm, which can be guaranteed via alternative approaches including adjusting the wafer fabrication starting time and the robot waiting time.As for the robot, due to the anisotropic distribution of the process step chain among two adjacent shared process steps,its activity cycle usually emerges as a dynamic one resulting in unstable work cycle and error propagation of the wafer fabrication in PMs. To obtain a stable robot activity cycle, in the bottom line, for ? δ ∈ ?ε?1= Nε?1∪ {0},=NkNk?γ, and, we must ensure

Consequently, for the tools’ operation in the steady state, (2)should be updated to

where

C. Workload Analysis and Balance

Due to the incongruous parametric distribution and the fierce resource contention that occur in the shared PMs, the system workload imbalance probably deteriorates to a severe level such that additional measures are needed, apart from the robot waiting time adjustment that is widely applied in [13],[14], [17]–[18], [22]–[25]. To tackle with these issues and realize stable cyclic operations, we adopt the virtual module technology that is introduced in our earlier work [46]. In the internal layer, we importθ ) (resp.,virtual modules as well as the regulating waitingbefore(resp., after) the first (resp., final) shared process step. Since there is no buffer between neighboring PMs, we have to allocate virtual robot operation to the process step. In the external layer, we set ηλ?1 virtual PM groups for each wafer type. In particular, the shared types are regarded as an individual group, i.e., ηk?γ+1= ηk?γ+2= ··· = ηk= ηs. Then, (1)for computing the production cycle time of PSλμshould be updated as

where

Equation (12) characterizes not only the production cycle time but also the workload range of each process step under a specific schedule. Because the specification defined by (12)includes the robot waiting time, we call such a workload as the scheduled workload that has a close relation with the robot cycle time. Their algebraic relationships can be maximally characterized by the coefficient ηλ. Consequently, the optimum quantitative proportion of the wafer types can be determined as follows:

After configuring the virtual modules, the robot activity cycle can be converted into a reductive specification as follows:

where

It should be noticed that ψRcis a predeterminable constant related to the inherent characteristics of the system including the WFP, processing times, and robot activity times, whereas ψσRwshall be determined by the specific schedule pursued in this paper. By using virtual module technology, we can alleviate the process step bottleneck in both internal and external layers. Moreover, when the system runs in the steady state, it can be inferred from (3), (4) and (12) that the wafer sojourn time at PSλμis

IV. Schedulability and Scheduling

schedule that satisfies (3), (4) and WRTCs, i.e., ψλμ∈ [ψλμL,ψλμU], simultaneously. To be specific, the problem converts

By this point, we have discussed the robot operation strategy and the corresponding temporal properties. The sequential work is to verify the feasibility of the target into how to clarify the variational mechanism ofthe production cycle time based on the limited manufacturing information that can be known in advance. Although such a solution cannot be derived directly, we can handle it by analyzing the distribution characteristic of the natural workload of PSλμ. Removing the robot waiting timefrom(12), we can obtain PSλμ’ s natural workload φλμand its lower and upper bounds as follows

Let φLmax= max{ φλμL, λ ∈ Nk, μ ∈ Nnλ} and φUmin=min{ φλμU, λ ∈ Nk, μ ∈ Nnλ}. Next, we investigate the systematic schedulability under the diverse distribution characteristic in manufacturing parameters.

Fig. 2. Illustration for Theorem 1.

Theorem 1:For the time-constrained dual-arm cluster tool withifthen, the system is schedulable; otherwise, it is not schedulable.

Proof:Case 1:Letand assign zero to the rest of robot waiting times. Then, we haveand the robot cycle timeThus, the time taken for completing a wafer in each process step is φLmaxin the steady state based on (3) and (4). Therefore, ψ =Then, from (21),we haveandαλμ+ βλμ] /(mλμζλμηλ) – [ξλμ(π + θ ) + π ] = αλμ+ βλμ, i.e.,τλμ∈[αλμ, αλμ+ βλμ]. In other words, there is enough time for completing a wafer in each process step; besides, the WRTC of each process step is satisfied. Thus, the system is schedulable for Case 1.

Case 2:For this case, let all the robot waiting times be zero,such that ψσRw= 0 and the robot cycle time ψσR= ψRc+ψσRw= ψRc. According to (3) and (4), in the steady state, the time taken for completing a wafer in each process step is forced to be ψRc, i.e., ψ = ψλμ= ψσR= ψRc, λ ∈ Nk, μ ∈ Nnλ, σ ∈ Nγ.Then, from (21), we have τλμ=mλμζλμηλψ – [ ξλμ(π + θ ) + π +=mλμζλμηλψRc– [ ξλμ(π + θ ) + π ] >mλμζλμηλψLmax–[ ξλμ( π + θ ) + π ] ≥mλμζλμηλ[ ξλμ( π + θ ) + π + αλμ] /(mλμζλμηλ)– [ ξλμ(π + θ ) + π ] = αλμ, and τλμ=mλμζλμηλψ – [ ξλμ( π + θ) +π +] =mλμζλμηλψRc– [ ξλμ( π + θ ) + π ] ≤mλμζλμηλφUmin–[ ξλμ( π + θ ) + π ] ≤mλμζλμηλ[ ξλμ( π + θ ) + π + αλμ+βλμ] /(mλμζλμηλ) – [ ξλμ(π + θ ) + π ] = αλμ+ βλμ, i.e., τλμ∈ [ αλμ,αλμ+ βλμ]. This means that the WRTC of each process step is satisfied. Thus, the system is schedulable for Case 2.

Case 3:It is clear that the production cycle time ψ > ψRcif the system is schedulable. According to (12), (18), and (21),we can easily deduce that ψσRw≥ ( ψ – φUmin)mλμζλμηλ. Then,ψσR= ψRc+ ψσRw≥ ψRc+ ( ψ – φUmin)mλμζλμηλ> ψRc+ ( ψ –ψRc)mλμζλμηλ= ψ+ (mλμζλμηλ– 1)( ψ – ψRc) > ψ. Thus, there always exists ψσR> ψ violating (4) no matter what schedules we adopt. This implies that the system is not schedulable for Case 3.

Algorithm 1 Scheduling time-constrained dual-arm cluster tools with multiple wafer types for

Algorithm 1 Scheduling time-constrained dual-arm cluster tools with multiple wafer types for

B. Situation With

Theorem 2:For the time-constrained dual-arm cluster tool withif ψRc≤ Ψ, then, the system is schedulable; otherwise, it is not schedulable.

Fig. 3. Illustration for Theorem 2.

Case 2:It is clear that the production cycle timeψ≥φLmaxif the feasible schedule can be found. From Ψ < ψRc≤φLmax,

Algorithm 2 Scheduling time-constrained dual-arm cluster tools with multiple wafer types for

Algorithm 2 Scheduling time-constrained dual-arm cluster tools with multiple wafer types for

C. Discussion

In Section III, we propose a novel robot operation strategy and the corresponding workload balancing methods. They provide a comprehensive approach to cope with the concurrent processing of multiple wafer types in dual-arm cluster tools. Combining with the schedulability criteria provided in this section, we can summarize the procedure to find the feasible cyclic schedule for dual-arm cluster tools with multiple wafer types and residency time constraints. As for the performance of the proposed algorithm, we have the following theorem.

Theorem 3:If the mixing ratio of the production order coincides withRopt, the schedule obtained by Algorithms 1 and 2 is optimal in terms of the cycle time.

Proof:Assume that the lower natural workload of PSλμ,λ∈Nk, μ ∈ Nnλ, φλμLis equal to φLmax. For the situations covered by Case 1 of Theorems 1 and 2, if the system is scheduled such that ψ < φLmax, then, according to (21), for the PSλμ, we haveThus, such schedule is infeasible. For the situation defined by the Case 2 of Theorem 1, if the system is scheduled such thatthen,according to (3) and (4),we havethat contradicts with the definition of the robot activity cycle.Therefore, such schedule is infeasible. In conclusion, the system driven by the obtained schedule can reach the lower bound of the production cycle time, i.e., the minimal cycle time. By considering the presented schedulability conditions that are constructed in terms of the quantitative proportion(see (12), (17), and (21)), the entire wafer types will be completed simultaneously within the identical processing cycle. Thus, the system can keep working throughout the whole processes with the minimal cycle time under the supposed conditions.

As stated above, the tool system can operate in the lower bound continually on the basis of the assumption that the mixing ratio of a specific production order is equal toRopt.However, the mixing ratio is inconsistent withRoptin many scenarios. In such cases, although the obtained schedule may no longer be the optimal one, it is still efficient due to the simple computation and implementation. In addition, we can adopt the virtual wafer technology, as implemented in [13],[14], to coordinate the robot activities. More specifically, we need to configure the mixing ratio in accordance withRoptby adding virtual wafers minimally. After configuring, thus, we havedenotes the number of the added virtual wafers of type λ.Given the WFP of a production order, one needs to calculate the cycle time ofnλprocess steps for the λ-th type of wafers.Thus, the computational complexity of the presented algorithm is O(nλ×K). However, by considering thatnλ≤ 6 andKis limited in practice, the presented approach is efficient and applicable to industrial cases.

V. Examples

In this section, we give several examples to demonstrate the effectiveness of the proposed algorithm as well as its implementation approach.

A. Illustrative Examples

Example 1:The processing paths of the first, second, and third wafer types are [LL → PM1→ PM2→ LL], [LL → PM3→ PM4→ LL], and [LL → PM5→ PM6→ LL],respectively. The processing parameters are as follows: κ1=240 pcs, α11= 286 s, β11= 26 s, α12= 264 s, β12= 30 s; κ2=180 pcs, α21= 128 s, β21= 15 s, α22= 110 s, β22= 28 s; κ3=600 pcs, α31= 120 s, β31= 24 s, α32= 133 s, β32= 17 s; ρ = 8 s, θ = 3 s, π = 19 s.

For this example, the WFP is {(1, 1), (1, 1), (1, 1)}. Then,η1= 2, η2= 3, and η3= 1.Thus, we have φ11L= 194 s, φ11U= 207 s, φ12L= 204 s,φ12U= 213 s, φ21L= 196 s, φ21U= 206 s, φ22L= 202 s, φ22U= 211 s, φ31L= 204 s, φ31U= 218 s, φ32L= 185 s, and φ32U= 206 s.Then,and ψRc< φLmax= 204 s.Hence, the conditions given by Case 1 of Theorem 1 are satisfied. According to Algorithm 1, a feasible cyclic schedule can be obtained by setting= φLmax– ψRc= 6 s, and the rest of robot waiting times are equal to zeros. The optimal quantity ratio of wafer types isRopt= 3 : 2 : 6. Thus, the quantities of the virtual wafers added necessarily are as follows:pcs. Fig. 4 depicts the Gantt chart of the obtained schedule.

Example 2:The processing paths of the first and second wafer types are [LL → PM1→ PM2(PM3) → PM4→ PM6→ LL] and [LL → PM1→ PM5→ PM6→ LL], respectively.The processing parameters are as follows: κ1= 480 pcs, α11=145 s, β11= 16 s, α12= 145 s, β12= 16 s, α13= 145 s, β13= 16 s, α14= 145 s, β14= 16 s; κ2= 200 pcs, α21= 348 s, β21= 24 s, α22= 326 s, β22= 28 s, α23= 145 s, β23= 16 s; ρ = 10 s, θ =2 s, π = 22 s.

Example 3:The processing paths of the first, second, and third wafer types are [LL → PM1( PM2) → PM3→ LL], [LL→ PM4→ PM5→ LL], and [LL → PM4→ PM5→ PM6→LL], respectively. The processing parameters are as follows:κ1= 580 pcs, α11= 145 s, β11= 16 s, α12= 348 s, β12= 24 s;κ2= 600 pcs, α21= 326 s, β21= 28 s, α22= 326 s, β22= 28 s;κ3= 550 pcs, α31= 156 s, β31= 15 s, α32= 139 s, β32= 18 s,α33= 145 s, β33= 16 s; ρ = 6 s, θ = 2 s, π = 14 s.

Fig. 4. Gantt chart of the obtained schedule for Example 1.

Fig. 5. Gantt chart of the obtained schedule for Example 2.

For this example, the WFP is {(2, 1), ([1], [1]), ([1], [1],1)}. Then, ψRc= (3 + 4) × (14 + 2) = 112 s, η1= 2, and η2=η3= 1. Thus, we have φ11L= 123 s, φ11U= 129 s, φ12L= 128 s,φ12U= 142 s, φ21L= 114 s, φ21U= 135 s, φ22L= 132 s, φ22U=150 s, φ31L= 114 s, φ31U= 135 s, φ32L= 132 s, φ32U= 150 s,φ33L= 122 s, and φ33U= 130 s. Then,= ?, and φLmax= 132 s > ψRc. Meanwhile, φ11L< φLmaxand φ33L< φLmax. However, φLmax– (φLmax– φ11L)m11ζ11η1–( φLmax– φ33L)m33ζ33η3= 132 – (132 – 129) × 2 × 2 × 1 –(132 – 130) × 1 × 2 × 1 = 116 s > ψRc. Hence, the conditions given by Case 1 of Theorem 2 are satisfied. According to Algorithm 2, a feasible cyclic schedule can be obtained by setting ψ = ψλμ= ψσR= ψRc= 132 s, ω11= (φLmax–= 4 s,= 4 s, and the rest of robot waiting times are equal to zeros. The optimal quantity ratio of wafer types isRopt= 1 :1 : 1. Thus, the quantities of the virtual wafers added necessarily are as follows:pcs. Fig. 6 depicts the Gantt chart of the obtained schedule.

B. Schedule Implementation

Fig. 6. Gantt chart of the obtained schedule for Example 3.

TABLE I Comparison of Typical Works

As outlined in the previous sections, the cyclic schedule obtained in this paper is applicable to the steady state process only. Before entering the steady state process, as known, the system will go through the start-up transient process that starts from the time the cluster tool begins to accept raw wafers to the point at which the full work cycle (i.e., the steady state) is reached. More crucially, the obtained steady state schedule demands distinctive requirements for the tool status while the cluster tool is going to the steady state. That is, the detailed status before the steady state must be compatible with that required by the obtained schedule. Thus, the robot activities during the start-up transient process should be accurately dispatched such that the system can converge to the desired state smoothly. When there is no longer raw wafers that are loaded into the tool, the system begins to go to the close-down transient process. Although the obtained schedule demands no special requirements for the tool status during the switching process, which is different from what the start-up transient process requires, we continue to hope that the close-down transient process can be sped up as soon as possible. Despite some studies with respect to the transient process scheduling for the single-wafer-type fabrication [48]–[53], none of them can be applied to the multi-type one. Thus, corresponding issues remain challenging and open. However, the primary goal pursued in this paper is to find the feasible cyclic steady state schedule and then implement it successfully. Inspired by the methods presented in [13], [14], we adopt the virtual wafer technology to avoid the transient state for implementing the obtained schedule.

We take Example 1 as an instance to illustrate how to avoid the transient state by using the virtual wafer technology. We first assume that the system has been in steady state and each PM is occupied by a virtual wafer (denoted by WV) at the tool boot time. In both the start-up and close-down transient processes, the cluster tool is manipulated in accordance with the obtained steady state schedule. Specially, in the start-up transient process, the robot catches the real wafers and loads them into PMs, and the system will not reach the steady state until all the virtual wafers in PMs are replaced by the real ones. Such operation process is illustrated in Fig. 4, and it shows that the system begins to get into the steady state during the fourth work cycle. In the close-down transient process, the virtual wafers will be loaded into the tool as the supplement of the real ones. This manipulation will be continued until the entire real wafers complete their processing at the entire process steps. As shown in Fig. 4, the final wafer of the first (resp., second and third) type will complete its processing at the first/final process step during the 480th/482nd (resp., 540th/543rd and 600th/601st) work cycle. Note that the robot operations involving the virtual wafers aim at guaranteeing that the system keeps running according to the steady state schedule throughout the whole processes including the start-up transient, steady state, and close-down transient process. It is clear that this is easy to realize.

C. Comparison With Existing Works

Table I summarizes typical works with respect to the scheduling of multiple wafer types. In our earlier work [46],we investigate the scheduling problems of single-arm cluster tools with multiple wafer types and WRTCs. In this paper, we conduct these issues in dual-arm cluster tools. Compared with single-arm cluster tools, dual-arm ones present distinct characteristics in multiple aspects such as the robot operation strategy, temporal properties, and systematic schedulability,due to the widely different structures. Thus, compared with the work [46] for single-arm cluster tools, this paper for dualarm ones is not a typical epsilon difference work, even though both of them assume identical constraints. Compared with previous works [54]–[56], this paper achieves some progresses on the scheduling and control of dual-arm cluster tools with multiple wafer types being concurrently processed.First, WRTCs are not considered in [54]–[56], while they are taken into account in this paper. Second, the work in [54] and[55] merely address the concurrent processing of two wafer types, whereas [56] and ours can handle more than two types.Third, parallel PMs (i.e., series-parallel wafer flow patterns)are not considered in [54] and [55], but they are conducted in[56] and ours. However, the approach in [56] assumes that each wafer type has identical wafer flow patterns, whereas ours does not make such an assumption, as shown in Examples 2 and 3. Finally, for revealing the PM sharing behaviors, we investigate both non-shared and shared types via an integrated framework, as shown in Example 3, rather than conduct only one scenario, i.e., either non-shared types[54], [56] or shared types [55].

VI. Conclusion

This work focuses on the scheduling problems of dual-arm cluster tools with multiple wafer types and residency time constraints. A novel robot operation strategy, namely the multiplex swap sequence, is proposed to realize the stable mixed-model wafer fabrication. Based on this novel strategy,an easy-to-implement robot manipulation sequence for manifold flow patterns can be produced effortlessly. To balance the uneven workloads among process steps, a virtual module technology is developed. In addition to the presented necessary and sufficient conditions for schedulability testing,efficient algorithms with polynomial complexity are developed to find the cyclic schedule. The methodology presented in this paper can handle diverse complex multi-type wafer flow patterns. Meanwhile, its correctness, effectiveness,and adaptability are validated by illustrative examples.

More significantly, several orientations deserve further explorations. First, there is still room for improvement. For instance, how to find the optimal schedule when the actual quantitative proportion is not equal toRopt? Especially, how to tackle with the scheduling problems when the shared types have different processing parameters at the shared steps?Second, it remains open and challenging for the scheduling and control problems with respect to the concurrent processing of multiple wafer types considering diverse operational requirements, e.g., revisiting processes, activity time variation, and cleaning operation. Third, it is of significance to investigate the concurrent processing of multiple wafer types within different tool architectures such as in-line cluster tools [4] and multi-cluster tools [2], [3]. In brief, these aforementioned topics deserve more attentiveness and we will investigate these issues in the future work.