考虑晶圆驻留时间约束的双臂组合设备群调度*

马利平 刘玉敏 赵艳平 王际鹏 承姿辛

（①河南工业大学漯河工学院，河南 漯河 462000；②湖北工业大学机械工程学院，湖北 武汉 430068；③湖北工业大学现代制造质量工程湖北省重点实验室，湖北 武汉 430068）

组合设备（cluster tool）是半导体制造中一类极为昂贵的高端装备，广泛用于半导体芯片制造的前端工艺[1]。多台单一组合设备（single-cluster tool，SCT）经缓冲模块（buffer module，BM）连接而成的设备集群，即组合设备群 （multi-cluster tool，MCT），代表了组合设备发展的新趋势，近年已在行业领先的芯片制造企业得到快速应用[2]。由多台单/双臂组合设备构成的设备集群称为单/双臂组合设备群，而混合组合设备群由单、双臂两种设备组合而成。按设备拓扑结构划分，组合设备群可分为线性和树形两种，如图1 所示为一台线性双臂组合设备群。

图1 线性双臂组合设备群

作为一种多设备集群系统，组合设备群调度是一类极为复杂的组合优化问题。对于组合设备群而言，k-晶圆周期调度难以控制和实现，且极易造成系统阻塞。1-晶圆周期调度可形成稳定的加工过程，操作简单且易于实施。Zhu Q H 等[3]证明了处于加工临界的单臂线性组合设备群必定存在1-晶圆周期调度。进一步，引入晶圆驻留时间约束并给出了相应的最优1-晶圆周期调度方法[4]。而后，利用剪枝策略将树形组合设备群转换为线性组合设备链，从而获得最优1-晶圆周期调度[5]；对于处于传输临界的单臂线性组合设备群，Yang F J 等[6]给出了最优1-晶圆周期调度求解方法。针对线性组合设备群，Bao T P 等[7]采用混合整数规划模型求解周期调度，Yan Y Y 等[8]通过帕累托优化方法求解非周期调度。而对于线性双臂组合设备群，Zhu Q H 等[9]运用集成调度方法优化暂态和稳态产能，Yang F J 等[10]采用实时调度策略计算设备在作业时间波动情形下的驻留时间延迟累积，Zhu Q H 等[11]研究了两种晶圆产品混合加工的调度优化问题。

除了设备的拓扑结构外，BM 容量和机械手构成形式亦对组合设备群的调度具有重要影响。 Yang F J 等[12]研究了BM 容量为2 的线性单臂组合设备群调度问题，提出了有效且易于实施的算法求解1-晶圆周期调度。李文涛等[13]修改Petri 网模型的初始标识，促使系统加速进入稳态，提出了有效的调度策略。黄鹏等[14]研究了BM 容量为2 的树形单臂组合设备群的优化调度问题，提出了最优1-晶圆周期调度求解算法。针对处于加工临界的线性单臂组合设备群，Bai L P 等[15]深入分析了BM 配置方式对系统调度的影响机理，给出了周期时间下界可达的BM 最优配置方法。Yang F J 等[16-18]证明线性混合组合设备群存在1-晶圆周期调度，并给出了不同约束条件下的最优1-晶圆周期调度求解方法。对于树形混合组合设备群，Yang F J 等[19-20]给出了最优1-晶圆周期调度方法。

综合前文所述，现有组合设备群调度控制的研究重点在于单臂组合设备群和混合组合设备群，而对于生产效率更高的双臂组合设备群，鲜有研究给予关注。此外，现有工作局限于特定拓扑结构的组合设备群，尚未有研究统一考虑线性和树形设备的调度问题。鉴于上述原因，本文对考虑晶圆驻留时间约束的双臂组合设备群调度问题开展研究。首先引入特征双臂组合设备并研究其稳态调度问题，随后采用特征转换方法将线性或树形双臂组合设备群转换为特征双臂组合设备，然后根据转换后的特征双臂组合设备求解双臂组合设备群的稳态调度，最后通过算例验证所提方法的可行性和有效性。

