Scheduling Dual-Arm Multi-Cluster Tools With Regulation of Post-Processing Time
双臂多簇工具调度与后处理时间调控

I Introduction  一 引言

SCHEDULING of multi-cluster tools has attracted much attention in recent years thanks to its popularity and complexity. A multi-cluster tool is a combination of several single-cluster tools. Typically, a single-cluster tool has a robot and several processing modules (PMs). The robot is surrounded by PMs to transport wafers. A dual-arm robot has two blades, which can hold two wafers at a time and import/export of wafers through the loadlock cassette modules (LLs). K (K ≥ 2) single-cluster tools are integrated linearly into a K-cluster tool system. An example of a four-cluster tool is shown in Fig. 1. A buffering module (BM) links two adjacent cluster tools. It can temporarily accommodate incoming and outgoing wafers. The cluster tool with LLs is called the head tool and it is numbered the first one. In a steady state, the robot in the first cluster tool unloads a wafer from LLs, transfers it to the PMs for processing according to a predefined route as shown in Fig. 1, where it goes through the downstream tools and backs through the upstream tools one by one [1]. Finally, the robot in the head tool carries the completed wafer back to LLs. A swap strategy is adopted to schedule a robot for a dual-blade cluster tool. The dual blades with a swap strategy make the robot task time much shorter than the wafer processing time in a PM. Therefore, two-blade robots are more efficient than single-blade robots [2].
多集群工具的调度近年来备受关注，因其广泛应用与复杂性而成为研究热点。多集群工具由多个单集群工具组合而成。通常，单集群工具配备一台机器人和若干处理模块（PMs），机器人被 PMs 环绕，负责搬运晶圆。双臂机器人拥有两片刀片，可同时持握两片晶圆，并通过装载锁定盒模块（LLs）进行晶圆的输入输出。K（K ≥ 2）个单集群工具线性集成，构成一个 K 集群工具系统。图 1 展示了一个四集群工具的实例。缓冲模块（BM）连接相邻的两个集群工具，能暂时容纳进出晶圆。带有 LLs 的集群工具称为头部工具，编号为首。在稳态下，第一集群工具中的机器人从 LLs 卸载晶圆，按照预设路径（如图 1 所示）将其转移至 PMs 进行处理，依次经过下游工具再逆流而上[1]。最终，头部工具中的机器人将完成处理的晶圆送回 LLs。 采用交换策略来调度双刀片簇工具中的机器人。配备交换策略的双刀片使得机器人任务时间远短于 PM 中的晶圆加工时间。因此，双刀片机器人比单刀片机器人效率更高[2]。

View

Download

 查看下载

Figure 1 图 1

A four-cluster tool. LLs are viewed as PM_1,0; PM_i,0 with i > 1 denotes a buffering module.
四簇工具。LLs 被视为 PM _1,0 ；PM _i,0 且 > 1 表示一个缓冲模块。

In semiconductor manufacturing [3], various constraints bring great challenges to scheduling cluster tools. During a chemical vapor deposition (CVD) process [4], a wafer must avoid excessive exposure to the mixed chemical gases at high temperatures in a PM. Thus, after a wafer is processed, it needs to limit the time during which it stays in a PM to avoid being scrapped, which is called wafer residency time constraints [5]-[10]. Furthermore, the circuit width on a wafer has been reduced to less than 10 nanometers under continuous development [11]. To fabricate high-end integrated-circuit chips, CVD equipment puts atom-thick layers of nanomaterials onto a wafer, which synthesizes monolayer, bilayer, or few-layer graphene. Consequently, as circuit width shrinks down, the quality of circuits on wafers is more susceptible to chemical reaction time in a chamber [12]. The wafer sojourn time in a chamber after its processing referred to as post-processing time affects the circuit quality. Wafer delay analysis has been done for single cluster tools [13]-[15]. It requires proper control on the post-processing time in different processing steps and the difference in post-processing time between two adjacent cluster tools as well.
在半导体制造中[3]，各种约束条件为调度集群工具带来了巨大挑战。在化学气相沉积（CVD）过程中[4]，晶圆必须避免在 PM 中长时间暴露于高温混合化学气体中，以免被废弃，这被称为晶圆驻留时间约束[5]-[10]。此外，随着持续发展，晶圆上的电路宽度已缩小至不足 10 纳米[11]。为制造高端集成电路芯片，CVD 设备将原子厚度的纳米材料层沉积在晶圆上，合成单层、双层或多层石墨烯。因此，随着电路宽度的缩小，晶圆上电路的质量更易受腔室内化学反应时间的影响[12]。晶圆在处理后在腔室内的停留时间，即后处理时间，影响着电路质量。针对单个集群工具的晶圆延迟分析已有研究[13]-[15]。 它要求在不同加工步骤中对后处理时间进行适当控制，同时也要控制相邻两台簇工具之间的后处理时间差异。

Great efforts have made for modeling, analysis, and scheduling cluster tools [5], [13], [14] and [16]-[32] and deadlock analysis in flexible manufacturing systems [33]-[36]. The robotic manufacturing systems in [33]-[35] differ from the multi-cluster tools in the following aspects. First, the former does not cover residency time constraints and revisiting processes. Second, the former has one input station and another output station and it is configured in a linear layout; however, the latter has the same input and output station (loadlock modules) and it is configured in a circular layout. Due to these differences, the methods in [33]-[35] cannot solve the deadlock problems for multi-cluster tools.
已为建模、分析和调度集群工具[5]、[13]、[14]及[16]-[32]以及柔性制造系统中的死锁分析[33]-[36]付出了巨大努力。文献[33]-[35]中的机器人制造系统与多集群工具在以下方面有所不同。首先，前者不涉及停留时间约束和重访过程。其次，前者具有一个输入站和一个输出站，并采用线性布局；而后者则拥有相同的输入和输出站（装载锁定模块），并采用环形布局。由于这些差异，[33]-[35]中的方法无法解决多集群工具的死锁问题。

A multi-cluster tool is said to be process-dominant if its bottleneck tool is process-bound. The study in [37] shows that a one-wafer cyclic schedule can be found for a process-dominant multi-cluster tool. A feasible one-wafer cyclic schedule can be found for a process-dominant multi-cluster tool under a steady state [38]-[41], and [5] derives its schedulability conditions under wafer residency time constraints. Thus, one can effectively find an optimal cyclic schedule if a feasible one exists. Reference [42] proposes a non-cyclic scheduling method for multi-cluster tools. Now, it is rather significant to further examine the wafer post-processing time for multi-cluster tools. For the requirements of high-quality functional circuits, field-effect transistors must be built with high uniformity on a wafer from transistors to circuits [43], e.g., MoS₂ is grown by CVD, and the residual film is expected to deposit uniformly. Reducing the difference in post-processing time among a variety of process steps is conducive to keeping good uniformity among different layers of circuits on a wafer since a layer of circuits are typically fabricated by a processing step.
如果多集群工具的瓶颈工具受制于工艺时间，则称该多集群工具为工艺主导型。[37]中的研究表明，可以为工艺主导型多集群工具找到一种单片循环调度。在稳态条件下，可以为工艺主导型多集群工具找到可行的单片循环调度[38]-[41]，并且[5]推导了其在晶片停留时间约束下的可调度性条件。因此，如果存在可行方案，可以有效找到最优的循环调度。参考文献[42]提出了一种针对多集群工具的非循环调度方法。现在，进一步研究多集群工具的晶片后处理时间显得尤为重要。为了满足高质量功能电路的要求，场效应晶体管必须在晶片上以高均匀性构建，从晶体管到电路[43]，例如，MoS ₂ 通过 CVD 生长，期望残余膜均匀沉积。减少各种工艺步骤之间的后处理时间差异，有助于保持晶片上不同电路层之间的良好均匀性，因为一层电路通常由一个处理步骤制成。

Differently from the aforementioned existing work, this study focuses on a K-cluster tool to get a better schedule with regulations on wafer post-processing time and high productivity. Reference [44] investigates the optimal scheduling of a dual-arm single-cluster tool with regulations of wafer post-processing time. However, its method and result cannot be applied to a multi-cluster tool.
与上述现有研究不同，本研究聚焦于一种 K 簇工具，旨在通过规定晶圆后处理时间和高生产率来获得更优的调度方案。参考文献[44]探讨了双臂单簇工具在晶圆后处理时间约束下的最优调度问题。然而，其方法和结果无法应用于多簇工具。

For a K-cluster tool, it is very challenging to regulate the wafer post-processing time. The challenges come from the following facts. 1) Shortening wafer post-processing time at a given step requires that the robot changes its time to load/unload a wafer, resulting in the changes of time to perform loading/unloading actions at upstream and downstream steps including the buffer steps, which interact with the robot actions in adjacent cluster tools. Such interplay requires that delicate control of the cycle time should be made to coordinate multiple robots’ actions to keep the cycle time of a K-cluster tool constant. If such coordination is not well conducted, there would be cycle time fluctuation that easily propagates to its adjacent cluster tools and affects their cycle time. 2) Narrowing the difference in post-processing time between adjacent tools is a complex issue because it is very delicate to coordinate multiple robots to pace each tool and each step in a single tool.
对于 K 簇工具而言，调控晶圆后处理时间极具挑战性。挑战源自以下事实：1) 在某一工序缩短晶圆后处理时间，要求机器人改变其装载/卸载晶圆的时间，进而导致包括缓冲步骤在内的上下游工序装卸动作时间的变化，这些步骤与相邻簇工具中的机器人动作相互影响。这种相互作用要求对周期时间进行精细控制，以协调多个机器人的动作，保持 K 簇工具的周期时间恒定。若协调不当，将导致周期时间波动，并容易波及相邻簇工具，影响其周期时间。2) 缩小相邻工具间后处理时间的差异是一个复杂问题，因为协调多个机器人以使每个工具及单个工具中的每个步骤同步进行极为精细且复杂。

The main contributions of this paper are twofold as follows.
本文的主要贡献如下双方面。

1) In order to realize the adjustment of post-processing time, we propose effective algorithms to minimize the total post-processing time and balance its difference among the processing steps inside each tool.
1) 为了实现后处理时间的调整，我们提出了有效的算法来最小化总后处理时间，并平衡每个工具内各处理步骤之间的差异。

2) We propose a linear programming model and a condition table to find the upper bound for adjusting the post-processing time in adjacent cluster tools. Then, an efficient algorithm is designed to adjust each cluster tool to balance the difference in post-processing time between adjacent cluster tools.
2) 我们提出了一种线性规划模型和条件表，用于确定相邻簇工具后处理时间调整的上限。随后，设计了一种高效算法，以调整每个簇工具，平衡相邻簇工具间后处理时间的差异。

The rest of this article is structured as follows. Section II analyzes the temporal properties of scheduling multi-cluster tools. Section III proposes algorithms to find an optimal schedule that can minimize post-processing time and avoid uneven post-processing time among the processing steps or two adjacent cluster tools. Section IV gives two examples for applying the proposed method. Section V makes a summary of this work.
本文其余部分的结构如下。第二部分分析了调度多集群工具的时间特性。第三部分提出了寻找最优调度的算法，以最小化后处理时间并避免处理步骤之间或两个相邻集群工具之间的后处理时间不均。第四部分给出了两个应用所提出方法的示例。第五部分对本工作进行了总结。

II Problem Description  II 问题描述

A Operation and Properties of a K-Cluster Tool
K-簇工具的操作与特性

Following [27] and [38], we make the following assumptions for a dual-arm K-cluster tool (K ≥ 2).
参考[27]和[38]，我们对双臂 K 簇工具（K ≥ 2）做出以下假设。

1) Two LLs can continuously provide enough wafers for PMs without interruption. Thus, a K-cluster tool can run under a steady state.
1) 两台 LL 设备能够持续不断地为 PM 设备提供足够的晶圆，从而确保 K-集群工具在稳定状态下运行。

2) A BM can hold one wafer at a time without a processing function.
2) 机械手可一次持有一个晶圆，但不具备加工功能。

3) Every processing step is configured with a PM. Thereafter, in order to facilitate the presentation, we refer to a PS as a PM. It is obvious that a wafer is processed at a PM once and enters a BM twice.
3) 每个加工步骤都配备了一个 PM。此后，为了便于表述，我们将 PS 称为 PM。显然，一个晶圆在 PM 中加工一次，并进入 BM 两次。

Let N_q = {0, 1, 2, 3, …, q} and $N_q^{+}$ = N_q\{0}, where q is a given positive integer. Then, C_i denotes the ith cluster tool and R_i denotes the robot in C_i, i ∈ $N_K^{+}$. The buffering step in C_i at a buffering module can be represented by b[i], i ∈ $N_{K-1}^{+}$. Let $b\left[K\right]=\varnothing$. Let n[i] denote the index of the last step in C_i. Then, the processing steps of C_i are denoted by PS_{i, 0}, PS_{i, 1}, …, PS_{i, b[i]}, …, and PS_{i, n[i]}. As shown in Fig. 1, we can get the wafer processing route in a K-cluster tool as $⟨$LL→ PM_1,1 → ···→ PM_{1, b[1]} (PM_2,0) → PM_2,1 → ···→ PM_{2, b[1]} (PM_3,0) → ··· → PM_{K − 1, (b[K − 1])} (PM_{K, 0}) → PM_{K, 1} → ··· → PM_{K, (n[K])} → ··· → PM_{K, 0} (PM_{K − 1, (b[K − 1])}) → PM_{K − 1, (b[K − 1] + 1)} → ··· → PM_3,0 (PM_{2, b[2]}) → PM_{2, (b[2] + 1)} → ··· → PM_2,0 (PM_{1, b[1]}) → ···→ PM_{1, n[1]} → LL$⟩$. For C_i, let ω_{i, j} and ω_{i, jS} denote the robot waiting time before unloading and loading a wafer from/into PM_{i, j}, respectively. For R_i, it takes μ_i time units to move between two PMs or a PM and an LL, λ_i time units to load/unload a wafer into/from a PM (LL), and ρ_i time units to make a rotation. Let α_{i, j} denote the wafer processing time at PM_{i, j}. The processing time at buffering modules and LLs is zero due to no functional processing there. The symbols for timeliness analysis are listed in Table I. In addition, the time required in a K-cluster tool is shown in Table II.
设 N _q = {0, 1, 2, 3, …, q} 且 $N_q^{+}$ = N _q \{0}，其中 q 为给定的正整数。记 C 为第 th 个簇工具，R 为 C 中的机器人，∈ $N_K^{+}$ 。C 中缓冲模块处的缓冲步骤可表示为 b[]，∈ $N_{K-1}^{+}$ 。令 $b\left[K\right]=\varnothing$ 。设 n[] 表示 C 中最后一步的索引。则 C 的处理步骤记为 PS _{i, 0} ，PS _{i, 1} ，…，PS _{i, b[i]} ，…，PS _{i, n[i]} 。如图 1 所示，我们可以得到 K-簇工具中的晶圆处理路径为 $⟨$ LL→ PM _1,1 → ···→ PM _{1, b[1]} (PM _2,0 ) → PM _2,1 → ···→ PM _{2, b[1]} (PM _3,0 ) → ··· → PM _{K − 1, (b[K − 1])} (PM _{K, 0} ) → PM _{K, 1} → ··· → PM _{K, (n[K])} → ··· → PM _{K, 0} (PM _{K − 1, (b[K − 1])} ) → PM _{K − 1, (b[K − 1] + 1)} → ··· → PM _3,0 (PM _{2, b[2]} ) → PM _{2, (b[2] + 1)} → ··· → PM _2,0 (PM _{1, b[1]} ) → ···→ PM _{1, n[1]} → LL $⟩$ 。对于 C，记 ω _{i, j} 和 ω _{i, jS} 分别为机器人从/向 PM _{i, j} 卸载/加载晶圆前的等待时间。对于 R，在两个 PM 或 PM 与 LL 之间移动需 μ 时间单位，加载/卸载晶圆到/从 PM（LL）需 λ 时间单位，旋转需 ρ 时间单位。设 α _{i, j} 表示晶圆在 PM _{i, j} 处的处理时间。 缓冲模块和 LL 处的处理时间为零，因为那里没有功能性处理。时效性分析的符号列于表 I 中。此外，K-集群工具所需的时间如表 II 所示。

