周炳海等：带并行腔和重入约束的双臂集束型设备调度方法 ·1191· 双臂集束型设备调度问题进行研究.Kim等切对比了 时刻： 不带约束与带驻留约束和重入约束相结合的双臂集束 T一第i片晶圆在PM内第h次的加工的开始 型设备调度问题，并采用分支定界法求解出晶圆的最 时间； 小完工时间.Zhou等在文献B]的基础上进一步将 T,一第i片晶圆在PM,内的加工的开始时间集 搜索可行机械手运行路径的方法应用于带驻留约束和 合，T={T1,T2’…,T}； 重入的双臂集束型设备的调度问题.Geng等在考 T一第i片晶圆在PM内第h次的加工的完成 虑驻留约束和重入的条件下提出了几种不同的启发式 时间： 搜索算法，并进行比较分析.上述文献模型中均假设 T一第i片晶圆在PM,内的加工的完成时间集 加工腔为串行连接，并未考虑集束型设备实际工程应 合，T,={T1,T2…,T}: 用中普遍存在的带并行处理腔的调度 T,一第i片晶圆在PM内第h次的加工的实际 并行腔一般设置于半导体晶圆制造过程加工时间 离开时间； 相对较长的处理模块，通过平衡不同工序之间负荷，可 有效提高系统产出。卢睿和李林瑛@研究带并行腔 T,一第i片晶圆在PM,内的加工的实际离开时间 的track系统，构建线性规划模型，并对问题的可调度 集合，T={T1,T2…,T}: 性进行分析，但其解法仅在小规模问题适用.Kim W:一编号为i的晶圆： 等提出考虑晶圆在并行腔中具有不同的加工时间 h一晶圆在加工腔重入的次数，h=1或2： 的集束型设备的最优调度方法.Zheng等构建带并 【一机械手完成一次装载动作的时间： 行腔的集束型设备的throughput模型，并利用时序图 n一晶圆在加工过程中存在的重入工序数； 分析并行腔数量与系统产出的关系 t。一机械手完成一次搬运动作的时间： 上述文献仅分别研究存在重入或并行腔的集束型 ,一机械手完成一次转动的时间； 设备的调度问题，并提出相应的调度方法.但是，在实 一机械手完成一次卸载动作的时间： 际工程应用中两种约束往往同时存在，目前还鲜有相 一机械手完成一片晶圆装载的整体动作的时间， 关文献对同时考虑重入和并行腔集束型设备的调度问 0=lm+1+u: 题进行研究.本文将并行腔和重入相结合，对双臂集 g一加工腔PM,的加工状态， 束型设备的调度进行研究，引入虚拟缓冲模块概念，提 0,加工腔空闲， 出一种基于机械臂交换策略的优化搜索算法 =1,加工腔繁忙. 根据所调度问题，作如下假设：①研究对象是四加 1问题描述 工腔集束型设备，且仅有一个机械手负责搬运（如图1 根据SEMⅡ标准E2196定义，集束型设备由真空 所示)）：②晶圆搬运模块采用双臂机械手，机械手的两 锁模块(oad lock,LL)、机械手搬运模块(robot 臂成180°角放置，不能改变，每次只能搬运一片晶圆： module,RM)以及若干加工模块(process module,PM) ③加工腔最多只能同时加工一片晶圆：④集束型设备 构成，一个加工模块中可能含有一个或多个加工腔. 第二个加工模块存在并行腔，即PM20)和PM2a:⑤加 晶圆由输入真空锁模块(LL)依次进入，经机械手搬 工晶圆的过程中存在重入现象，且属于并行腔重入：⑥ 运在各处理模块加工，加工完成后从输出真空锁模块 晶圆的加工时间远大于机械手的操作时间，但机械手 (Lb)离开. 的操作时间不可忽略：⑦晶圆的加工路径为 本文选用四加工腔的双臂集束型设备，同时考虑 LL.→PM→(PM2a,PM2a）→PM3→ 重入和并行腔模块，基于优化的FO搜索原则建立模 (PM2a,PM22)→LL, 型为清晰描述调度问题，作以下符号及变量定义： 如图1所示. A=0,1,2(A=0表示机械手的两个手臂都空闲， 结合假设②和假设⑥可知，晶圆在任意加工腔的 A=1表示机械手有一个手臂空闲，A=2表示机械手的 任一次的开始时间或结束时间的差值必然大于机械手 两个手臂均忙碌)； 完成一次晶圆装载的整体动作的时间： N一一个批次(Iot)晶圆数量： 1T4-Tk1≥6， (1) PMo一加工模块j的第q个并行腔： 1Tk,-Tl≥0， (2) P,一第i片晶圆在PM内第h次的加工时间： 1T-T≥A (3) T一第i片晶圆完成加工后返回到真空锁模块的 由假设③可知，在同一个加工腔中，后一片晶圆必 时刻： 须是在前一片晶圆离开后才能进入，不能出现晶圆的 T一重新搜索最早完成加工之前机械手的操作 抢占现象：周炳海等: 带并行腔和重入约束的双臂集束型设备调度方法 双臂集束型设备调度问题进行研究． Kim 等［7］对比了 不带约束与带驻留约束和重入约束相结合的双臂集束 型设备调度问题，并采用分支定界法求解出晶圆的最 小完工时间． Zhou 等［8］在文献［3］的基础上进一步将 搜索可行机械手运行路径的方法应用于带驻留约束和 重入的双臂集束型设备的调度问题． Geng 等［9］ 在考 虑驻留约束和重入的条件下提出了几种不同的启发式 搜索算法，并进行比较分析． 上述文献模型中均假设 加工腔为串行连接，并未考虑集束型设备实际工程应 用中普遍存在的带并行处理腔的调度． 并行腔一般设置于半导体晶圆制造过程加工时间 相对较长的处理模块，通过平衡不同工序之间负荷，可 有效提高系统产出． 卢睿和李林瑛［10］研究带并行腔 的 track 系统，构建线性规划模型，并对问题的可调度 性进行 分 析，但其解法仅在小规模问题适用． Kim 等［11］提出考虑晶圆在并行腔中具有不同的加工时间 的集束型设备的最优调度方法． Zheng 等［12］构建带并 行腔的集束型设备的 throughput 模型，并利用时序图 分析并行腔数量与系统产出的关系． 上述文献仅分别研究存在重入或并行腔的集束型 设备的调度问题，并提出相应的调度方法． 但是，在实 际工程应用中两种约束往往同时存在，目前还鲜有相 关文献对同时考虑重入和并行腔集束型设备的调度问 题进行研究． 本文将并行腔和重入相结合，对双臂集 束型设备的调度进行研究，引入虚拟缓冲模块概念，提 出一种基于机械臂交换策略的优化搜索算法． 1 问题描述 根据 SEMI 标准 E21-96 定义，集束型设备由真空 锁模 块 ( load lock，LL ) 、机 械 手 搬 运 模 块 ( robot module，ＲM) 以及若干加工模块( process module，PM) 构成，一个加工模块中可能含有一个或多个加工腔． 晶圆由输入真空锁模块( LLa) 依次进入，经机械手搬 运在各处理模块加工，加工完成后从输出真空锁模块 ( LLb) 离开． 本文选用四加工腔的双臂集束型设备，同时考虑 重入和并行腔模块，基于优化的 FIFO 搜索原则建立模 型． 为清晰描述调度问题，作以下符号及变量定义: A = 0，1，2( A = 0 表示机械手的两个手臂都空闲， A = 1表示机械手有一个手臂空闲，A = 2 表示机械手的 两个手臂均忙碌) ; N—一个批次( lot) 晶圆数量; PMj( q) —加工模块 j 的第 q 个并行腔; Ph i，j —第 i 片晶圆在 PMj 内第 h 次的加工时间; TLi—第 i 片晶圆完成加工后返回到真空锁模块的 时刻; Tnew—重新搜索最早完成加工之前机械手的操作 时刻; Tb i，j，h—第 i 片晶圆在 PMj 内第 h 次的加工的开始 时间; Tb i，j —第 i 片晶圆在 PMj 内的加工的开始时间集 合，Tb i，j = { Tb i，j，1，Tb i，j，2，…，Tb i，j，n } ; Tc i，j，h—第 i 片晶圆在 PMj 内第 h 次的加工的完成 时间; Tc i，j —第 i 片晶圆在 PMj 内的加工的完成时间集 合，Tc i，j = { Tc i，j，1，Tc i，j，2，…，Tc i，j，n } ; Tl i，j，h—第 i 片晶圆在 PMj 内第 h 次的加工的实际 离开时间; Tl i，j —第 i 片晶圆在 PMj 内的加工的实际离开时间 集合，Tl i，j = { Tl i，j，1，Tl i，j，2，…，Tl i，j，n } ; Wi—编号为 i 的晶圆; h—晶圆在加工腔重入的次数，h = 1 或 2; l—机械手完成一次装载动作的时间; n—晶圆在加工过程中存在的重入工序数; tm—机械手完成一次搬运动作的时间; tz—机械手完成一次转动的时间; u—机械手完成一次卸载动作的时间; θ—机械手完成一片晶圆装载的整体动作的时间， θ = tm + l + u; ξj( q) —加工腔 PMj( q) 的加工状态， ξj( q) = 0， 加工腔空闲， {1， 加工腔繁忙． 根据所调度问题，作如下假设: ①研究对象是四加 工腔集束型设备，且仅有一个机械手负责搬运( 如图 1 所示) ; ②晶圆搬运模块采用双臂机械手，机械手的两 臂成 180°角放置，不能改变，每次只能搬运一片晶圆; ③加工腔最多只能同时加工一片晶圆; ④集束型设备 第二个加工模块存在并行腔，即 PM2( 1) 和 PM2( 2) ; ⑤加 工晶圆的过程中存在重入现象，且属于并行腔重入; ⑥ 晶圆的加工时间远大于机械手的操作时间，但机械手 的操作时间不可忽略; ⑦晶圆的加工路径为 LLa→PM1→( PM2( 1) ，PM2( 2) ) →PM3→ ( PM2( 1) ，PM2( 2) ) →LLb， 如图 1 所示． 结合假设②和假设⑥可知，晶圆在任意加工腔的 任一次的开始时间或结束时间的差值必然大于机械手 完成一次晶圆装载的整体动作的时间: | Tb i1，j1，h1 － Tb i2，j2，h2 | ≥θ， ( 1) | Tc i1，j1，h1 － Tc i2，j2，h2 | ≥θ， ( 2) | Tb i1，j1，h1 － Tl i2，j2，h2 | ≥θ． ( 3) 由假设③可知，在同一个加工腔中，后一片晶圆必 须是在前一片晶圆离开后才能进入，不能出现晶圆的 抢占现象: · 1911 ·