带并行腔和重入约束的双臂集束型设备调度方法

工程科学学报，第38卷，第8期：1190-1195,2016年8月 Chinese Journal of Engineering,Vol.38,No.8:1190-1195,August 2016 D0l:10.13374/j.issn2095-9389.2016.08.020:http://journals..ustb.edu.cn 带并行腔和重入约束的双臂集束型设备调度方法 周炳海四，黎 明，苏谊 同济大学机械与能源工程学院，上海201804 ☒通信作者，E-mail:bhzhou@tongji.edu.cn 摘要为有效解决半导体制造业中带并行腔和重入约束的双臂集束型设备调度问题，提出一种以优化搜索为核心的调度 方法.首先，引入优化FIFO(first in first out)搜索规则，并以系统总完工时间最小化作为目标，建立带并行腔和重入约束的四 加工腔双臂集束型设备调度数学模型.在此基础之上，结合虚拟缓冲模块的概念，提出一种基于机械臂交换策略的优化搜索 算法.最后，对所提出的算法进行仿真实验，实验结果表明该算法是可行且有效的 关键词调度方法：集束型设备：并行腔：重入 分类号TP391 Scheduling method for dual-blade cluster tools with parallel chambers and reentrancy constraints ZHO0 Bing-hat≌，LI Ming,SUi School of Mechanical Engineering,Tongji University,Shanghai 201804,China Corresponding author,E-mail:bhzhou@tongji.edu.cn ABSTRACT To effectively solve the scheduling problems of dual-blade cluster tools with parallel processing chambers and reentran- cy constraints in semiconductor manufacturing,this article introduces a scheduling method centering on optimal searching.Firstly, according to the optimization search rule (FIFO),a mathematical programming model of 4-ehamber dual-blade cluster tools with paral- lel processing chambers and reentrancy constraints was built to minimize the makespan of the system.Combined with the concept of virtual buffer module,an optimum searching algorithm was proposed based on the robot swap strategy.Finally,simulation experiments were conducted for the proposed algorithm,and the results indicate that the algorithm is feasible and effective. KEY WORDS scheduling methods:cluster tools:parallel chambers:reentrancy 半导体制造行业中，集束型设备广泛用于晶圆的 提出一种搜索可行机械手运行路径的调度方法，但其 加工制造过程.晶圆加工工序复杂繁多，常常一片晶 假设晶圆重入次数最多为一次.Zu等0研究了考虑 圆需要多次重复进入同一加工腔进行加工，例如原子 晶圆多次重入的集束型设备调度，并提出了一种启发 层沉积(atomic layer deposition,ALD)过程m.晶圆重 式算法使系统总完工时间最小化.Zhou和Si进一 入大大增加了集束型设备调度的复杂性. 步在含有多机械手同时作业的多集束型设备群中研究 目前为止，考虑晶圆重入约束的单臂束集束型设 重入的影响，建立了双集束型设备的非线性规划模型， 备的调度研究已相对成熟.Lee等回建立单臂集束型 并提出分解求解的方法 设备Peni网模型，验证了防止重入现象引起死锁的充 为了提高集束型设备运行效率，双臂集束型设备 分必要条件，并采用线性规划法进行调度求解.Chen 被广泛使用.Qiao等圆通过Peri网建立数学模型，定 和Zhou对三个加工腔的单臂集束型设备进行研究， 义1unit周期调度的方法，对存在驻留或重入约束的 收稿日期：2015-10-23 基金项目：国家自然科学基金资助项目(61273035,71471135)

