基于earliest调度策略对带驻留时间约束单臂组合设备的暂态分析

胡 勋，伍乃骐，乔 岩

（广东工业大学机电工程学院，广东广州 510006）

0 引言

在半导体制造中，由于晶圆直径越来越大，加工工艺复杂，组合设备被广泛的用来加工晶圆。组合设备是一类集成制造设备。在这样的一台设备中，有几个加工模块（Processing Module，PM），一个机械手以及真空锁（Loadlock）。机械手分为单臂机械手和双臂机械手，如图1所示为单臂机械手，因此叫单臂组合设备。此系统的工作过程大致如下：一批装在一个卡盒中待加工的晶圆首先放入真空锁中，然后由机械手从卡盒中抓取一枚晶圆放到AL中，经AL的视觉系统进行校准后，由机械手按照工艺要求将该枚晶圆依次放入相应的PM中加工，晶圆在每一个加工模块内完成一道工序，当完成最后一道工序后，晶圆被送入CL中冷却，避免热的晶圆影响到真空锁内其他的晶圆，最后晶圆被送回到真空锁。整个过程由程序自动控制，当该批晶圆加工完成后，真空锁中卸载，并装入下一批晶圆。两个真空锁通过轮流使用实现对晶圆的装卸作业，以保证组合装置加工的连续性，使得系统绝大部分时间都是处在稳定运行的状态。这样的组合设备可以为半导体制造提供一个灵活的、可重置的和有效的环境，减小生产节拍，提高空间的利用率，降低成本。一个晶圆通过真空所进入系统，然后按照已知的加工路径在加工模块中加工，当所有的加工工序完成后，由机械手送回真空所。

图1 单臂组合设备

为了调度组合设备，许多学者在建模和对系统执行评估做了很多工作[1-2]。基于这些研究发现，在稳态下，当机械手有空闲时间时，加工模块的加工时间决定系统的生产周期，当机械手一直忙的时候，系统的生产节拍由机械手的活动时间决定。在一台组合设备中，仅仅当一个晶圆载入到加工模块中，加工模块才开始加工晶圆。因此，加工模块的活动跟随着机械手的任务[3]。这样，调度组合设备的关键在于调度机械手的任务。众所周知，组合设备中机械手从一个加工模块移动到另一个加工模块的时间可以看作为常数，并且比晶圆的加工时间短很多[4]。这样，对于单臂组合设备拉式调度是最优的[5-6]。然而，以上的研究结果都是基于假设晶圆加工完成后可以在加工模块中停留无限长的时间。

对于一些晶圆加工工艺，例如低压化学沉积工艺，它对晶圆在加工模块中的滞留时间有严格的约束。这种约束叫晶圆驻留时间约束（residen⁃cy time constraint，RTC）[4]。RTC指一个晶圆在加工模块中加工完成后，必须在规定的有限的时间内卸载出来，否则此晶圆将成为废品。由于在加工模块之间没有缓冲区，使得很难调度组合设备去满足晶圆在每个加工模块中的驻留时间约束。这样，为了能够调度带驻留时间约束的组合设备，文献[4]提出了一些方法为双臂组合设备找到最优的周期性调度。之后，为了提高计算有效性，伍乃骐等人分别对于单臂和双臂组合设备提出了充分必要的可行性调度条件[2，7]。如果可调度，可通过由解析表达式组成的调度算法找到最优的周期性调度。然而在以上的研究中，并没有给出怎么样进入稳态调度更好。也就是说，不同文献给出进入稳态的调度方法不一样。这就意味着，不同进入稳态的调度方法导致不同的稳态调度方案。这样，本文基于earliest调度策略，通过对系统暂态过程的分析，给出了系统进入稳态后，机械手的等待时间分布。

接下来文章主要介绍Petri网建模。基于此Petri网模型，第二部分分析了系统进入稳态后机械手的等待时间分布。第三部分给出了实例验证了本文得出的结论。第四部分对文章进行了总结。

1 Petri网建模

本文用Petri网（Petri net，PN）对系统进行建模。Petri网的概念来自于文献[8-9]，对于没有重入加工工艺的组合设备，晶圆的加工模式可以定义为(m1，m2，…，mn)，其中n是晶圆加工步骤数目，mi是晶圆加工步骤i中所包含的加工模块数目。

