## 1 Introduction  
In semiconductor manufacturing, cluster tools are important for wafer fabrication. A modern semiconductor fabrication plant (fab) is equipped with hundreds of cluster tools. A cluster tool is very expensive, and the cost for equipment accounts for more than a half of the total investment for a fab. Therefore, maximizing the productivity of cluster tools is an important means for manufacturers to ensure the return on their investment. A cluster tool consists of a wafer handling robot, an aligner (AL), several process modules (PMs), and two loadblocks (LLs) for raw wafer lot loading/unloading. Figure 0(a),b shows two kinds of cluster tools equipped with a one-arm or two-arm robot, called a single-arm cluster tool (SACT) and dual-arm cluster tool (DACT), respectively. The single-wafer processing technology is adopted for processing large-size wafers in cluster tools. By such a technology, a PM in a tool can process only one wafer at a time. In this way, precision processing requirements can be satisfied such that the quality of processed wafers can be guaranteed. For a cluster tool, the robot moving time between two PMs or a PM and an LL is much shorter than the wafer processing time at a PM in practice. Thus, the time taken for completing a wafer at the bottleneck step determines the system cycle time. With such a property, a tool is said to be process-bound. A backward strategy is optimal for process-bound SACTs [1], while a swap strategy is efficient for process-bound DACTs [2]. With the increasing of wafer diameter and the shrinkage of circuit width, in order to guarantee wafer quality, strict wafer residency time constraints (WRTCs) are imposed on many wafer fabrication processes. They require that a wafer should be removed out of a PM within a given time window after it is processed, otherwise the wafer may be damaged by the residual chemicals, particles, and high temperature in the PM. Low pressure chemical-vapor deposition is such a typical process. Without intermediate buffers between PMs, WRTCs definitely make the scheduling problem of cluster tools complicated. Important efforts have been made in scheduling cluster tools with WRTCs by reducing the wafer delay time in PMs, i.e., the time a wafer is detained in a PM after it is processed. [PERSON] et al. [3] and [PERSON] and [PERSON] [4] present methods for DACTs with WRTCs to find an optimal and feasible periodic schedule. To reduce the wafer delay time for DACTs, a modified swap strategy is proposed in [5] such that a wafer waits on the robot for some time during a swap operation. For SACTs, the wafer delay time at a step can be reduced by delaying the time point of unloading a wafer at the previous step, so that the time point of loading the wafer at the step is delayed [1; 6]. Feedback control methods are proposed in [7; 8] to control wafer delays such that a feasible schedule can be found for both SACTs and DACTs. If a conventional swap strategy cannot achieve a feasible schedule for DACTs with WRTCs, a new class of robot task sequences is proposed in [9] such that WRTCs can be met. [PERSON] et al. [10] developed closed-form formulas for most frequently used wafer flow patterns and an optimization model that computes the worst-case wafer delay of dual-armed cluster tools. They also analyze the factors that affect the worst-case wafer delay and their influences by experiments. By considering processing time variation, an adaptive scheduling method is presented for cluster tools with wafer delay constraints in [11]. With WRTCs and multiple wafer types being processed, efficient scheduling approaches are proposed for SACTs in [12] and DACTs in [13; 14]. For process-bound cluster tools, robot tasks take much less time than processing a wafer in a PM such that the system cycle time is determined by the time taken for completing a wafer at the bottleneck step. Hence, in a cycle, the robot has idle time that can be treated as robot waiting time.