工程科学学报，第 38 卷，第 8 期: 1190--1195，2016 年 8 月 Chinese Journal of Engineering，Vol． 38，No． 8: 1190--1195，August 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 08． 020; http: / /journals． ustb． edu． cn 带并行腔和重入约束的双臂集束型设备调度方法 周炳海，黎 明，苏 谊 同济大学机械与能源工程学院，上海 201804  通信作者，E-mail: bhzhou@ tongji． edu． cn 摘 要 为有效解决半导体制造业中带并行腔和重入约束的双臂集束型设备调度问题，提出一种以优化搜索为核心的调度 方法． 首先，引入优化 FIFO ( first in first out) 搜索规则，并以系统总完工时间最小化作为目标，建立带并行腔和重入约束的四 加工腔双臂集束型设备调度数学模型． 在此基础之上，结合虚拟缓冲模块的概念，提出一种基于机械臂交换策略的优化搜索 算法． 最后，对所提出的算法进行仿真实验，实验结果表明该算法是可行且有效的． 关键词 调度方法; 集束型设备; 并行腔; 重入 分类号 TP391 Scheduling method for dual-blade cluster tools with parallel chambers and reentrancy constraints ZHOU Bing-hai ，LI Ming，SU Yi School of Mechanical Engineering，Tongji University，Shanghai 201804，China  Corresponding author，E-mail: bhzhou@ tongji． edu． cn ABSTＲACT To effectively solve the scheduling problems of dual-blade cluster tools with parallel processing chambers and reentran￾cy constraints in semiconductor manufacturing，this article introduces a scheduling method centering on optimal searching． Firstly， according to the optimization search rule ( FIFO) ，a mathematical programming model of 4-chamber dual-blade cluster tools with paral￾lel processing chambers and reentrancy constraints was built to minimize the makespan of the system． Combined with the concept of virtual buffer module，an optimum searching algorithm was proposed based on the robot swap strategy． Finally，simulation experiments were conducted for the proposed algorithm，and the results indicate that the algorithm is feasible and effective． KEY WOＲDS scheduling methods; cluster tools; parallel chambers; reentrancy 收稿日期: 2015--10--23 基金项目: 国家自然科学基金资助项目( 61273035，71471135) 半导体制造行业中，集束型设备广泛用于晶圆的 加工制造过程． 晶圆加工工序复杂繁多，常常一片晶 圆需要多次重复进入同一加工腔进行加工，例如原子 层沉积( atomic layer deposition，ALD) 过程［1］． 晶圆重 入大大增加了集束型设备调度的复杂性． 目前为止，考虑晶圆重入约束的单臂束集束型设 备的调度研究已相对成熟． Lee 等［2］建立单臂集束型 设备 Petri 网模型，验证了防止重入现象引起死锁的充 分必要条件，并采用线性规划法进行调度求解． Chen 和 Zhou［3］对三个加工腔的单臂集束型设备进行研究， 提出一种搜索可行机械手运行路径的调度方法，但其 假设晶圆重入次数最多为一次． Zhou 等［4］研究了考虑 晶圆多次重入的集束型设备调度，并提出了一种启发 式算法使系统总完工时间最小化． Zhou 和 Shi［5］进一 步在含有多机械手同时作业的多集束型设备群中研究 重入的影响，建立了双集束型设备的非线性规划模型， 并提出分解求解的方法． 为了提高集束型设备运行效率，双臂集束型设备 被广泛使用． Qiao 等［6］通过 Petri 网建立数学模型，定 义 1-unit 周期调度的方法，对存在驻留或重入约束的

周炳海等：带并行腔和重入约束的双臂集束型设备调度方法 ·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 ·