1 问题描述

1.1 基本假设

与文献[3-9, 16-20]一致，不失一般性，针对双臂组合设备群稳态调度问题做出如下约定：① 不考虑并行加工模块（process module，PM），即每个PM 仅执行一道工序的加工；② 每个BM 被两个邻接单台组合设备共享，容量为1, 且不具备晶圆加工功能；③晶圆加工时间和机械手作业时间为常量；④ 所有晶圆拥有相同的配方，访问每个PM 不超过一次（BM 除外）。此外，考虑晶圆驻留时间约束，即晶圆在PM 完成加工后必须在限定的时间之内卸载。

1.2 符号设定

晶圆在组合设备群中的加工路径用 R表示, 沿路径 R 的第i台SCT 用Ci表示，i∈ NK= {1, 2,···,K}。线性组合设备群中的C1/CK与树形组合设备群中的“叶设备”（leaf SCT），均只有一台邻接SCT，其余任意SCT 至少有两台邻接SCT。当Ci至少有3 台邻接SCT 时，称之为“叉设备”（fork SCT）。令和分别表示组合设备群的“叶设备”和“叉设备”符号下标的集合，则有= {i|i∈,Ci是“叶设备”}，= {i|i∈,Ci是“叉设备”}。沿路径 R，若Ci的排序相对Cj靠前，则称Ci为Cj的上游设备，或称Cj为Ci的下游设备。

在组合设备群中，两台邻接的SCT 通过BM 相连，该BM 可视作下游SCT 的输入模块或上游SCT 的输出模块。另外，C1的真空锁可视作输入模块。“叶设备”没有输出模块，而其余SCT 拥有一个输入模块和至少一个输出模块。具体来说，线性组合设备群中的Ci只有一个输出模块（符号标记为b[i]）, 而树形组合设备群中的Ci至少拥有一个输出模块（符号标记分别为b[i]_1,b[i]_2,···,b[i]_ci, 其中i∈）。令 Sb为输出模块符号标记的集合,即 Sb= {b[i]_1,b[i]_2,···,b[i]_ci, 其中i∈}。需要注意的是，输入模块可视作没有加工功能的第0 道工序，则Ci总计可执行n[i] + 1 道工序。

用Pij（i∈，j∈Ωn[i]={0}）表示Ci的第j道工序，其中Pi0表示输入模块对应的工序。晶圆在工序Pij（i∈，j∈）的加工时间用αij表示，加工完成后允许停留的最长时间为βij。与文献[3-9, 16-20]中的设定相同，对于一台组合设备群，Ci中机械手在任意工序装/卸载一枚晶圆耗费的时间相同，用ρci表示。同样地，Ci中机械手运送一枚晶圆至任意模块所耗费的时间相同，用θci表示。设机械手在工序Pij执行交换操作需要的时间为γci，执行交换操作前后的等待时间分别表示为ωij1和ωij2。此外，组合设备群的生产周期时间用ϕm表示。

2 特征双臂组合设备及其调度

2.1 特征双臂组合设备

传统双臂组合设备与特征双臂组合设备的结构如图2 所示，二者不同之处在于传统设备至多有6个PM，特征设备配置h（h∈）个PM。为克服工序瓶颈，传统设备会考虑配置并行PM，而特征设备不考虑并行PM，每道工序仅配置一个PM。在传统设备中，机械手运送晶圆到各个PM 所耗费的时间一般相同；而在特征设备中，约定机械手运送晶圆到各个PM 所耗费的时间不一定相同。由于特征设备与传统设备差别巨大，现有传统双臂组合设备的调度方法已经不再适用，需探索新的调度方法。

图2 传统双臂组合设备与特征双臂组合设备的结构

