随着半导体制造进入450 mm晶圆时代，集束型设备群(multi-cluster tools,MCTs)被普遍使用.MCTs调度属于典型NP难问题，具有多晶圆流、驻留及缓冲区资源约束等特殊性，使得传统单集束型设备(single-cluster tool,SCT)调度方法^{[1, 2, 3, 4]}无法满足MCTs调度要求，因此MCTs调度问题亟待解决.

MCTs调度研究尚处于初始阶段，目前大多数文献集中于单种晶圆稳态模式下的周期性调度研究.Yi等^[5]将MCTs调度问题分解为多个SCT调度问题建模分析，并求解出单种晶圆无驻留调度条件下的基本周期下界，但其忽略机械手搬运时间.Chan等^{[6, 7]}将机械手搬运时间假定为固定常数，对两种不同结构的MCTs进行研究，以最小循环周期为目标，提出了基于资源的分析建模方法.石萧铭等^[8]考虑实际加工存在的驻留约束，构造了顺序搜索启发式算法，但其对象仅是双集束型设备.上述文献均未考虑实际调度中普遍存在的多晶圆流现象.

多晶圆流是指同一个晶圆加工批次中具有多条工艺路径.多晶圆流的研究对提高MCTs设备利用率和满足顾客产品多样化需求具有重大意义.

目前大多数学者对单晶圆MCTs调度进行了研究，对多晶圆流的多品种调度问题鲜有研究.仅Liu等^[9]在单臂MCTs中同时考虑晶圆驻留约束和多晶圆流，提出了相应的算法.但其假设晶圆的加工序列确定，未对初始晶圆进入顺序进行考虑.本文在考虑多晶圆流、驻留约束及晶圆的加工序列不确定的基础上，进一步对初始晶圆进入MCTs顺序进行研究，提出了AS&TC(ant systems and time constraints)调度算法.

典型多晶圆流MCTs如图 1所示.晶圆按照其晶圆流从输入卡闸模块CM_a进入系统，依次经过各加工模块，连接相邻集束型设备的缓冲模块，最终加工完成后存放在输出卡闸模块CM_b，晶圆在不同模块间的转移通过搬运模块完成.图中2条折线分别代表 2条不同的晶圆流，可分别用晶圆依次经过加工模块的路径坐标集X_w来表示.

图1(Figure 1)

图1 集束型设备群示意图 Fig. 1 An illustrative chart for the multi-flow pattern in single arm multi-cluster tools

C^h表示MCTs中的第h个集束型设备；R_h表示C^h的搬运模块；PM_hj表示第h个集束型设备中的第j个加工模块；BM_hj表示连接C^h和C^h+1的缓冲模块；晶圆流路径坐标集X_w={x₁,…,x_i,…,x_φ(w)}，x_i=(h,j)表示晶圆第i步经过的处理模块序号，φ(w)表示晶圆w总加工步骤数.

问题假定：1) 加工模块同时只能加工1片晶圆；2) 搬运模块采用单臂机械手，每次仅搬运 1片晶圆，且装卸时间相同；3) 晶圆在缓冲模块驻留时间无限；4) 晶圆加工完成后，在加工模块内有驻留时间上限，超过该上限，成为次品；5) 晶圆批具有多晶圆流，且晶圆加工序列不确定.

据假定1) 第w+1片晶圆进入PM_hj的时间S_hj(w+1)与第w片晶圆离开PM_hj的时间L_hj(w)之差必定超过机械手搬运时间t_M，即：

同理，对缓冲模块：

据假定2) 晶圆在任何一个加工模块的进入时间或离开时间的差值必定超过t_M，即：

同理在任一缓冲模块中应满足：

假定4) 晶圆在PM_hj中的实际停留时间应满足：

式中：P_hj(w)表示晶圆的加工时间；U_hj(w)表示晶圆加工完成后允许的最大驻留时间.

由假定5) 知晶圆具有多种晶圆流模式，所以晶圆转移须满足：

批量为n的晶圆批，晶圆序号{J₁,J₂,…,J_n}，进入CM_a后，需按照顺序依次进入系统加工，即晶圆进入首个加工模块的时间需满足：

式中，q_n为第n片进入系统的晶圆序号.

根据文献[10]对时间约束集的概念作如下定义：

T_R,h(w)表示对晶圆w调度时，机械手R_h的可用时间区间集，包含φt(w,h)个区间，即： T_R,h(w)={t_R,h,1(w),t_R,h,2(w),…,t_R,h,φt(w,h)(w)}；T_PM,xi(w)表示PM_xi可用的时间区间集，包含φ(w,x_i)个时间区间，即：T_PM,xi(w)={t_PM,xi,1(w),t_PM,xi,2(w),…,t_{PM,xi,φ(w,xi)}(w)}；T_PB,hj(w)表示BM_hj可用的时间区间集，包含φb(w,h,j)个区间，即：T_PB,hj(w)={t_PB,hj,1(w),t_PB,hj,2(w),…,t_{PB,hj,φb(w,h,j)}(w)}.

