带驻留约束的双臂集束型设备群的调度方法

周炳海，刘明祥，周淑美

（同济大学机械与能源工程学院，201804上海）

随着300 mm晶圆制造技术的问世，集束型设备群正在被越来越广泛地应用于半导体制造过程中.目前，如何优化半导体集束型设备群的调度问题，已成为提升半导体制造系统整体效率的关键途径.对单个集束型设备调度的研究已比较成熟.例如 Perkinson 等［1］和 Venkatesh 等［2］对单个单臂和双臂集束型设备稳态下的产能进行了分析，建立了单臂、双臂集束型设备的分析模型，提出了基础调度周期（fundamental period，FP）的计算方法，并建立了单臂机械手调度的拉动（pull）策略和双臂机械手的交换（SWAP）策略.

研究集束型设备群调度问题的文献报道较少，已有文献主要关注同种晶圆产品在稳态下的调度方法.例如 Yi［3］等在不考虑机械手搬运时间，仅仅考虑集束型设备群加工同种晶圆产品的情况下，对其进行了产能和FP分析，给出了一种分解方法来构建集束型设备群的FP下界，并给出了相应的优化调度方法.Chan［4-5］等在考虑机械手搬运时间为非零情况下，对集束型设备群调度问题进行了研究，构造了一种基于资源约束的分析模型，并给出了相应的调度方法.上述文献主要关注集束型设备群在稳态下的产能分析，且均没有考虑晶圆加工过程中的晶圆在处理腔中的驻留约束现象.文献［6-12］对带驻留约束的单个集束型设备调度问题进行了研究.然而Chan［4-5］等已经指出，集束型设备群调度问题的复杂性使得现有的方法均不能直接推广应用于集束型设备群的调度问题中.文献［13］对带驻留约束的单臂集束型设备群进行了研究，提出了一种基于时间约束集的建模与调度方法.

本文在提出虚拟缓冲模块（virtual buffer module，VBM）概念的基础上，结合时间区间集概念［14］，进行了带驻留约束的双臂集束型设备群的调度问题研究.

1 问题描述

根据SEMI标准E21-96定义，一个集束型设备一般由卡匣模块（load lock，LL）、单臂或双臂机械手搬运模块（robot module，RM）以及若干个晶圆加工模块（process module，PM）组成．LL的功能是存储晶圆，RM负责完成晶圆的搬运、装载或卸载任务，PM负责晶圆的加工.一个集束型晶圆制造设备群通常包含多个由缓冲模块（buffer module，BM）相互连接的集束型设备，如图1所示，其中Ch表示第h台单个集束型设备．

图1 双臂集束型设备群示意图

为有效地描述集束型设备群调度问题，假设：①每一个集束型设备最多和两个集束型设备连接；②两个相邻的集束型设备由两个BM连接，其中一个BM用于暂存进入集束型设备的晶圆，一个BM用于暂存离开集束型设备的晶圆，BM最多只能储存一片晶圆，晶圆在BM的处理时间为0，驻留约束时间没有限制；③所有的RM采用双臂机械手，机械手的两臂呈180°角放置，每次允许搬运一片晶圆，在不同模块间的晶圆移动时间固定；④每个PM一次只能加工一片晶圆；⑤晶圆在PM中有驻留时间约束，即加工完成后，晶圆在PM内驻留时间有限制，超过该时间上限，晶圆的产品质量会下降，甚至会变成次品；⑥要调度的晶圆具有不同的晶圆流模式，也即是有不同的晶圆种类，并且晶圆允许跳过在同一个集束型设备中的某一个或几个PM．

符号定义如下：

CTm为一个集束型设备群，其中下标m表示这个集束型设备群中包含的单集束型设备的数目；

Ji为当前调度的晶圆；

Ch为在该集束型设备群中的第h个集束型设备；

Rh1、Rh2分别表示第h个集束型设备的机械手的两只手臂；

BMhj为用于连接Ch和Ch+1的缓冲模块；

VBMhj为假设的存在于PMh（j-1）PMhj之间的虚拟的缓冲模块；

MHL为晶圆进入BM（h-1）2之前在Ch的实际上的最后一道工序的序号；

Mh为Ch与Ch+1连接前Ch中处理模块的数目；

MH为Ch中的处理模块的数目；

aihj为跳过的工序数，若晶圆没有跳过任何工序，则aihj=0；若晶圆在PMhj或BMhj之后跳过了k个工序，则aihj=k；

tP，i，hj为Ji在工序PMhj上所需的加工时间；