I

Table I   表 I Symbols for Timeliness Analysis
时效性分析符号

Symbol 符号	Meaning 意义
Nq	= {0, 1, 2, 3, …, q}, where q is a positive integer. = {0, 1, 2, 3, …, q}，其中 q 为正整数。
$N_q^{+}$	= {1, 2, 3, …, q}. = {1, 2, 3, …, q}。
Ci	The ith cluster tool. 第 th 簇工具。
Ri	The robot in Ci. C 中的机器人。
PMi, j	The jth process module in Ci. C 语言中的第 th 个进程模块。
n[i]	The index of the last step in Ci. C 中最后一步的索引。
b[i]	Index of the buffering step in Ci. C 语言中缓冲步骤的索引。
λi	Time taken by Ri for unloading/loading a wafer. R 卸载/加载一个晶圆所需的时间。
μi	Time taken by Ri for moving from one PM to another. R 从一个 PM 移动到另一个 PM 所花费的时间。
ρi	Time taken by Ri’s rotation. R 旋转所需的时间。
αij	The time of processing a wafer at PMi, j. 处理 PM i, j 晶圆的时间。
θi, j	Cycle time of PMi, j. PM i, j 的周期时间。
δi, j	The permissive longest time for a wafer to stay at PMi, j after its processing. 晶圆在加工后允许停留在 PM i, j 位置的最长时间。
ξi, j	The time needed for completing a wafer at PMi, j. 完成 PM i, j 晶圆所需的时间。
Πi, jL	The lower bound of θi, j. θ i, j 的下限。
Πi, jU	The upper bound of θi, j. θ i, j 的上限。
Θi	The cycle time of Ci. C 的周期时间。
Θ	The cycle time of a K-cluster tool. K-集群工具的循环时间。
ψi	Robot Ri’s cycle time. 机器人 R 的循环时间。

II

Table II   表二 Decision Variables and Their Associated Variables
决策变量及其相关变量

Symbol 符号	Meaning 意义
ωi, j	Ri’s waiting time before unloading a wafer from PMi, j. R 在从 PM i, j 卸载晶圆前的等待时间。
ωi, jS	Ri’s waiting time before loading a wafer into PMi, j. R 在将晶圆装入 PM i, j. 之前的等待时间
τi, j	Wafer sojourn time at PMi, j. 晶圆在 PM i, j. 处的停留时间
ri, j	The post-processing time of a wafer at PMi, j. 0 号位 PM 的晶圆后处理时间。

B Temporal Properties of Individual Tools
B 个体工具的时间特性

By a swap strategy, robot R_i executes the following sequence of operations in C
通过交换策略，机器人 R 在 C 中执行以下操作序列_i

$⟨$Moving to PM_{i, 0} (it takes μ_i time units; hereafter, only the amount of time is presented) → waiting there for ω_{i, 0} time units → unloading a wafer from PM_{i, 0} (λ_i) → rotating (ρ_i) → waiting there for ω_{i, 0S} time units → loading a wafer gripped by the other blade into PM_{i, 0} (λ_i) → ··· → moving to PM_{i, b[i]} (μ_i) → waiting there for ω_{i, b[i]} time units → unloading a wafer from PM_{i, b[i]} (λ_i) → rotating (ρ_i) → waiting there for ω_{i, b[i]S} time units → loading a wafer gripped by the other blade into PM_{i, b[i]} (λ_i) → ··· → moving to PM_{i, n[i]} (μ_i) → waiting there for ω_{i, n[i]} time units → unloading the finished wafer from PM_{i, n[i]} (λ_i) → rotating (ρ_i) → waiting there for ω_{i, n[i]S} time units → loading a wafer gripped by the other blade into PM_{i, n[i]} (λ_i) → moving to PM_{i, 0} (μ_i) again$⟩$.
$⟨$ 移动到 PM _{i, 0} （耗时μ时间单位；此后，仅呈现时间量）→ 在那里等待ω _{i, 0} 时间单位 → 从 PM _{i, 0} 卸载晶圆（λ）→ 旋转（ρ）→ 在那里等待ω _{i, 0S} 时间单位 → 将另一刀片夹持的晶圆装入 PM _{i, 0} （λ）→ ··· → 移动到 PM _{i, b[i]} （μ）→ 在那里等待ω _{i, b[i]} 时间单位 → 从 PM _{i, b[i]} 卸载晶圆（λ）→ 旋转（ρ）→ 在那里等待ω _{i, b[i]S} 时间单位 → 将另一刀片夹持的晶圆装入 PM _{i, b[i]} （λ）→ ··· → 移动到 PM _{i, n[i]} （μ）→ 在那里等待ω _{i, n[i]} 时间单位 → 从 PM _{i, n[i]} 卸载成品晶圆（λ）→ 旋转（ρ）→ 在那里等待ω _{i, n[i]S} 时间单位 → 将另一刀片夹持的晶圆装入 PM _{i, n[i]} （λ）→ 再次移动到 PM _{i, 0} （μ） $⟩$ 。

Hence, robot R_i’s (2 ≤ i ≤ K) cycle time is
因此，机器人 R 的（2 ≤ ≤ K）周期时间为

$\begin{array}{cc}{\psi }_i=& \left(n\right[i]+1)\left(2{\lambda }_i+{\mu }_i+{\rho }_i\right)+\sum _{j=0}^{n\left[i\right]}{\omega }_{i,jS}+\sum _{j=0}^{n\left[i\right]}{\omega }_{i,j}\\ =& {\psi }_{i,1}+{\psi }_{i,2}\end{array}$

where ψ_{i, 1} = (n[i] + 1)(2λ_i + μ_i + ρ_i), i ∈ $N_K^{+}$\{1}.
其中 ψ _{i, 1} = (n[] + 1)(2λ + μ + ρ), ∈ $N_K^{+}$ \{1}。

Since LLs in C₁ have no capacity limit, robot R₁ can directly load/unload wafers with the same blade. Hence, robot R₁’s cycle time is
由于 C ₁ 中的 LLs 没有容量限制，机器人 R ₁ 可以直接使用同一刀片装载/卸载晶圆。因此，机器人 R ₁ 的循环时间

$\begin{array}{cc}{\psi }_1=& \left(n\right[1]+1)\left(2{\lambda }_1+{\mu }_1\right)+n\left[1\right]\times {\rho }_1+\sum _{j=0}^{n\left[1\right]}{\omega }_{1,jS}+\sum _{j=0}^{n\left[1\right]}{\omega }_{1,j}\\ =& {\psi }_{1,1}+{\psi }_{1,2}\end{array}$

where ψ_1,1 = (n[1] + 1)(2λ₁ + μ₁) + n[1] × ρ₁.
其中 ψ _1,1 = (n[1] + 1)(2λ ₁ + μ ₁ ) + n[1] × ρ ₁ 。

Therefore, by (1) and (2), a robot’s cycle time consists of its task time and waiting time. The former is a constant that is equal to ψ_{i, 1}, while the latter is ψ_{i, 2} =${\sum }_{j=0}^{n\left[i\right]}{\omega }_{i,j}+{\sum }_{j=0}^{n\left[i\right]}{\omega }_{i,jS}$.
因此，根据（1）和（2），机器人的周期时间由其任务时间和等待时间组成。前者是一个常数，等于ψ _{i, 1} ，而后者为ψ _{i, 2} = ${\sum }_{j=0}^{n\left[i\right]}{\omega }_{i,j}+{\sum }_{j=0}^{n\left[i\right]}{\omega }_{i,jS}$ 。

The key to scheduling a multi-cluster tool is to coordinate the operations of the multiple robots. To do so, we need to analyze its temporal properties. The time is taken to complete a wafer at PS_{i, j}, i ∈ $N_K^{+}$, as follows:
调度多集群工具的关键在于协调多个机器人的操作。为此，我们需要分析其时间特性。完成一张晶圆在 PS _{i, j} , ∈ $N_K^{+}$ 所需的时间如下：

${\xi }_{i,j}={\alpha }_{i,j}+2{\lambda }_i+{\rho }_i+{\omega }_{i,jS},j\in N_{n\left[i\right]}^{+}$

and 和

${\xi }_{i,0}=2{\lambda }_i+{\rho }_i+{\omega }_{i,0S}.$

In (3) and (4), ω_{i, jS} is a decision variable, while λ_i, ρ_i, and α_{i, j} are given parameters. When ω_{i, jS} is zero, we get the shortest time for completing a wafer at PM_{i, j}, i.e., the lower bound Π_{i, jL}, i ∈ $N_K^{+}$, as
在(3)和(4)中，ω _{i, jS} 是一个决策变量，而 λ、ρ 和 α _{i, j} 是给定的参数。当 ω _{i, jS} 为零时，我们得到在 PM _{i, j} 完成一片晶圆的最短时间，即下界 Π _{i, jL} ，∈ $N_K^{+}$ ，为

${\Pi }_{i,jL}={\alpha }_{i,j}+2{\lambda }_i+{\rho }_i,j\in N_{n\left[i\right]}^{+}$

and 和

${\Pi }_{i,0L}=2{\lambda }_i+{\rho }_i.$

After a wafer is processed at PM_{i, j}, it cannot stay at PM_{i, j} for more than δ_{i, j}≥ 0 time units. Thus, the upper bound of Π_{i, j} is
在晶圆于 PM _{i, j} 加工后，它不能在 PM _{i, j} 停留超过δ _{i, j} ≥ 0 个时间单位。因此，Π _{i, j} 的上限为

${\Pi }_{i,jU}={\alpha }_{i,j}+{\delta }_{i,j}+2{\lambda }_i+{\rho }_i,j\in N_{n\left[i\right]}.$

The time between loading a wafer into PM_{i, j} and unloading it from there is called wafer sojourn time, which is denoted by τ_{i, j}. Obviously, α_{i, j}+δ_{i, j}≥ τ_{i, j}≥ α_{i, j} should be met, which means that a wafer staying at a PM subject to such a constraint leads to a feasible schedule. The cycle time at PS_{i, j} is
将晶圆装入 PM _{i, j} 到从那里卸载的时间间隔称为晶圆停留时间，记作τ _{i, j} 。显然，应满足α _{i, j} + δ _{i, j} ≥ τ _{i, j} ≥ α _{i, j} ，这意味着晶圆在受此约束的 PM 中停留会导致一个可行的调度。PS _{i, j} 的周期时间为

${\theta }_{i,j}={\tau }_{i,j}+2{\lambda }_i+{\rho }_i+{\omega }_{i,jS},j\in N_{n\left[i\right]}^{+}.$

Although BMs and LLs perform no functional processing, i.e., α_{i, 0} = 0, a wafer may stay at BMs or LLs for τ_{i, 0} time units. We get that the cycle time at PS_{i, 0} is
尽管批量模块和装载锁不执行任何功能性处理，即α _{i, 0} = 0，但晶圆可能在批量模块或装载锁中停留τ _{i, 0} 时间单位。由此得出，在工艺步骤 _{i, 0} 处的循环时间为

${\theta }_{i,0}={\tau }_{i,0}+2{\lambda }_i+{\rho }_i+{\omega }_{i,0S}.$

τ_{i, j} can be calculated as follows:
τ _{i, j} 可以按如下方式计算：

${\tau }_{i,j}={\psi }_i-\left(2{\lambda }_i+{\rho }_i+{\omega }_{i,jS}\right),j\in N_{n\left[i\right]}.$

The above equation shows that the wafer residency time depends on robot waiting time ω_{i, jS} when ψ_i is given.
上述方程表明，晶圆驻留时间取决于给定ψ时的机器人等待时间ω _{i, jS} 。

Let Π_i = max{Π_{i, 0L}, Π_{i, 1L},…, Π_{i, n[i]L}, ψ_{i, 1}} and Θ_i denote the cycle time of C_i. Then, if Π_i ≠ ψ_{i, 1}, C_i is process-bound. To get a cyclic schedule, C_i should be scheduled to satisfy
设 Π = max{Π _{i, 0L} , Π _{i, 1L} ,…, Π _{i, n[i]L} , ψ _{i, 1} }，Θ 表示 C 的周期时间。那么，如果 Π ≠ ψ _{i, 1} ，C 是过程受限的。为了获得一个循环调度，C 应被调度以满足

${\Theta }_i={\psi }_i={\theta }_{i,j}={\xi }_{i,j},j\in N_{n\left[i\right]}\setminus \{0,b\left[i\right]\}.$

Equations (8) and (9) show that ω_{i, jS} is a decision variable for cycle time θ_{i, j} at PS_{i, j} with j$\in N_{n[i]}$. Notice that (1), (2) and (8) contain decision variables ω_{i, jS}. Thus, (11) can be made to be satisfied by adjusting R_i’s waiting time ω_{i, jS}. Suppose that Θ is the given cycle time for a K-cluster tool and let Θ_i = ψ_i = θ_{i, j} = Θ. After ω_{i, jS} is determined to meet (8) and (9), the robot’s remaining idle time (ψ_{i, 2} − ${\sum }_{j=0}^{n[i]}{\omega }_{i,jS}$) can be assigned to ω_{i, j}’s.
式(8)和(9)表明，ω _{i, jS} 是 PS _{i, j} 上周期时间θ _{i, j} 的决策变量，其中 $\in N_{n[i]}$ 。注意到(1)、(2)和(8)包含决策变量ω _{i, jS} 。因此，通过调整 R 的等待时间ω _{i, jS} ，可以使(11)得到满足。假设Θ是给定的 K-集群工具的周期时间，并设Θ = ψ = θ _{i, j} = Θ。在确定ω _{i, jS} 以满足(8)和(9)后，机器人剩余的空闲时间(ψ _{i, 2} − ${\sum }_{j=0}^{n[i]}{\omega }_{i,jS}$ )可以分配给ω _{i, j} 。

Let r_{i, j} denote the wafer post-processing time at PM_{i, j}, which is the time between the time when its processing ends and the time when R_i starts to unload the wafer. Thus, the post-processing time at PM_{i, j}, i ∈ $N_K^{+}$, is
设 r _{i, j} 表示在 PM _{i, j} 处的晶圆后处理时间，即其加工结束与 R 开始卸载晶圆之间的时间。因此，PM _{i, j} 处的后处理时间，∈ $N_K^{+}$ ，为

$r_{i,j}={\tau }_{i,j}-{\alpha }_{i,j},j\in N_{n\left[i\right]}\setminus \{0,b\left[i\right]\}.$