为便于分析，机械手的常规作业时间（即装载、卸载、交换）和晶圆在PM 内的加工时间可认为是常量。第i道工序记为Pi，i∈ Ωh+1。真空锁可认为是第0 或h+ 1 道工序，因此用P0表示释放待加工晶圆的初始工序，而Ph+1表示存储已完成加工晶圆的终止工序。机械手在任意工序Pi装/卸载晶圆耗费的时间用ρi（i∈ Ωh+1）表示，在工序Pi执行交换操作耗费的时间用γi（i∈）表示，将晶圆从工序Pi运送至工序Pi+1耗费的时间用θi（i∈ Ωh）表示。晶圆在工序Pi的加工时间和驻留时间（即自载入PM 开始至卸载时，晶圆在PM 内停留的时间）分别记为αi、τi，i∈。加工完毕后，晶圆在PMi内允许停留的最长时间记为βi，则有τi∈ [αi,αi+βi]，i∈。

2.2 作业时间分析

当机械手抵达工序Pi执行交换操作时，PMi中的晶圆有可能仍旧处在加工状态。此时，机械手须等待一段时间（记为ωi1），直至晶圆完成加工。为获得可行的调度，机械手在Pi执行交换操作后可能仍旧需要等待若干时间（记为ωi2）。在工序Pi，晶圆加工和停留（耗时τi）和机械手交换作业及等待（耗时γi+ωi2）重复执行。分别用ϕi、ϕiL、ϕiU表示工序Pi（i∈）的生产周期及其下界和上界, 则有

移除式（1）～（3）中的机械手等待时间ωi2,可得工序Pi（i∈）的自然负载（用φi表示）及其上、下界（分别用φiU、φiL表示）, 则有

在每个作业循环中，机械手执行一系列相同序列的常规作业（即装载、卸载、交换）和等待。因此，机械手的生产周期ϕr由常规作业和等待两个部分构成。用ϕt和ϕw分别表示机械手在一个作业循环内执行常规作业和等待耗费的时间。为推导ϕr的计算方法，我们需要分析机械手在每个作业循环内的调度机制。基于交换策略，机械手在每个作业循环访问的工序顺序为：P0→P1→P2→···→Ph-1→Ph→Ph+1。因此，稳态时机械手在每个作业循环执行的作业序列为: 从工序P0卸载（耗时ρ0） 一枚待加工晶圆 → 运送（耗时θ0）晶圆至工序P1→ 在工序P1处等待（耗时ω11） → 在工序P1执行交换作业并等待（耗时γ1+ω12） → 移动（耗时θ1）至工序P2→ 在工序P2等待（耗时ω21）→ 在工序P2执行交换作业并等待（耗时γ2+ω22） → ··· → 移动（θh-2）至工序Ph-1→ 在工序Ph-1等待（耗时ω（h-1）1） →在工序Ph-1执行交换作业并等待（耗时γh-1+ω（h-1）2） →移动（耗时θh-1）至工序Ph→ 在工序Ph等待（耗时ωh1） → 在工序Ph执行交换作业并等待（耗时γh+ωh2） → 移动（耗时θh）至工序Ph+1→ 装载（耗时ρh+1）完成加工的晶圆进入工序Ph+1。因此，可知采用交换策略的特征双臂组合设备的机械手生产周期为

其中

2.3 可调度性分析与调度

稳态时，机械手在每个作业循环中重复相同的任务序列。机械手完成一个作业循环时，一枚晶圆完成所有加工并返回真空锁。在每个机械手作业循环中，每道工序完成一枚晶圆的加工，这意味着机械手的生产周期与系统的生产周期必然相同。为确保稳定的晶圆加工，晶圆在每道工序内的驻留时间必须保持一致。因此，在稳态时，每道工序的生产周期与机械手和系统的生产周期必须保持一致。特征双臂组合设备的生产周期记为ϕd，则在稳态时有

由上式可知，当设备运行在稳态时,必然有