tp为晶圆Ji在晶圆流模式上的各个处理模块PMhj的加工时间的集合；

tU，i，hj为Ji在工序PMhj上最大允许驻留时间；

tu为晶圆在晶圆Ji流模式上的各个处理模块PMhj的最大允许驻留时间的集合；

tPVB，hj为虚拟的连接存储模块VBMhj所需要的加工时间tPVB，hj=0；

tUVB，hj为用于连接的存储模块VBMhj最大允许驻留时间tUVB，hj=∞；

Ti为Ji各工序需要加工时间集合，即Ti=｛tP，i，11，tP，i，12，…，tP，i，mj，…，tP，i，14｝；

TP，i，hj为Ji在PMhj上允许停留的时间区间TP，i，hj=［tP，i，hj，tP，i，hj+tU，i，hj］；

tF，i，hj为Ji在PMhj中的实际停留时间；

tS，i，hj为Ji在PMhj中的开始时间；

tL，i，hj为Ji在PMhj中的离开时间；

t为J从Ch进入B后的实际停留

FB，i，hjiMhj时间；

t为J从Ch进入B中的时间；

SB，i，hjiMhj

t为J从Ch进入B后的离开时间；

LB，i，hjiMhj

tUD为机械手卸载Ji的时间，为常数；

tLD为机械手装载Ji的时间，为常数；

tM，i，hj为把Ji从PMh（j-1）搬运到PMhj需要的时间，含装卸时间，为常数tM；

tFVB，i，hj为Ji从CTm（m=1，2，…，n） 进入虚拟的存储模块VBMhj后实际停留时间；

tSVB，i，hj为Ji从CTm（m=1，2，…，n） 进入虚拟的存储模块VBMhj中的时间；

tLVB，i，hj为Ji从CTm（m=1，2，…，n） 进入虚拟的存储模块VBMhj后的离开时间；

tMV，i，hj为把Ji从工序j-1 搬运到虚拟的存储模块VBMhj需要的时间，含装载和卸载的时间；

tTMRES，i，hj为Ji从PMhj卸载后到被装载到下一个处理模块之间在机械手的手臂上驻留的时间；

TTW，i，hk为K等于1 或2，表示第h个集束型设备的机械手的两只手臂Rh2或Rh2对的可用时间区间；

TFL，i，hj为在当前调度下，Ji在PMhj可行的结束时间区间集， 包含有ϕl（i，h，j） 个区间， 即有TFL，i，hj=｛TFL，i，hj，1，TFL，i，hj，2，…，TFL，i，hj，ϕl（i，h，j）｝ ；

TFSB，i，hj为在当前调度下，Ji在BMhj可行的开始时间区间集，包含有ϕbs（i，h，j） 个区间，即有TFSB，i，hj=｛TFSB，i，hj，1，TFSB，i，hj，2，…，TFSB，i，hj，ϕbs（i，h，j）｝．

TPWVB，i，hj为虚拟的模块缓冲模块中VBMhj可用的时间区间集；

TFSVB，i，hj为在当前调度下，用时间区间集来表示VBMhj的可行的开始存储时间（tSVB，i，hj）．

由假设③可知，晶圆在任意一个PM或BM的开始时间或结束时间的差值至少大于或等于RM完成一次晶圆装载的时间，于是可得

由假设④可知，任意一个PM或BM都不可能同时拥有两个或两个以上的晶圆，于是有

由于双臂机械手采用SWAP策略，其对晶圆的移动不是一个连续的动作，由假设⑥可知，晶圆在晶圆流模式上相邻的PM之间的开始时间和结束时间的关系必须满足如下关系：

由于集束型设备群的特殊的结构，晶圆在不同集束型设备之间的移动必须通过BM进行中转，所以在约束条件（1）～（5）中应满足如下约束：

由假设条件⑤可知，晶圆在PM中的时间应该大于其处理时间，于是可得

tF，i，hj≥tP，i，hj，j=1，2，…，MH，h=1，2，…，n；tF，i，hj≤tP，i，hj+tU，i，hj，j=1，2，…，MH，h=1，2，…，n；

对晶圆的搬运必须发生在机械手的两只机械臂中的某一个机械臂的可用的时间区间内，于是有

晶圆在PM中的实际停留的时间区间必须在PM的某个可用时间区间内，于是有

同理，对BM也是如此：

调度目标是最小化晶圆加工的makespan，即

至此，在对调度问题进行分析的基础上，关于在多晶圆流模式条件下，带有驻留约束的双臂集束型设备群调度问题的数学模型已经建立.