·1192· 工程科学学报，第38卷，第8期 PM PM PM 图1品圆加工路径流程图 Fig.1 Flow chart of the wafer processing route T4-Th≥20. (4) 在机械手上停留时间的长短判断其虚拟化状态 结合假设④可知，晶圆离开上一个加工腔至少需 判定规则如下： 要经历一次机械手搬运时间日到达下一个加工腔开始 (1)当晶圆在机械手上停留时间1，=0时，机械手 加工： 不进行虚拟化，仅作为搬运模块： Ta-T-a≥. (5) (2)当晶圆在机械手上停留时间1，>0时，机械手 晶圆在加工腔内的加工时间约束： 虚拟化为缓冲模块VBM. Ti=Tij+Phj (6) 定义2优化FIFO(first in first out)规则：在下一 由假设⑤可知，加工过程中存在重入现象，晶圆在 道工序空闲的情况下，晶圆完成加工后，机械手首先搬 同一加工腔加工必须等上一次加工完成才能开始下一 运该晶圆到下一道工序加工：当有两片晶圆同时完成 次重入加工： 加工且都可行，那么首先搬运后一道工序的晶圆 T-TA≥h+20. (7) 本文提出了一种基于搜索的结构式算法(struc-- 调度目标是最小化晶圆加工的总完工时间： tured algorithm).其调度的主要原理是：先将未加工的 min (TLx). (8) 晶圆依次从真空锁搬运到加工腔加工，并记录各晶圆 由上可知，本文提出的调度问题是以式(8)为目 的完成时刻。再搜索所有的完成时刻，记录完成时刻 标，式(1)~(7)为约束条件的非线性规划问题. 最早的晶圆，通过判断机械手状态A和加工腔状态 2算法构建 ,推导出晶圆在机械手上停留时间，对双臂作选择 性虚拟化处理.同时，结合优化FFO(first in first out) 双臂集束型设备的机械手，在调度晶圆时一般有 规则，决策算法的下一个步骤是搬运晶圆还是在剩下 两个作用：搬运与缓冲.为了提高集束型设备的利用 的晶圆中重新选择下一个最早完成时间的晶圆，直到 率，本文引入文献I3]中虚拟缓冲模块(virtual buffer 完成将最后一片晶圆搬运真空锁模块 module,VBM)概念，将双臂集束型设备转换成带缓冲 由算法的中心思想可知，每次搜索出的晶圆的离 的单臂集束型设备，如图2所示.同时根据晶圆状态 开时间由上一片晶圆的开始加工时间决定，记录晶圆 对集束型设备的双臂作选择性虚拟化(selective virtu-- 在新加工腔的开始时间为T1,,则晶圆的开始时间、 alization)处理. 离开时间的计算如下，即机械手搬运晶圆的序列按以 下情况分析 VBM (1)当W,离开PM1时且2=0，A=0,满足以下 约束： RM Ta=max(Tia+l,T+2。+l+w）, (9) PM, Ta=Ta+,+山， (10) BM T1A=Th+n+儿 (11) (2)当W:离开PM1时且2=1，A=0,满足以下 约束： 图2虚拟化示意图 Fig.2 Virtualization sketch map of the wafer flow Tij max (Tij+l,T++), (12) Ticlgj Tigjh +lm+L. (13) 定义1选择性虚拟化(selective virtualization):根 (3)当W,离开PM,时且点2=0，A=1,满足以下 据晶圆在调度中的状况，将双臂机械手的其中一个机 约束： 械手选择性作为虚拟缓冲模块或搬运模块，根据晶圆 Tijh max(Tij+l,Tm+, (14)

工程科学学报，第 38 卷，第 8 期 图 1 晶圆加工路径流程图 Fig． 1 Flow chart of the wafer processing route Tb i + 1，j，h － Tl i，j，h≥2θ． ( 4) 结合假设④可知，晶圆离开上一个加工腔至少需 要经历一次机械手搬运时间 θ 到达下一个加工腔开始 加工: Tb i，j，h － Tl i，j － 1，h≥θ． ( 5) 晶圆在加工腔内的加工时间约束: Tc i，j，h = Tb i，j，h + Ph i，j ． ( 6) 由假设⑤可知，加工过程中存在重入现象，晶圆在 同一加工腔加工必须等上一次加工完成才能开始下一 次重入加工: Tb i，j，h2 － Tl i，j，h1 ≥Ph1 i，j + 2θ． ( 7) 调度目标是最小化晶圆加工的总完工时间: min( TLN ) ． ( 8) 由上可知，本文提出的调度问题是以式( 8) 为目 标，式( 1) ～ ( 7) 为约束条件的非线性规划问题． 2 算法构建 双臂集束型设备的机械手，在调度晶圆时一般有 两个作用: 搬运与缓冲． 为了提高集束型设备的利用 率，本文引入文献［13］中虚拟缓冲模块( virtual buffer module，VBM) 概念，将双臂集束型设备转换成带缓冲 的单臂集束型设备，如图 2 所示． 同时根据晶圆状态 对集束型设备的双臂作选择性虚拟化( selective virtu￾alization) 处理． 图 2 虚拟化示意图 Fig． 2 Virtualization sketch map of the wafer flow 定义1 选择性虚拟化( selective virtualization) : 根 据晶圆在调度中的状况，将双臂机械手的其中一个机 械手选择性作为虚拟缓冲模块或搬运模块，根据晶圆 在机械手上停留时间的长短判断其虚拟化状态． 判定规则如下: ( 1) 当晶圆在机械手上停留时间 ts = θ 时，机械手 不进行虚拟化，仅作为搬运模块; ( 2) 当晶圆在机械手上停留时间 ts ＞ θ 时，机械手 虚拟化为缓冲模块 VBM． 定义 2 优化 FIFO ( first in first out) 规则: 在下一 道工序空闲的情况下，晶圆完成加工后，机械手首先搬 运该晶圆到下一道工序加工; 当有两片晶圆同时完成 加工且都可行，那么首先搬运后一道工序的晶圆． 本文提出了一种基于搜索的结构式算法( struc￾tured algorithm) ． 其调度的主要原理是: 先将未加工的 晶圆依次从真空锁搬运到加工腔加工，并记录各晶圆 的完成时刻． 再搜索所有的完成时刻，记录完成时刻 最早的晶圆，通过判断机械手状态 A 和加工腔状态 ξj( q) ，推导出晶圆在机械手上停留时间，对双臂作选择 性虚拟化处理． 同时，结合优化 FIFO ( first in first out) 规则，决策算法的下一个步骤是搬运晶圆还是在剩下 的晶圆中重新选择下一个最早完成时间的晶圆，直到 完成将最后一片晶圆搬运真空锁模块． 由算法的中心思想可知，每次搜索出的晶圆的离 开时间由上一片晶圆的开始加工时间决定，记录晶圆 在新加工腔的开始时间为 Tb i，j + 1，h，则晶圆的开始时间、 离开时间的计算如下，即机械手搬运晶圆的序列按以 下情况分析． ( 1) 当 Wi 离开 PM1 时且 ξ2 = 0，A = 0，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + 2tm + l + u) ， ( 9) Tb i + 1，j，h = Tl i，j，h + tz + l， ( 10) Tb i，j + 1，h = Tb i + 1，j，h + tm + l． ( 11) ( 2) 当 Wi 离开 PM1 时且 ξ2 = 1，A = 0，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 12) Tb i + 1，j，h = Tl i，j，h + tm + l． ( 13) ( 3) 当 Wi 离开 PM1 时且 ξ2 = 0，A = 1，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 14) · 2911 ·