机械手搬运必须在某个可行时间区间完成，即：

其中：t_R,h,q(w)表示T_R,h(w)的第q个可行的时间区间；[S_xi(w)－t_M,S_xi(w)]表示晶圆w从模块PM_xi-1搬运到模块PM_xi所占用机械手的时间区间.

加工模块须满足

其中：t_PM,xi,k(w)表示T_PM,xi(w)的第k个可行的时间区间；[S_xi(w),L_xi(w)]表示晶圆w实际占用模块PM_xi的时间区间.

同理，对缓冲模块有

调度目标是使系统的Makespan最小，即：

本文调度问题是以式(17)为目标函数，式(1)~式(16)为约束条件的非线性规划问题.

为阐明本文的算法，现作如下定义.

定义1 晶圆流差异化因子DFP(difference of flow pattern)，DFP_ij=φ(i)+φ(j)－2φ_s(i,j)；φ(i)，φ(j)为晶圆J_i和J_j各自的需要经过的加工模块数目，φ_s(i,j)表示晶圆J_i和J_j共享加工模块(即两条路径都需要经过的加工腔)的数目.

定理1 相邻晶圆DFP越大，晶圆加工对资源的冲突越小，调度可获得驻留时间越短.

证明 假设晶圆A＼B＼C三片晶圆，加工路径坐标集分别为x_a，x_b，x_c，φ(b)=φ(c)， DFP_ab≥DFP_ac.则DFP_ab=φ(a)+φ(b)－2φ_s(a,b),DFP_ac=φ(a)+φ(c)－2φ_s(a,c).

因为DFP_ab≥DFP_ac，则φ_s(a,b)<φ_s(a,c).又因A/B/C为相邻晶圆，共享设备越多，资源冲突越大，则在共享设备累积驻留时间越长，即

式中:PM_abⁱ为晶圆J_a与晶圆J_b第i个共享加工模块；T_delay(PM_abⁱ)为晶圆J_a(晶圆J_b)由于等待晶圆J_b(晶圆J_a)在PM_abⁱ加工而发生的驻留时间.

定义2 蚁群期望启发因子η_ij，表示路径(i,j)的能见度，反映晶圆J_i转移到晶圆J_j的启发程度，这个量在系统运行中不改变，为了尽量避免相邻晶圆流的冲突，根据定理1，令η_ij/=DFP_ij.

定义3 蚁群信息启发因子τ_ij(t)，表示t时刻路径(i,j)上的信息素轨迹强度.

定义4 蚂蚁搜索得到的一条运动路径即为一个晶圆初始进入顺序方案，用禁忌表tabu_k(s)记录，k为蚂蚁编号，s为晶圆加工序号.

本文AS&TC算法的核心思想包括两个阶段：外层晶圆顺序决策和内层机械手调度.

算法的具体步骤描述如下：

步骤1 产生初始晶圆进入顺序.

步骤1.1 将m只蚂蚁随机的置于n片晶圆节点上，赋值s=1，tabu_k(s)=random(1，n)，k=1,2,…,m，对n片晶圆进行编号，为J₁,J₂,…,J_n，作为蚂蚁路径搜索初始节点.

步骤1.2 按照蚁群算法状态转移概率式(18)和式(19)选取下一片晶圆j，并更新禁忌表.赋值s=s+1，产生随机数q=random(0，1)，

q₀为转移判定系数，q₀~U(0,1)，J由式(19)确定，当q > q₀,则j由转移概率P_ij^k(t)确定.

步骤1.3 信息素局部更新.

其中：1－ρ为信息素挥发系数；τ₀为信息素初始值.

步骤1.4 重复步骤1.2，1.3直至产生完整的晶圆进入顺序.

步骤2 正向查找可用时间区间.

步骤2.1 根据x_i的位置类型，计算晶圆在相应加工模块可行开始区间.

1) 假设x_i－1位于C^h－1(i>1)则使用式(21)计算ts_xi,d(w)：

式中：ts_xi,d(w)是处理模块x_i的第d个可行的开始时间区间;t_PM,hj,d(w)是PM_hj的第d个可行的时间区间；t_LD,t_UD分别为晶圆装载和卸载时间.

3) 假设x_i－1位于C^h+1(i>1)则使用式(22)计算ts_xi,d(w)：

4) 其他情况，则转至步骤2.4.

步骤2.2 使用式(23)计算可行结束时间区间tl_xi,d(w)：

步骤2.3 若ts_xi,d(w)=φ or tl_xi,d(w)=φ，则令d=d+1，并返回步骤2.1;否则转到下一步.

步骤2.4 使用式(24)计算晶圆在相应加工模块可行开始时间约束集

步骤2.5 使用式(25)计算晶圆在相应加工模块可行结束时间约束集TL_xi(w):

步骤2.6 若TS_xi(w)=φ or TL_xi(w)=φ，则令d=d+1，并返回步骤2.1；否则转到下一步.

步骤3 后向求解调度时间点.