2 计算方法

首先，引入文献［14］中有关时间区间集运算的定义，具体描述如下：

定义1假设有时间区间集T=｛T1，T2，…，Tn｝ 和时间区间集S=｛S1，S2，…，Sn｝，T1，…Tn，S1，…，Sn为时间区间：1）T和S的交集，用T∩S表示；2）T和S的并集，用T∪S表示．

定义2假设有时间区间集T=｛［L1，H1］，［L2，H2］，…，［Ln，Hn］｝ 和区间Q=［a，b］：1）T和Q的和用符号T⊕Q来表示，T⊕Q=｛［L1+a，H1+b］，［L2+a，H2+b］，…，［Ln+a，Hn+b］｝；2）min和max函数分别用minT=L1和maxT=Hn来表述．

2.1 算法流程

算法的核心思想是引入VBM概念，将双臂集束型设备群的调度问题转化为带有VBM的单臂集束型设备群的调度问题进行研究．VBM的依据是基于双臂的搬运机械手实际上相当于在每两个相邻的PM（BM）之间增加了一个BM，当晶圆产生驻留约束时，机械手可以暂时存储晶圆，相当于为晶圆提供了一个BM．双臂的机械手转化为单臂的机械手，同时在集束型设备里的每两个模块之间增加了一个VBM，虚拟化处理如图2所示．PM之间的圆圈表示为VBM．

图2 虚拟化示意图

基于上述核心思想，算法的流程见图3．首先，将双臂机械手的一个手臂虚拟为存在于相邻的PM（BM）的VBM．这样，带驻留约束的双臂集束型设备群的调度问题就转化为相应的带驻留约束带VBM的单臂集束型设备群的调度问题．最后，利用VBM上的开始和结束的时间就是晶圆在RM的其中一个机械手的开始和结束时间，结合SWAP策略，并以此为依据对此进行修正，得到修正的SWAP调度策略，进而完成调度.

图3 基于SWAP策略的算法流程

2.2 各模块的调度时间节点确定

针对已经转化后的带有驻留约束和VBM的单臂集束型设备群调度问题，需要计算调度的时间节点，即晶圆在转化后的晶圆流模式上的各个模块（包括PM、BM、VBM和RM） 的开始和结束时间．各模块的调度时间节点确定步骤如图4所示．逆序策略为计算PM的开时间取可行时间区间的最大值；计算BM的开始时间取可行区间最小值．

图4 各模块的调度时间节点确定

具体的计算方法如下：

首先，在计算可行时间区间集部分，关于VBM的可行的开始和结束时间区间集TFSVB，i，hj和TFLVB，i，hj的计算，根据计算基于的模块的不同，可以分为以下3种情况：

1）上一模块是LL，即计算是基于LL的，那么计算的方法如下：

2）上一个模块是PMhk，即计算是基于上一个PM的调度结果，那么计算方法如下：

（3） 如果上一个处理模块是BMh′k＇，即计算是基于BM计算结果的，那么计算的方法如下：

其次，晶圆在进入PM之前必须先“进入”VBM，所有处理模块的计算都是基于VBMh”k”计算结果的，其计算方法如下：

最后，关于BM的可行开始和结束时间区间的计算．与PM类似，BM的计算也都是基于相应的VBMh”k”计算结果的，其相应的计算公式如下：

通过上述公式，按照晶圆流模式上各模块的顺序，可以一次计算出相应的可行和结束时间区间集．在此基础上进行调度时间点的计算．

首先是关于晶圆在各个VBM的开始和结束时间点计算，下面对几种不同的情况进行分析．

1）上一个模块是用于存储已加工完成的晶圆的L，则

那么晶圆的最早完工时间显然是tLVB，i，hn+tM/2．

2）如果上一个模块是PMhk，即计算是和上一个PM相关联的，则

3） 如果上一个模块是BMh′k′，即计算是和上一个BM相关联的，则

其次是关于晶圆在BM的开始和结束时间的计算，其计算肯定是基于VBMh”k”的，相应的计算公式如下：

最后是晶圆在各个PM上的开始和结束时间的计算．由于PM的计算也必定是基于VBMh”k”的，所以其计算的方法可归纳如下：

2.3 基于修正的SWAP策略调度