但是，我们无法通过系统设定参数直接获知这一结果。然而，我们可以通过工序自然负载和机械手常规任务时间的参数分布特点（即[φiL,φiU],i∈ Nh,ϕt）来予以分析。为保证调度的可行性，晶圆在PM 内的驻留时间（即τi,i∈ Nh）必须落于区间[αi,αi+βi]，使得ϕiL≤ϕi≤ϕiU成立。因此，设备调度可行性判定的关键在于τi的分布特点及计算, 而由式（1）和式（10）可知：

通过式（4）～式（7），可以分析[φiL,φiU]和ϕt的变动机制，进而推测设备在运行在稳态时是否满足晶圆驻留时间约束。因此，由已知系统参数可推知[ϕiL,ϕiU]和ϕr的参数分布特点。令φUmin= min{φiU,i∈}，φLmax= max{φiL,i∈},= {i|i∈,φiU＜φLmax},，则有如下定理。

定理1 对于具有晶圆驻留时间约束的特征双臂组合设备，若[φiL,φiU] ≠ ∅，且ϕt≤φUmin，则设备可以调度；否则，设备不可调度。

证毕

证毕

综合作业时间分析和可调度性判定，对于考虑晶圆驻留时间约束的特征双臂组合设备，稳态时的1-晶圆周期调度求解可归结为如下算法：

?

3 双臂组合设备群调度

3.1 特征转换

第2 节引入了特征双臂组合设备，相比传统双臂组合设备，前者PM 的数量可能大于6，并且机械手在各工序的任务时间不一定相同。一台双臂组合设备群由多个SCT 组成，故双臂组合设备群中配置的PM 数量也可能大于6。另外，双臂组合设备群中各SCT 的机械手任务时间明显不一定相同。从一个整体的视角来看，双臂组合设备群的上述两种特征，与特征双臂组合设备具备相当程度的相似性。可以采取某种方法将双臂组合设备群转化为特征双臂组合设备。将双臂组合设备群中的工序分为规范工序和协调工序，前者为执行晶圆加工的工序，后者指执行晶圆输入、输出和存储的工序。 Sn和Sr分别表示双臂组合设备群中规范工序和协调工序的集合,则有令Ci的规范工序数量为nci，则有。

首先将双臂组合设备群的规范工序沿晶圆加工路径 R重新编号。然后，将双臂组合设备群对应工序的晶圆加工参数传递给转换后的特征双臂组合设备。最后，确定机械手在双臂组合设备群任意模块间传递晶圆的运动机制，即所需时间。当机械手在任意两个不同模块间传递晶圆时，有两种情形需要考虑。当两模块间不含有协调工序时，则仅需传递双臂组合设备群的源参数给特征双臂组合设备即可。若两模块间含有协调工序，则机械手运送晶圆所需时间必须考虑在协调工序的转运时间（包括运送、装载、卸载时间）。综上，具体转换过程如下：

步骤1 沿路径 R 重置双臂组合设备群的工序编号：Pij→Pi；

步骤2 传递设备群工序的晶圆加工参数至重编号后的特征设备工序: {αij,βij,ρci,γci} → {αi,βi,ρi,γi}；

步骤3 确定机械手运送晶圆至不同规范工序所需时间θi。

3.2 调度算法

从上一节的分析可知，双臂组合设备群可以通过特征转换的方式转换为特征双臂组合设备。此时，双臂组合设备群的调度问题即可转变为特征双臂组合设备的调度问题。综合前文的相关分析，双臂组合设备群稳态调度的求解过程可分为三个阶段：① 将双臂组合设备群转化为特征双臂组合设备；② 求解转化后的特征双臂组合设备可行稳态调度；③ 通过特征转换的逆变换操作设定双臂组合设备群的机械手等待时间。求解过程可归结为如下算法：

?

4 例子

为说明本文所提方法的有效性，本节给出两个算例。其中，晶圆加工参数的单位为s。