步骤3.1 使用式(26)计算晶圆的最早的加工结束时间S_CMb(w):

步骤3.2 使用式(27)计算L_xφ(w)(w):

步骤3.3 使用式(28)计算S_xφ(w)(w):

步骤3.4 使用式(29)计算LB_hj(w):

步骤3.5 使用式(30)计算SB_hj(w):

步骤3.6 使用式(31)计算L_xi(w):

步骤3.7 使用式(32)计算S_xi(w):

步骤3.8 令i=i－1;若i=0，后向搜索结束，否则转至步骤3.4.

步骤4 数据信息更新.

步骤4.1 更新搬运模块可用时间集数据:

步骤4.2 更新各加工模块的可用时间集数据:

步骤4.3 各缓冲模块可用时间集数据:

步骤5 令s=s+1;若s≤n，则返回步骤2，否则转至下一步.

步骤6 初始化集束型设备群,令k=k+1;若k≤m，则返回步骤2，否则转至下一步.

步骤7 信息素全局更新.

其中

式中:1－α₁表示信息素全局挥发系数；L_min=min{L₁,L₂,…,L_m},L₁,L₂,…,L_m表示蚂蚁1~m搜索到的晶圆序列调度得到的Makespan.

步骤8 令循环次数N_c=N_c+1;若N_c≤N_max，则返回步骤1，否则算法结束.

现将实验相关的符号与变量定义如下.

R=(C_ASTC－C_SPT^*)/C_SPT^*×100%为制造期相对延时率，表示算法相对于C_SPT^*的延迟，该值越小，表明调度得到的制造期越接近C_SPT^*，即算法的性能越好.C_ASTC表示本文算法处理一批晶圆的Makespan.C_SPT^*表示文献[11]中提出的初始晶圆进入顺序按SPT(shortest processing time)排序的情况下处理一批晶圆的Makespan.df=k/n，为晶圆流批异化率，即批量为n的批中具有k种不同的晶圆种类的比例.实验用C++实现，仿真环境为主频2.13 GHz,内存8 GB的PC机.算法相关基本参数设定：m=25,α=2,β=5,α₁=0.1,ρ=0.1,q₀=0.9.

晶圆处理时间服从P～N(40,10)，驻留约束时间服从U～N(20,5).集束型设备数目CT=3；每个集束型设备的加工模块数目MH=4；t_M=4；df=0.6.仿真运行的结果如图 2所示.

图2(Figure 2)

图2 算法运行时间分析 Fig. 2 The running time of algorithm

图 2显示了算法的运行时间随着晶圆数目的增加大体上呈正相关，在晶圆数目较少时(小于10片)显然算法的运算时间是非常小的，当晶圆数目N=9时，运算时间仅为0.39 s.当晶圆数目增加到20片以上时，算法运算时间较长.

令CT=3；MH=4；t_M=4；df=0.4,0.6,0.8,1.处理时间服从P～N(40,10)，U～N(20,5).仿真运行的结果如图 3所示.

图3(Figure 3)

图3 不同晶圆流批异化率下R与晶圆数目的关系 Fig. 3 The relationship between R and N with different df

图 3显示不同晶圆流批异化率情况下，随着加工晶圆数量增加，R值呈现先上升后逐渐趋于稳定.实际工程应用中，一般批量设置为25片左右，右半段(批量大于10)更具参考价值.

CT=3；MH=4；t_M=4；df=0.6；处理时间分别服从P～N(20,10),P～N(40,10)，P～N(60,10)，U～N(30,5).结果见图 4.

图4(Figure 4)

图4 处理时间波动下R与晶圆数目的关系 Fig. 4 The relationship between R and N with different P

图 4显示在处理时间波动的情况下R与晶圆数目的关系.由于处理时间与搬运时间差别较小,E(P)=20曲线波动较大，图 4中E(P)=40和E(P)=60的两条曲线的走向趋势基本一致的，说明算法对不同驻留约束时间的适应性.

令CT=3；MH=4；t_M=4；df=0.6；P～N(40,10).驻留约束时间分别服从U～N(10,5),U～N(20,5),U～N(30,5).结果见图 5.

图5(Figure 5)

图5 驻留约束时间波动下R与晶圆数目的关系 Fig. 5 The relationship between R and N with different U

图 5显示在驻留约束时间波动的情况下R与晶圆数目的关系.一般情况下，驻留约束时间越短，调度越严格，所需加工时间可能越长，图 5的结果与此相符.随着每批晶圆数目增大，R不断减小，说明该算法在批量较大时有较好的调度效果.

1) 本文算法可以有效地解决单臂MCTs调度中存在的多品种加工以及晶圆驻留问题，特别为客户需求多样化问题提供了良好的解决方案.

2) 批量较小(每批少于10片)得出算法仿真运行时间非常小，可有效地进行实时调度，即使批量较大也满足调度的要求，证明了算法的高效性.

3) 对于晶圆加工时间、驻留时间波动性和晶圆流模式的仿真证明算法对不同的晶圆加工数据具有非常好的适应性.