对于集束型设备群的调度就是要在满足各种要求的情况下，确定各个机械手的动作顺序和时间，以实现预定的调度目标．对于不带驻留约束限制的双臂集束型设备来说，SWAP策略是其基本的调度策略，并且是已经被证明了的优化的调度策略［2］．对于带有驻留约束的双臂集束型设备群来说，双臂机械手在调度上最大的功能就是提供了一个临时的“缓冲”模块．双臂机械手的这一作用也正为带驻留约束的集束型设备群的调度提供了新的调度空间．在本文的算法中，将双臂虚拟为单臂，晶圆在VBM上的开始和结束的时间就是晶圆在双臂PM的其中一个模块的开始和结束时间，结合修正的SWAP策略，可得到对集束型设备群的调度．对于不带驻留约束限制的集束型设备群来说，SWAP策略就是完全根据晶圆的加工时间来确定机械手各个动作的时间和顺序．在考虑驻留约束限制的情况下，根据2.2节的调度，首先可以确定的一个机械手的各个动作的时间，再根据晶圆在虚拟处理模块上的开始和结束时间确定另一只机械手的相应的开始和结束时间，从而可以确定双臂机械手对晶圆的搬运的动作顺序和时间，从而完成调度．

3 仿真实验与分析

为了有效地评价本文提出的调度算法，选取文献［3］构造的基础调度周期（fundamental period，FP） 下界作为 benchmark，并且与文献［3］提出的下界的非VBM调度方法进行对比，期望通过对下界的综合使用来更加有效地评价本文的算法.周期延长率［13］

表示因为驻留约束而相对于FPB的延时率，R越小，越接近FPB，即本文提出的算法性能越好．

表示集束型设备群中RM的繁忙程度，CF越大，晶圆的最大处理时间和RM完成一次搬运所需时间的比例越大，说明RM越空闲，反之表明RM越繁忙．

相关符号定义如下：FPZ表示处理一批晶圆所需的平均周期时间；FPB表示文献［3］中的下界周期时间；tpmax表示晶圆在某个集束型设备中各个PM的最大处理时间；tM表示完成一次搬运的时间；N表示每个集束型设备中的PM的数目；N∗表示文献［3］中提出的VBM块的数目．

为了方便仿真，在不失一般性的前提下，本文假设晶圆在晶圆流模式上的各个加工时间tp和驻留约束时间tu服从相应的正态分布．此外，根据对集束型设备群调度研究的通行做法，本文假设机械手在不同模块间的搬运时间tM，i，hj、tMV，i，hj等相同，并用T表示．最后，假设集束型设备群中每个集束型设备含有的处理腔的数目相等，并用Np表示．

3.1 运算时间分析

为了确定算法是否能够快速响应调度，对算法运行时间进行了仿真分析，实验设计如下：令m=8；Np=6；T=2；tp～N（40，10）；tu～N（30，5）；依次令晶圆的数目为：5、10、15、20、25、30、35、40、45、50，分别计算算法求得调度结果的时间.程序运行的硬件环境为320 G硬盘、2 GB内存和2.13 GHz主频英特尔处理器的ACER个人笔记本电脑.运行的结果如图5所示.

图5 算法运行时间

由图5可以看出，当一次处理的晶圆数量为25片（1个Lot）时，算法的运行时间为0.5 s，也就是说算法可以在0.5 s以内完成对1个Lot的优化调度.随晶圆数量的增加其算法的求解时间呈单调递增.完成两个Lot的调度仅用了3.4 s左右，可知算法产生调度解的时间是比较短的，响应时间较快.

3.2 设备因子对算法的影响

设备因子CF是反映在集束型设备群内机械手的装载、卸载的时间和晶圆在各个PM上加工时间的关系的指标．设备因子实际上反映的是在集束型设备群内机械手繁忙程度的函数．

实验的设计如下：令Np=4，T=2；tp～N（40，10），tu～N（30，5）；分别令m=2、3、4、5，求出在CF=1、2、3、4、5、6 时的R值，分析在各种情况下CF对R影响．仿真结果如图6所示．

图6 CF对算法的影响

由图6可以看出，周期延长率R基本上是随着CF的逐渐增大而不断下降，且不同m值的仿真曲线的走向基本相同．当CF＞5时，R＜0.05，表明在不同m值的集束型设备群均取得了较好的调度效果．而且，在实际中机械手的搬运时间通常相对于晶圆的最大加工时间要小，从而CF较大，所以本文提出的算法具有较好的实际意义．

3.3 集束型设备群结构对算法的影响

本节仿真的主要目的是要测试算法对不同的集束型设备群结构的适应性和优化性.