本文展示的Petri网模型中，用库所pi表示步骤i的加工模块并有K（pi）=mi，i ϵ{1，2，…，n}。将真空锁看作一个加工步骤并称之为步骤0，用p0表示。由于真空锁可以容纳设备中的所有晶圆，因而有K（p0）=∞。这样，整个系统就有n+1步加工步骤。让Ω={0，1，…，n}表示包含步骤0的步骤集，让Nn={1，…，n}表示可加工晶圆的步骤集。机械手由库所r表示，K(r)=1意味着机械手只有一只手臂。当库所r中有令牌时表示机械手是空闲状态。

图2 有n个加工模块的单臂组合设备Petri网模型

对于带驻留时间约束的单臂组合设备，机械手的等待时间用来平衡加工步骤之间的工作负载。用库所qi2和qi1表示机械手在缷载或安装晶圆到加工步骤i之前的等待时间。模型中变迁，si1，i ϵ Nn，和s01分别表示机械手安装一个晶圆到加工模块pi和真空锁p0中。变迁si2，i ϵ Nn-1，表示机械手从加工模块pi卸载一个晶圆然后移动到加工模块pi+1。变迁s02表示机械手从真空锁p0下载一个晶圆然后移动到加工模块p1。变迁sn2表示机械手从加工模块pn中下载一个晶圆然后移动到真空锁。yi表示机械手从第（i+2）道工序旋转至第i道工序，yn-1表示机械手从真空所旋转至第（n-1）道工序，yn表示机械手从第1道工序旋转至第n道工序，y0表示机械手从第2道工序旋转至第0道工序。图2展示了单臂组合设备具有n个加工步骤的Petri网模型。

假设组合设备按照给定的晶圆加工流模式（m1，m2，…，mn）对晶圆进行加工，稳态时系统达到最大产能时有个晶圆同时在系统中加工。所以，让初始状态M0为M0（pi）=mi，i ϵ Nn，M0（r）=1来表示机械手为空，让M0（p0）=n表示系统中总有晶圆可被载入到系统中。为了避免图2中的Petri网模型死锁，给出让Petri网避免死锁的控制策略。

定义1[2]：在标识M下，如果M（pi+1）=mi+1-1 ，则变迁yi，i ϵ Nn-1∪{0}，是可触发的；如果M（pi）=mi，i ϵ Nn，则变迁yn是可触发的。

通过定义1，强迫Petri基于拉式策略运行。下面我们展示采用拉式策略的单臂组合设备的运行过程。稳态时一定有状态为M（pi）=mi，i ϵ Nn，M（r）=1，接着系统的运行过程如：yn→qn2→sn2→q01→s01→yn-1→q(n-1)2→s(n-1)2→qn1→sn1→yn-2→q(n-2)2→s(n-2)2→q(n-1)1→s(n-1)1→yn-3→…→q12→s12→q21→s21→y0→q02→s02→q11→s11→yn，这样系统走完一个周期。基于拉式策略，系统不断的周期性重复以上的运行过程。

为了解决该系统的调度问题，需将系统的活动时间与系统的Petri网模型联系起来。令机械手每次的运动时间为μ，机械手从ρ0卸载一枚晶圆的时间为λ0，而在其他步骤中卸载或安装晶圆的时间均为λ。这样，有激活变迁yi，i ϵΩ，需要μ个单位时间，激活变迁si1，i ϵΩ，需要λ个单位时间，激活si2，i ϵ Nn，需要λ+μ个单位时间，激活s02需要λ0+μ个单位时间。用ai表示晶圆在加工模块中的加工时间。由于考虑驻留时间约束，这样用δi表示这样的约束，即：晶圆在第i步加工完后，需要在δi个单位时间内移走，否则将变为废品。用ωi1和ωi2分别表示机械手在库所qi1和qi2中的等待时间。这样就完成了对单臂组合设备的Petri网建模。

2 基于Earliest调度策略，机械手等待时间的分布规律

Earliest调度策略是指：（1）机械手到达加工模块卸载晶圆时，如果加工模块中的晶圆已经加工好，那么机械手立即将其卸载下来；（2）机械手到达加工模块卸载晶圆时，如果加工模块中的晶圆还没加工好，那么机械手在此等待，一旦晶圆加工好，机械手立即将其卸载下来；（3）机械手拿着待加工的晶圆来到加工模块时，如果该加工模块是空的，立即将其载入加工模块中。暂态是指组合设备所有加工模块中从没有加工晶圆开始，机械手将晶圆一个个的载入到组合设备中，到所有的加工模块都有加工晶圆并最终组合设备进入稳态运行的过程。