例1 如图3 所示线性双臂组合设备群，其加工参数如下:C1=（α11，β11;α12，β12;α13，β13;ρc1，θc1，γc1）=（144 s，18 s; 0 s，+∞; 154 s，15 s; 4 s，2 s，12s）；C2=（α21，β21;α22，β22;α23，β23;ρc2，θc2，γc2）=（130 s，21 s; 0 s，+∞; 148 s，16 s; 5 s，2 s，14 s）；C3=（α31，β31;α32，β32;α33，β33;ρc3，θc3，γc3）=（156 s，14 s; 140 s，20 s; 162 s，12 s; 4 s，1 s，10 s）。

图3 线性组合设备群

对于本例，h= 2 + 2 +3 = 7。规范工序重编号为：P10→P0（P8），P11→P1，P21→P2，P31→P3，P32→P4，P33→P5，P23→P6，P13→P7。此时，设备加工参数可重置为：α1=α11= 144 s，α2=α21=130 s，α3=α31= 156 s，α4=α32= 140 s，α5=α33=162 s，α6=α23= 148 s，α7=α13= 154 s；β1=β11= 18 s，β2=β21= 21 s，β3=β31= 14 s，β4=β32= 20 s，β5=β33=12 s，β6=β23= 16 s，β7=β13= 15 s；γ1=γc1= 12 s，γ2=γc2= 14 s，γ3=γ4=γ5=γc3= 10 s，γ6=γc2= 14 s，γ7=γc1= 12 s；ρ0=ρ8=ρc1= 4 s；θ0=θ7=θc1= 2 s，θ1=θc1+ρc1+ρc2+θc2= 13 s，θ2=θc2+ρc2+ρc3+θc3= 12 s，θ3=θ4= 1s，θ5=θc3+ρc3+ρc2+θc2= 12s，θ6=θc2+ρc2+ρc1+θc1= 13 s。

随后，则有φ1L= 156 s，φ1U= 174 s，φ2L= 144 s，φ2U= 165 s，φ3L= 156 s，φ3U= 180 s，φ4L= 150 s，φ4U= 170 s，φ5L= 172 s，φ5U= 184 s，φ6L= 164 s，φ6U=180 s，φ7L= 162 s，φ7U= 177 s，φLmax= 172 s，φUmin=165 s，因此，ϕt＜φUmin＜φLmax，由定理2 可知，设备可以调度。根据算法2 可求得ϕd=φLmax= 172 s，ω12=ω21=ω31=ω32=ω41=ω51=ω52=ω61=ω62=ω71=ω72= 0 s，ω22=φLmax-φ2U= 7 s，ω42=φLmax-φ4U= 2 s，ω11=φLmax-ϕt-ω22-ω42= 7 s。进而，可知设备的稳态调度为：ϕm=ϕd= 172 s,ω111=ω11= 17 s，ω112=ω12= 0 s，ω131=ω71= 0 s，ω132=ω72= 0 s，ω211=ω21=0 s，ω212=ω22= 7 s，ω231=ω61= 0 s，ω232=ω62= 0 s，ω311=ω31= 0 s，ω312=ω32= 0 s，ω321=ω41= 0 s，ω322=ω42= 2 s，ω331=ω51= 0 s，ω332=ω52= 0 s。调度甘特图如图4 所示。

图4 算例1 调度甘特图

例2 如图5 所示树形双臂组合设备群，其加工参数如下:C1=（α11，β11;α12，β12;α13，β13;ρc1，θc1，γc1）=（172 s，15 s; 0 s，+∞; 185 s，10 s; 3 s，1 s，8 s）；C2=（α21，β21;α22，β22;α23，β23;ρc2，θc2，γc2）=（0 s，+∞ s; 0 s，+∞; 156 s，23 s; 5 s，3 s，15 s）；C3=（α31，β31;α32，β32;ρc3，θc3，γc3）=（179 s，19 s;168 s，20 s; 5 s，2 s，12 s），C4=（α41，β41;α42，β42;ρc4，θc4，γc4）=（163 s，25 s; 180 s，16 s; 4 s，2 s，10 s）。

图5 树形组合设备群

