Corresponding author: ZHOU Bing-hai, professor, E-mail: bhzhou@tongji.edu.cn
半导体制造系统具有工艺过程复杂、生产周期长、多重入流、系统不确定性大等特点，是当今最复杂的离散制造系统之一[1].在300mm晶圆制造工厂中，晶舟多次往返于清洗、氧化、沉淀、蚀刻等工艺过程间，系统中可能同时有多达50000个晶舟等待数百种设备进行加工[2, 3]，因此，高效的自动物料搬运系统(automated material handling systems,AMHSs)对于提升晶圆制造系统的整体性能有很重要的意义.高空提升运输(overhead hoist transport,OHT)实现了晶圆在各加工区间快速稳定的搬运且不占用洁净室地面空间，成为晶圆制造工厂应用最广泛的搬运工具[4].
300mm半导体晶圆制造工厂建设耗时，设施昂贵，若搬运系统设计和运营不当，极易引起晶舟的搬运延迟和机器的闲置，进而影响整个晶圆工厂的有效产出.调度规则的设计在OHT搬运系统性能优化中举足轻重，近年来诸多国内外学者针对该问题进行了较深入的研究[5, 6, 7, 8, 9, 10, 11].这些文献大多针对单一Interbay或Intrabay搬运系统的车辆调度进行研究，而不是针对整合式布局环境下的大规模搬运问题.同时，以往文献中多数将车辆调度简化为指派问题，对于OHT小车运行过程可能出现的路径冲突、车辆阻塞问题鲜有提及；然而，对于OHT搬运系统运行策略的研究，一方面应充分考虑资源分配以达到调度的最优化，另一方面也应切实进行路径规划，才能确保调度的合理性.
为了有效解决半导体晶圆制造工厂搬运系统整合式布局运行过程中的运输阻塞问题，提高OHT搬运系统的综合效率，本文在充分考虑搬运系统中各搬运设备间相互影响的基础上建立数学模型，引入时间约束集进行路径规划，结合无等待轨道的设计和基于检测点的空车运行策略，构建OHT搬运系统防阻塞调度策略，最后进行大量仿真分析以验证其可行性和有效性.
1 问题描述目前在300mm半导体晶圆制造工厂中最常见的AMHS系统采用的是脊柱型布局，根据生产工艺的不同，将相似工艺的加工设备放置在同一制程区间(Bay)内，Intrabay搬运系统负责Bay内的物料搬运；Interbay搬运系统负责Bay间的物料搬运.系统内搬运工具采用OHT小车，小车以晶舟为单位运输晶圆，一个晶舟容量为25片晶圆.OHT小车在轨道上单向行进，小车轨道位于加工设备的装卸端口(port)之上，在搬运过程中，通过升降装置将晶舟从设备的装卸端口送达OHT小车或者由OHT小车装载到设备的装卸端口.典型的OHT搬运系统布局如图 1所示.
|
图1 OHT搬运系统布局示意图 Fig. 1 Layout of OHT system |
为有效描述OHT搬运系统调度问题，现作如下假设：① 每辆OHT小车每次只能搬运一个晶舟；② 系统轨道单向、不可逆、不可更改；③ 小车搬运任务的起止时间是未知的，在调度过程中确定；④ 小车只能在节点处即工站或暂存区(stocker)驻停，进行装卸或等待；⑤ 小车匀速运行，忽略运行起止的加速度影响；⑥ 同一时刻，任一节点只允许一辆小车进行装卸作业，后一辆小车必须在前一辆离开后方能进入；⑦ 在OHT搬运系统运行过程中，以下两种情况可以触发小车指派过程： a. 晶舟触发(lot selects vehicle,LSV),当某一晶舟在相应机器或存储柜的装卸端口等待搬运时，其向系统发出搬运请求，系统根据调度规则指派某一空闲小车到达起始点，装载晶舟，完成搬运； b. 车辆触发(vehicle selects lot,VSL),新出现某一空闲小车时，系统会搜寻待搬运晶舟，并根据调度规则将最合适的搬运任务指派给该小车，小车前往装载晶舟，完成搬运；⑧ OHT搬运系统运行中，小车分为三种状态： a. 当小车没有搭载任何晶舟且没有被指派给任何搬运任务时，其状态为空闲(idle vehicle)； b. 当空闲小车被指派给某一搬运任务，则其状态变为取件(retrieval vehicle)； c. 当取件小车到达搬运起始点，装载待搬运的晶舟后，小车状态变为送件(delivery vehicle)；当送件小车到达目的地卸载晶舟后，其状态又变回空闲.
2 数学建模为清晰描述本文的调度问题，定义以下符号：
| i | 表示待搬运晶圆批次即晶舟编号； |
| NV,j | 表示系统中OHT小车总数及编号； |
| L,Z | 表示路径中弧段的数目及编号； |
| N,n | 表示路径中节点的数目及编号； |
| ei | 表示晶舟i提出搬运请求的时间点； |
| Pi,ju | Pi,ju=G(N,P)i,ju表示OHT小车j搬运晶舟i的静态第u短路径； |
| Dz | 表示路径Lz的长度； |
| v | 表示OHT小车在轨道上的运行速度； |
| Ti,j,zL | 表示OHT小车j搬运晶舟i时在路径Lz上的时间占用； |
| Ti,j,nN | 表示OHT小车j搬运晶舟i时在节点Nn上的时间占用； |
| ts,zL | 表示OHT小车在路径Lz的运行时间； |
| (ti,j,zL)in/out | 表示OHT小车j搬运晶舟i时进入/离开路径Lz的时间； |
| (ti,j,nN)in/out | 表示OHT小车j搬运晶舟i时进入/离开节点Nn的时间； |
| td,n,i,jN | 表示OHT小车j搬运晶舟i时在节点Nn处的作业时间.td,n,i,jN=Tl/u或0，Tl/u为小车在节点处的装卸时间； |
| Adj(Lz)I/O | Adj(Lz)I/O={u}表示路径Lz的开始/结束节点为Nμ； |
| ArcAdj(Nμ)I/O | ArcAdj(u)I/O={z1,z2}，表示以Nμ为进入/离开节点的路径的集合； |
| Ti,jN〈S〉 | 表示节点的可行准入时间约束集.其中 Ti,jN〈S〉= {Ti,j,1N〈S〉,Ti,j,2N〈S〉,…, Ti,j,φ(i,j)N〈S〉}，φ(i,j)表示Ti,jN〈S〉元素数目； |
| Ti,jN〈L〉 | 表示节点的可行离开时间约束集.其中 Ti,jN〈L〉= {Ti,j,1 N〈L〉,Ti,j,2N 〈L〉,…, Ti,j,ω(i,j)N〈L〉}，ω(i,j)表示Ti,jN〈L〉元素数目； |
| T(Pi,ju) | 表示OHT小车j沿第u短路径完成晶舟i搬运所需时间. |
由假设②可知，OHT小车必须沿着AMHS轨道路径运行，其行走的轨迹需满足路径与节点之间的相互连接关系，该路径约束表示如下：
由假设④和⑤可知，OHT小车在每节轨道上保持相同的运行速度，只有在轨道节点才能停车进行装卸及等待，且在节点的驻留时间必须符合晶圆生产工艺相关要求，因此小车运行的时间约束表示如下：
由假设⑥可知，多辆OHT小车不能在同一时刻占用同一节点进行作业，后一辆小车必须等待前一辆离开后方能进入，即小车必须在节点的可用时间区间内进入节点，并在该时间区间内完成相应的操作，所以模型有如下装卸点约束：
OHT搬运系统调度目标是从所有满足约束条件的调度方案中找到合适的小车及相应的路径，使得搬运任务的结束时间最早，即
综上所述，整合式布局环境下OHT小车调度问题是以式(16)为目标函数，以式(1)~(15)为约束条件的非线性规划问题.
3 防阻塞策略虽然OHT小车无需经过暂存区(Stocker)转运而能直接进行设备到设备的搬运，但由此造成更多的路径冲突和车辆阻塞，降低了搬运效率，进而影响到整个晶圆厂的有效产出.针对这一问题，本文提出小车防阻塞策略(vehicle congestion-avoidance policy,VCAP)并用于OHT搬运系统的调度过程.
目前的300mm晶圆生产车间内，OHT小车沿着AMHS系统的固定轨道单向运行，每段路径能允许多辆小车依次通过，但不允许多辆小车并行或超越情况的发生.当系统中小车数量较多，搬运载荷增加时，传统轨道设置极易导致小车阻塞现象的频繁发生，取件小车或送件小车都可能被途中正在进行装卸的小车阻挡，造成运送时间增加进而导致晶圆加工操作延迟.为了消除装卸点阻塞对搬运系统造成的影响，本文提出如图 2所示的无等待轨道设计(no-wait loop designing,NWL)改进设想.在该设计下，当取件小车或送件小车到达目的机器时，小车经过扫描点(checkpoint)确认后进入相应的边轨(side-track)进行装卸作业，在其装卸过程中，经过该段路径的后续车辆无需驻停等待.
|
图2 无等待轨道设计 Fig. 2 No-wait loop designing |
为了在满足系统搬运需求的前提下提高响应速度，同时尽可能减少车辆阻塞，本文提出一种OHT搬运系统基于检测点的空车运行策略(checkpoint-based circulation policy,CBCP)，具体描述如下.
所有已被指派任务的小车按照系统调度沿最短路径运送晶舟，所有空闲小车均匀速在Interbay轨道上循环运行，不得驻停，直到其被指派给某一搬运任务.在小车运行过程中，每一个其经过的节点会有扫描点(checkpoint)对其进行扫描，符合以下任一条件的小车将被准予进入相应的IntrabayI：① 小车为送件状态且目的地在IntrabayI；② 小车为取件状态且目的地在IntrabayI；③ 小车为空闲状态，IntrabayI中在阈时间Tt内将有晶舟加工完毕需要搬运且当前无空闲小车；如果IntrabayI 中的某一OHT小车不符合上述三个条件中的任意一个，则该小车必须离开IntrabayI，在Interbay轨道上循环运行等待调度.
引入时间约束集进行路径规划，预测小车下一步路径状况，结合NWL和CBCP，将防阻塞策略运用到OHT小车调度过程，基本步骤如下.
步骤1 更新OHT搬运系统状态，查看是否生成新的搬运任务及新的空闲小车，否则停止；
步骤2 生成搬运任务i，确定搬运任务的初始点Na和终止点Nb，令j=0；
步骤3 令j=j+1，OHT小车j的搬运开始节点为Nc，令u=0；
步骤4 令u=u+1，生成从节点Nc经过初始点Na到终止点Nb的第u短路径，记为Pi,ju=G Nij,Lij u；
步骤5 计算ti,j,1N〈S〉和ti,j,1N〈L〉；
步骤6 令n=n+1，计算tNi,j,n〈S〉和tNi,j,n〈L〉；
步骤7 若n＜N，返回步骤6，否则进入下一步；
步骤8 根据不同的调度规则所考虑的不同因素计算目标函数Z(Pi,ju)；
步骤9 若u＜U，返回步骤4，否则进入下一步；
步骤10 计算Z(Pi,ju*)=min Z(Pi,ju),u∈[1,U]；
步骤11 若j＜M，返回步骤3，否则进入下一步；
步骤12 计算Z(Pu*i,j*)=min Z(Pu*i,j),j∈[1,M]；
步骤13 确定搬运小车为j*，搬运路径为Pi,j*u=G(Nij*,Lij*)u*，生成调度方案，更新路径和节点时间约束集；
步骤14 算法结束，完成调度.
4 仿真实验使用eM-Plant仿真软件构建AMHS模型，在主频1.6GHz、内存3GB、Intel(R)Core(TM)2 Duo CPU的便携式计算机上进行仿真实验，对不同调度方法下得出的AMHS性能参数进行比较分析.
为有效评价各调度方法的性能，定义以下指标.
1) 等待时间(waiting time,WT)：表示从晶舟提出搬运请求到相应取件小车到达搬运起始点的时间长度.WT表征晶圆制造系统的空闲率，该值越小，调度策略越好；
2) 搬运时间(transport time,TT)：表示送件小车从搬运起始点到搬运结束点的时间长度.TT表征物料搬运系统的运行效率，该值越小，说明调度策略越好；
3) 运送总时间(delivery time,DT)：表示从晶舟提出搬运请求到晶舟被送达目的地的时间长度，包含WT，TT及装卸时间.DT表征物料搬运系统的响应速度和搬运效率，该值越小，说明调度策略越好； 4) 有效产出(throughput,TH)：表示系统中完成搬运的晶舟数量，该值越大，说明调度策略越好；
5) 及时率(due date satisfaction,DDS)：表示在规定时间内完成所有加工步骤的晶舟的百分比，该值越高，说明调度策略越好；
6) 在制品库存(work in process,WIP)：表示系统中在制品库存水平，该值越小，说明调度策略越好.
4.1 NWL布局对搬运效率的影响分别构建传统整合式布局及NWL布局AMHS，采用STT调度规则运行AMHS， 进行仿真实验对比.定义搬运任务的到达率λ服从正态分布N(μ,σ)，μ=720 lots · h-1，σ=20 lots · h-1，小车数量NV分别设定为30,40,50,60,70,80,90和100辆，系统中Bay的数目NBay=12，每个Bay中工站的数目NM=10.每个实验预热时间20个仿真日，运行240个仿真日，重复5次.仿真结果如图 3所示.
由图 3可见，传统布局下，随着小车数量的增加，WT曲线在逐渐下降后呈小幅上升的趋势，可见小车数目未达到资源饱和状态前，搬运任务的响应时间随小车数目增加而缩短，当小车到达一定数目之后，车辆阻塞和路径冲突现象增多导致WT增加.而在NWL布局下，即便系统中车辆已经达到满足搬运需求的数目，WT均值依然保持平稳，表现优于传统布局方式.观察两种布局下的TT曲线，随着车辆数的增加，NWL布局下TT值的增长也较传统布局下缓慢.在WT和TT的复合作用下，传统布局下搬运任务平均完成时间DT随着小车数量的增加先下降后上升，在车辆数目超过60之后，虽然车辆数继续增长，搬运效率却反而下降.而NWL布局下，搬运效率则如预期随着车辆数目的增加而逐渐提升然后保持平稳，实验结果表明NWL布局在搬运效率方面优于传统布局.
|
图3 传统整合式布局与NWL布局下AMHS性能对比 Fig. 3 Performance comparison between the traditional AMHS configuration and the NWL-AMHS. |
为了验证本文所提的防阻塞策略的有效性和可行性，设计仿真实验，将AMP调度方法(adaptive multi-parameter based dispatching policy)[8]、 HABOR调度方法(Hungarian algorithm-based OHT reassignment)[11]与MAMP(modified AMP)，MHABOR(modified HABOR)进行对比.其中，MAMP为AMP结合VCAP的改进方法，MHABOR为HABOR结合VCAP的改进方法.
AMHS车辆调度问题的实质是利用有限的资源完成尽可能多的任务，表征资源限度的小车数目与表征任务繁忙程度的晶舟到达率都对AMHS性能有较大影响.将NV设为50,70和90三个级别，λ的均值μ分别设为360,720和1080 (lots · h-1)，各调度方法将分别用于表 1所示9种场景进行实验.NBay=12，NM=10，每个实验预热时间20个仿真日，运行时间240个仿真日，重复5次.仿真结果如图 4所示.
|
表1 9种仿真场景 Table 1 Nine simulation scenarios |
|
图4 4种调度方法在9种场景下的指标对比 Fig. 4 Comparison of indices under 4 different dispatching rules in 9 different scenarios |
由图 4可知，在不同的晶舟到达率下，4种方法都能够满足系统的搬运需求，虽然4种方法在9种场景下TH指标的表现没有较大差异，但MHABOR和MAMP在WIP和DDS指标上的性能明显优于HABOR和AMP，这表明VCAP在后两种调度方法中的运用能够通过减少车辆阻塞和路径冲突，缩短晶舟等待时间，提高准时到达率，进而降低系统的在制品库存水平.运用HABOR和AMP进行调度时，当晶舟到达率处于较高水平时，车辆数目越多，TT平均值越高;而WT平均值随着搬运任务的增多而提高.相反，用MHABOR和MAMP调度方法时，TT保持较平稳的水平，在晶舟到达率为1080 lots · h-1，车辆数90时，VCAP的运用使得TT值分别下降高达40.4 % 和40.3 % .由此可见VCAP能够有效提高搬运效率.
4.3 防阻塞策略的稳定性为了证实防阻塞策略的稳定性，选取4.2中表现最好的调度策略MAMP，在不同规模的OHT搬运系统中进行仿真实验，NV=70，NM=10，分别令NBay=8，12，16，令μ=360，720，1080lots · h-1，每个实验均在20个仿真日预热后运行240个仿真日，重复5次.仿真结果如图 5所示.
|
图5 不同规模OHT搬运系统的MAMP性能 Fig. 5 Performances of MAMP in different OHT systems. |
由图 5可知，在晶圆到达率一定时，随着OHT搬运系统内Bay数量的增加，搬运路径变得更长更复杂，因而WT和TT的值都随之增大.对比搬运系统高负载率时的TT值，OHT系统规模较小时优于系统规模较大时的表现，说明在OHT轨道范围较小的情况下，搬运效率并没有受到车辆阻塞的明显影响.在相同规模的OHT搬运系统中，随着晶圆到达率的增大，WT和TT都随之提高，但是数值波动在可以接受的范围之内(5 % ~10 % )，而且随着NBay的增大，WT和TT曲线的上升幅度均逐渐趋缓，这表明该方法适用于复杂系统的物料搬运调度.
5 结 论本文在充分考虑搬运系统中各搬运设备间相互影响的基础上建立数学模型，提出无等待轨道的设计和基于检测点的空车运行策略，引入时间约束集进行OHT小车路径规划，从而构建了OHT搬运系统防阻塞调度策略(VCAP).仿真实验结果表明VCAP能够在避免车辆碰撞和路径冲突的基础上获得较高的搬运效率.对于不同繁忙程度及不同规模的OHT搬运系统，结合VCAP的调度方法具有良好的适应性，证明该调度策略适用于复杂系统的物料搬运调度.
| [1] | Agrawal G K,Heragu S S.A survey of automated material handling systems in 300 mm semiconductor fabs[J].IEEE Transactions on Semiconductor Manufacturing,2006,19(1):112-120.( 1) |
| [2] | Montoya-Torres J R.A literature survey on the design approaches and operational issues of automated wafer-transport systems for wafer fabs[J].Production Planning & Control,2006,17(7):648-663.(1) |
| [3] | Chung S L,Jeng M.An overview of semiconductor fab automation systems[J].IEEE Robotics & Automation Magazine,2004,11(1):8-18.(1) |
| [4] | Nazzal D,McGinnis L F.Analytical approach to estimating AMHS performance in 300 mm fabs[J].International Journal of Production Research,2007,45(3):571-590.(1) |
| [5] | Govind N,Roeder T M,Schruben L W.A simulation-based closed queueing network approximation of semiconductor automated material handling systems[J].IEEE Transactions on Semiconductor Manufacturing,2011,24(1):5-13.(1) |
| [6] | Kuo C H,Huang C S.Dispatching of overhead hoist vehicles in a fab intrabay using a multimission-oriented controller[J].The International Journal of Advanced Manufacturing Technology,2006,27(7/8):824-832.(1) |
| [7] | Wang K J,Lin J T,Weigert G.Agent-based interbay system control for a single-loop semiconductor manufacturing fab[J].Production Planning & Control,2007,18(2):74-90.(1) |
| [8] | Wu L H,Mok P Y,Zhang J.An adaptive multi-parameter based dispatching strategy for single-loop interbay material handling systems[J].Computers in Industry,2011,62(2):175-186.(2) |
| [9] | Im K,Kim K,Park T,et al.Effective vehicle dispatching method minimising the blocking and delivery times in automatic material handling systems of 300 mm semiconductor fabrication[J].International Journal of Production Research,2009,47(14):3997-4011. (1) |
| [10] | Guan X,Dai X.Deadlock-free multi-attribute dispatching method for AGV systems[J].The International Journal of Advanced Manufacturing Technology,2009,45(5/6):603-615.(1) |
| [11] | Kim B I,Shin J,Jeong S,et al.Effective overhead hoist transport dispatching based on the Hungarian algorithm for a large semiconductor FAB[J].International Journal of Production Research,2009,47(10):2823-2834.(2) |