If the robot waiting time ω_{i, jS} is properly set, (11) can be satisfied. It implies that the cycle time of each cluster tool, each robot, and each PM is equal so that a multi-cluster tool can yield one wafer within a cycle. Given cycle time Θ_i = θ_{i, j} = Θ with i$\in$$N_K^{+}$ and j$\in$$N_{n[i]}$, by (8) and (9), if ω_{i, jS} (i$\in$$N_K^{+}$) increases, then wafer sojourn time τ_{i, j} decreases, and by (12), r_{i, j} decreases as well. In the view of tool C_i, minimizing the total post-processing time ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \{b\left[i\right]\}}{r}_{i,j}$ is conducive to producing high-quality circuit chips on wafers.
若机器人等待时间ω _{i, jS} 设置得当，则（11）式可满足。这意味着每个集群工具、每台机器人及每个 PM 的周期时间相等，从而使得多集群工具能在一个周期内产出一片晶圆。给定周期时间Θ = θ _{i, j} = Θ $\in$ $N_K^{+}$ 及 $\in$ $N_{n[i]}$ ，根据（8）和（9）式，若ω _{i, jS} （ $\in$ $N_K^{+}$ ）增加，则晶圆停留时间τ _{i, j} 减少，且由（12）式可知，r _{i, j} 亦随之减少。从工具 C 的角度看，最小化总后处理时间 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \{b\left[i\right]\}}{r}_{i,j}$ 有助于在晶圆上制造出高质量的电路芯片。

C Problem Definition C 问题定义

The objective of this work is to regulate wafer post-processing time such that high-quality circuits can be ensured on a wafer. Therefore, this work aims to accomplish the following missions.
本工作的目标是调控晶圆后处理时间，以确保晶圆上能制造出高质量的电路。因此，本工作旨在完成以下任务。

1) Minimize the cycle time of a dual-arm K-cluster tool.
1) 最小化双臂 K 簇工具的循环时间。

2) Minimize ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ for C_i, i$\in$$N_K^{+}$ and shorten the difference in post-processing time among PS_{i, j}, j$\in$N_n[i]\{0, b[i]}.
2) 最小化 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 对于 C， $\in$ $N_K^{+}$ ，并缩短 PS _{i, j} ， $\in$ N _n[i] \{0, b[]} 之间的后处理时间差异。

3) Shorten the difference in post-processing time between adjacent cluster tools.
3) 缩短相邻簇工具间后处理时间的差异。

III Scheduling Algorithms
III 调度算法

A Coordination of Multiple Robots
多机器人协同

The minimal cycle time of a process-bound dual-arm cluster tool C_i can be calculated as Π_i = max{Π_{i, 0L}, Π_{i, 1L}, …, Π_{i, n[i]L}}, i$\in$$N_K^{+}$. When a K-cluster tool runs, multiple robots can be coordinated such that the cycle time of R_i is the same as C_i, i.e., ψ_i = Π_i.
过程约束型双臂集群工具 C 的最小循环时间可计算为Π = max{Π _{i, 0L} , Π _{i, 1L} , …, Π _{i, n[i]L} }, $\in$ $N_K^{+}$ 。当 K 集群工具运行时，多个机器人可协调工作，使得 R 的循环时间与 C 相同，即ψ = Π。

Let Π = max {Π₁, Π₂, …, Π_K}. As aforementioned, Θ is the cycle time of a K-cluster tool. Assume that C_g (2 ≤ g ≤ K–1) has the heaviest workload among the K individual tools. Thus, we have Π = Π_g, and the bottleneck of a K-cluster tool is C_g. For a process-dominant K-cluster tool, to obtain a one-wafer cyclic schedule, we must have
设 Π = max {Π ₁ , Π ₂ , …, Π _K }。如前所述，Θ 是 K-集群工具的周期时间。假设 C _g (2 ≤ g ≤ K–1) 在 K 个独立工具中具有最重的工作负荷。因此，我们有 Π = Π _g ，且 K-集群工具的瓶颈为 C _g 。对于过程主导的 K-集群工具，为了获得单片循环调度，我们必须满足

${\Theta }_1={\Theta }_2=\cdots ={\Theta }_K=\Theta .$

This means that each cluster tool should be scheduled with the same cycle time. The cycle time must satisfy Θ ≥ Π = Π_g. Under this premise, it can guarantee to apply a swap strategy to each C_i, i ∈ $N_K^{+}$.
这意味着每个簇工具应按相同的周期时间进行调度。周期时间必须满足 Θ ≥ Π = Π _g 。在此前提下，可以保证对每个 C, ∈ $N_K^{+}$ 应用交换策略。

Given the cycle time, the wafer processing time and the robot activity time are deterministic, the post-processing time and robot waiting time are variables, and interact with each other. Therefore, it is necessary to ensure that the robot waiting time is coordinated so that an individual tool can be scheduled at the same pace without conflict over its buffering module, and the difference in post-processing time among different steps can be regulated as small as possible. Note that a BM does not participate in the processing of wafers. Thus, BMs have no wafer residency time constraints.
鉴于循环时间、晶圆加工时间和机器人活动时间是确定的，而后处理时间和机器人等待时间是变量，并相互影响。因此，有必要确保机器人等待时间协调一致，使得单个工具能够在其缓冲模块上无冲突地按相同节奏调度，并且不同步骤之间的后处理时间差异尽可能小。需要注意的是，缓冲模块（BM）不参与晶圆的处理，因此 BM 没有晶圆停留时间的约束。

Algorithm 1 Determine the Robot Waiting Time for a K-Cluster Tool
算法 1 确定 K 簇工具的机器人等待时间

Input: λ_i, μ_i, α_{i, j}, δ_{i, j}, ρ
输入：λ, μ, α _{i, j} , δ _{i, j} , ρ_i

Output: Θ, ω_{i, jS}, ω_i,j
输出: Θ, ω _{i, jS} , ω _i,j

1: Calculate ψ_{i, 1}, ψ_{i, 2}, Π_{i, jL}, Π_{i, jU,}, by (1), (2) and (5)–(7), respectively.
计算 ψ _{i, 1} , ψ _{i, 2} , Π _{i, jL} , Π _{i, jU,} ，分别通过公式 (1), (2) 和 (5)–(7)。

2: Π_i ← max{Π_{i, 0L}, Π_{i, 1L}, …, Π_{i, n[i]L}}for i$\in$$N_K^{+}$.
2: Π ← max{Π _{i, 0L} , Π _{i, 1L} , …, Π _{i, n[i]L} }对于 $\in$ $N_K^{+}$ 。

3: Θ ← max {Π₁, Π₂, …, Π_K}

4: Fori =1 to Kdo
4: 对于 i = 1 到 K 执行

5:Ifψ_{i, 1} ≤ Θ and Θ ≤ Π_{i, jU}, j ∈ $N_{n[i]}^{+}$\{b[i]} Then
5:若ψ _{i, 1} ≤ Θ且Θ ≤ Π _{i, jU} ，则∈ $N_{n[i]}^{+}$ \{b[]}

6: 　　Call Algorithm 2 //*Case 2
6: 调用算法 2 //*情况 2

7: 　Else if Π_{i, jL} ≤ ψ_i1 ≤ Π_{i, jU}, j ∈ $N_{n[i]}^{+}$\{b[i]}
7: 否则如果 Π _{i, jL} ≤ ψ _i1 ≤ Π _{i, jU} , ∈ $N_{n[i]}^{+}$ \{b[]}

　 　　Then　　　//*Case 1 那么 //*情况 1

8: 　　　ω_{i, jS} ←0, ω_{i, j} ←0, for j ∈ $N_{n[i]}$
8: ω _{i, jS} ←0, ω _{i, j} ←0, 对于 ∈ $N_{n[i]}$

9: 　　　Elseif${\cap }_{j\in N_{n[i]}^{+}\setminus \left\{b\right[i\left]\right\}}$ [Π_{i, jL}, Π_{i, jU}] = $\varnothing$Then
9: 否则如果 ${\cap }_{j\in N_{n[i]}^{+}\setminus \left\{b\right[i\left]\right\}}$ [Π _{i, jL} , Π _{i, jU} ] = $\varnothing$ 那么

10: 　Call Algorithm 3 //*Case 3
10: 调用算法 3 //*情况 3

11:　　　　　Else 11: 其他

12:　　　　　　Return //*Unschedulable
12: 返回 //*不可调度

13:　　　　　Endif 13: 结束条件

14:　　　Endif 14: 结束判断

15:　EndIf 15: 结束判断

16:　Ifi ≠ K and τ_{i, b[i]} < 2λ_i+1 + ρ_i+1, Then
16: 若 ≠ K 且 τ _{i, b[i]} < 2λ _i+1 + ρ _i+1 ，则

17:　　Return //*Unschedulable
17: 返回 //*不可调度

18:　End if 18: 结束如果

19: EndFor 19: 结束循环

20: End 20: 结束

Algorithm 2 Set R_i’s Waiting Time for Case 2
算法 2 设置 R 的等待时间，情况 2

Input: λ_i, μ_i, α_{i, j}, δ_{i, j}, Θ, ρ
输入：λ, μ, α _{i, j} , δ _{i, j} , Θ, ρ_i

Output: ω_{i, j}, ω_{i, jS}, r_{i, j}
输出: ω _{i, j} , ω _{i, jS} , r _{i, j}

1: 　V← {j | j ≠ 0 and j ≠ b[i], j ∈ N_n[i]}
1: V← { | ≠ 0 且 ≠ b[], ∈ N _n[i] }

2: 　 ε ←${\sum }_{j\in V}($Θ − (α_{i, j}+ 2λ_i + ρ_i)

3: 　Ifψ_{i, 2}≥ ε
3: 若ψ _{i, 2} ≥ ε

4: 　　h←ψ_{i, 2}-ε

5: 　　Forj∈Vdo 5: 对于∈V 中的每个元素执行

6: 　　　r_{i, j} ←0, ω_{i, jS} ←Θ – (α_{i, j} + 2λ_i + ρ_i), ω_{i, j}←h/|V|

7: 　　Endfor 7: 结束循环

8: 　Else //*ψ_{i, 2} < ε
8: 其他情况 //*ψ _{i, 2} < ε

9: 　　h←ε-ψ_{i, 2}

10:　　WhileV ≠ $\varnothing$Then
10: 当 V ≠ $\varnothing$ 时

11:　　　Δ←h/|V|, A← $\varnothing$, B← $\varnothing$

12:　　　For each j ∈ Vdo
12: 对于每个 ∈ V 执行

13:　　　　If Δ ≤ Θ − (α_{i, j} + 2λ_i + ρ_i) ThenA←A$\cup${j}
13: 若 Δ ≤ Θ − (α _{i, j} + 2λ + ρ) 则 A←A $\cup$ {}

14:　　　　ElseB ←B$\cup${j}

15:　　　Endif 15: 结束判断

16:　　Endfor 16: 结束循环

17:　　IfB ≠ $\varnothing$Then
17: 如果 B ≠ $\varnothing$ 那么

18:　　　For each j ∈ Bdo
18: 对于每个 ∈ B 执行

19:　　　　r_{i, j}←Θ − (α_{i, j} + 2λ_i + ρ_i), ω_{i, jS} ←0, ω_{i, j} ←0

20:　　　　h←h − (Θ − (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}))

21:　　　EndFor 21: 结束循环

22:　　　V←V \ B

23:　　Else 23: 否则

24:　　　For each j ∈ Ado
24: 对于每个 ∈ Ado

25:　　　　r_{i, j} ←Δ

26:　　　　ω_{i, jS} ← Θ − (α_{i, j}+ 2λ_i + ρ_i)− r_{i, j}, ω_{i, j} ←0

27:　　　EndFor 27: 结束循环

28:　　　V←$\varnothing$

29:　　　EndIf 29: 结束判断

30:　　Endwhile 30: 结束循环

31:　EndIf 31: 结束如果

32:　ω_{i, 0S} ←0, ω_{i, 0} ←0, ω_{i, b[i]S} ←0, ω_{i, b[i]} ←0

33:　End 33: 结束

It follows from [24] that if Θ ≥ Π is the cycle time of a process-dominant K-cluster tool with wafer residency time constraints, a one-wafer periodic schedule exists if and only if, for any pair of C_i and C_i+1, i ∈ $N_{K-1}^{+}$, ω_{i, jS}’s and ω_{(i+1), fS}’s are set such that the following conditions are satisfied:
由[24]可得，若Θ ≥ Π为具有晶圆驻留时间约束的过程主导型 K-簇工具的周期时间，当且仅当对于任意一对 C 和 C _i+1 ，∈ $N_{K-1}^{+}$ ，ω _{i, jS} 和ω _{(i+1), fS} 被设定以满足以下条件时，存在一种单晶圆周期调度：

${\theta }_{i,j}={\theta }_{(i+1),f}=\Theta ,j\in N_{n\left[i\right]}andf\in N_{n[i+1]}$

${\tau }_{i,j}\in \left[{\alpha }_{i,j},{\alpha }_{i,j}+{\delta }_{i,j}\right],i\in N_K^{+}andj\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}$

${\tau }_{i,b\left[i\right]}\ge 2{\lambda }_{i+1}+{\rho }_{i+1}+{\omega }_{(i+1),0S}$

and 和

${\tau }_{(i+1),0}\ge 2{\lambda }_i+{\rho }_i+{\omega }_{i,b\left[i\right]S}.$

B Algorithms B 算法

By (10), (12) and (15)−(17), setting appropriate ω_{i, jS}’s can render conditions (15)−(17) satisfied and further shorten wafer post-processing time. If ω_{i, jS}’s are determined, a one-wafer cyclic schedule is found. Therefore, we propose Algorithms 1−3 to calculate ω_{i, jS}’s to obtain a schedule, where the cardinality of set V is denoted by |V|. We propose Algorithm 1 to handle three different workload cases for each cluster tool. Algorithm 1 determines the condition to be satisfied by a K-cluster tool. Section IV details the calculation process for Algorithm 1.
通过(10)、(12)及(15)−(17)，设定适当的ω _{i, jS} 可以满足条件(15)−(17)，并进一步缩短晶圆后处理时间。若ω _{i, jS} 确定，则可找到一个单晶圆循环调度。因此，我们提出算法 1−3 来计算ω _{i, jS} 以获得调度，其中集合 V 的基数记为|V|。我们提出算法 1 来处理每种集群工具的三种不同工作负载情况。算法 1 确定了一个 K 集群工具需满足的条件。第四节详细阐述了算法 1 的计算过程。

Case1: Π_{i, jL} ≤ ψ_{i, 1} ≤ Π_{i, jU}, i ∈ $N_K^{+}$, indicates that robot R_i is always busy and tool C_i is transport-bound. Therefore, the robot waiting time is zero as shown in Line 8 of Algorithm 1.
案例 1：Π _{i, jL} ≤ ψ _{i, 1} ≤ Π _{i, jU} , ∈ $N_K^{+}$ , 表明机器人 R 始终处于忙碌状态，而工具 C 则受限于运输。因此，如算法 1 第 8 行所示，机器人等待时间为零。

Case 2:ψ_{i, 1} ≤ Θ and Θ ≤ Π_{i, jU}, i ∈ $N_K^{+}$, means that the workloads of all processing steps in C_i are relatively balanced and tool C_i is process-bound.
案例 2：ψ _{i, 1} ≤ Θ 且 Θ ≤ Π _{i, jU} ，∈ $N_K^{+}$ ，意味着 C 中所有处理步骤的工作负载相对均衡，且工具 C 受限于加工过程。