周炳海等：带并行腔和重入约束的双臂集束型设备调度方法 *1193· Ta=T+儿。+山， (15) (开始) Ta=T+2。+l+. (16) (4)当W,离开PM2时且专=0，A=1,满足以下 初始化T2 rTirTa 约束： 搜索当前加工腔中巾最早完成 Tij max(Tij+l,T++), (17) 加T的晶圆W记录Tg Ti=Ti+t,+l. (18) Ta=max(Th+1。+l,Th++).（19） T=7+0 =2,h=2? (5)当W,离开PM2时且5=0，A=0,满足以下 否立 是 约束： i<N? A=2? Tij=max (T+lT+), (20) 是 Tijtik Tij +lm+L (21) 输出T (6)当W,离开PM2时且53=1，A=0,满足以下 结束) 下一模块加工腔1w0 约束： 是 Ti max(Ti +l,T+t+D). (22) 释放当前机械于中品圆到可行加工控 (7)当W,离开PM2时且点=1，A=1,满足以下 约束： A=1? Tij max (+T+), (23) 是 Ta=T++1. (24) 香 搬运W到下一工序，计算 (8)当W,离开PM,时且2=0，A=0,满足以下 加工腔？ TT4Th记录TnA 约束： 是 Tij.s max (TD), (25) Wn和W执行swap操作，计算T,. T-la=Tb+l。+l. (26) TTbe Ti4并i记录Tiin4 (9)当W,离开PM3时且专2=0，A=1,满足以下 约束： 搬离W到机械于暂存 Tij.k max (Ti+lT++), (27) 图3算法流程图 Tiiv=Tij+l+l, (28) Fig.3 Flow chart of the algorithm -h=Ta+.+儿， (29) j=+l (30) 第4步判断i=N,j=2且h=2是否成立.若 (10)当W,离开PM3时且2=1，A=0,满足以下 是，则转入第9步；否则转入下一步. 约束 第5步判断机械手状态和下道工序加工腔状 Tij max (Ti+T++). (31) 态.若为A=2,Gwg=1,则回到第3步重新搜索：若 (11)当W,离开PM3时且2=1，A=1,满足以下 为A=2,专G)0=0,则释放当前机械手晶圆至可行加 约束： 工腔：若为A<2,表明存在空闲机械手，则转入下 Tijh max (Tij+l,T++l), (32) 一步 Ticij Tij +t+l (33) 第6步判断机械手臂空闲的数量.若A=1,则 在计算晶圆的离开时间时，还有几种情况上述并 转入第7步：若A=0,转入第8步 未详细说明，如果算法的下一个步骤是晶圆W,离开 第7步判断机械手上现有晶圆W:的下一道工 PM,机械手上有晶圆暂存，但是它的下一道工序并不 序的加工腔和W的加工腔是否相同.否是，则对W, 在PM上加工，此时机械手的操作序列和上述I1种情 和Wn执行swap操作：搬离Wn到机械手上，将W,释 况都不同.图3为算法流程图 放到加工腔上加工，再释放W到下一道工序的加工 算法具体步骤如下： 腔加工，记录W,和W的完成时间，转到第3步：否则 第1步基本参数输入，初始化各变量. 搬离W到下一道工序的加工腔加工，并记录W的 第2步计算系统瞬时状态下各加工腔中晶圆的 完成时间，转到第3步： 完成加工时间. 第8步搬离W到机械手暂存，转到第3步； 第3步搜索最早完成加工的晶圆W,并记录 第9步令Tu=Th+0,输出Tu: 其T 第10步结束算法

