一种Intrabay物料运输系统的多目标实时调度方法

吴立辉 朱登洁 张 洁

1.河南工业大学，郑州，450007 2.上海交通大学，上海，200240

0 引言

半导体晶圆制造系统是当今最为复杂的离散制造系统之一，具有多重入流、多品种大规模在制品、加工工序复杂、加工周期长、设备昂贵等特点［1］。一条典型的300mm晶圆制造系统通常有数千卡晶圆在制品（晶圆加工过程以“卡”为计量单位进行搬运，每个晶圆卡包括25片晶圆），每卡晶圆大概包括200～600道加工工序，20～40次重入各类型加工设备。为完成全部工序，每卡晶圆需要被搬运上千次，运输的距离达12872～16090m（8～10英里）［2］。因此，自动化物料运输系统成为晶圆制造系统的重要组成部分。其中，Intrabay物料运输系统（简称Intrabay系统）是自动化物料运输系统的主要组成部分，Intrabay系统运行效率的提高，对提高自动化物料运输系统及晶圆制造系统的系统性能具有重要意义［3］。

Intrabay系统具有大规模、动态、实时性和随机性等特点，国内外针对Intrabay系统调度问题进行了大量研究。Lin等［4］和 Hasenbein等［5］认为，Intrabay系统的调度策略对晶圆卡等待运输时间、晶圆卡搬运时间等性能指标有显著影响。Liu等［6］和Liao等［7］采用了数学规划方法对小规模Intrabay系统调度问题进行全局优化求解。Liao等［8］和 Wang［9］提出了一种分类优先级规则的Intrabay系统调度方法，该方法可明显缩短紧急晶圆卡的搬运时间。Lin等［10］将先到先服务规则用于Intrabay系统调度，并将推拉结合的策略用于物料运输小车的配送。Le－anh等［11］提出了一种基于组合派发规则方法的Intrabay系统调度方法，晶圆卡平均等待时间和运输小车有效利用率等指标得到明显提高。然而，整数规划方法主要适用于小规模的物料运输问题优化求解。基于单/多规则的启发式调度方法通常适用于稳态环境下的系统单/多目标优化调度，难以满足随机、动态变化环境下的Intrabay系统多目标调度优化需求。

本文在对Intrabay调度问题分析的基础上，提出了一种基于模糊逻辑和匈牙利方法的Intrabay系统多目标实时调度方法，该方法实时响应运输小车空载和晶圆卡请求运输等事件，对各动态事件时刻的Intrabay系统调度子问题进行多目标优化求解。针对Intrabay系统调度子问题，在基于模糊逻辑方法对晶圆卡运输优先级排序的基础上，采用匈牙利方法对Intrabay系统的运输小车和晶圆卡进行优化指派，并采用贪婪优化的运输小车搬运策略指导运输小车搬运晶圆卡，从而形成优化的Intrabay系统调度方法，提高了Intrabay系统和晶圆加工系统的多目标综合性能。

1 Intrabay系统调度问题

Intrabay系统通常采用单闭环型轨道布局（图1），由运输导轨、存储仓库、晶圆加工设备装/卸缓冲区和运输小车组成，晶圆加工设备装/卸缓冲区与晶圆加工设备相连，存储仓库与Intrabay系统连接。Intrabay系统有多台运输小车，负责将晶圆卡按加工工艺运输到各晶圆加工设备或存储仓库。Intrabay系统的运输任务十分庞大，待搬运晶圆卡竞争运输小车以及运输小车之间堵塞等现象频繁发生，晶圆卡搬运过程容易出现死锁，使得Intrabay系统运行效率降低。因此，需通过Intrabay系统调度以合理安排运输小车搬运晶圆卡，提高Intrabay系统和晶圆加工系统的多目标综合效率。

图1 Intrabay系统布局示意图

Intrabay系统调度问题有如下假设和约束：①晶圆卡每道工序的加工时间是确定的；②每个晶圆卡在加工设备上完成当前工序后，根据加工工艺等待运输小车搬运到下一工序晶圆加工设备或存储仓库；③存储仓库的容量足够大；④每个运输小车1次只能搬运1个晶圆卡；⑤各运输小车互相独立，且运行过程中不能互相穿越；⑥为避免运输小车冲突，每段运输导轨任意时刻只允许一台运输小车运行；⑦晶圆卡部分加工工序间的等待时间具有时效性约束；⑧晶圆卡搬运过程中存在死锁。

2 Intrabay系统多目标实时调度方法