The following results are given to show the optimality of the schedule obtained by Algorithm 2.
以下结果用于展示算法 2 所获得调度的最优性。

Theorem 1: Given Θ = Π_g as the cycle time for a dual-arm cluster tool, if and only if ψ_{i, 1} ≤ Θ and Θ ≤ Π_{i, jU}, i ∈ $N_K^{+}$, are satisfied, Algorithm 2 finds a schedule that achieves the lower bound of its cycle time and minimizes the total post-processing time.
定理 1：给定Θ = Π _g 为双臂集群工具的周期时间，当且仅当 ψ _{i, 1} ≤ Θ 且 Θ ≤ Π _{i, jU} ，∈ $N_K^{+}$ 条件满足时，算法 2 能找到一种调度方案，实现其周期时间下限并最小化总后处理时间。

Proof: Let Θ = Π_g be the cycle time of a K-cluster tool. We examine whether a feasible schedule with cycle time Θ can be found and whether the post-processing time is minimal.
证明：设Θ = Π _g 为 K 簇工具的循环时间。我们考察是否能找到具有循环时间Θ的可行调度，并验证后处理时间是否最小。

By Lines 1 and 2, we have ε = ${\sum }_{j\in V}($Θ – (α_{i, j} + 2λ_i + ρ_i)). If ψ_{i, 2}≥ ε, we set ω_{i, jS} = Θ – (α_{i, j} + 2λ_i + ρ_i), j ∈ V. Then, we have τ_{i, j} = Θ – (2λ_i+ρ_i + ω_{i, jS}), j ∈ V. The post-processing time at step j in C_i is r_{i, j} = τ_{i, j} – α_{i, j} = 0 < δ_{i, j}, j ∈ V. Thus, r_{i, j} is minimized, and the wafer residency time constraints are satisfied. If ψ_{i, 2} < ε, we have h = ψ_{i, 2}–ε. By Line 11, Δ = h/|V|. Lines 13 and 14 show that if Δ ≤ Θ – (α_{i, j} + 2λ_i + ρ_i) holds, Step j is put into set A, otherwise, Step j is put into set B.
根据第 1 和第 2 行，我们有ε = ${\sum }_{j\in V}($ Θ – (α _{i, j} + 2λ + ρ))。若 ψ _{i, 2} ≥ ε，则设 ω _{i, jS} = Θ – (α _{i, j} + 2λ + ρ)，∈ V。于是，τ _{i, j} = Θ – (2λ+ρ + ω _{i, jS} )，∈ V。步骤 C 中的后处理时间为 r _{i, j} = τ _{i, j} – α _{i, j} = 0 < δ _{i, j} ，∈ V。因此，r _{i, j} 被最小化，且晶圆停留时间约束得以满足。若 ψ _{i, 2} < ε，则有 h = ψ _{i, 2} –ε。根据第 11 行，Δ = h/|V|。第 13 和 14 行表明，若 Δ ≤ Θ – (α _{i, j} + 2λ + ρ) 成立，则将步骤放入集合 A，否则，将步骤放入集合 B。

If B ≠ $\varnothing$, r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i) and ω_{i, jS} = 0 for j ∈ B, Lines 18−22 deal with this situation. We have r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i) ≥ Π_{i, jL} – (α_{i, j} + 2λ_i + ρ_i) = 0 and r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i) ≤ Π_{i, jU} – (α_{i, j} + 2λ_i + ρ_i) = δ_{i, j}. Then, h = h – r_{i, j}. Because of Δ = h/|V| and Δ > Θ – (α_{i, j} + 2λ_i + ρ_i), we have h = Δ|V| > ${\sum }_{j\in B}($Θ – (α_{i, j} + 2λ_i + ρ_i)). Therefore, h > 0 always holds. By Line 22, V = V\B.
若 B ≠ $\varnothing$ ，则对 ∈ B 有 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ) 且 ω _{i, jS} = 0，第 18−22 行处理此情形。我们有 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ) ≥ Π _{i, jL} – (α _{i, j} + 2λ + ρ) = 0 及 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ) ≤ Π _{i, jU} – (α _{i, j} + 2λ + ρ) = δ _{i, j} 。于是，h = h – r _{i, j} 。由于 Δ = h/|V| 且 Δ > Θ – (α _{i, j} + 2λ + ρ)，故 h = Δ|V| > ${\sum }_{j\in B}($ Θ – (α _{i, j} + 2λ + ρ))。因此，h > 0 恒成立。根据第 22 行，V = V\B。

If B = $\varnothing$, r_{i, j} = Δ and ω_{i, jS} = Θ – (α_{i, j} + 2λ_i +ρ_i) – r_{i, j} for j ∈ A, Lines 24−28 deal with this situation. We have r_{i, j} = Δ = h/|V| ≤ Θ – (α_{i, j} + 2λ_i + ρ_i) ≤ Π_{i, jU} – (α_{i, j} +2λ_i + ρ_i) = δ_{i, j} and r_{i, j} > 0 because of ψ_{i, 2} < ε. Since ${\sum }_{j\in V}{\omega }_{i,jS}$ = ${\sum }_{j\in V}($Θ – (α_{i, j} + 2λ_i + ρ_i)) –${\sum }_{j\in V}{r}_{i,j}$ = ψ_{i, 2}, we ensure that the value of ψ_{i, 2} has been assigned to ω_{i, jS}’s (j ∈ V), i.e.,${\sum }_{j\in V}{\omega }_{i,jS}$ is maximized and ${\sum }_{j\in V}{r}_{i,j}$ is minimized.■
若 B = $\varnothing$ ，r _{i, j} = Δ 且 ω _{i, jS} = Θ – (α _{i, j} + 2λ + ρ) – r _{i, j} 对于 ∈ A，第 24−28 行处理此情况。我们有 r _{i, j} = Δ = h/|V| ≤ Θ – (α _{i, j} + 2λ + ρ) ≤ Π _{i, jU} – (α _{i, j} + 2λ + ρ) = δ _{i, j} 且 r _{i, j} > 0 因 ψ _{i, 2} < ε。由于 ${\sum }_{j\in V}{\omega }_{i,jS}$ = ${\sum }_{j\in V}($ Θ – (α _{i, j} + 2λ + ρ)) – ${\sum }_{j\in V}{r}_{i,j}$ = ψ _{i, 2} ，我们确保 ψ _{i, 2} 的值已赋给 ω _{i, jS} 的 ( ∈ V)，即 ${\sum }_{j\in V}{\omega }_{i,jS}$ 最大化且 ${\sum }_{j\in V}{r}_{i,j}$ 最小化。■

Algorithm 2 deals with the processing steps in V = {j | j ≠ 0 and j ≠ b[i],j ∈ N_n[i]}. In the case of ε≥ ψ_{i, 2}, we have that, for any step j ∈ V, the available idle time for robot R_i’s waiting is enough so that the post-processing time is zero and it is unnecessary to handle this situation. In the case of ψ_{i, 2} < ε, it is easy to show that, for step j ∈ V, R_i’s available idle time for waiting is not enough so that the post-processing time should be evenly distributed. Then, Algorithm 2 solves the above two cases. Lines 1−8 handle the case of ε≥ ψ_{i, 2}. Lines 10−33 deal with the case of ε < ψ_{i, 2} to adjust the post-processing time evenly. In addition, Lines 4 and 9 can ensure the most effective distribution of waiting time and minimize the total post-processing time.
算法 2 处理了在 V = { | ≠ 0 且 ≠ b[] ∈ N _n[i] }中的处理步骤。在ε≥ ψ _{i, 2} 的情况下，对于任何步骤 ∈ V，机器人 R 的可用等待空闲时间足够，使得后处理时间为零，因此无需处理此情况。在ψ _{i, 2} < ε的情况下，容易证明，对于步骤 ∈ V，R 的可用等待空闲时间不足，因此后处理时间应均匀分布。随后，算法 2 解决了上述两种情况。第 1−8 行处理ε≥ ψ _{i, 2} 的情况。第 10−33 行处理ε < ψ _{i, 2} 的情况，以均匀调整后处理时间。此外，第 4 行和第 9 行确保了等待时间的最佳分配并最小化了总后处理时间。

Algorithm 3 Set R_i’s Waiting Time for Case 3
算法 3 设置 R 的等待时间（情况 3）

Input: λ_i, μ_i, α_{i, j}, δ_{i, j}, Θ, ρ
输入：λ, μ, α _{i, j} , δ _{i, j} , Θ, ρ_i

Output: ω_{i, j}, ω_{i, jS}, r_{i, j}
输出: ω _{i, j} , ω _{i, jS} , r _{i, j}

1: 　E← {j| Π_{i, jU} < Θ, j ≠ 0, j ≠ b[i], j$\in$N_n[i]}

2: 　F←N_n[i]\(E$\cup${0, b[i]}), V = E$\cup$F

3: 　ω_{i, jS} ←Θ–(α_{i, j} + δ_{i, j} +2λ_i +ρ_i), for j$\in$E
3: ω _{i, jS} ←Θ–(α _{i, j} + δ _{i, j} +2λ +ρ), 对于 $\in$ E

4: 　ω_{i, jS} ← 0, for j$\in$F
4: ω _{i, jS} ← 0, 对于 $\in$ F

5: 　If${\sum }_{j\in E}$ω_{i, jS} > ψ_i2Then
5: 如果 ${\sum }_{j\in E}$ ω _{i, jS} > ψ _i2 那么

6: 　　Return //* Unschedulable
6: 　　返回 //* 不可调度

7: 　EndIf 7: 结束判断

8: 　ε←ψ_{i, 2}–${\sum }_{j\in E}$ω_{i, jS}

9: 　η←${\sum }_{j\in F}($Θ – (α_{i, j} + 2λ_i + ρ_i)) + ${\sum }_{j\in E}$δ_{i, j}

10:　Ifε≥ η 10: 如果ε≥ η

11:　h←ε–η

12:　　For each j$\in$Vdo
12: 对于每个 $\in$ Vdo

13:　　　r_{i, j} ← 0, ω_{i, jS} ← Θ – (α_{i, j} + 2λ_i + ρ_i), ω_{i, j} ← h/|V|

14:　　EndFor 14: 结束循环

15:　Else //*ε < η
15: 否则 //*ε < η

16:　　h← η – ε

17:　　WhileV ≠ $\varnothing$Then
17: 当 V ≠ $\varnothing$ 时

18:　　　Δ←h/|V|, A← $\varnothing$, B← $\varnothing$

19:　　　For each j$\in$Vdo
19: 对于每个 $\in$ Vdo

20:　　　　If Δ ≤ Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}) ThenA←A$\cup${j}
20: 若 Δ ≤ Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) 则 A←A $\cup$ {}

21:　　　　ElseB ←B$\cup${j}

22:　　　　EndIf 22: 结束如果

23:　　　Endfor 23: 结束循环

24:　　　IfB ≠ $\varnothing$Then
24: 如果 B ≠ $\varnothing$ 那么

25:　　　　For each j$\in$Bdo
25: 对于每个 $\in$ Bdo

26:　　　　r_{i, j}←Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}),

　　　　　ω_{i, jS} ←0, ω_{i, j} ←0

27:　　　　h←h – (Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}))

28:　　　　Endfor 28: 结束循环

29:　　　　V←V \ B

30:　　　Else 30: 其他

31:　　　　For each j ∈ Ado
31: 对于每个 ∈ Ado

32:　　　　r_{i, j} ←Δ

33:　　　　ω_{i, jS} ← Θ – (α_{i, j} + 2λ_i + ρ_i) – r_{i, j}, ω_{i, j} ←0

34:　　　　EndFor 34: 结束循环

35:　　　　V←$\varnothing$

36:　　　EndIf 36: 结束如果

37:　　Endwhile 37: 结束循环

38:　EndIf 38: 结束如果

39:　ω_{i, 0S} ←0, ω_{i, 0} ←0, ω_{i, b[i]S} ←0, ω_{i, b[i]} ←0

40:　End 40：结束

In Algorithm 2, all the statements make calculations based on closed-form expressions. The number of iterations in the For-loop of Lines 5−7 is no more than n[i]. The number of iterations in the For-loop of Lines 10−30 is no more than (n[i])². It is obvious that the computational complexity of Algorithm 2 is polynomial.
在算法 2 中，所有语句均基于封闭形式的表达式进行计算。第 5 至 7 行的 For 循环迭代次数不超过 n[]。第 10 至 30 行的 For 循环迭代次数不超过(n[]) ² 。显然，算法 2 的计算复杂度为多项式。

Case 3:${\cap }_{j\in N_{n\left[i\right]\setminus \left\{b\left[i\right]\right\}}^{+}}$[Π_{i, jL}, Π_{i, jU}] = $\varnothing$, i ∈ $N_K^{+}$, means that the workloads of the processing steps are unbalanced. In this case, Algorithm 3 is proposed to find a feasible schedule so that each processing step can achieve the cycle time of a K-cluster tool.
案例 3： ${\cap }_{j\in N_{n\left[i\right]\setminus \left\{b\left[i\right]\right\}}^{+}}$ [Π _{i, jL} , Π _{i, jU} ] = $\varnothing$ , ∈ $N_K^{+}$ , 意味着处理步骤的工作负荷不平衡。在这种情况下，提出算法 3 以找到一个可行调度，使得每个处理步骤都能达到 K 集群工具的周期时间。

Theorem 2: If ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$[Π_{i, jL}, Π_{i, jU}] = $\varnothing$ holds with i ∈ $N_K^{+}$, Algorithm 3 can determine whether a feasible schedule exists. If so, Algorithm 3 finds a schedule that minimizes the total post-processing time.
定理 2：若 ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$ [Π _{i, jL} , Π _{i, jU} ] = $\varnothing$ 在∈ $N_K^{+}$ 条件下成立，算法 3 可判定是否存在可行调度。若存在，算法 3 将找到使总后处理时间最小化的调度方案。

Proof: By Lines 1 and 2, we have E = {j| Π_{i, jU} <Θ, j ≠ 0, j ≠ b[i], j ∈ N_n[i]}, F = N_n[i]\E∪{0, b[i]}, and V = E∪F. For j ∈ E, we set ω_{i, jS} = Θ – (α_{i, j} + δ_{i, j} + 2λ_i + ρ_i). Hence, we have τ_{i, j} = Θ – (2λ_i + ρ_i + ω_{i, jS}) = α_{i, j} + δ_{i, j}. Then, by Line 5, if ${\sum }_{j\in E}{\omega }_{i,jS}$ ≤ ψ_{i, 2}, all steps in E can satisfy the wafer residency time constraints. If ${\sum }_{j\in E}{\omega }_{i,jS}$ > ψ_{i, 2}, ∃i ∈ E such that ω_{i, jS} < Θ – (α_{i, j} + δ_{i, j} + 2λ_i + ρ_i) holds, which leads to τ_{i, j} > α_{i, j} + δ_{i, j}. Therefore, tool C_i is not schedulable, which is given by Line 6 in Algorithm 3.
证明：根据第 1 和第 2 行，我们有 E = {| Π _{i, jU} <Θ, ≠ 0, ≠ b[], ∈ N _n[i] }，F = N _n[i] \E∪{0, b[]}，以及 V = E∪F。对于∈ E，我们设定ω _{i, jS} = Θ – (α _{i, j} + δ _{i, j} + 2λ + ρ)。因此，我们有τ _{i, j} = Θ – (2λ + ρ + ω _{i, jS} ) = α _{i, j} + δ _{i, j} 。接着，根据第 5 行，如果 ${\sum }_{j\in E}{\omega }_{i,jS}$ ≤ ψ _{i, 2} ，E 中的所有步骤都能满足晶圆驻留时间约束。如果 ${\sum }_{j\in E}{\omega }_{i,jS}$ > ψ _{i, 2} ，则存在∈ E 使得ω _{i, jS} < Θ – (α _{i, j} + δ _{i, j} + 2λ + ρ)成立，这将导致τ _{i, j} > α _{i, j} + δ _{i, j} 。因此，工具 C 不可调度，这在算法 3 的第 6 行中给出。