周炳海等: 带并行腔和重入约束的双臂集束型设备调度方法 Tb i，j + 1，h = Tl i，j，h + tm + l， ( 15) Tb i + 1，j，h = Tb i，j，h + 2tm + l + u． ( 16) ( 4) 当 Wi 离开 PM2 时且 ξ3 = 0，A = 1，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 17) Tb i + 1，j，h = Tl i，j，h + tz + l， ( 18) Tb i，j + 1，h = max( Tb i + 1，j，h + tm + l，Tl i，j，h + tm + l) ． ( 19) ( 5) 当 Wi 离开 PM2 时且 ξ3 = 0，A = 0，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 20) Tb i，j + 1，h = Tl i，j，h + tm + l． ( 21) ( 6) 当 Wi 离开 PM2 时且 ξ3 = 1，A = 0，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ． ( 22) ( 7) 当 Wi 离开 PM2 时且 ξ3 = 1，A = 1，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 23) Tb i + 1，j，h = Tl i，j，h + tz + l． ( 24) ( 8) 当 Wi 离开 PM3 时且 ξ2 = 0，A = 0，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 25) Tb i，j － 1，h = Tl i，j，h + tm + l． ( 26) ( 9) 当 Wi 离开 PM3 时且 ξ2 = 0，A = 1，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 27) Tb i + 1，j，h = Tl i，j，h + tz + l， ( 28) Tb i，j － 1，h = Tb i + 1，j，h + tm + l， ( 29) Tb i，j + 1，h = Tl i + 1，j，h + tm + l． ( 30) ( 10) 当 Wi 离开 PM3 时且 ξ2 = 1，A = 0，满足以下 约束 Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ． ( 31) ( 11) 当 Wi 离开 PM3 时且 ξ2 = 1，A = 1，满足以下 约束: Tl i，j，h = max( Tc i，j，h + l，Tnew + tm + l) ， ( 32) Tb i + 1，j，h = Tl i，j，h + tz + l． ( 33) 在计算晶圆的离开时间时，还有几种情况上述并 未详细说明，如果算法的下一个步骤是晶圆 Wi 离开 PMj ，机械手上有晶圆暂存，但是它的下一道工序并不 在 PMj 上加工，此时机械手的操作序列和上述 11 种情 况都不同． 图 3 为算法流程图． 算法具体步骤如下: 第 1 步 基本参数输入，初始化各变量． 第 2 步 计算系统瞬时状态下各加工腔中晶圆的 完成加工时间． 第 3 步 搜索最早完成加工的晶圆 Wmin，并记录 其 Tc i，j，h ． 图 3 算法流程图 Fig． 3 Flow chart of the algorithm 第 4 步 判断 i = N，j = 2 且 h = 2 是否成立． 若 是，则转入第 9 步; 否则转入下一步． 第 5 步 判断机械手状态和下道工序加工腔状 态． 若为 A = 2，ξ( j + 1) ( q) = 1，则回到第 3 步重新搜索; 若 为 A = 2，ξ( j + 1) ( q) = 0，则释放当前机械手晶圆至可行加 工腔; 若 为 A ＜ 2，表 明 存 在 空 闲 机 械 手，则 转 入 下 一步． 第 6 步 判断机械手臂空闲的数量． 若 A = 1，则 转入第 7 步; 若 A = 0，转入第 8 步． 第 7 步 判断机械手上现有晶圆 Wi 的下一道工 序的加工腔和 Wmin的加工腔是否相同． 否是，则对 Wi 和 Wmin执行 swap 操作: 搬离 Wmin到机械手上，将 Wi 释 放到加工腔上加工，再释放 Wmin到下一道工序的加工 腔加工，记录 Wi 和 Wmin的完成时间，转到第 3 步; 否则 搬离 Wmin到下一道工序的加工腔加工，并记录 Wmin的 完成时间，转到第 3 步; 第 8 步 搬离 Wmin到机械手暂存，转到第 3 步; 第 9 步 令 TLi = Tl i，j，h + θ，输出 TLi ; 第 10 步 结束算法． · 3911 ·