对于本例，h=nc1+nc2+nc3+nc4= 2 + 1 + 2 + 2 = 7。规范工序重编号为：P10→P0（P8），P11→P1，P31→P2，P32→P2，P41→P4，P42→P5，P23→P6，P13→P7。此时，设备加工参数可重置为：α1=α11= 172 s，α2=α31= 179 s，α3=α32= 168 s，α4=α41= 163 s，α5=α42= 180 s，α6=α23= 156 s，α7=α13= 185 s；β1=β11=15 s，β2=β31= 19 s，β3=β32= 20 s，β4=β41= 15 s，β5=β42= 16 s，β6=β23= 23 s，β7=β13= 10 s；γ1=γc1=8 s，γ2=γ3=γc3= 12 s，γ4=γ5=γc4= 10 s，γ6=γc2=15 s，γ7=γc1= 8 s；ρ0=ρ8=ρc1= 3 s；θ0=θ7=θc1= 1 s，θ1=θc1+ρc1+ρc2+θc2+ρc3+θc3= 24 s，θ2=θc3= 2 s，θ3=θc3+ρc3+ρc2+θc2+ρc2+ρc4+θc4= 26 s，θ4=θc4=2 s，θ5=θc4+ρc4+ρc2+θc2= 14 s，θ6=θc2+ρc2+ρc1+θc1= 12 s。

随后有φ1L= 180 s，φ1U= 195 s，φ2L= 191 s，φ2U=210 s，φ3L= 180 s，φ3U= 200s，φ4L= 173 s，φ4U= 188 s，φ5L= 190 s，φ5U= 206 s，φ6L= 171 s，φ6U= 194 s，φ7L=193 s，φ7U= 203 s，φLmax= 193 s，φUmin= 194 s，ϕt=因此，∅，ϕt＜φLmax＜φUmin，由定理1 可知，设备可以调度。根据算法2 可求得ϕd=φLmax= 193 s，ω11=φLmax-ϕt=30 s，ω12=ω21=ω31=ω32=ω41=ω41=ω51=ω52=ω61=ω62=ω71=ω72= 0 s。进而，可知设备的稳态调度为：ϕm=ϕd= 193 s,ω111=ω11= 30 s，ω112=ω12= 0 s，ω131=ω71= 0 s，ω132=ω72= 0 s，ω231=ω61= 0 s，ω232=ω62=0 s，ω311=ω21= 0 s，ω312=ω22= 0 s，ω321=ω31= 0 s，ω322=ω32= 0 s，ω411=ω41= 0 s，ω411=ω41= 0 s，ω412=ω42= 0 s，ω421=ω51= 0 s，ω422=ω52= 0 s。调度甘特图如图6 所示。

图6 算例2 调度甘特图

通过上述两个实例不难发现，本文提出的双臂组合设备群的稳态周期调度求解方法为多项式方法。一旦判定系统可以调度，算法可以高效地求得可行的稳态周期调度。现有针对双臂组合设备群调度问题的研究[7-11]，重点关注线性设备群的调度优化问题，而本文提出的方法可以在一个统一的框架下处理线性和树形设备群的调度问题。从计算开销来看，文献[7-9]只适合求解中小规模问题。文献[10-11]虽然给出了对应的多项式求解算法，但算法涉及迭代过程，略显复杂。表1 总结了现有双臂组合设备群的研究工作，不论是从可处理的设备类型还是调度求解的复杂性上看，本文所提方法均有良好的表现。

表1 现有双臂组合设备群研究工作比较

5 结语

本文研究了半导体芯片制造中考虑晶圆驻留时间约束的双臂组合设备群调度控制问题，提出了一种基于特征转换的调度控制方法。该方法建立了一个统一的控制框架，采用一种全新的视角调度双臂组合设备群。突破了现有研究对于双臂组合设备群拓扑结构的依赖，有效地降低了调度计算复杂度和机械手协调难度。本文仅考虑了晶圆驻留时间约束，下一步的工作将考虑PM 故障、时变加工、重入加工等更为复杂条件下的调度优化问题。