By Lines 8 and 9, we have ε = ψ_{i, 2} – ${\sum }_{j\in E}{\omega }_{i,jS}$ and η = ${\sum }_{j\in F}($Θ – (α_{i, j} + 2λ_i + ρ_i)) + ${\sum }_{j\in E}{\delta }_{i,j}$.
通过第 8 和第 9 行，我们有 ε = ψ _{i, 2} – ${\sum }_{j\in E}{\omega }_{i,jS}$ 以及 η = ${\sum }_{j\in F}($ Θ – (α _{i, j} + 2λ + ρ)) + ${\sum }_{j\in E}{\delta }_{i,j}$ 。

If ε≥ η, then Lines 10−14 present that ω_{i, jS} = Θ – (α_{i, j} + 2λ_i + ρ_i), j ∈ V. We have τ_{i, j} = Θ – (2λ_i + ρ_i + ω_{i, jS}) = α_{i, j}, j ∈ V. The post-processing time at PM_{i, j} is r_{i, j} = τ_{i, j} – α_{i, j} = 0 < δ_{i, j}, j ∈ V. Thus, r_{i, j} is minimized, and the wafer residency time constraints are satisfied.
若ε≥η，则第 10 至 14 行表明ω _{i, jS} = Θ – (α _{i, j} + 2λ + ρ)，∈ V。我们有τ _{i, j} = Θ – (2λ + ρ + ω _{i, jS} ) = α _{i, j} ，∈ V。PM _{i, j} 的后处理时间为 r _{i, j} = τ _{i, j} – α _{i, j} = 0 < δ _{i, j} ，∈ V。因此，r _{i, j} 被最小化，且晶圆停留时间约束得以满足。

If ε < η, we have h = ε – η. By Line 18, Δ = h/|V|. Lines 19−22 show that for j ∈ V, if Δ ≤ Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}) holds, Step j is put into set A, otherwise, it is put into set B. Lines 24−29 set the post-processing time and robot waiting time at steps in B.
若ε < η，则有 h = ε – η。根据第 18 行，Δ = h/|V|。第 19−22 行表明，对于∈ V，若Δ ≤ Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} )成立，则将 Step 放入集合 A，否则将其放入集合 B。第 24−29 行设定 B 中步骤的后处理时间和机器人等待时间。

If B ≠ $\varnothing$, r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i+ ω_{i, jS}) and ω_{i, jS} = 0 for j ∈ B. We have r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}) ≥ Π_{i, jL} – (α_{i, j} + 2λ_i + ρ_i+ ω_{i, jS}) = 0 and r_{i, j} = Θ – (α_{i, j} + 2λ_i + ρ_i+ ω_{i, jS}) ≤ Π_{i, jU} – (α_{i, j} +2λ_i +ρ_i + ω_{i, jS}) = δ_{i, j}. Then, h = h– r_{i, j}. Because of Δ = h/|V| and Δ> Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}), h = Δ|V| > ${\sum }_{j\in B}($ Θ – (α_{i, j} + 2λ_i+ρ_i + ω_{i, jS})) holds. Therefore, h > 0 always holds. By Line 29, V = V \ B.
若 B ≠ $\varnothing$ ，则 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) 且 ω _{i, jS} = 0 对 ∈ B 成立。我们有 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) ≥ Π _{i, jL} – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) = 0 及 r _{i, j} = Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) ≤ Π _{i, jU} – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) = δ _{i, j} 。于是，h = h – r _{i, j} 。由于 Δ = h/|V| 且 Δ > Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} )，故 h = Δ|V| > ${\sum }_{j\in B}($ Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} )) 成立。因此，h > 0 恒成立。根据第 29 行，V = V \ B。

If B = $\varnothing$, Lines 31−35 set robot waiting time and post-processing time at steps in A. We have r_{i, j} = Δ and ω_{i, jS} = Θ – (α_{i, j} + 2λ_i + ρ_i) – r_{i, j} for j ∈ A. Then, r_{i, j} = Δ = h/|V| ≤ Θ – (α_{i, j} + 2λ_i + ρ_i + ω_{i, jS}) ≤ Π_{i, jU} – (α_{i, j} + 2λ_i + ρ_i+ω_{i, jS}) = δ_{i, j} and r_{i, j} > 0 because of ψ_{i, 2} < ε. Since ${\sum }_{j\in V}{\omega }_{i,jS}$ = ${\sum }_{j\in V}($Θ– (α_{i, j} + 2λ_i + ρ_i)) –${\sum }_{j\in V}{r}_{i,j}$ = ψ_{i, 2}, we have that the value of ψ_{i, 2} has been assigned to ω_{i, jS}’s (j ∈ V), i.e., ${\sum }_{j\in V}{\omega }_{i,jS}$ is maximized and ${\sum }_{j\in V}{r}_{i,j}$ is minimized.■
若 B = $\varnothing$ ，第 31-35 行设定机器人 A 中各步骤的等待时间和后处理时间。我们有 r _{i, j} = Δ 且 ω _{i, jS} = Θ – (α _{i, j} + 2λ + ρ) – r _{i, j} 对于 ∈ A。接着，r _{i, j} = Δ = h/|V| ≤ Θ – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) ≤ Π _{i, jU} – (α _{i, j} + 2λ + ρ + ω _{i, jS} ) = δ _{i, j} 且 r _{i, j} > 0 因 ψ _{i, 2} < ε。由于 ${\sum }_{j\in V}{\omega }_{i,jS}$ = ${\sum }_{j\in V}($ Θ – (α _{i, j} + 2λ + ρ)) – ${\sum }_{j\in V}{r}_{i,j}$ = ψ _{i, 2} ，我们得出 ψ _{i, 2} 的值已赋给 ω _{i, jS} 的 ( ∈ V)，即 ${\sum }_{j\in V}{\omega }_{i,jS}$ 最大化且 ${\sum }_{j\in V}{r}_{i,j}$ 最小化。■

Algorithm 3 deals with the situation ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$[Π_{i, jL}, Π_{i, jU}] = $\varnothing$, i ∈ $N_K^{+}$, which implies that some steps have a heavier workload than other steps. Given the cycle time of Θ, the robot waiting time is pre-allocated in E and F. Then, check whether a cluster tool is schedulable or not in Line 5. After that, according to the workloads of a robot and processing steps, Lines 10–40 can assign post-processing time evenly which is also minimized. Notice that Condition ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$[Π_{i, jL}, Π_{i, jU}] = $\varnothing$ for Algorithm 3 indicates that the workloads of the processing steps are significantly unbalanced. That is to say, the processing steps in E are much faster than others and a feasible schedule can be obtained only by carefully setting the robot waiting time at different steps.
算法 3 处理了以下情况： ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$ [Π _{i, jL} , Π _{i, jU} ] = $\varnothing$ , ∈ $N_K^{+}$ ，这意味着某些步骤的工作负载比其他步骤更重。在给定周期时间Θ的情况下，机器人的等待时间在 E 和 F 中预先分配。然后，在第 5 行检查集群工具是否可调度。之后，根据机器人和工作步骤的工作负载，第 10-40 行可以均匀且最小化地分配后处理时间。注意，算法 3 的条件 ${\cap }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}$ [Π _{i, jL} , Π _{i, jU} ] = $\varnothing$ 表明处理步骤的工作负载显著不平衡。也就是说，E 中的处理步骤比其他步骤快得多，只有通过仔细设置不同步骤的机器人等待时间才能获得可行的调度。

In Algorithm 3, all the statements make the calculations based on closed-form expressions. The number of iterations in the For-loop of Lines 3 and 4 is no more than n[i]. The number of iterations in the For-loop of Lines 10−30 is no more than (n[i])². It is obvious that the computational complexity of Algorithm 3 is polynomial.
在算法 3 中，所有语句均基于封闭形式的表达式进行计算。第 3 行和第 4 行的 For 循环迭代次数不超过 n[]。第 10 至 30 行的 For 循环迭代次数不超过(n[]) ² 。显然，算法 3 的计算复杂度是多项式的。

C Post-Processing Time of Two Adjacent Cluster Tools
C 相邻簇工具的后处理时间

To keep a high quality of circuit chips on wafers, in real-world production, it is not recommended that the sum of post-processing time ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ in some cluster tools is longer than that in others and in particular, between two adjacent tools, the difference in ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ for them is too large. Consequently, it is necessary to adjust ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ for two adjacent cluster tools.
为保持晶圆上电路芯片的高质量，在实际生产中，不建议某些簇工具的后处理时间总和 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 超过其他工具，尤其在相邻两工具间，其 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 差异过大。因此，有必要调整相邻两簇工具的 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 。