根据文献[7]，设τi表示第i道工序的晶圆在加工模块中的停留时间，如果晶圆在第i道工序满足驻留时间约束，那么τiϵ[ai，ai，+δi]。根据图2中的Petri网模型，第i步完成一个晶圆需要经过以下过程：触发si2（λ+μ）→触发si+1（λ）→触发yi-1（μ）→机械手在第i-1步等待（ω（i-1）2）→触发s(i-1)2（λ+μ）→触发sil（λ）→晶圆在第i步加工（τi）→触发si2（λ+μ）。则该过程所需时间为

ρi=τi+4λ+3μ+ω（i-1）2。这样，考虑并行模块，第i道工序完成一个晶圆允许的最短的时间为：

第i道工序完成一个晶圆允许的最长时间为：

第一道工序完成一个晶圆允许的最短时间为：

第一道工序完成一个晶圆允许的最长时间为：

在图2的Petri网模型中，分析机械手走过一个周期的活动路径及时间：触发yn（μ）→机械手在qn步等待（ωn）→触发sn2（λ+μ）→触发s01（λ）→触发yn-1（μ）→机械手在qn-1步等待（ωn-1）→触发s（n-1）2（λ+μ）→触发sn1（λ）→…→触发yi（μ）→机械手在qi步等待ωi→触发Si2（λ+μ）→触发s(i+1)1（λ）→触发yi-1（μ）→机械手在q(i-1)2步等待(ω(i-1)2）触发s(i-1)2（λ+μ）→触发si1（λ）→…→触发y1（μ）→机械手在q12步等待（ω1）→触发s12（λ+μ）→触发s21（λ）→触发y0（μ）→机械手在q02步等待（ω02）→触发s02（λ0+μ）→触发s11（λ）→再次触发yn（μ），这样一个周期完成，若令机械手的节拍为ψ，可得到：

式（5）中可以发现2（n+1）μ+（2n+1）λ+λ0是一个常数，可令其为ψ1，而是不确定的，可令其为ψ2，所以

根据文献[7]，晶圆在加工模块的停留时间如下式：

引理1：对于带驻留时间约束的单臂组合设备，当所有的加工模块都有晶圆在加工时，有θi=ψ，i ϵ Nn。

让ΠiL和ΠiU分别表示第i道工序允许生产节拍的上限和下限，那么有:

文献[7]针对带驻留时间约束的单臂组合设备的调度问题，提出了使系统可调度的充分必要条件。在此基础上，给出稳态下机械手的等待时间分布规律。假设第k道工序为瓶颈工序，1≤k≤n。那么有下面的定理。

定理1：对于带驻留时间约束的单臂组合设备，基于earliest调度策略，当系统到达稳态后，等待时间ωi1=0，iϵΩ和ωi=0，i=0，1，……，k-1，成立。

证明：根据拉式调度策略，当机械手拿着待加工的晶圆来到第i步时，第i步一定为空。这样根据earliest调度策略定义，机械手可以立即将此晶圆载入第i步中，即ωi1=0。因为真空锁总有待加工的晶圆，这样当机械手来到真空锁可立即将其中的晶圆卸载出一个，所以有ω02=0。根据拉式调度策略，当机械手来到第一步时，其一定已经在瓶颈工序第k步完成一系列的机械手活动，这样此时该系统的周期由瓶颈工序决定，即为ΠkL。这样由引理1和式子（8）可得τ1=m1×ΠkL-（3λ+λ0+3μ+ω0）=m1×ΠkL-（3λ+λ0+3μ)≥m1×Π1L-（3λ+λ0+3μ）=a1，所以当机械手来到第1步卸载晶圆时，第1步中的晶圆已经加工好了。因此机械手可以立刻将其中的晶圆卸载出来，同时不需要等待，即ω1=0。当机械手来到第2步时，同理由引理1和式子（7）τ2=m2×ΠkL-（4λ+3μ+ω1）=m2×ΠkL-（4λ+3μ≥

m2×Π2L-（4λ+3μ）=a2，所以当机械手来到第2步卸载晶圆时，第2步中的晶圆已经加工好了。因此机械手可以立刻将其中的晶圆卸载出来，同时不需要等待，即ω2=0。相似的，可推出ω3=ω4=…=ωk-1=0。因此定理1成立。

根据文献[10]，可知机械手在qi2中的等待时间是有上界的，否则此等待时间将会影响系统的最优性。让γi表示可分配到库所qi2最大的等待时间，这样有γi-1=mi×ΠkL-（ai+4λ+3μ），1≤i≤n和ωnϵ[0，∞]成立[10]。