Intrabay系统多目标实时调度方法框架如图2所示。该方法实时响应运输小车空载和晶圆卡请求运输等事件，对各动态事件时刻的Intrabay系统调度子问题进行求解。针对Intrabay系统调度子问题，首先，利用模糊逻辑方法快速响应和动态推理决策的优点［13］，建立基于模糊逻辑的晶圆卡运输优先级动态决策模型，该模型根据晶圆交货期满足率参数、晶圆卡的等待时间参数和In－trabay系统的负载参数，对等待搬运晶圆卡的运输优先级进行动态决策，从而提高晶圆交货期满足率和晶圆产出量，减少晶圆卡总的运输时间和晶圆加工周期。其次，利用匈牙利算法快速全局优化求解的优点［14］，对空闲运输小车和高优先级的晶圆卡进行优化指派，减少搬运过程中运输小车的临时性堵塞，从而缩短晶圆卡被运输小车搬运时间和晶圆加工周期，提高运输小车搬运量。再次，根据优化指派结果，提出基于贪婪优化的运输小车搬运策略，该策略根据当前晶圆卡所处加工设备和下一工序加工设备（目标加工设备）的状态，指导相应运输小车选择推/拉的搬运策略，以减少加工设备的空载等待时间；在推/拉式搬运过程中，运输小车根据晶圆卡目标加工设备的输入端口的状态，选择晶圆卡的临时存储位置，避免晶圆卡目标加工设备的输入端口负载导致运输小车无法卸载晶圆卡的死锁现象，从而提高运输小车搬运量和晶圆产出量。

图2 Intrabay系统的多目标实时调度方法框架

2.1 基于模糊逻辑的晶圆卡运输优先级动态决策模型

基于模糊逻辑的晶圆卡运输优先级动态决策模型建立过程包括：定义输入/输出变量、确定输入/输出变量的隶属度函数，建立模糊推理规则表，确定模糊推理策略、规则聚合策略和解模糊化策略等。晶圆卡运输优先级动态决策模型的输出变量为晶圆卡运输优先级，模糊推理策略采用Mamdani方法，规则聚合策略选用最大－最小规则，解模糊化策略采用最大隶属度函数方法［15］。Mamdani推理策略、最大－最小规则聚合策略和最大隶属度函数的解模糊化策略的具体描述请参考文献［16］。

2.1.1 输入变量

晶圆卡运输优先级动态决策模型的输入变量包括：晶圆交货期满足率参数、晶圆卡的等待时间参数和Intrabay系统的负载参数，分别定义为x1、x2和x3。

（1）晶圆交货期满足率参数x1，表示Intrabay系统中的晶圆交货期紧急程度，可描述为

式中，Fac为Intrabay系统中已完成加工晶圆的平均交货期松弛系数；RTi为晶圆i距离指定交货期的剩余时间；RPi为晶圆i剩余工序的加工时间；PTj为晶圆j各工序总的加工时间；CTj为晶圆j交货周期；k为已完成加工的晶圆数量。

（2）晶圆卡的等待时间参数x2，表示晶圆卡在当前设备或存储仓库输出端口的等待时间，可描述为

式中，AW为Intrabay系统中晶圆卡的平均等待时间；CWi为晶圆卡i的当前等待时间。

（3）Intrabay系统的负载参数x3，表示Intra－bay系统当前负载率的大小，可描述为

式中，NC为Intrabay系统中等待运输的晶圆卡的数量；NV为Intrabay系统中运输小车的数量。

2.1.2 隶属度函数和模糊规则表

基于模糊逻辑的晶圆卡运输优先级动态决策模型采用三角型和梯型隶属度函数［17］，建立的输入输出变量隶属度函数如表1所示。在调研获取专家经验的基础上，采用实验设计方法对各模糊语言变量的模糊值进行组合实验，选取其中实验结果较优的输入输出模糊语言变量组合值建立的模糊规则表如表2所示。

表1 晶圆卡运输优先级动态决策模型输入和输出变量的隶属度函数

表2 晶圆卡运输优先级动态决策模型的模糊规则表

2.2 基于匈牙利算法的物料运输任务指派方法

设定运输小车空载和晶圆卡请求运输等事件时刻，Intrabay系统中有Nw个等待运输的晶圆卡和m个空载运输小车。当Nw＞m时，选取优先级较高的前m个晶圆卡作为物料运输调度的晶圆卡子集合。则物料运输调度的晶圆卡数量n可表示为n＝min（m，Nw）。m个运输小车搬运n个晶圆卡的Intrabay系统调度子问题可描述为

式中，C0为晶圆卡运输成本矩阵；Cij为运输小车j搬运晶圆卡i所需要的运输时间；Xij为匹配系数，当指定采用运输小车j搬运晶圆卡i时，则对应的Xij值为1，否则为0。