By Algorithms 1−3, ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ for each tool C_i is minimized. Therefore, ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ cannot be reduced anymore. However, we can appropriately increase the sum of post-processing time of a cluster tool to reduce the difference between ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ and ${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$, i ∈ $N_{K-1}^{+}$.
通过算法 1−3，每个工具 C 的 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 被最小化。因此， ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 无法进一步减少。然而，我们可以适当增加簇工具的后处理时间总和，以缩小 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 与 ${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$ 之间的差异，其中∈ $N_{K-1}^{+}$ 。

Let Z_i = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ –${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$, i ∈ $N_{K-1}^{+}$, denote the difference in total post-processing time between two adjacent cluster tools. Table III determines the cluster tools whose ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$, i ∈ $N_K^{+}$, should be increased.
设 Z = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ – ${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$ ，∈ $N_{K-1}^{+}$ ，表示相邻两台簇工具之间总后处理时间的差异。表 III 确定了应增加其 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ ，∈ $N_K^{+}$ 的簇工具。

III

Table III   表三 Conditions for Adjusting Post-Processing Time in a Tool
调整工具后处理时间的条件

Zi–1 > 0	Zi > 0	Zi+1 > 0	Operation 操作
False 假	False 假	False 假	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
False 假	False 假	True 真	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
False 假	True 真	False 假	Unchanged 未改变
False 假	True 真	True 真	Unchanged 未改变
True 真	False 假	False 假	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
True 真	False 假	True 真	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
True 真	True 真	False 假	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
True 真	True 真	True 真	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
×	True 真	True 真	Unchanged 未改变
×	True 真	False 假	Unchanged 未改变
×	False 假	True 真	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
×	False 假	False 假	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
False 假	False 假	×	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
False 假	True 真	×	Unchanged 未改变
True 真	False 假	×	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
True 真	True 真	×	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$
False 假	×	×	Unchanged 未改变
True 真	×	×	Increase ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 增加 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$

Reducing the robot waiting time for an individual tool at some processing steps leads to an increase in its robot waiting time at LLs and BMs. As a result, its post-processing time is also increased. During such an adjustment for robot waiting time, (15)−(17) should be satisfied. It is known that Algorithms 2 and 3 determine the post-processing time r_{i, j}, which should now be adjusted. After r_{i, j} is adjusted, its new value is denoted by r′_{i, j}. Let υ_i = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$ – ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ be an increment in post-processing time. Let υ_i ∈ [0, γ_i], i ∈ $N_K^{+}$, where γ_i is the upper bound of υ_i. To find each minimum υ_i, i ∈ $N_K^{+}$, a linear programming model is given as follows.
在某些加工步骤中减少机器人对单个工具的等待时间，会导致其在 LLs 和 BMs 处的机器人等待时间增加，从而也延长了后续处理时间。在进行此类机器人等待时间调整时，需满足(15)−(17)条件。已知算法 2 和算法 3 决定了后续处理时间 r _{i, j} ，现需对其进行调整。调整后的 r _{i, j} 新值记为 r′ _{i, j} 。设υ = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$ – ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 为后续处理时间的增量，且υ ∈ [0, γ]，其中γ为υ的上限。为求得每个最小υ，建立如下线性规划模型。

Linear programming model (LPM):
线性规划模型 (LPM)

$\begin{array}{cc}& Maximize{\gamma }_i\\ & s.t.\\ & {\gamma }_i\le \sum _{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{\omega }_{i,jS},i\in N_K^{+}\end{array}$

${\gamma }_i\le {\tau }_{(i+1),0}-(2{\lambda }_i+{\rho }_i+{{\omega }_i}_{,b\left[i\right]S}),i=1$

$\begin{array}{cc}& {\gamma }_i\le ({\tau }_{(i-1),b\left[i\right]}-(2{\lambda }_i+{\rho }_i+{{\omega }_i}_{,0S}\left)\right)\\ & +({\tau }_{(i+1),0}-(2{\lambda }_i+{\rho }_i+{{\omega }_i}_{,b\left[i\right]S}\left)\right)\\ & 2\le i\le K-1\end{array}$

${\gamma }_i\le ({\tau }_{(i-1),b\left[i\right]}-(2{\lambda }_i+{\rho }_i+{{\omega }_i}_{,0S}\left)\right),i=K$

${\gamma }_i\le \left|Z_i\right|,i=1$

${\gamma }_i\le \left|Z_i\right|,2\le i\le K-1$

${\gamma }_i\le \left|{Z_i}_{-1}\right|,2\le i\le K-1$

${\gamma }_i\le \left|{Z_i}_{-1}\right|,i=K$

$0\le {\gamma }_i,0\le i\le K.$

The above LPM can get the maximum γ_i. In LPM, (18) indicates that there should be enough robot idle time at the processing steps to be moved to be a part of r_{i, j}. Inequalities in (18) make sure that a part of robot idle time can be moved from ω_{i, jS}’s (j ∈N_n[i]\{0, b[i]}) to ω_{i, j}’s (j ∈ {0, b[i]}).
上述 LPM 可获得最大γ。在 LPM 中，(18)表明在处理步骤中应有足够的机器人空闲时间，以便移动成为 r _{i, j} 的一部分。(18)中的不等式确保了机器人空闲时间的一部分可以从ω _{i, jS} （∈N _n[i] \{0, b[]}）移动到ω _{i, j} （∈{0, b[]}）。

Inequalities (19)−(21) indicate that the increased post-processing time should satisfy (16) and (17). By (17), we have τ_{(i+1), 0}≥ 2λ_i + ρ_i + ω_{i, b[i]S}. While adjusting the waiting time of R₁, we need to make (17) hold, leading to that τ_2,0≥ (2λ₁ + ρ₁ + ω_{1, b[1]S}) holds. Note that λ₁ and ρ₁ are constant, and τ_2,0 is unchanged when a schedule is given by Algorithm 1. Let χ denote the increment in ω_{1, b[1]S}. Then, we have τ_2,0≥ (2λ₁ + ρ₁ + ω_{1, b[1]S} + χ). Thus, τ_2,0 − (2λ₁ + ρ₁+ω_{1, b[1]S}) ≥ χ = γ₁. Similarly, we can get (21) for C_K.
不等式(19)−(21)表明，增加的后处理时间应满足(16)和(17)。根据(17)，我们有τ _{(i+1), 0} ≥ 2λ + ρ + ω _{i, b[i]S} 。在调整 R ₁ 的等待时间时，需确保(17)成立，从而得出τ _2,0 ≥ (2λ ₁ + ρ ₁ + ω _{1, b[1]S} )。注意，λ ₁ 和ρ ₁ 是常数，且当调度由算法 1 给出时，τ _2,0 保持不变。设χ表示ω _{1, b[1]S} 的增量。于是，我们有τ _2,0 ≥ (2λ ₁ + ρ ₁ + ω _{1, b[1]S} + χ)。因此，τ _2,0 − (2λ ₁ + ρ ₁ + ω _{1, b[1]S} ) ≥ χ = γ ₁ 。类似地，我们可以得到 C _K 的(21)。

While adjusting the waiting time of R_i, 2 ≤ i ≤ K – 1, we should make (16) and (17) hold for the adjacent cluster tools. Thus, τ_{(i – 1), b[i]}≥ (2λ_i + ρ_i + ω_{i, 0S}) and τ_{(i + 1), 0}≥ (2λ_i + ρ_i + ω_{i, b[i]S}) hold. λ_i and ρ_i are constants, and τ_{(i–1), b[i]} and τ_{(i+1), 0} are unchanged when a schedule is given by Algorithm 1. Let χ₁ and χ₂ denote the increments in ω_{i, 0S} and ω_{i, b[i]S}, respectively. Then, we have τ_{(i – 1), b[i]}≥ (2λ_i + ρ_i + ω_{i, 0S}+χ₁) and τ_{(i+1), 0}≥ (2λ_i + ρ_i + ω_{i, b[i]S} + χ₂). Thus, (τ_{(i – 1), b[i]} – (2λ_i + ρ_i + ω_{i, 0S})) + (τ_{(i + 1), 0} – (2λ_i + ρ_i + ω_{i, b[i]S})) ≥ χ₁ + χ₂ = γ_i.
在调整 R 的等待时间时，2 ≤ ≤ K – 1，我们应确保相邻簇工具满足(16)和(17)式。因此，τ _{(i – 1), b[i]} ≥ (2λ + ρ + ω _{i, 0S} ) 和 τ _{(i + 1), 0} ≥ (2λ + ρ + ω _{i, b[i]S} ) 成立。λ 和 ρ 为常数，且当算法 1 给定调度时，τ _{(i–1), b[i]} 和 τ _{(i+1), 0} 保持不变。令 χ ₁ 和 χ ₂ 分别表示 ω _{i, 0S} 和 ω _{i, b[i]S} 的增量。于是，我们有 τ _{(i – 1), b[i]} ≥ (2λ + ρ + ω _{i, 0S} + χ ₁ ) 和 τ _{(i+1), 0} ≥ (2λ + ρ + ω _{i, b[i]S} + χ ₂ )。因此，(τ _{(i – 1), b[i]} – (2λ + ρ + ω _{i, 0S} )) + (τ _{(i + 1), 0} – (2λ + ρ + ω _{i, b[i]S} )) ≥ χ ₁ + χ ₂ = γ。

Inequalities (22)−(25) mean that the increased post-processing time cannot exceed the difference between the adjacent cluster tools. Obviously, the increased post-processing time should satisfy (26) and an efficient adjustment on post-processing time ranges from 0 to γ_i. After γ_i is determined by LPM, the increment in post-processing time υ_i ∈ [0, γ_i] can be given according to a real-world production scenario.
不等式(22)−(25)意味着增加的后处理时间不能超过相邻簇工具之间的差异。显然，增加的后处理时间应满足(26)，且高效调整的后处理时间范围在 0 到γ之间。在 LPM 确定γ后，根据实际生产场景，后处理时间的增量υ ∈ [0, γ]即可给出。

Algorithm 4. Adjusting Post-Processing Time for C
算法 4. 调整 C 的后处理时间_i

Input: υ 输入：υ_i

Output: ω_{i, j}, ω_{i, jS}, r_{i, j}
输出: ω _{i, j} , ω _{i, jS} , r _{i, j}

1: 　V← N_n[i] \ {0, b[i]}, M← $\varnothing$

2: 　Forj ∈Vdo 2: 对于 ∈V 执行

3: 　　If Π_{i, jU} < Θ ThenM←M$\cup${j}
3: 若 Π _{i, jU} < Θ 则 M←M $\cup$ {}

4: 　　EndIf 4: 结束如果

5: 　EndFor 5: 结束循环

6: 　ω_{i, j}←ω_{i, j} +υ_i /|V| for j ∈V
6: ω _{i, j} ←ω _{i, j} +υ /|V| 对于 ∈V

7: 　WhileV ≠ $\varnothing$Then
7: 当 V ≠ $\varnothing$ 时

8: 　　Δ←υ_i /|V|, A← $\varnothing$, B← $\varnothing$

9: 　　Forj ∈ Vdo 9: 对于 ∈ V 执行

10:　　　Ifj ∈ MThen 10: 如果 ∈ M 那么

11:　　　　If Δ ≤ Π_{i, jU} – Π_{i, jL} – r_{i, j}thenA←A$\cup${j}
11: 若 Δ ≤ Π _{i, jU} – Π _{i, jL} – r _{i, j} ，则 A ← A $\cup$ {}

12:　　　　ElseB ←B$\cup${j}

13:　　　　EndIf 13: 结束判断

14:　　　Else 14: 其他

15:　　　　If Δ ≤ ω_{i, jS}thenA←A$\cup${j}
15: 若 Δ ≤ ω _{i, jS} ，则 A←A $\cup$ {}

16:　　　　ElseB ←B$\cup${j}

17:　　　　EndIf 17: 结束如果

18:　　　EndIf 18: 结束判断

19:　　EndFor 19: 结束循环

20:　　IfB ≠ $\varnothing$Then
20: 如果 B ≠ $\varnothing$ 那么

21:　　For each j ∈ Bdo
21: 对于每个 ∈ B 执行

22:　　　Ifj ∈ MThen 22: 如果 ∈ M，则

23:　　　　υ_i←υ_i–(Π_{i, jU}–Π_{i, jL}–r_{i, j}), r_{i, j}←Π_{i, jU}–Π_{i, jL}, ω_{i, jS} ←Θ–Π_{i, jU}

24:　　　Else 24: 其他

25:　　　　υ_i←υ_i–ω_{i, jS}, r_{i, j}←Θ–Π_{i, jL}, ω_{i, jS} ← 0

26:　　　EndIf 26: 结束判断

27:　　EndFor 27: 结束循环

28:　　V←V\B

29:　　Else 29: 否则

30:　　For each j ∈ Ado
30: 对于每个 ∈ Ado

31:　　　r_{i, j} ←Δ + r_{i, j}, ω_{i, jS} ←Θ – (α_{i, j} + 2λ_i + ρ_i) – r_{i, j}

32:　　EndFor 32: 结束循环

33:　　V←$\varnothing$

34:　　EndIf 34: 结束判断

35:　EndWhile 35: 结束循环

36:　End 36：结束

Table III determines a set of tools, denoted by C_A in which post-processing time should be adjusted. LPM gives the adjusted value υ_i for the post-processing time in C_i ∈ C_A. Then, Algorithm 4 calculates the post-processing time adjustment for C_i ∈ C_A$.$
表 III 确定了一组工具，记为 C_A，其中后处理时间应进行调整。LPM 给出了 C ∈ C_A 中后处理时间的调整值υ。然后，算法 4 计算 C ∈ C_A 的后处理时间调整。

Theorem 3: For ∀υ_i ∈ [0, γ_i], Algorithm 4 can find an efficient schedule, which balances the post-processing time between a pair of adjacent cluster tools.
定理 3：对于∀υ ∈ [0, γ]，算法 4 能够找到一个有效的调度方案，该方案能平衡一对相邻簇工具之间的后处理时间。

Proof: By Table III, we determine the robots’ waiting time that should be adjusted. By LPM, we find the maximum value γ_i that is set for a certain cluster tool. υ_i ranges from 0 to γ_i, and obviously a schedule can still be obtained. Then, when we balance the post-processing time of adjacent tools, we ensure that the difference in post-processing time at each processing step in the cluster tool remains unchanged.
证明：根据表 III，我们确定了需要调整的机器人等待时间。通过 LPM，我们找到了为某个簇工具设定的最大值γ。υ的范围从 0 到γ，显然仍可获得一个调度。然后，在平衡相邻工具的后处理时间时，我们确保簇工具中每个加工步骤的后处理时间差保持不变。

By Lines 1 and 3 of Algorithm 4, we have V = {j | j ≠ 0 and j ≠ b[i], j ∈ N_n[i]} and M = {j | Π_{i, jU} <Θ, j ∈ V}. For j ∈ V, we set ω_{i, j} = ω_{i, j} + υ_i/|V| in Line 6. Then, Lines 7−35 present the specific adjustment operations for each processing module. By Lines 8, 23 and 31, Δ = υ_i/|V| means that the post-processing time at a processing step is increased.
根据算法 4 的第 1 行和第 3 行，我们有 V = { | ≠ 0 且≠ b[]，∈ N _n[i] } 和 M = { | Π _{i, jU} <Θ，∈ V}。对于∈ V，我们在第 6 行设置 ω _{i, j} = ω _{i, j} + υ/|V|。接着，第 7−35 行展示了每个处理模块的具体调整操作。根据第 8、23 和 31 行，Δ = υ/|V| 意味着处理步骤的后处理时间增加。

For j ∈ V, when j ∈ M, if Step j satisfies Δ ≤ Π_{i, jU} – Π_{i, jL} – r_{i, j}, it is put into set A, otherwise, it is put into set B. Lines 15 and 16 indicate that when j ∈ V \ M, if Step j satisfies Δ ≤ ω_{i, jS}, it is put into set A, otherwise, it is put into set B. If B ≠ $\varnothing$, Lines 20−28 present the adjustment of post-processing time for step j ∈ B as follows:
对于∈ V，当∈ M 时，若步骤满足Δ ≤ Π _{i, jU} – Π _{i, jL} – r _{i, j} ，则将其放入集合 A，否则放入集合 B。第 15 和 16 行表明，当∈ V \ M 时，若步骤满足Δ ≤ ω _{i, jS} ，则将其放入集合 A，否则放入集合 B。若 B ≠ $\varnothing$ ，第 20−28 行给出了对步骤∈ B 的后处理时间调整如下：

1) If j ∈ M, we have υ_i = υ_i – (Π_{i, jU} – Π_{i, jL} – r_{i, j}), r_{i, j} = Π_{i, jU} – Π_{i, jL}, and ω_{i, jS} = Θ – Π_{i, jU}, and
1) 若 ∈ M，则有 υ = υ – (Π _{i, jU} – Π _{i, jL} – r _{i, j} )，r _{i, j} = Π _{i, jU} – Π _{i, jL} ，且 ω _{i, jS} = Θ – Π _{i, jU} ，

2) if j ∈ B \ M, we have υ_i = υ_i – ω_{i, jS}, r_{i, j} = Θ – Π_{i, jL}, ω_{i, jS} = 0. Lines 30−33 present the adjustment of post-processing time for step j ∈ A, i.e., when B = $\varnothing$, we have r_{i, j} = Δ + r_{i, j}, ω_{i, jS} = Θ – (α_{i, j} + 2λ_i + ρ_i) – r_{i, j}.
2) 若 ∈ B \ M，则有 υ = υ – ω _{i, jS} , r _{i, j} = Θ – Π _{i, jL} , ω _{i, jS} = 0。第 30 至 33 行展示了针对步骤 ∈ A 的后处理时间的调整，即当 B = $\varnothing$ 时，有 r _{i, j} = Δ + r _{i, j} , ω _{i, jS} = Θ – (α _{i, j} + 2λ + ρ) – r _{i, j} 。

So far, we have carried out the adjustment of post-processing time for tool C_i. The wafer post-processing time in C_i increases so that |Z_i–1| and |Z_i| become smaller. Z_i = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ – ${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$, i ∈ $N_{K-1}^{+}$, means the difference in post-processing time between two adjacent cluster tools. The smaller the value of |Z_i| is, the smaller the post-processing time difference between two adjacent cluster tools becomes. Thus, the wafer post-processing time in adjacent cluster tools is balanced as well as possible.■
到目前为止，我们已经对工具 C 的后处理时间进行了调整。C 中的晶圆后处理时间增加，使得|Z _i–1 |和|Z|变小。Z = ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ – ${\sum }_{j\in N_{n\left[i+1\right]}^{+}\setminus \left\{b\right[i+1\left]\right\}}{r}_{i+1,j}$ , ∈ $N_{K-1}^{+}$ , 表示两个相邻集群工具之间后处理时间的差异。|Z|的值越小，两个相邻集群工具之间的后处理时间差异就越小。因此，相邻集群工具中的晶圆后处理时间尽可能地得到了平衡。■

Algorithm 4 makes calculations based on closed-form expressions. The number of iterations in the For-loop of Lines 2−5 and Line 6 is no more than n[i]. The number of iterations in the For-loop of Lines 7−35 is no more than (n[i])². Thus, the computational complexity of Algorithm 4 is polynomial.
算法 4 基于封闭形式的表达式进行计算。第 2−5 行和第 6 行的 For 循环的迭代次数不超过 n[]。第 7−35 行的 For 循环的迭代次数不超过(n[]) ² 。因此，算法 4 的计算复杂度是多项式的。

D Algorithm Analysis D 算法分析

Algorithm 1 decides whether a K-cluster tool is schedulable; if so, then Algorithm 1 checks the case that each tool belongs to, and calls Algorithms 2 or 3 to calculate the robot waiting time. By doing so, a schedule can be found to reach the optimal cycle time of a K-cluster tool and minimize the total post-processing time. Upon such an initial schedule solution, Table III determines the robot waiting time to be adjusted for cluster tools. LPM, Table III, and Algorithm 4 can well balance the post-processing time difference between adjacent cluster tools.
算法 1 用于判定一个 K 集群工具是否可调度；若可调度，则算法 1 进一步判断各工具所属情况，并调用算法 2 或算法 3 计算机器人等待时间。通过此过程，可找到实现 K 集群工具最佳周期时间并最小化总后处理时间的调度方案。基于此初始调度方案，表 III 确定了需调整的集群工具机器人等待时间。LPM、表 III 及算法 4 能有效平衡相邻集群工具间的后处理时间差异。

As aforementioned, the computational complexity of Algorithms 2–4 is O((n[i])²). Let e = ${max}_{i\in N_K^{+}}n\left[i\right]$. Then, by the “For loop” in Lines 4–19 of Algorithm 1, the number of calculations for ω_{i, jS} and ω_{i, j} depends on the total number of processing modules in a K-cluster tool, which is no more than ${\sum }_{i=1}^K{e}^2$ = e² × K. Notice that e is a small constant and is no more than six. Overall, the computational complexity of Algorithms 1−4 is polynomial.
如前所述，算法 2 至 4 的计算复杂度为 O((n[]) ² )。设 e = ${max}_{i\in N_K^{+}}n\left[i\right]$ 。然后，根据算法 1 中第 4 至 19 行的“For 循环”，ω _{i, jS} 和 ω _{i, j} 的计算次数取决于 K 簇工具中处理模块的总数，该总数不超过 ${\sum }_{i=1}^K{e}^2$ = e ² × K。注意，e 是一个小常数，且不超过六。总体而言，算法 1 至 4 的计算复杂度是多项式的。

IV Examples  IV 示例

Example 1: In a four-cluster tool, PM_1,0 is LLs. PM_1,0, PM_2,0, PM_3,0, PM_4,0, PM_1,2, PM_2,2, and PM_3,2 are BMs. The time unit is second and omitted hereafter. For C₁, we have (α_1,0, α_1,1, α_1,2, α_1,3, α_1,4; λ₁, μ₁, ρ₁) = (0, 47, 0, 50, 52; 2, 2, 2); for C₂, we have (α_2,0, α_2,1, α_2,2, α_2,3, α_2,4; λ₂, μ₂, ρ₂) = (0, 38, 0, 37, 53; 2, 2, 2); for C₃, we have (α_3,0, α_3,1, α_3,2, α_3,3, α_3,4; λ₃, μ₃, ρ₃) = (0, 57, 0, 56, 38; 2, 2, 2); and for C₄ we have (α_4,0, α_4,1, α_4,2, α_4,3, α_4,4; λ₄, μ₄, ρ₄) = (0, 54, 49,44, 34; 2, 2, 2). The wafer processing route is LLs→ PM_1,0 → PM_1,1 → PM_1,2 (PM_2,0) → PM_2,1 → PM_2,2 (PM_3,0) → PM_3,1 → PM_3,2 (PM_4,0) → PM_4,1 → PM_4,2 → PM_4,3 → PM_4,4→ PM_4,0 (PM_3,2) → PM_3,3 → PM_3,4 → PM_3,0 (PM_2,2) → PM_2,3 → PM_2,4 → PM_2,0 (PM_1,2) → PM_1,3 → PM_1,4 → LLs. After being processed, a wafer can stay at PM_{i, j} for no more than δ_1,1 = 20, δ_1,3 = 20, δ_1,4 = 20, δ_2,1 = 20, δ_2,3 = 20, δ_2,4 = 20, δ_3,1 = 20, δ_3,3 =20, δ_3,4 = 16, δ_4,1 = 20, δ_4,2 = 20, δ_4,3 =10, and δ_4,4 = 13, respectively. There are no residency time constraints at LLs and BMs.
示例 1：在一个四簇工具中，PM _1,0 是 LLs。PM _1,0 、PM _2,0 、PM _3,0 、PM _4,0 、PM _1,2 、PM _2,2 和 PM _3,2 是 BMs。时间单位为秒，此后省略。对于 C ₁ ，我们有 (α _1,0 , α _1,1 , α _1,2 , α _1,3 , α _1,4 ; λ ₁ , μ ₁ , ρ ₁ ) = (0, 47, 0, 50, 52; 2, 2, 2)；对于 C ₂ ，我们有 (α _2,0 , α _2,1 , α _2,2 , α _2,3 , α _2,4 ; λ ₂ , μ ₂ , ρ ₂ ) = (0, 38, 0, 37, 53; 2, 2, 2)；对于 C ₃ ，我们有 (α _3,0 , α _3,1 , α _3,2 , α _3,3 , α _3,4 ; λ ₃ , μ ₃ , ρ ₃ ) = (0, 57, 0, 56, 38; 2, 2, 2)；对于 C ₄ ，我们有 (α _4,0 , α _4,1 , α _4,2 , α _4,3 , α _4,4 ; λ ₄ , μ ₄ , ρ ₄ ) = (0, 54, 49, 44, 34; 2, 2, 2)。晶圆加工路线为 LLs→ PM _1,0 → PM _1,1 → PM _1,2 (PM _2,0 ) → PM _2,1 → PM _2,2 (PM _3,0 ) → PM _3,1 → PM _3,2 (PM _4,0 ) → PM _4,1 → PM _4,2 → PM _4,3 → PM _4,4 → PM _4,0 (PM _3,2 ) → PM _3,3 → PM _3,4 → PM _3,0 (PM _2,2 ) → PM _2,3 → PM _2,4 → PM _2,0 (PM _1,2 ) → PM _1,3 → PM _1,4 → LLs。 经过处理后，晶圆在 PM _{i, j} 的停留时间分别不得超过 δ _1,1 = 20, δ _1,3 = 20, δ _1,4 = 20, δ _2,1 = 20, δ _2,3 = 20, δ _2,4 = 20, δ _3,1 = 20, δ _3,3 = 20, δ _3,4 = 16, δ _4,1 = 20, δ _4,2 = 20, δ _4,3 = 10, 和 δ _4,4 = 13。在 LLs 和 BMs 处没有停留时间限制。

By (4), (10) and (12), the cycle time of this four-cluster tool is Θ = 63. By Algorithm 1, we have
根据(4)、(10)和(12)，该四簇工具的循环时间为Θ = 63。通过算法 1，我们得到

1) For C₁, ψ_1,1 ≤ Θ and Θ ≤ Π_{1, jU}, j ∈ $N_{n\left[1\right]}^{+}$\{b[1]}, are satisfied and Algorithm 2 is applied;
1) 对于 C ₁ ，满足 ψ _1,1 ≤ Θ 且 Θ ≤ Π _{1, jU} ，∈ $N_{n\left[1\right]}^{+}$ \{b[1]}，并应用算法 2；