首先分析的是集束型设备群的m值对算法的影响.实验设计如下：令Np=4，T=2；tp～N（40，10），tu～N（30，5）；分别令m=2、3、4、5、6、7，计算出相应的R值，分析m的变化对算法的性能影响，结果如图7所示．

图7 m对算法性能影响

下面分析每个单集束型设备里的PM的数量对算法性能的影响．实验设计如下：令m=3，T=2；tp～N（40，10），tu～N（30，5）；分别令Np=2、4、6、8，计算其相应的R值，并分析Np变化对算法的性能影响，结果如图8所示．

由图7所示，周期延长率R随着m的变化，虽然有波动，但总的来说，上下波动的范围在正负0.01以内，相对来说比较小．由此可见算法对于m变化具有较好的稳定性．从图8也可以看出类似的规律，即周期延长率R基本上比较平稳，没有发生太大的波动，算法对于Np变化也具有较好的适应性．综上可知，本文构造的算法对不同配置的集束型设备群具有良好的适应性．

图8 Np值对算法的影响

4 结 论

1）在提出虚拟缓冲模块概念的基础上，构造了基于修正SWAP策略的带驻留约束限制的可调度多种晶圆种类的双臂集束型设备群的调度算法，为研究此类问题提供了一种调度方法.

2）所构建的算法运行时间短，在调度1个Lot数量的晶圆，仅需0.5 s左右，响应时间较短.

3）由集束型设备群的配置对算法影响的分析可知：当设备因子＞5时，周期延长率R已经全部＜0.05，表明算法取得了较好的调度效果；另外，随着m和Np的变化，周期延长率R虽然有些波动，但总体波动相对较小，算法对不同的集束型设备群的配置具有较好的适应性．

［1］PERKINSON T L， MCLARTY P K， GYURCSIK R S，et al.Single-wafer cluster tool performance：an analysis of throughput［J］.IEEE Transactions on Semiconductor Manufacturing， 1994， 7（3）： 369-373.

［2］VENKATESH S， DAVENPORT S， FOXHOVEN P， et al.A steady-state throughput analysis of cluster tools：dual-blade versus single-blade robots ［J］.IEEE Transactions on Semiconductor Manufacturing， 1997， 10（4）： 418-424.

［3］YI J， DING S， SONG D， et al.Steady-state throughput and scheduling analysis of multi-cluster tools： a decomposition approach ［J］.IEEE Transactions on Automation Science and Engineering，2008，5（2）： 321-336.

［4］CHAN W，YI J， DING D.On the Optimality of one-unit cycle scheduling of multi-clustertools with singleblade robots［C］／／Proceedings of the 3rd Annual IEEE Conference on Automation Science and Engineering.Piscataway， New York， USA：IEEE， 2007： 392-397.

［5］CHAN WKV， YI J， DING D.Optimal scheduling ofk-unit production of cluster tools with single-blade robots［C］／／IEEE International Conference on Automation Science and Engineering.Piscataway， New York， USA：IEEE，2008：335-340.

［6］ZHOU B H， LI X.Try and error-based scheduling algorithm for cluster tools of wafer fabrications with residency time constraints［J］.Journal of Central South University of Technology， 2012， 19（1）： 187-192.

［7］陈佳，周炳海.带驻留与重入约束的集束型设备调度算法［J］.计算机集成制造系统，2012，18（12）： 2667-2673.

［8］WU N Q，ZHOU M.Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraintand activity time variation ［J］.IEEE Transactions on Automation Science and Engineering，2012， 9（1）： 203-209.

［9］WU N Q， ZHOU M.A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis［J］.IEEE Transactions on Automation Science and Engineering，2010，7（2）： 303-315.

［10］YAN Q，WU N Q，ZHOU M.Petri net modeling and wafer sojourn time analysis of single-arm cluster tools with residency time constraints and activity time variation［J］.IEEE Transactions on Automation Science and Engineering， 2012， 25（3）：432-446.

［11］LEE H T， LEE H Y， PARK D B.Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri Net［ J］.IEEE Transactions on Automation Science and Engineering，2008， 5（3）： 490-503

［12］ROSTAMI S， HAMIDZADEH B， CAMPORESE D.An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints［J］.IEEE Transactions on Robotics and Automation， 2001， 17（5）， 609-618.

［13］刘明祥，周炳海.基于时间约束集的集束型设备群调度方法［J］.自动化学报， 2012， 38（3）： 479-485.

［14］DECHTER R， MEIRI I， PEARL J.Temporal constraint networks［J］.Artificial Intelligence， 1991， 49（1）：61-95.