·1194 工程科学学报，第38卷，第8期 3仿真实验及分析 170 160 150 为了有效地评价本文提出的算法，选取swap策略 140 构建算法的平均周期作为比较基准.现有文献4]已 130 120 证明，对于不带重入与并行腔约束限制的双臂集束型 ÷110 设备来说，sw即策略是其基本的调度策略，并且已经 100 90 是被证明的优化的调度策略).相关的符号定义 80 748494104114124134144 如下. 并行腔的加工时间/ PR CT-CT四，表示本文的算法相对于基于 图5并行腔对调度的影响 CT Fig.5 Effect of parallel chambers on scheduling sw即策略的一般算法的调度算法的提高率，晶圆总完 工时间的减少率 由图5知：当并行腔的加工时间在74,94幻之间 CTro=makespan(FIFO) 时，本文的算法和基于sw即策略的算法求得的平均周 N 表示本文算法的平均 期相同：当并行腔的加工时间在大于94时，本文的算 周期 法得到的平均周期较优，且并行腔的加工时间越长，本 CT-makespan (swap) 文的算法得到的结果越优 表示基于swa即策略的 3.3重入对算法的影响 一般算法的平均周期 令晶圆的加工时间分别服从P~U(50,100), 3.1算法的运行时间 P-U(70,130),P~U(90,150),tm=t,=1:依次令 本文提出的算法运用Visual studio2013软件 晶圆的数目为15、20、25、30、35和40，分别求解得到 (C++语言)编程实现. PR如图6示（图中PR1、PR2和PR3分别代表P~ 仿真环境为主频2.0GHz,内存为4GB的便携式 U(50,100)、P-U(70,130)和P-U(90,150). 计算机.实验设计如下：P,~U(70,110),t。=t.=1, 0.25r 一PR1一◆—PR2★—PR3 令晶圆的数目分别为5、10、15、20、25、30、35、40、45和 0.20 50.调度结果的时间如图4. 0.15 ◆一 0.07 ◆◆ 0.06 0.10 0.05 0.05 0.04 15 20 25303540 0.03 品圆数 0.02 图6重入对调度的影响 0.01 Fig.6 Effect of reentrancy on scheduling 5 101520253035404550 由图6知，PR值在0.05~0.25之间，表明本文的 品数 算法求解的值比对比的算法求解的值优，其提高率为 图4算法运行时间 Fig.4 Running time of the algorithm 5%~25%之间.通过比较可知，晶圆总体的加工时间 越短，算法的提高率越大，重入对算法的影响越大 由图4知，随着晶圆数量的增加，算法的运行时间 以非负的形式递增，但未超过0.1s.当一次处理25片 4实例分析 (一个lot)晶圆时，算法的运行时间为0.05s,可知算法 晶圆的加工工艺路径如图1所示，P.=74,P2= 产生调度解的时间是非常短的，适合于对晶圆进行实 97,P3=64,P22=54,tm=t=1,N=25.程序运行的 时调度 结果为：总完工时间为2183s,CTo=87.32,PR= 3.2并行腔对算法的影响 19.21%.晶圆加工的甘特图如图7.从图中可以看 令P~0(70,110),tm=t.=1,N=25,其中并行 出，本算法对加工腔的利用率和平衡率都很高.其中 腔的加工时间为74、84、94、104、114、124、134和144s, RM行表示双臂机械手的利用时间，RM模块与PM模 分别计算本文算法和对比算法求得调度的平均周期 块在时间上的重叠区表示此区域其中一个机械手中有 CTo和CT的结果如图5所示. 缓冲晶圆