2) For C₂, ψ_2,1 ≤ Θ and Θ ≤ Π_{2, jU}, j ∈$N_{n\left[2\right]}^{+}$\{b[2]}, are satisfied and Algorithm 2 is also applied;
2) 对于 C ₂ ，满足 ψ _2,1 ≤ Θ 且 Θ ≤ Π _{2, jU} ，∈ $N_{n\left[2\right]}^{+}$ \{b[2]}，并且也应用了算法 2；

3) For C₃, [Π_3,1L, Π_3,1U] ∩ [Π_3,3L, Π_3,3U] ∩ [Π_3,4L, Π_3,4U] = $\varnothing$ is satisfied and Algorithm 3 is applied; and
3) 对于 C ₃ ，满足 [Π _3,1L , Π _3,1U ] ∩ [Π _3,3L , Π _3,3U ] ∩ [Π _3,4L , Π _3,4U ] = $\varnothing$ ，并应用算法 3；且

4) For C₄, [Π_4,1L, Π_4,1U] ∩ [Π_4,2L, Π_4,2U] ∩ [Π_4,3L, Π_4,3U] ∩ [Π_4,4L, Π_4,4U] = $\varnothing$ is satisfied and Algorithm 3 is applied.
4) 对于 C ₄ ，满足 [Π _4,1L , Π _4,1U ] ∩ [Π _4,2L , Π _4,2U ] ∩ [Π _4,3L , Π _4,3U ] ∩ [Π _4,4L , Π _4,4U ] = $\varnothing$ ，并应用算法 3。

For C₁, by Algorithm 2, ε = 22 satisfies ε < ψ_{i, 2} = 25. Then, we have (ω_1,0S, ω_1,1S, ω_1,2S, ω_1,3S, ω_1,4S) = (0, 10, 0, 7, 5), (ω_1,0, ω_1,1, ω_1,2, ω_1,3, ω_1,4) = (0, 1, 0, 1, 1), and (r_1,1, r_1,3, r_1,4) = (0, 0, 0).
对于 C ₁ ，根据算法 2，ε = 22 满足 ε < ψ _{i, 2} = 25。于是，我们有 (ω _1,0S , ω _1,1S , ω _1,2S , ω _1,3S , ω _1,4S ) = (0, 10, 0, 7, 5), (ω _1,0 , ω _1,1 , ω _1,2 , ω _1,3 , ω _1,4 ) = (0, 1, 0, 1, 1)，以及 (r _1,1 , r _1,3 , r _1,4 ) = (0, 0, 0)。

For C₂, by Algorithm 2, ε = 43 satisfies ψ_{i, 2} = 23 < ε. Obviously, by Δ and Θ – (α_{2, j} +2λ₂ + 3ρ₂) for j ∈ {1, 3, 4} we have A = {1, 3} and B = {4}. Let r_2,4 = Θ – (α_2,4 +3λ₂ + ρ₂). Then, V = V\B, we have (ω_2,0S, ω_2,1S, ω_2,2S, ω_2,3S, ω_2,4S) = (0, 11, 0, 12, 0), (ω_2,0, ω_2,1, ω_2,2, ω_2,3, ω_2,4) = (0, 0, 0, 0, 0), and (r_2,1, r_2,3, r_2,4) = (8, 8, 4).
对于 C ₂ ，根据算法 2，ε = 43 满足 ψ _{i, 2} = 23 < ε。显然，通过 Δ 和 Θ – (α _{2, j} +2λ ₂ + 3ρ ₂ ) 对于 ∈ {1, 3, 4}，我们有 A = {1, 3} 和 B = {4}。设 r _2,4 = Θ – (α _2,4 +3λ ₂ + ρ ₂ )。然后，V = V\B，我们有 (ω _2,0S , ω _2,1S , ω _2,2S , ω _2,3S , ω _2,4S ) = (0, 11, 0, 12, 0), (ω _2,0 , ω _2,1 , ω _2,2 , ω _2,3 , ω _2,4 ) = (0, 0, 0, 0, 0)，以及 (r _2,1 , r _2,3 , r _2,4 ) = (8, 8, 4)。

For C₃, by Algorithm 3, E = {4} and F = {1, 3}, and V = {1, 3, 4}. By Lines 3 and 4, the waiting time can be set as (ω_3,1S, ω_3,3S, ω_3,4S) = (0, 0, 3). Then, we have ε = 20 > η = 17. Thus, we have (ω_3,0S, ω_3,1S, ω_3,2S, ω_3,3S, ω_3,4S) = (0, 0, 0, 1, 19), (ω_3,0, ω_3,1, ω_3,2, ω_3,3, ω_3,4) = (0, 1, 0, 1, 1), and (r_3,1, r_3,3, r_3,4) = (0, 0, 0).
对于 C ₃ ，根据算法 3，E = {4} 且 F = {1, 3}，V = {1, 3, 4}。根据第 3 和第 4 行，等待时间可设为 (ω _3,1S , ω _3,3S , ω _3,4S ) = (0, 0, 3)。于是，我们有 ε = 20 > η = 17。因此，得到 (ω _3,0S , ω _3,1S , ω _3,2S , ω _3,3S , ω _3,4S ) = (0, 0, 0, 1, 19)，(ω _3,0 , ω _3,1 , ω _3,2 , ω _3,3 , ω _3,4 ) = (0, 1, 0, 1, 1)，以及 (r _3,1 , r _3,3 , r _3,4 ) = (0, 0, 0)。

For C₄, by Algorithm 3, E = {3, 4} and F = {1, 2}, and V = {1, 2, 3, 4}. By Lines 3 and 4, the waiting time can be set as (ω_4,1S, ω_4,2S, ω_4,3S, ω_4,4S) = (0, 0, 3, 10). Then, we have ε = 10 < η = 34. Obviously, by Δ and Θ – (α_{4, j} + 2λ₄ + ρ₄) for j ∈ {1, 2, 3, 4}, we have A = {2, 3, 4} and B = {1}. Let r_{4, j} = Θ – (α_{4, j} +4λ₄ + ρ₄) for j ∈ B. Then, V = V\B, we have (ω_4,0S, ω_4,1S, ω_4,2S, ω_4,3S, ω_4,4S) = (0, 0, 1, 6, 16), (ω_4,0, ω_4,1, ω_4,2, ω_4,3, ω_4,4) = (0, 0, 0, 0, 0), and (r_4,1, r_4,2, r_4,3, r_4,4) = (3, 7, 7, 7).
对于 C ₄ ，通过算法 3，E = {3, 4} 且 F = {1, 2}，V = {1, 2, 3, 4}。根据第 3 和第 4 行，等待时间可设为 (ω _4,1S , ω _4,2S , ω _4,3S , ω _4,4S ) = (0, 0, 3, 10)。于是，我们有 ε = 10 < η = 34。显然，通过 Δ 和 Θ – (α _{4, j} + 2λ ₄ + ρ ₄ ) 对于 ∈ {1, 2, 3, 4}，我们得到 A = {2, 3, 4} 和 B = {1}。令 r _{4, j} = Θ – (α _{4, j} + 4λ ₄ + ρ ₄ ) 对于 ∈ B。然后，V = V\B，我们得到 (ω _4,0S , ω _4,1S , ω _4,2S , ω _4,3S , ω _4,4S ) = (0, 0, 1, 6, 16)，(ω _4,0 , ω _4,1 , ω _4,2 , ω _4,3 , ω _4,4 ) = (0, 0, 0, 0, 0)，以及 (r _4,1 , r _4,2 , r _4,3 , r _4,4 ) = (3, 7, 7, 7)。

By Table II, we know that the post-processing time should be adjusted for C₁ and C₃. By LPM, we have γ₁ = 20 and γ₃ = 20. Then, we have υ₁ ∈ [0, 20] and υ₃ ∈ [0, 20]. Assume that the post-processing time difference between adjacent tools of this multi-cluster tool cannot exceed 16. Then, we let υ₁ = 6 and υ₃ = 6. By Algorithm 4, (ω_{1, 0S}, ω_{1, 1S}, ω_{1, 2S}, ω_{1, 3S}, ω_{1, 4S}) = (0, 8, 0, 5, 3), (ω_1,0, ω_2,1, ω_2,2, ω_2,3, ω_2,4) = (0, 3,0, 3, 3), (r_1,1, r_1,3, r_1,4) = (2, 2, 2), (ω_3,0S, ω_3,1S, ω_3,2S, ω_3,3S, ω_3,4S) = (0, 0, 0, 0, 14), (ω_3,0, ω_3,1, ω_3,2, ω_3,3, ω_3,4) = (0, 3,0, 3, 3), and (r_3,1, r_3,3, r_3,4) = (2, 2, 2). It can be found that τ_{i, j} ∈ [α_{i, j}, α_{i, j} + δ_{i, j}], i ∈ $N_K^{+}$ holds.
根据表 II，我们知道需要调整 C ₁ 和 C ₃ 的后处理时间。通过 LPM，我们得到γ ₁ = 20 和γ ₃ = 20。于是，我们有υ ₁ ∈ [0, 20]和υ ₃ ∈ [0, 20]。假设此多集群工具相邻工具之间的后处理时间差不能超过 16。然后，我们设υ ₁ = 6 和υ ₃ = 6。根据算法 4，(ω _{1, 0S} , ω _{1, 1S} , ω _{1, 2S} , ω _{1, 3S} , ω _{1, 4S} ) = (0, 8, 0, 5, 3), (ω _1,0 , ω _2,1 , ω _2,2 , ω _2,3 , ω _2,4 ) = (0, 3, 0, 3, 3), (r _1,1 , r _1,3 , r _1,4 ) = (2, 2, 2), (ω _3,0S , ω _3,1S , ω _3,2S , ω _3,3S , ω _3,4S ) = (0, 0, 0, 0, 14), (ω _3,0 , ω _3,1 , ω _3,2 , ω _3,3 , ω _3,4 ) = (0, 3, 0, 3, 3), 以及 (r _3,1 , r _3,3 , r _3,4 ) = (2, 2, 2)。可以发现，τ _{i, j} ∈ [α _{i, j} , α _{i, j} + δ _{i, j} ], ∈ $N_K^{+}$ 成立。