定理2：对于带驻留时间约束的单臂组合设备，基于earliest调度策略，当系统到达稳态后，有结论：如果那么和ωi=0，d+1≤i≤n成立；如果，那么ωi=γi，i

证明：根据定理1可知，ωi1=0，i ϵΩ 和ωi2=0，i=0，1，…，k-1，成立。假设机械手在第k步的等待时间ωk2>γk2，根据引理1和式子（7）有τk+1=mk+1×ΠkL-（4λ+3μ+ωk）ak+1，根据earliest调度策略，这就暗示着不断减小同时 ωk2不断增加并且。直到当ωk2=γk2时，有τk+1=mk+1×ΠkL-（4λ+3μ+ωk2）=ak+1，这时根据earliest调度策略，ωk2此时不再增加。同理可以得到，如果那么ωk2=γk2，k≤i

到现在为止，分析了基于earliest调度策略，稳态时机械手等待时间的分布情况。同时，机械手的等待时间分布可通过解析表达式计算出来，因此非常有效。

3 实例验证

一台组合设备有四道加工工序，其中第三道工序有两个并行加工模块，而其他工序只有一个加工模块。每道工序的加工时间分别为：a1=92 s，a2=98 s，a3=210 s，a4=95 s。机械手的活动时间分别为：λ=10 s，λ0=15 s，μ=2 s。

基于工艺参数可以求得：ψ1=125 s，Π1L=143 s，Π2L=144 s，Π3L=128 s和 Π4L=141 s，其中第二道工序为瓶颈工序。基于定理1和定理2得出，稳态时，机械手的等待时间分布为：ω02=ω12=0，ω22=19和ω32=ω42=0。通过基于eM-plant仿真，采用earliest调度策略，系统稳态时机械手等待时间的分布为ω02=ω12=0，ω22=19和ω32=ω42=0。此仿真结果与基于定理1和定理2得出的结果一致，因此验证了本文的结论。

4 结束语

半导体加工是极复杂的制造系统，它的调度问题非常复杂。本文对基于earliest调度策略的带驻留时间约束的单臂组合设备的暂态过程进行了分析，运用Petri网模型得出了系统达到稳态后机械手的等待时间分布情况，并且此分布可通过解析表达式计算得出，因此非常有效。基于以上成果，今后将着重研究基于earliest调度策略多组合设备到达稳态时机械手的等待时间分布情况。

［1］J.Yi，S.Ding，M.Zhang.Steady-state throughput and scheduling analysis of multi-cluster tools：A decomposi⁃tion approach［J］.IEEE Trans.Automation Sci.Eng.，Apr，2008，5（2）：321-336.

［2］N.Q.Wu，M.C.Zhou.A closed-form solution for schedu⁃lability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis［J］.IEEE Transactions on Automa⁃tion Science and Engineering，2010，7（2）：303-315.

［3］Y.-H.Shin，T.-E.Lee，J.-H.Kim，et al.Modeling and implementing a real-time scheduler for dual-armed cluster tools［J］.Computers In Industry，2001，45（1）：13-27.

［4］J.-H.Kim，T.-E.Lee，H.-Y.Lee，et al.Scheduling analysis of timed-constrained dual-armed cluster tools［J］.IEEE Transactions on Semiconductor Manufactur⁃ing，2003，16（3）：521-534.

［5］T.-E.Lee，H.-Y.Lee，Y.-H.Shin.Workload balanc⁃ing and scheduling of a single-armed cluster tool［A］.Proceedings of the 5th APIEMS Conference［C］，Gold Coast，Australia.2004：1-15.

［6］M.-J.Lopez，S.-C.Wood.Systems of multiple cluster tools- configuration， reliability， and performance［J］.IEEE Transactions on Semiconductor Manufactur⁃ing，2003，16（2）：170-178.

［7］N.Q.Wu，C.B.Chu，F.Chu，et al.A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints［J］.IEEE Transactions on Semiconductor Manufacturing，2008，21（2）：224-237.

［8］M.C.Zhou，K.Venkatesh.Modeling，simulation and control of flexible manufacturing systems［A］.Petri net approach，World Scientific，Singapore，1998.

［9］T.Murata.Petri nets：Properties，analysis and applica⁃tions［A］.Proceedings of the IEEE［C］.1989，77（4）：541-580.

［10］Y.Qiao，N.Q.Wu，M.C.Zhou.Real-time scheduling of single-arm cluster tools subject to residency time con⁃straints and bounded activity time variation［J］.IEEE Transactions on Automation Science and Engineering，2012，9（3）：564-577.