工程科学学报，第 38 卷，第 8 期 3 仿真实验及分析 为了有效地评价本文提出的算法，选取 swap 策略 构建算法的平均周期作为比较基准． 现有文献［14］已 证明，对于不带重入与并行腔约束限制的双臂集束型 设备来说，swap 策略是其基本的调度策略，并且已经 是被证 明 的 优 化 的 调 度 策 略［3］． 相 关 的 符 号 定 义 如下． PＲ = CTswap － CTFIFO CTswap ，表示本文的算法相对于基于 swap 策略的一般算法的调度算法的提高率，晶圆总完 工时间的减少率． CTFIFO = makespan( FIFO) N ，表示本文 算 法 的 平 均 周期． CTswap = makespan( swap) N ，表示 基 于 swap 策 略 的 一般算法的平均周期． 3. 1 算法的运行时间 本文 提 出 的 算 法 运 用 Visual studio 2013 软 件 ( C + + 语言) 编程实现． 仿真环境为主频 2. 0 GHz，内存为 4 GB 的便携式 计算机． 实验设计如下: Ph i，j ～ U( 70，110) ，tm = tz = 1， 令晶圆的数目分别为 5、10、15、20、25、30、35、40、45 和 50． 调度结果的时间如图 4． 图 4 算法运行时间 Fig． 4 Ｒunning time of the algorithm 由图 4 知，随着晶圆数量的增加，算法的运行时间 以非负的形式递增，但未超过 0. 1 s． 当一次处理 25 片 ( 一个 lot) 晶圆时，算法的运行时间为0. 05 s，可知算法 产生调度解的时间是非常短的，适合于对晶圆进行实 时调度． 3. 2 并行腔对算法的影响 令 Ph i，j ～ U( 70，110) ，tm = tz = 1，N = 25，其中并行 腔的加工时间为 74、84、94、104、114、124、134 和 144 s， 分别计算本文算法和对比算法求得调度的平均周期 CTFIFO和 CTswap的结果如图 5 所示． 图 5 并行腔对调度的影响 Fig． 5 Effect of parallel chambers on scheduling 由图 5 知: 当并行腔的加工时间在［74，94］之间 时，本文的算法和基于 swap 策略的算法求得的平均周 期相同; 当并行腔的加工时间在大于 94 时，本文的算 法得到的平均周期较优，且并行腔的加工时间越长，本 文的算法得到的结果越优． 3. 3 重入对算法的影响 令晶圆的加工时间分别服从 Ph i，j ～ U( 50，100) ， Ph i，j ～ U( 70，130) ，Ph i，j ～ U( 90，150) ，tm = tz = 1; 依次令 晶圆的数目为 15、20、25、30、35 和 40，分别求解得到 PＲ 如图 6 示( 图中 PＲ1、PＲ2 和 PＲ3 分别代表Ph i，j ～ U( 50，100) 、Ph i，j ～ U( 70，130) 和 Ph i，j ～ U( 90，150) ． 图 6 重入对调度的影响 Fig． 6 Effect of reentrancy on scheduling 由图 6 知，PＲ 值在 0. 05 ～ 0. 25 之间，表明本文的 算法求解的值比对比的算法求解的值优，其提高率为 5% ～ 25% 之间． 通过比较可知，晶圆总体的加工时间 越短，算法的提高率越大，重入对算法的影响越大． 4 实例分析 晶圆的加工工艺路径如图 1 所示，P1 i，1 = 74，P1 i，2 = 97，P1 i，3 = 64，P2 i，2 = 54，tm = tz = 1，N = 25． 程序运行的 结果为: 总 完 工 时 间 为 2183 s，CTFIFO = 87. 32，PＲ = 19. 21% ． 晶圆加工的甘特图如图 7． 从图中可以看 出，本算法对加工腔的利用率和平衡率都很高． 其中 ＲM 行表示双臂机械手的利用时间，ＲM 模块与 PM 模 块在时间上的重叠区表示此区域其中一个机械手中有 缓冲晶圆． · 4911 ·

周炳海等：带并行腔和重入约束的双臂集束型设备调度方法 ·1195· PMI PM2(1) PM2(2) W.3 W PM3 RM 317 375404 48406 1568 564597 1668 440 644 497 724 578 时间店 图7计算实例甘特图 Fig.7 Gant chart of the example Univ Nat Sci,2013,34(9):1305 5结论 (周炳海，石满铭.带重入约束的双集束型晶圆制造设备调度 算法.东北大学学报（自然科学版），2013,34(9)：1305) (1)算法有效地解决了重入与并行腔共存而存在 [6]Qiao Y,Wu N Q,Zhou M C,et al.Petri net-based scheduling 的冲突和死锁问题，为此类集束型设备的调度问题提 analysis of dual-arm cluster tools subject to wafer revisiting and 出一种有效的求解方法. residency time constraints /2013 IEEE 10th International Con- ference on Networking,Sensing and Control.Evry,2013:252 (2)算法的运行时间以非负的形式递增，但未超 [7]Kim HJ,Lee J H,Lee T E.Noncyclic scheduling of cluster tools 过0.1$，可有效地进行实时调度，证明算法的高效性. with a branch and bound algorithm.IEEE Trans Autom Sci Eng, (3)通过分析比较可知：晶圆总体的加工时间越 2015,12(2):690 8] Zhou B H,Gao Z S,Chen J.Scheduling algorithm of dual-armed 短，算法的提高率越大，重入对算法的影响越大：同时， cluster tools with residency time and reentrant constraints.J Cent 并行腔的加工时间越长，本文的算法得到的结果越优 South Unit,2012,18(12):2667 (4)对于晶圆加工时间波动性、并行腔和重入的 9]Geng Y F,Kang K,Liu J,et al.Manufacturing schedule of dual- armed cluster tools based on heuristic search//IEEE Internation- 仿真实验证明算法对不同的加工数据和设备具有非常 al Conference on Industrial Technology,ICIT 2008.Chengdu, 好的适应性 2008:1 [10]Lu R,Li L Y.Research on scheduling problem of cluster tools with 参考文献 residency time constraints.J Syst Simul,2014,26(8):1775 (卢容，李林瑛。有品圆滞留时间约束的集束型装备调度问 []Odrey NC.Green JD,Appello A.A generalized Petri net modeling 题研究.系统仿真学报，2014,26(8)：1775) approach for the co of reeran flow semiconductor wafer fabri- [11]Kim D K,Jung Y J,Jung C,et al.Cyclie scheduling of cluster cation.Rob Comput Integr Manuf.2001,17(1):5 2]Lee HY,Lee T E.Scheduling single-arm cluster tools with reentrant tools with non-identical chamber access times between parallel chambers.IEEE Trans Semicond Manuf,2012,25(3):420 wafer flows.IEEE Trans Semicond Manuf,2006,19(2):226 [12]Zheng X H,Yu H B,Hu J T.A general throughput model for par- B3]Chen J.Zhou B H.Scheduling algorithm for cluster tools with res allel cluster tools /International Colloquium on Computing,Com- idency and reentrant constraints.Comput Integr Manuf Syst, munication,Control,and Management.Melboume,2011:215 2012,18(12):2667 03] Zhou B H,Liu M X,Zhou S M.Scheduling method for dual- (陈佳，周炳海.带驻留与重入约束的集束型设备调度算法 blade multi-cluster tools with residency constraints.IHarbin Inst 计算机集成制造系统，2012,18(12)：2667) Technol,2014,46(1):83 [4]Zhou B H,Wang Z,Chen J.Scheduling method for singlearm (周炳海，刘明样，周淑美。带驻留约束的双臂集束型设备 cluster tools of wafer fabrications with residency and continuous re- 群的调度方法.哈尔滨工业大学学报，2014,46(1)：83) entrancy.J Southeast Unig Engl Ed,2013,29(2):187 [14]Venkatesh S,Davenport R,Foxhoven P,et al.A steady-state [5]Zhou B H,Shi X M.Scheduling algorithm for double-cluster tools throughput analysis of cluster tools:dual-blade versus single- of wafer fabrication system with reentrant constraints.J Northeast blade robots.IEEE Trans Semicond Manuf,1997,10(4):418