以上Intrabay系统调度子问题可等效为运输小车集合向晶圆卡集合派发的二部图匹配问题。而匈牙利方法可快速获得二部图匹配问题的全局优化解［18］，有效减少运输小车的临时性堵塞，适合该子问题的求解。基于匈牙利方法的具体求解过程可参考文献［18］。

2.3 基于贪婪优化的运输小车搬运策略

基于贪婪优化的运输小车搬运策略采用推/拉结合的思想［19］，根据当前晶圆卡所处加工设备和目标加工设备的状态，指导运输小车选择推/拉的搬运策略对当前晶圆卡进行搬运，如图3所示。该方法的运行逻辑描述如下：

图3 基于贪婪优化的运输小车搬运策略

（1）运输小车判断当前晶圆卡的目标加工设备属性，当目标加工设备为存储仓库时，运输小车将当前晶圆卡搬运至存储仓库；否则，进入步骤（2）。

（2）当有其他晶圆卡请求进入当前晶圆卡所处加工设备时，运输小车基于推式的搬运策略将当前晶圆卡搬离其所处加工设备，搬运过程中，运输小车根据当前晶圆卡的目标加工设备输入端口的状态空闲与否，选择将晶圆卡搬运至目标加工设备或存储仓库，避免晶圆卡目标加工设备的输入端口负载导致运输小车无法卸载晶圆卡的死锁现象。否则，当没有其他晶圆卡请求进入当前晶圆卡所处加工设备时，进入步骤（3）。

（3）运输小车基于拉式的搬运策略对当前晶圆卡进行搬运，当晶圆卡的目标加工设备输入端口空闲时，运输小车将该晶圆卡搬运至目标加工设备；当晶圆卡的目标加工设备输入端口有负载时，运输小车取消当前运输任务，避免晶圆卡目标加工设备的输入端口负载导致运输小车无法卸载晶圆卡的死锁现象。

3 仿真实验分析

采用某300mm晶圆制造系统的Intrabay系统的生产数据，基于eM－Plant软件建立Intrabay系统仿真模型，对提出的Intrabay系统多目标实时调度方法进行实验分析。Intrabay子系统共包括28台设备和2个存储仓库，运输轨道长108m，运输小车运行速度1m/s，晶圆卡装载和卸载的时间为16s。设定Intrabay子系统共加工2种晶圆产品（A、B），每个晶圆卡重入Intrabay系统次数为5次，晶圆投料比例为3∶2，投料时间服从正态分布。Intrabay系统调度算法采用C＋＋语言实现，并通过eM－Plant软件的C/C C＋＋接口调用。仿真实验运行时间周期设定为15天；运输小车数量分别选取为5台、6台、7台，系统负载率分别选取为90%、100%和110%，共组成9种实验场景。

为了验证本文提出的多目标实时调度方法的有效性，将其与传统的先到先服务规则（简称FEFS）和最高优先级规则（简称HP）进行比较，FEFS和HP规则方法是晶圆制造工厂Intrabay系统调度中最常采用且被验证为有效的调度方法［20－21］，比较的性能指标采用综合性能指标函数D。实验比较结果如图4所示，从图4可以看出，GDP方法在9种实验场景下的综合期望函数值都优于传统的FEFS和HP方法。在此基础上，将多目标实时调度方法与FEFS、HP方法进行方差分析（简称ANOVA）比较（表3），从表3可知，多目标实时调度方法与FEFS、HP方法的F统计值分别为26.72和16.22，表明提出的多目标实时调度方法与FEFS、HP方法的综合期望函数值有显著差异。以上实验结果表明：本文提出的Intrabay系统多目标实时调度方法的综合性能明显优于传统的FEFS和HP方法，验证了该方法的有效性。

图4 多目标实时调度方法与FEFS、HP方法的仿真实验比较结果

表3 多目标实时调度方法与FEFS、HP方法的方差分析比较

4 结束语

本文提出了一种Intrabay系统的多目标实时调度方法。该方法实时响应运输小车空载和晶圆请求运输等动态事件，并对各事件时刻的Intrabay系统调度子问题进行优化求解。采用300mm晶圆制造系统的生产数据进行仿真实验，并与传统基于先到先服务和最高优先级规则的Intrabay系统调度方法进行比较，实验结果表明：在各种实验场景下，本文提出的多目标实时调度方法在晶圆卡被运输小车搬运时间、晶圆卡总的运输时间、运输小车搬运量、晶圆产出量、晶圆加工周期和晶圆交货期满足率等指标方面具有更优的综合性能，表明了本文提出的Intrabay系统多目标实时调度方法是有效的。在本文的研究基础上，将进一步研究晶圆加工系统与物料运输系统集成调度问题。