After the post-processing time is adjusted, the Gantt chart for this schedule is shown in Fig. 2. The horizontal axis represents time and each horizontal lane marks the activities performed at a PM, which is drawn in different colors. Vertical axis represents different PMs. In each horizontal lane of a PM, let yellow stand for a wafer being processed, blue for a robot’s moving, red for a wafer that is waiting to be unloaded after its processing, green for a robot’s unloading a processed wafer, brown for a robot’s rotation, a white bar for a PM being idle, and dark blue for a robot’s loading a wafer.
调整后处理时间后，该计划的甘特图如图 2 所示。横轴表示时间，每个水平轨道标记在PM执行的活动，以不同颜色绘制。纵轴代表不同的 PMs。在每个PM的水平轨道中，黄色表示晶圆正在处理，蓝色表示机器人移动，红色表示处理后等待卸载的晶圆，绿色表示机器人卸载已处理晶圆，棕色表示机器人旋转，白色条表示PM空闲，深蓝色表示机器人加载晶圆。

View

Download

 查看下载

Figure 2 图 2

Gantt chart for the schedule in Example 1 (a four-cluster tool)
示例 1 中进度计划的甘特图（四簇工具）

Fig. 2 shows that the post-processing time marked with red is short and the differences among the post-processing time marked by red bars are small. In Fig. 2, we use arrows to illustrate the operation routes of robots.
图 2 显示，红色标记的后处理时间较短，且红色条形标记的后处理时间差异较小。在图 2 中，我们使用箭头来说明机器人的操作路径。

The algorithms in [24] give a schedule by setting the following robot waiting time:
[24]中的算法通过设定以下机器人等待时间来给出调度方案：

(ω′_1,0S, ω′_1,1S, ω′_1,2S, ω′_1,3S, ω′_1,4S) = (0, 0, 0, 0, 0)

(ω′_1,0, ω′_1,1, ω′_1,2, ω′_1,3, ω′_1,4) = (0, 0, 0, 0, 25)

(r′_1,1, r′_1,3, r′_1,4) = (10, 7, 5)

(ω′_2,0S, ω′_2,1S, ω′_2,2S, ω′_2,3S, ω′_2,4S) = (0, 0, 0, 0, 0)

(ω′_2,0, ω′_2,1, ω′_2,2, ω′_2,3, ω′_2,4) = (0, 0, 0, 0, 23)

(r′_2,1, r′_2,3, r′_2,4) = (19, 20, 4)

(ω′_3,0S, ω′_3,1S, ω′_3,2S, ω′_3,3S, ω′_3,4S) = (0, 0, 0, 0, 3)

(ω′_3,0, ω′_3,1, ω′_3,2, ω′_3,3, ω′_3,4) = (0, 0, 0, 0, 20)

(r′_3,1, r′_3,3, r′_3,4) = (0, 1, 16)

(ω′_4,0S, ω′_4,1S, ω′_4,2S, ω′_4,3S, ω′_4,4S) = (0, 0, 0, 3, 10)

(ω′_4,0, ω′_4,1, ω′_4,2, ω′_4,3, ω′_4,4) = (0, 0, 0, 0, 10)

(r′_4,1, r′_4,2, r′_4,3, r′_4,4) = (3, 8, 10, 13).
(r′ _4,1 , r′ _4,2 , r′ _4,3 , r′ _4,4 ) = (3, 8, 10, 13)。

Let r_{i, jmax} and r_{i, jmin} denote the maximum r_{i, j} and minimum r_{i, j} in C_i, respectively. Obviously, we can get
设 r _{i, jmax} 和 r _{i, jmin} 分别表示 C 中的最大值 r _{i, j} 和最小值 r _{i, j} 。显然，我们可以得到

${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ < ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$, i ∈ $N_4^{+}$, and ${\sum }_{i=1}^4{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ = 56, ${\sum }_{i=1}^4{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{{}^{\prime }}$ = 116. Thus, the total post-processing time of this four-cluster tool is decreased by 51.7%. Furthermore, we have the following results.
${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ < ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$ ，∈ $N_4^{+}$ ，且 ${\sum }_{i=1}^4{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ = 56， ${\sum }_{i=1}^4{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{{}^{\prime }}$ = 116。因此，该四集群工具的后处理时间减少了 51.7%。此外，我们得到以下结果。

1) |r_{i, jmax} − r_{i, fmin}| < |r′_{i, jmax}− r′_{i, fmin}|, i ∈ $N_4^{+}$, j ≠ f, $\{j,f\}\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}$; and
1) |r _{i, jmax} − r _{i, fmin} | < |r′ _{i, jmax} − r′ _{i, fmin} |, ∈ $N_4^{+}$ , ≠ f, $\{j,f\}\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}$ ; 且

2) |Z_i| < |Z′_i|, i ∈ $N_4^{+}$.

Example 2: In a two-cluster tool, PM_1,0 is LLs. PM_2,0, and PM_1,2 are BMs. The time unit is second and omitted hereafter. For C₁, we have (α_1,0, α_1,1, α_1,2, α_1,3, α_1,4; λ₁, μ₁, ρ₁) = (0, 22, 0, 25, 27; 1, 1, 1); for C₂, we have (α_2,0, α_2,1, α_2,2, α_2,3, α_2,4; λ₂, μ₂, ρ₂) = (0, 32, 27, 23, 25; 1, 1, 1). The wafer processing route is LLs→ PM_1,0 → PM_1,1 → PM_1,2 (PM_2,0) → PM_2,1 → PM_2,2 → PM_2,3 → PM_2,4 → PM_2,0 (PM_1,2) → PM_1,3 → PM_1,4 → LLs. After being processed, a wafer can stay at PM_{i, j} for no more than δ_1,1 = δ_1,3 =δ_1,4 = δ_2,1 = δ_2,2 = δ_2,3 = δ_2,4 = 10, respectively. There are no wafer residency time constraints at LLs and BMs.
示例 2：在双簇工具中，PM _1,0 是 LLs，PM _2,0 和 PM _1,2 是 BMs。时间单位为秒，后续省略。对于 C ₁ ，我们有 (α _1,0 , α _1,1 , α _1,2 , α _1,3 , α _1,4 ; λ ₁ , μ ₁ , ρ ₁ ) = (0, 22, 0, 25, 27; 1, 1, 1)；对于 C ₂ ，我们有 (α _2,0 , α _2,1 , α _2,2 , α _2,3 , α _2,4 ; λ ₂ , μ ₂ , ρ ₂ ) = (0, 32, 27, 23, 25; 1, 1, 1)。晶圆加工路线为 LLs→ PM _1,0 → PM _1,1 → PM _1,2 (PM _2,0 ) → PM _2,1 → PM _2,2 → PM _2,3 → PM _2,4 → PM _2,0 (PM _1,2 ) → PM _1,3 → PM _1,4 → LLs。加工后，晶圆在 PM _{i, j} 停留时间分别不超过 δ _1,1 = δ _1,3 =δ _1,4 = δ _2,1 = δ _2,2 = δ _2,3 = δ _2,4 = 10。LLs 和 BMs 处无晶圆停留时间限制。

By (4), (10) and (12), the cycle time of this two-cluster tool is Θ = 35. By Algorithm 1, we have
根据(4)、(10)和(12)，该双簇工具的周期时间为Θ = 35。通过算法 1，我们有

1) For C₁, ψ_1,1 ≤ Θ and Θ ≤ Π_{1, jU}, j ∈ $N_{n\left[1\right]}^{+}$\{b[1]}, are satisfied and Algorithm 2 is applied;
1) 对于 C ₁ ，满足 ψ _1,1 ≤ Θ 且 Θ ≤ Π _{1, jU} ，∈ $N_{n\left[1\right]}^{+}$ \{b[1]}，并应用算法 2；

2) For C₂, ψ_2,1 ≤ Θ and Θ ≤ Π_{2, jU}, j ∈ $N_{n\left[2\right]}^{+}$, are satisfied and Algorithm 2 is also applied.
2) 对于 C ₂ ，满足 ψ _2,1 ≤ Θ 且 Θ ≤ Π _{2, jU} ，∈ $N_{n\left[2\right]}^{+}$ ，并且也应用了算法 2。

For C₁, by Algorithm 2, ε = 22 satisfies ε > ψ_{i, 2} = 19. Then, we have (ω_1,0S, ω_1,1S, ω_1,2S, ω_1,3S, ω_1,4S) = (0, 8, 0, 5, 3), (ω_1,0, ω_1,1, ω_1,2, ω_1,3, ω_1,4) = (0, 0, 0, 0, 0), and (r_1,1, r_1,3, r_1,4) = (2, 2, 2).
对于 C ₁ ，根据算法 2，ε = 22 满足ε > ψ _{i, 2} = 19。于是，我们有(ω _1,0S , ω _1,1S , ω _1,2S , ω _1,3S , ω _1,4S ) = (0, 8, 0, 5, 3)，(ω _1,0 , ω _1,1 , ω _1,2 , ω _1,3 , ω _1,4 ) = (0, 0, 0, 0, 0)，以及(r _1,1 , r _1,3 , r _1,4 ) = (2, 2, 2)。

For C₂, by Algorithm 2, ε = 21 satisfies ε > ψ_{i, 2} = 23. Then, we have (ω_2,0S, ω_2,1S, ω_2,2S, ω_2,3S, ω_2,4S) = (0, 0, 3, 7, 5), (ω_2,0, ω_2,1, ω_2,2, ω_2,3, ω_2,4) = (0, 0, 0, 0, 0), and (r_2,1, r_2,2, r_2,3, r_2,4) = (0, 2, 2, 2).
对于 C ₂ ，根据算法 2，ε = 21 满足 ε > ψ _{i, 2} = 23。于是，我们有 (ω _2,0S , ω _2,1S , ω _2,2S , ω _2,3S , ω _2,4S ) = (0, 0, 3, 7, 5), (ω _2,0 , ω _2,1 , ω _2,2 , ω _2,3 , ω _2,4 ) = (0, 0, 0, 0, 0)，以及 (r _2,1 , r _2,2 , r _2,3 , r _2,4 ) = (0, 2, 2, 2)。

Fig. 3 shows that the post-processing time marked with red is short and the post-processing time difference between the adjacent tools marked by red bars is small. In Fig. 3, we use arrows to illustrate the operation routes of robots.
图 3 显示，红色标记的后处理时间较短，且红色柱状图表示的相邻工具间的后处理时间差异较小。在图 3 中，我们使用箭头来描绘机器人的操作路径。

View

Download

 查看下载

Figure 3 图 3

Gantt chart for the schedule in Example 2 (a two-cluster tool)
示例 2 中时间表的甘特图（双簇工具）

The algorithms in [24] give a schedule by setting the following robot waiting time:
[24]中的算法通过设定以下机器人等待时间来给出调度方案：

(ω′_1,0S, ω′_1,1S, ω′_1,2S, ω′_1,3S, ω′_1,4S) = (0, 0, 0, 0, 0)

(ω′_1,0, ω′_1,1, ω′_1,2, ω′_1,3, ω′_1,4) = (0, 0, 0, 0, 16)

(r′_1,1, r′_1,3, r′_1,4) = (10, 7, 5)

(ω′_2,0S, ω′_2,1S, ω′_2,2S, ω′_2,3S, ω′_2,4S) = (0, 0, 0, 0, 0)

(ω′_2,0, ω′_2,1, ω′_2,2, ω′_2,3, ω′_2,4) = (0, 0, 0, 0, 15)

(r′_2,1, r′_2,3, r′_2,4) = (0, 5, 9, 7).

Obviously, we can get 显然，我们可以得到

${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ < ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$, i ∈ $N_2^{+}$

${\sum }_{i=1}^2{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ = 12, ${\sum }_{i=1}^2{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$ = 43. Thus, the total post-processing time of this four-cluster tool is decreased by 72.0%. Furthermore, we have the following results.
${\sum }_{i=1}^2{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ = 12, ${\sum }_{i=1}^2{\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}^{\prime }$ = 43。因此，该四集群工具的后处理时间减少了 72.0%。此外，我们得到以下结果。

1) |r_{i, jmax} − r_{i, fmin}| < |r′_{i, jmax} − r′_{i, fmin}|, i ∈ $N_2^{+}$, j ≠ f, $\{j,f\}\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}$; and
1) |r _{i, jmax} − r _{i, fmin} | < |r′ _{i, jmax} − r′ _{i, fmin} |, ∈ $N_2^{+}$ , ≠ f, $\{j,f\}\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}$ ; 且

2) |Z_i| < |Z′_i|, i ∈ $N_2^{+}$.

The results of the above examples have been shown as bar graphs in Figs. 4 and 5. It is obvious that the total post-processing time and the post-processing time difference between different steps are significantly less for C_i than that for C_i′. Compared with the schedule obtained by [24], the obtained schedule by the proposed method achieves the following goals.
上述示例的结果已以柱状图形式展示在图 4 和图 5 中。显而易见，C 的总后处理时间以及不同步骤间的后处理时间差异均显著小于 C′。相较于[24]所获得的调度方案，本文提出的方法所获调度方案实现了以下目标。

View

Download

 查看下载

Figure 4 图 4

Comparison for Example 1.
示例 1 的比较。

View

Download

 查看下载

Figure 5 图 5

Comparison for Example 2.
示例 2 的比较。

1) Minimize ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ for C_i, i ∈ $N_K^{+}$;
1) 最小化 ${\sum }_{j\in N_{n\left[i\right]}^{+}\setminus \left\{b\right[i\left]\right\}}{r}_{i,j}$ 对于 C, ∈ $N_K^{+}$ ;

2) Balance the difference in post-processing time among PS_{i, j}, j ∈ N_n[i]\ {0, b[i]}; and
2) 平衡 PS _{i, j} , ∈ N _n[i] \ {0, b[]}之间的后处理时间差异；

3) Balance the post-processing time difference between adjacent cluster tools.
3) 平衡相邻簇工具之间的后处理时间差异。

V Conclusion  五 结论

Multi-cluster tools are widely used in wafer manufacturing in the semiconductor manufacturing industry due to their high efficiency. In order to load/unload wafers according to the wafer route, proper cooperation between the robots of each cluster tool is demanded. Furthermore, after a wafer is processed in a processing module, the robot is scheduled to unload it timely because the decreasing narrow circuit width demands limit the post-processing time. This study finds an optimal schedule for a multi-cluster tool to minimize the wafer post-processing time. Besides, we make efforts to avoid uneven post-processing time among the processing steps. The proposed method can handle the case where the difference in post-processing time between two adjacent cluster tools is large. The method can greatly lead to high-yield and high-quality integrated-circuit chips on a wafer.
多集群工具因高效性在半导体制造行业的晶圆生产中得到广泛应用。为了按照晶圆路径进行装载/卸载操作，各集群工具的机器人之间需进行恰当协作。此外，晶圆在处理模块中加工后，机器人需及时调度以卸载晶圆，因为日益缩小的电路宽度对后处理时间提出了严格限制。本研究旨在为多集群工具找到一种最优调度方案，以最小化晶圆后处理时间。同时，我们努力避免各处理步骤间后处理时间的不均衡。所提出的方法能够应对相邻两集群工具间后处理时间差异较大的情况。该方法有望大幅提升晶圆上集成电路芯片的产量与质量。

In future work, we will investigate how to regulate the wafer post-processing time for a multi-cluster tool when its processing time is disturbed.
在未来的工作中，我们将研究如何在多集群工具的加工时间受到干扰时，调整晶圆的后处理时间。