周炳海等: 带并行腔和重入约束的双臂集束型设备调度方法 图 7 计算实例甘特图 Fig． 7 Gant chart of the example 5 结论 ( 1) 算法有效地解决了重入与并行腔共存而存在 的冲突和死锁问题，为此类集束型设备的调度问题提 出一种有效的求解方法． ( 2) 算法的运行时间以非负的形式递增，但未超 过 0. 1 s，可有效地进行实时调度，证明算法的高效性． ( 3) 通过分析比较可知: 晶圆总体的加工时间越 短，算法的提高率越大，重入对算法的影响越大; 同时， 并行腔的加工时间越长，本文的算法得到的结果越优． ( 4) 对于晶圆加工时间波动性、并行腔和重入的 仿真实验证明算法对不同的加工数据和设备具有非常 好的适应性． 参 考 文 献 ［1］ Odrey N G，Green J D，Appello A． A generalized Petri net modeling approach for the control of re-entrant flow semiconductor wafer fabri￾cation． Ｒob Comput Integr Manuf，2001，17( 1) : 5 ［2］ Lee H Y，Lee T E． Scheduling single-arm cluster tools with reentrant wafer flows． IEEE Trans Semicond Manuf，2006，19( 2) : 226 ［3］ Chen J，Zhou B H． Scheduling algorithm for cluster tools with res￾idency and reentrant constraints． Comput Integr Manuf Syst， 2012，18( 12) : 2667 ( 陈佳，周炳海． 带驻留与重入约束的集束型设备调度算法． 计算机集成制造系统，2012，18( 12) : 2667) ［4］ Zhou B H，Wang Z，Chen J． Scheduling method for single-arm cluster tools of wafer fabrications with residency and continuous re￾entrancy． J Southeast Univ Engl Ed，2013，29( 2) : 187 ［5］ Zhou B H，Shi X M． Scheduling algorithm for double-cluster tools of wafer fabrication system with reentrant constraints． J Northeast Univ Nat Sci，2013，34( 9) : 1305 ( 周炳海，石潇铭． 带重入约束的双集束型晶圆制造设备调度 算法． 东北大学学报( 自然科学版) ，2013，34( 9) : 1305) ［6］ Qiao Y，Wu N Q，Zhou M C，et al． Petri net-based scheduling analysis of dual-arm cluster tools subject to wafer revisiting and residency time constraints / / 2013 IEEE 10th International Con￾ference on Networking，Sensing and Control． Evry，2013: 252 ［7］ Kim H J，Lee J H，Lee T E． Noncyclic scheduling of cluster tools with a branch and bound algorithm． IEEE Trans Autom Sci Eng， 2015，12( 2) : 690 ［8］ Zhou B H，Gao Z S，Chen J． Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints． J Cent South Univ，2012，18( 12) : 2667 ［9］ Geng Y F，Kang K，Liu J，et al． Manufacturing schedule of dual￾armed cluster tools based on heuristic search / / IEEE Internation￾al Conference on Industrial Technology，ICIT 2008． Chengdu， 2008: 1 ［10］ Lu Ｒ，Li L Y． Ｒesearch on scheduling problem of cluster tools with residency time constraints． J Syst Simul，2014，26( 8) : 1775 ( 卢睿，李林瑛． 有晶圆滞留时间约束的集束型装备调度问 题研究． 系统仿真学报，2014，26( 8) : 1775) ［11］ Kim D K，Jung Y J，Jung C，et al． Cyclic scheduling of cluster tools with non-identical chamber access times between parallel chambers． IEEE Trans Semicond Manuf，2012，25( 3) : 420 ［12］ Zheng X H，Yu H B，Hu J T． A general throughput model for par￾allel cluster tools / / International Colloquium on Computing，Com￾munication，Control，and Management． Melbourne，2011: 215 ［13］ Zhou B H，Liu M X，Zhou S M． Scheduling method for dual￾blade multi-cluster tools with residency constraints． J Harbin Inst Technol，2014，46( 1) : 83 ( 周炳海，刘明祥，周淑美． 带驻留约束的双臂集束型设备 群的调度方法． 哈尔滨工业大学学报，2014，46( 1) : 83) ［14］ Venkatesh S，Davenport Ｒ，Foxhoven P，et al． A steady-state throughput analysis of cluster tools: dual-blade versus single￾blade robots． IEEE Trans Semicond Manuf，1997，10( 4) : 418 · 5911 ·