［1］Lin D P，Lee K M.A Review of the Research Meth－odology for the Re－entrant Scheduling Problem［J］.International Journal of Production Research，2011，49（8）：2221－2242.

［2］Govind N，Roeder T，Schruben L W.A Simulationbased Closed Queuing Network Approximation of Semiconductor Automated Material Handling Systems［J］.IEEE Transactions on Semiconductor Manufacturing，2011，24（1）：5－13.

［3］Agrawal G K，Heragu S S.A Survey of Automated Material Handling Systems in 300mm Semiconductor Fabs［J］.IEEE Transactions on Semiconductor Manufacturing，2006，19（1）：112－120.

［4］Lin J T，Wang F K，Yen P Y.Simulation Analysis of Dispatching Rules for An Automated Interbay Material Handling System in Wafer Fab［J］.International Journal of Production Research，2001，39（6）：1221－1238.

［5］Hasenbein J，Sigireddy S，Wright R.Taking a Queue from Simulation：The Many Rules of Scheduling Semiconductor Material Handling［J］.IEEE Transactions，2004，36（8）：39－43.

［6］Liu C Y，Liao D Y.An Optimal OHT Dispatching System for 300mm Semiconductor Manufacturing［C］//IEEE International Conference on Systems，Man and Cybernetics.Piscataway：IEEE Press，2004：1631－1636.

［7］Liao D Y，Jeng M D，Zhou M C.Application of Petri Nets and Lagrangian Relaxation to Scheduling Automatic Material－ handling Vehicles in 300mm Semiconductor Manufacturing［J］.IEEE Transactions on Systems，Man and Cybernetics－Part C：Applications and Reviews，2007，37（4）：504－516.

［8］Liao D Y，Wang C N.Differentiated Pre－emptive Dispatching for Automatic Materials Handling Services in 300mm Semiconductor Foundry［J］.International Journal of Advanced Manufacturing Technology，2006，29（9/10）：890－896.

［9］Wang C N.The Heuristic Dispatching Method of Automatic Material Handling System in 300mm Semiconductor Fabrication［J］.International Journal of Innovative Computer Information and Control，2009，5（7）：1927－1935.

［10］Lin J T，Wang F K，Chang Y M.A Hybrid Push/Pull Dispatching Rule for a Photo－bay in a 300mm Wafer Fab［J］.Robotics and Computer Integrated Manufacturing，2006，2（1）：47－55.

［11］Le－anh T，De－Koster M.On－line Dispatching Rules for Vehicle－based Internal Transport Systems［J］.International Journal of Production Research，2005，43（8）：1711－1728.

［12］Myers R H，Montgomery D C.Response Surface Methodology：Process and Production Optimization Using Designed Experiments（Wiley Series in Probability and Statistics）［M］.New York：Wiley Inter－Science Publications，2009.

［13］Vinodh S，Balaji S R.Fuzzy Logic Based Leanness Assessment and Its Decision Support System［J］.International Journal of Production Research，2011，49（13）：4027－4041.

［14］Goldberger J，Tassa T.A Hierarchical Clustering Algorithm Based on the Hungarian Method［J］.Pattern Recognition Letters，2008，29（11）：1632－1638.

［15］Azadegan A，Ghazinoory S，Samouei P.Fuzzy Logic in Manufacturing：A Review of Literature and a Specialized Application［J］.International Journal of Production Economics，2011，132（2）：258－270.

［16］李士勇.模糊控制［M］.哈尔滨：哈尔滨工业大学出版社，2011.

［17］Mok P Y，Kwong C K，Wong W K.Optimization of Fault－tolerant Fabric－cutting Schedules Using Genetic Algorithms and Fuzzy Set Theory［J］.European Journal of Operational Research，2007，177（26）：1876－1893.

［18］Wu L H，Mok P Y，Zhang J.An Adaptive Multiparameter Based Dispatching Strategy for Singleloop Interbay Material Handling Systems［J］.Computers in Industry，2011，62：175－186.

［19］Li B，Yang C J.Production Logistics System Based on a Hybrid Push/Pull Control Strategy in Maketo－order Environments［J］.International Journal of Innovative Computing Information and Control，2009，5（5）：1343－1350.

［20］Kuo C H，Wang C H，Huang K W.Behavior Modeling and Control of 300mm Fab Intrabays Using Distributed Agent Oriented Petri Net［J］.IEEE Transactions on Systems，Man and Cybernetics－Part A：Systems and Humans，2003，33（5）：641－648.

［21］Wang C N，Liao D Y.Expeditious Hot Lots Handling in 300mm Semiconductor Foundry［C］//IEEE International Conference on Systems，Man and Cybernetics.Piscataway：IEEE Press，2006：4677－4681.