工程科学学报，第41卷，第2期：261-268,2019年2月 Chinese Joural of Engineering,Vol.41,No.2:261-268,February 2019 DOI:10.13374/j.issn2095-9389.2019.02.014;http://journals.ustb.edu.cn 基于捷径重试规则晶圆带式搬运系统性能优化 周炳海⑧，陈立扬 同济大学机械与能源工程学院，上海201804 区通信作者，E-mail:bhzhou@tongji.cu.cm 摘要采用数学分析的方法构建了性能分析模型并提出了制定捷径决策的方法.在建模过程中，首先引入了重试运输规 则，并考虑重试率随捷径策略变动的情况下，引用相关重试排队模型，构建了系统期望在制品数量的数学表达式.同时根据每 条捷径的使用成本，构建了相应的捷径成本的数学表达式.从而获得以最小化捷径数量与在制品数量为目标函数的优化分析 模型.此外，引入了基于传送带长度的约束条件，使系统在每段传送带以及捷径上的在制品数量不会超过传送带的容量限制. 最后使用NSGA-Ⅱ算法对多目标优化问题进行分析计算.考察在不同物流负荷下的系统在制品数量和成本之间的关系变化 规律，并分别绘制帕累托前沿图形进行比较分析，研究了目标函数中的系数设定对系统的影响，并结合聚类分析的算法对所 得的解集进行分类.综合以上分析结果总结出系统捷径的最佳使用策略，并通过与现有系统和搬运策略进行比较，证实了该 策略在降低成本和在制品方面的有效性。 关键词晶圆制造；捷径优化；自动物料搬运系统；重试排队模型；interbay系统 分类号TP29 Performance optimization of the wafer conveyor handling system using the crossover retrial rule ZHOU Bing-hai,CHEN Li-yang School of Mechanical Engineering,Tongji University,Shanghai 201804,China Corresponding author,E-mail:bhzhou@tongji.edu.cn ABSTRACT The semiconductor wafer fabrication system is one of the most complex discrete manufacturing systems owing to its great number of production steps,heavy re-entry production flow,various kinds of products,etc.The automatic material handling system plays a key role in improving the production efficiency.reducing the work in process (WIP),and shortening the production cycle time of the semiconductor factory.To rapidly and effectively evaluate the impact of crossover systems on the overall performance of transport systems in wafer production,a performance analysis model was built by mathematical analysis and a decision-making method of cross- overs was established.In the modeling procedure,the retrial transportation rule was first introduced.Then,considering the change in retrial rate affected by the crossovers strategy and referencing the related retrial queuing model,the mathematical expression of the ex- pected WIP was constructed.Simultaneously,according to the cost of each crossover,the mathematical expression of the cost of cross- overs was built.The optimization analysis model was obtained with the objective of minimizing the number of crossovers and WIP.Fur- thermore,the constraint conditions based on the length of the conveyor belt were introduced,so that the number of WIP products on each conveyor belt and crossover would not exceed the capacity limit of the conveyor belt.Finally,the NSGA-II algorithm was used to solve the multi-objective optimization problem.The relation between the number of WIP and cost of crossovers under different logistics loads was investigated,and Pareto frontier charts were drawn up for comparative analysis.The influence of parameter settings on the objective function of the system was studied,and the solution set was classified by clustering the analysis algorithm.Based on the above 收稿日期：2017-12-30 基金项目：国家自然科学基金资助项目(71471135)
工程科学学报,第 41 卷,第 2 期:261鄄鄄268,2019 年 2 月 Chinese Journal of Engineering, Vol. 41, No. 2: 261鄄鄄268, February 2019 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2019. 02. 014; http: / / journals. ustb. edu. cn 基于捷径重试规则晶圆带式搬运系统性能优化 周炳海苣 , 陈立扬 同济大学机械与能源工程学院, 上海 201804 苣通信作者, E鄄mail: bhzhou@ tongji. edu. cn 摘 要 采用数学分析的方法构建了性能分析模型并提出了制定捷径决策的方法. 在建模过程中,首先引入了重试运输规 则,并考虑重试率随捷径策略变动的情况下,引用相关重试排队模型,构建了系统期望在制品数量的数学表达式. 同时根据每 条捷径的使用成本,构建了相应的捷径成本的数学表达式. 从而获得以最小化捷径数量与在制品数量为目标函数的优化分析 模型. 此外,引入了基于传送带长度的约束条件,使系统在每段传送带以及捷径上的在制品数量不会超过传送带的容量限制. 最后使用 NSGA鄄鄄II 算法对多目标优化问题进行分析计算. 考察在不同物流负荷下的系统在制品数量和成本之间的关系变化 规律,并分别绘制帕累托前沿图形进行比较分析,研究了目标函数中的系数设定对系统的影响,并结合聚类分析的算法对所 得的解集进行分类. 综合以上分析结果总结出系统捷径的最佳使用策略,并通过与现有系统和搬运策略进行比较,证实了该 策略在降低成本和在制品方面的有效性. 关键词 晶圆制造; 捷径优化; 自动物料搬运系统; 重试排队模型; interbay 系统 分类号 TP29 收稿日期: 2017鄄鄄12鄄鄄30 基金项目: 国家自然科学基金资助项目(71471135) Performance optimization of the wafer conveyor handling system using the crossover retrial rule ZHOU Bing鄄hai 苣 , CHEN Li鄄yang School of Mechanical Engineering, Tongji University, Shanghai 201804, China 苣Corresponding author, E鄄mail: bhzhou@ tongji. edu. cn ABSTRACT The semiconductor wafer fabrication system is one of the most complex discrete manufacturing systems owing to its great number of production steps, heavy re鄄entry production flow, various kinds of products, etc. The automatic material handling system plays a key role in improving the production efficiency, reducing the work in process (WIP), and shortening the production cycle time of the semiconductor factory. To rapidly and effectively evaluate the impact of crossover systems on the overall performance of transport systems in wafer production, a performance analysis model was built by mathematical analysis and a decision鄄making method of cross鄄 overs was established. In the modeling procedure, the retrial transportation rule was first introduced. Then, considering the change in retrial rate affected by the crossovers strategy and referencing the related retrial queuing model, the mathematical expression of the ex鄄 pected WIP was constructed. Simultaneously, according to the cost of each crossover, the mathematical expression of the cost of cross鄄 overs was built. The optimization analysis model was obtained with the objective of minimizing the number of crossovers and WIP. Fur鄄 thermore, the constraint conditions based on the length of the conveyor belt were introduced, so that the number of WIP products on each conveyor belt and crossover would not exceed the capacity limit of the conveyor belt. Finally, the NSGA鄄鄄II algorithm was used to solve the multi鄄objective optimization problem. The relation between the number of WIP and cost of crossovers under different logistics loads was investigated, and Pareto frontier charts were drawn up for comparative analysis. The influence of parameter settings on the objective function of the system was studied, and the solution set was classified by clustering the analysis algorithm. Based on the above
·262· 工程科学学报，第41卷，第2期 analysis results,the best strategy of system crossovers was summarized.By comparing the proposed system with the existing system and transportation strategy,the effectiveness of the strategy in reducing cost and WIP was confirmed. KEY WORDS wafer fabrications;crossover-optimization;automatic material handling system;retrial queuing model;interbay sys- tem 自动化物料运输系统(automatic material han- 然而以上文献在进行晶圆搬运系统分析的时 dling system,AMHS)作为品圆制造的重要组成部 候，基本没有考虑提出基于带传送系统缓存容量约 分，对其进行优化研究具有重要意义.经由制造控 束的优化问题，同时对于无法进入intrabay的在制 制系统的调控，AMHS具有运输快速、准确、灵活等 品只能通过interbay闭环传送带搬运，降低了效率. 特点，同时还可以提高晶圆的品质，减少由于搬运中 为此，选取interbay为研究对象，基于利用捷径进行 震动带来的问题).AMHS能有效减少生产周期时 快速重试的晶圆搬运规则，建立系统总的加工在制 间、增加设备使用率，从而提高整个生产流程的绩 品数量以及捷径使用成本的数学表达关系式，结合 效.因此，一个性能稳定且搬运效率高的AMHS在 考虑各处传送带对系统的约束，建立相应的数学模 晶圆制造系统中扮演着一个非常重要的角色.随着 型，对系统进行综合的分析和优化，获得相应的综合 品圆制造技术的发展，晶圆尺寸不断扩大，450mm 性最优的捷径使用策略 直径品圆的出现将使目前的高空提升运输车(over- 1系统描述 head hoist transporter,OHT)不能满足晶圆搬运需 求[2)，而基于带传送的连续物料搬运方式(continual 选取的系统是基于传送带连续流动搬运方式 flow transporter,CFT),将成为下一代晶圆制造中最 (C℉T)的对称脊柱式布局的晶圆生产系统，晶圆制 有效的一种自动物料搬运方式) 造的AMHS主要由Interbay与Intrabay两部分组成， 针对CFT的AMHS系统的研究主要从系统模 即中央布置基于带传输的封闭式Interbay,上下两侧 型分析以及系统性能优化两个方面进行.在模型分 分布着同样基于带传输的封闭式ntrabay.两者之 析方面，Bozer和Hsieh提出了一种基于CFT系统 间通过品舟存储柜(Stockers)来实现两者之间晶舟 的闭环传送带分析模型，可以有效求解系统的期望 的交换及暂存.而由于晶圆制造系统中设备复杂、 运输能力及在制品数量.Nazzal等[)提出了符合晶 产品数量众多、反复重入型的制造过程使得Inter- 圆制造环境的CT系统的分析模型.为了更贴近实 bay物料搬运系统承担了较重的搬运负荷，所以结 际的晶圆生产系统，其又在上述分析模型中加入了 合重试排队理论中重试率与队列长的关系，提出利 捷径的设置，得到的模型能较理想的反映了CFT系 用捷径进行快速的重试搬运.在该规则下，无法进 统的运行情况[.Zhou和Chen7-8]分析了传送带 入intrabay的品圆将通过使用捷径选择最短的路径 转向装置服务时间变动下的捷径问题，并考虑集合 运输以达到尽快进行下次重试的目的.以具有2m interbay系统与intrabay系统，将性能分析模型从in- 个Intrabay系统为例，其整体结构如图1所示，其 terbay系统扩展到完整的整体式晶圆连续物料搬运 中，n≤2m. 系统.在系统性能优化方面，许多研究集中于研究 针对该系统，在每个intrabay的人口处设置与 如何降低运输距离、运输成本以及运输时间.Wang interbay中传送带方向一致的捷径，并进行如下的假 等[9-o]提出了在intrabay系统中考虑将调度规则与 设：(I)所有的intrabay设备组之间的运输流量需 转向捷径结合的方法来提升搬运的性能.Hong 求以从至表表示，每个intrabay设备组晶舟到达过 等基于捷径布局优化目标提出了以在制品数量 程服从泊松过程a];(2)每个intrabay的进口处都 最小化为目标的数学模型，并运用多种启发式算法 有一个缓冲区，假设缓冲区容量为1，所有需要进入 对其进行优化分析.Lasrado与Nazzal[2]在此基础 该intrabay的晶舟会首先尝试转入缓冲区，如果缓 上提出了对捷径使用优化的数学模型，并分析了不 冲区满，则晶舟进入重试环路循环运输直到成功为 同搬运强度下的最优捷径策略.周炳海等]在此 止：(3)所有进入重试循环运输的晶舟都会选择最 基础上提出将interbay系统设置成具有相反运输路 短的重试路径：(4)每个intrabay的出口处也有一 径的内外圈结构，内外圈间以捷径进行连接，以达到 个缓冲区，假设缓冲区容量无限制，其主要作用是控 更快的搬运速度，并对该模型进行了性能分析和仿 制intrabay之间的流量：(5)传送带可以根据其长 真实验比较. 度划分为相同尺寸的片段，每一片段可以容纳一个
工程科学学报,第 41 卷,第 2 期 analysis results, the best strategy of system crossovers was summarized. By comparing the proposed system with the existing system and transportation strategy, the effectiveness of the strategy in reducing cost and WIP was confirmed. KEY WORDS wafer fabrications; crossover鄄optimization; automatic material handling system; retrial queuing model; interbay sys鄄 tem 自动化物料运输系统( automatic material han鄄 dling system,AMHS) 作为晶圆制造的重要组成部 分,对其进行优化研究具有重要意义. 经由制造控 制系统的调控,AMHS 具有运输快速、准确、灵活等 特点,同时还可以提高晶圆的品质,减少由于搬运中 震动带来的问题[1] . AMHS 能有效减少生产周期时 间、增加设备使用率,从而提高整个生产流程的绩 效. 因此,一个性能稳定且搬运效率高的 AMHS 在 晶圆制造系统中扮演着一个非常重要的角色. 随着 晶圆制造技术的发展,晶圆尺寸不断扩大,450 mm 直径晶圆的出现将使目前的高空提升运输车( over鄄 head hoist transporter, OHT) 不能满足晶圆搬运需 求[2] ,而基于带传送的连续物料搬运方式(continual flow transporter, CFT),将成为下一代晶圆制造中最 有效的一种自动物料搬运方式[3] . 针对 CFT 的 AMHS 系统的研究主要从系统模 型分析以及系统性能优化两个方面进行. 在模型分 析方面,Bozer 和 Hsieh [4]提出了一种基于 CFT 系统 的闭环传送带分析模型,可以有效求解系统的期望 运输能力及在制品数量. Nazzal 等[5] 提出了符合晶 圆制造环境的 CFT 系统的分析模型. 为了更贴近实 际的晶圆生产系统,其又在上述分析模型中加入了 捷径的设置,得到的模型能较理想的反映了 CFT 系 统的运行情况[6] . Zhou 和 Chen [7鄄鄄8] 分析了传送带 转向装置服务时间变动下的捷径问题,并考虑集合 interbay 系统与 intrabay 系统,将性能分析模型从 in鄄 terbay 系统扩展到完整的整体式晶圆连续物料搬运 系统. 在系统性能优化方面,许多研究集中于研究 如何降低运输距离、运输成本以及运输时间. Wang 等[9鄄鄄10]提出了在 intrabay 系统中考虑将调度规则与 转向捷径结合的方法来提升搬运的性能. Hong 等[11]基于捷径布局优化目标提出了以在制品数量 最小化为目标的数学模型,并运用多种启发式算法 对其进行优化分析. Lasrado 与 Nazzal [12] 在此基础 上提出了对捷径使用优化的数学模型,并分析了不 同搬运强度下的最优捷径策略. 周炳海等[13] 在此 基础上提出将 interbay 系统设置成具有相反运输路 径的内外圈结构,内外圈间以捷径进行连接,以达到 更快的搬运速度,并对该模型进行了性能分析和仿 真实验比较. 然而以上文献在进行晶圆搬运系统分析的时 候,基本没有考虑提出基于带传送系统缓存容量约 束的优化问题,同时对于无法进入 intrabay 的在制 品只能通过 interbay 闭环传送带搬运,降低了效率. 为此,选取 interbay 为研究对象,基于利用捷径进行 快速重试的晶圆搬运规则,建立系统总的加工在制 品数量以及捷径使用成本的数学表达关系式,结合 考虑各处传送带对系统的约束,建立相应的数学模 型,对系统进行综合的分析和优化,获得相应的综合 性最优的捷径使用策略. 1 系统描述 选取的系统是基于传送带连续流动搬运方式 (CFT)的对称脊柱式布局的晶圆生产系统,晶圆制 造的 AMHS 主要由 Interbay 与 Intrabay 两部分组成, 即中央布置基于带传输的封闭式 Interbay,上下两侧 分布着同样基于带传输的封闭式 Intrabay. 两者之 间通过晶舟存储柜(Stockers)来实现两者之间晶舟 的交换及暂存. 而由于晶圆制造系统中设备复杂、 产品数量众多、反复重入型的制造过程使得 Inter鄄 bay 物料搬运系统承担了较重的搬运负荷,所以结 合重试排队理论中重试率与队列长的关系,提出利 用捷径进行快速的重试搬运. 在该规则下,无法进 入 intrabay 的晶圆将通过使用捷径选择最短的路径 运输以达到尽快进行下次重试的目的. 以具有 2m 个 Intrabay 系统为例,其整体结构如图 1 所示,其 中,n臆2m. 针对该系统,在每个 intrabay 的入口处设置与 interbay 中传送带方向一致的捷径,并进行如下的假 设:(1) 所有的 intrabay 设备组之间的运输流量需 求以从至表表示,每个 intrabay 设备组晶舟到达过 程服从泊松过程[4] ;(2) 每个 intrabay 的进口处都 有一个缓冲区,假设缓冲区容量为 1,所有需要进入 该 intrabay 的晶舟会首先尝试转入缓冲区,如果缓 冲区满,则晶舟进入重试环路循环运输直到成功为 止;(3) 所有进入重试循环运输的晶舟都会选择最 短的重试路径;(4) 每个 intrabay 的出口处也有一 个缓冲区,假设缓冲区容量无限制,其主要作用是控 制 intrabay 之间的流量;(5) 传送带可以根据其长 度划分为相同尺寸的片段,每一片段可以容纳一个 ·262·
周炳海等：基于捷径重试规则晶圆带式搬运系统性能优化 ·263· /品圆存储柜n 士 Intrabay 。捷径n Interbay m41 m+2 2n-n-1 2m-1 2m 图1基于捷径的AMHS布局图 Fig.1 AMHS layout with crossover 晶舟：(6)假设晶舟在通过转向节点时的时间很短， 对interbay整体分析的影响较小，此处不作计算； s.t.(E+1) 克E(WIP(x》+()产+ i=1 (7)晶舟在重试循环运输的重试率服从以平均运输 时间为参数的指数分布；(8)假设所有intrabay生 A(x)<,n=1,2,…,2m (3) 产时间都服从相互独立的一般分布. 为方便模型表述，定义如下符号及变量： (+1) 入：由intrabay i前往intrabay j的晶舟流量；入，： intrabay i的整体到达晶舟流量；B、B,:intrabay i处 /1(x)2<4,n=1,2,,2m-1(4） 设备加工时间所服从分布的一阶矩与二阶矩；l:in- (+1) trabay i与intrabayj之间传送带的长度；s:为捷径i E(WIP ()+ 的长度；x:表示intrabay i处捷径的使用情况，I表 (5) 示启用，0表示未启用：x:各捷径使用情况变量组成 (2m 10 的变量组，即(x1,x2,…,x2m);S:由启用的捷径构成 其中，对所有x∈{0,1}×2m. 的集合；S,:通过捷径i进行intrabay间运输的流量 在上述多目标问题模型的描述中，目标函数 入，集合；R:使用捷径i上游启用捷径进行intrabay (I)定义为最小化整个interbay系统中在制品的数 间物料搬运的流量集合：”：表示单位时间内传送带 量，其中E(WIP(x))表示intrabay i处的期望在制 的平均运输速度；心：表示单个产品所占用的传送带 品数量.目标函数(2)则定义了最小化捷径使用的 的长度；入+1：表示intrabay间运输在闭环传送带 总成本，其中捷径所消耗的成本c:是与捷径i的长 lna+1上的总流量；A:表示intrabay间运输在捷径i 度s:有关的成本，本文中假设其值与长度成正比， 上的总流量；T,(t):表示intrabay i处重试时间间隔 即c:=c×s,c为单位长度的成本.约束条件(3)确 的概率密度函数；WIP°(x):intrabay i处重试区中 保捷径上的在制品数量不会超过捷径容量，其中ε 的在制品数量；WIP(x):捷径n上intrabay i的在制 表示宽放系数.约束条件(4)和(5)确保了在闭环 品数量：WIP+'(x):闭环传送带n,n+1上intra- 上运输的在制品数量不会超过闭环传送带的容量. bayi的在制品数量. 2.2模型参数分析 2.2.1路径选择分析 2模型构建 在目标函数(1)和约束(3)、(4)和(5)的计算 2.1目标函数与约束 过程中，要进行品圆搬运的路径选择.由于捷径的 有效评估Interbay系统中整体的在制品量，对 设置，所以所有的物料运输都将遵守最短路径的原 了解搬运系统运行状况具有很大参考价值.在减少 则.由于捷径的开闭情况以及物料运输的起止位 在制品数量的同时如何控制成本同样是管理者的目 置，可能出现三种捷径使用情况：(1)使用两条捷 标.所以在上述介绍的模型的基础上提出如下多目 径：(2)使用一条捷径：(3)不使用捷径. 标问题，其中用f(x)5(x)表示两个目标函数， 在此假设p表示intrabay i出发的在制品运输 过程中选择的同侧出发的捷径编号，q表示intrabay min f(x)= CE(WIP (x)) (1) i选择的对侧出发的捷径编号.令d:(x)表示在已 min6(x)=C(x)=合 知捷径策略为x=(x1,名2，…，x2m)的情况下从intra- (2) bayi到intrabay j的搬运距离，则对于从intrabay i
周炳海等: 基于捷径重试规则晶圆带式搬运系统性能优化 图 1 基于捷径的 AMHS 布局图 Fig. 1 AMHS layout with crossover 晶舟;(6) 假设晶舟在通过转向节点时的时间很短, 对 interbay 整体分析的影响较小,此处不作计算; (7) 晶舟在重试循环运输的重试率服从以平均运输 时间为参数的指数分布;(8) 假设所有 intrabay 生 产时间都服从相互独立的一般分布. 为方便模型表述,定义如下符号及变量: 姿ij:由 intrabay i 前往 intrabay j 的晶舟流量;姿i: intrabay i 的整体到达晶舟流量;茁 i 1 、茁 i 2 :intrabay i 处 设备加工时间所服从分布的一阶矩与二阶矩;l ij:in鄄 trabay i 与 intrabay j 之间传送带的长度;si:为捷径 i 的长度;xi:表示 intrabay i 处捷径的使用情况,1 表 示启用,0 表示未启用;x:各捷径使用情况变量组成 的变量组,即(x1 ,x2 ,…,x2m );S:由启用的捷径构成 的集合;Si:通过捷径 i 进行 intrabay 间运输的流量 姿ij集合;Ri:使用捷径 i 上游启用捷径进行 intrabay 间物料搬运的流量集合;v:表示单位时间内传送带 的平均运输速度;w:表示单个产品所占用的传送带 的长度;姿 I n,n + 1 :表示 intrabay 间运输在闭环传送带 l n,n + 1上的总流量;姿 I i:表示 intrabay 间运输在捷径 i 上的总流量;Ti(t):表示 intrabay i 处重试时间间隔 的概率密度函数; WIP O i ( x):intrabay i 处重试区中 的在制品数量;WIP n i (x):捷径 n 上 intrabay i 的在制 品数量;WIP n,n + 1 i ( x):闭环传送带 n,n + 1 上 intra鄄 bay i 的在制品数量. 2 模型构建 2郾 1 目标函数与约束 有效评估 Interbay 系统中整体的在制品量,对 了解搬运系统运行状况具有很大参考价值. 在减少 在制品数量的同时如何控制成本同样是管理者的目 标. 所以在上述介绍的模型的基础上提出如下多目 标问题,其中用 f 1 (x),f 2 (x)表示两个目标函数, min f 1 (x) = 移 2m i = 1 E(WIP O i (x)) (1) min f 2 (x) = C(x) = 移 2m i = 1 ci xi (2) s. t. (着 + 1) 移 2m i = 1 E(WIP n i (x)) + 姿 I n (x) sn v + 姿 I n (x) sn v < sn w ,n = 1,2,…,2m (3) (着 + 1) 移 2m i = 1 E(WIP n,n + 1 i (x)) + 姿 I n,n + 1 (x) l n,n + 1 v + 姿 I n,n + 1 (x) l n,n + 1 v < l n,n + 1 w ,n = 1,2,…,2m - 1 (4) (着 + 1) 移 2m i = 1 E(WIP 2m,1 i (x)) + 姿 I 2m,1 (x) l 2m,1 v + 姿 I 2m,1 (x) l 2m,1 v < l 2m,1 w ,n = 2m (5) 其中,对所有 x沂{0,1} 伊 2m. 在上述多目标问题模型的描述中,目标函数 (1)定义为最小化整个 interbay 系统中在制品的数 量,其中 E(WIP O i (x))表示 intrabay i 处的期望在制 品数量. 目标函数(2)则定义了最小化捷径使用的 总成本,其中捷径所消耗的成本 ci 是与捷径 i 的长 度 si 有关的成本,本文中假设其值与长度成正比, 即 ci = c 伊 si,c 为单位长度的成本. 约束条件(3)确 保捷径上的在制品数量不会超过捷径容量,其中 着 表示宽放系数. 约束条件(4)和(5)确保了在闭环 上运输的在制品数量不会超过闭环传送带的容量. 2郾 2 模型参数分析 2郾 2郾 1 路径选择分析 在目标函数(1) 和约束(3)、(4) 和(5) 的计算 过程中,要进行晶圆搬运的路径选择. 由于捷径的 设置,所以所有的物料运输都将遵守最短路径的原 则. 由于捷径的开闭情况以及物料运输的起止位 置,可能出现三种捷径使用情况:(1) 使用两条捷 径;(2)使用一条捷径;(3)不使用捷径. 在此假设 p 表示 intrabay i 出发的在制品运输 过程中选择的同侧出发的捷径编号,q 表示 intrabay i 选择的对侧出发的捷径编号. 令 dij ( x)表示在已 知捷径策略为 x = (x1 ,x2 ,…,x2m )的情况下从 intra鄄 bay i 到 intrabay j 的搬运距离,则对于从 intrabay i ·263·
·264· 工程科学学报，第41卷，第2期 到intrabayj的物流，应选择捷径的编号p,q令dg最 小，可分为如下三种情况： 入+ A.设备组j在i的同侧下游，此时不需要使用 克A,-∑ (11) 捷径： i=2m-n+lj=2m-n+1 j-1 则在此段闭环传送带上的在制品平均流量为： d,(x)= (6) 入+1=5+52+5 (12) B.设备组j在i的对侧，则需要考虑两种情况， 则由泊松过程可知，在传送带(n,n+1)上的intra- 即需要使用一条捷径，或不使用捷径： di(x)= y间运输的期望在制品数量为X一 同理可知捷径i上的intrabay间运输的在制品 min k=2m-p+1 数量，可由捷径n右侧的流量，减去由捷径n上游的 (7) 同向捷径分流的流量而获得： 其中，2m-p+1<j,p>i,x。=1. 2m C.设备组j在i的同侧上游，则需要考虑三种 入+ 情况，即使用一条捷径，使用两条捷径，或不使用 (13) 捷径： i=2m-n+j=2m-n+1 AjeRn 2.2.3重试相关参数分析及在制品计算 dg(x）=min +1+ + 对于上述系统，当在制品到达时，如果该intra- 5+ bay缓冲区已满则该在制品将进入重试运输回路进 ++5p+ k=2m-9+1 行下一次尝试，则由假设(7)可知，两次尝试之间时 l+1+g+ 间间隔的分布是与重试平均时间有关的指数分布 k=2m-p+l 例如，对于intrabay i,令t:表示intrabay i处重试的 lk+ (8) 平均时间，则由重试环路的长度与传送带的平均运 k=2m-g+1 k=i 其中，p>i,9<j,x。=1,xg=1. 输速度可得： 2.2.2 intrabay间在制品数量计算 di(x) t:=- (14) 约束(3)、(4)和(5)中，期望在制品数量E (WIP(x),E(WIPa+'(x))的计算涉及到通过该 则由假设可知该intrabay的重试时间分布函数为： 捷径和闭环传送带上的intrabay间流量以及重试流 T.(t)=1-e立=1-ea,t≥0(15) 量的计算.以图1为例，在Intrabay n与n+1之间 则由M/G/I重试排队的队长公式可得4： 的传送带上运输量由所有通过此处的intrabay间运 输量以及通过此处的重试运输量决定.Intrabay间 E(WIP(x))=B 运输可以根据其起止位置分为三种不同的情况进行 分析，令(n,n+1)表示Intrabay n与n+1之间的传 其中人= 入 j=i 送带： 由于intrabay所产生的重试流的详细计算非常 A.由intrabayn右侧intrabay出发前往其左侧intra- 困难，所以此处针对传送带各处的重试在制品数量 bay经过传送带(n,n+I)的流量： 结合传送带长度进行了近似的计算，再通过宽放系 三+三， 数来保证约束条件的有效性.所以可由E(WIP (9) +1i三m+ (x)以及各传送带的长度与总路径长度的比值获 B.由intrabay n左侧intrabay间运输经过传送带n, 得捷径与闭环传送带上的重试在制品数量： n+1的流量： 捷径上WIP数量： 2m- 2周-a+1i-1 点=∑∑+∑∑-，∑ i=m+=+1 i=m+1=n+1 AgE R2m-it1 E(WP()=aE(Wm()（)） (10) 传送带上WIP数量： C.由intrabay n右侧intrabay间运输经过传送带n, n+1的流量： E(wP"(e）=iE(W(）（8）
工程科学学报,第 41 卷,第 2 期 到 intrabay j 的物流,应选择捷径的编号 p,q 令 dij最 小,可分为如下三种情况: A. 设备组 j 在 i 的同侧下游,此时不需要使用 捷径: dij(x) = 移 j-1 k = i l k,k + 1 (6) B. 设备组 j 在 i 的对侧,则需要考虑两种情况, 即需要使用一条捷径,或不使用捷径: dij(x) = min ( 移 p-1 k = i l k,k + 1 + sp + 移 j-1 k = 2m-p+1 l k,k + 1 , 移 j-1 k = i l k,k + 1 ) (7) 其中,2m - p + 1 < j,p > i,xp = 1. C. 设备组 j 在 i 的同侧上游,则需要考虑三种 情况,即使用一条捷径,使用两条捷径,或不使用 捷径: dij(x) = min ( 移 p-1 k = i l k,k + 1 + sp + 移 q-1 k = 2m-p+1 l k,k + 1 + sq + 移 j-1 k = 2m-q+1 l k,k + 1 , 移 p-1 k = i l k,k + 1 + sp + 移 j-1 k = 2m-p+1 l k,k + 1 , 移 q-1 k = i l k,k + 1 + sq + 移 j-1 k = 2m-q+1 l k,k + 1 , 移 j-1 k = i l k,k + 1 ) (8) 其中,p > i,q < j,xp = 1,xq = 1. 2郾 2郾 2 intrabay 间在制品数量计算 约束(3)、 (4) 和(5) 中,期望在制品数量 E (WIP n i (x)),E(WIP n,n + 1 i ( x))的计算涉及到通过该 捷径和闭环传送带上的 intrabay 间流量以及重试流 量的计算. 以图 1 为例,在 Intrabay n 与 n + 1 之间 的传送带上运输量由所有通过此处的 intrabay 间运 输量以及通过此处的重试运输量决定. Intrabay 间 运输可以根据其起止位置分为三种不同的情况进行 分析,令(n,n + 1)表示 Intrabay n 与 n + 1 之间的传 送带: A郾 由 intrabayn 右侧 intrabay 出发前往其左侧 intra鄄 bay 经过传送带(n,n + 1)的流量: 孜1 = 移 n i = 1 移 2m-n j = n+1 姿ij + 移 2m i = 2m-n+1移 2m-n j = n+1 姿ij (9) B郾 由 intrabay n 左侧 intrabay 间运输经过传送带 n, n + 1 的流量: 孜2 = 移 2m-n i = m+1移 m j = n+1 姿ij + 移 2m-n+1 i = n+1 移 i-1 j = n+1 姿ij - 姿 移ij沂R2m-i+1 姿ij (10) C郾 由 intrabay n 右侧 intrabay 间运输经过传送带 n, n + 1 的流量: 孜3 = 移 n i = 1 移 2m j = 2m-n+1 姿ij + 移 n i = 1 移 i-1 j = 1 姿ij + 移 2m i = 2m-n+1 移 i-1 j = 2m-n+1 姿ij - 姿移ij沂Rn+1 姿ij (11) 则在此段闭环传送带上的在制品平均流量为: 姿 I n,n + 1 = 孜1 + 孜2 + 孜3 (12) 则由泊松过程可知,在传送带( n,n + 1) 上的 intra鄄 bay 间运输的期望在制品数量为 姿 I n,n + 1 l n,n + 1 v . 同理可知捷径 i 上的 intrabay 间运输的在制品 数量,可由捷径 n 右侧的流量,减去由捷径 n 上游的 同向捷径分流的流量而获得: 姿 I n = 移 n i = 1 移 2m j = 2m-n+1 姿ij + 移 n i = 1 移 i-1 j = 1 姿ij + 移 2m i = 2m-n+1 移 i-1 j = 2m-n+1 姿ij - 姿移ij沂Rn 姿ij (13) 2郾 2郾 3 重试相关参数分析及在制品计算 对于上述系统,当在制品到达时,如果该 intra鄄 bay 缓冲区已满则该在制品将进入重试运输回路进 行下一次尝试,则由假设(7)可知,两次尝试之间时 间间隔的分布是与重试平均时间有关的指数分布. 例如,对于 intrabay i,令 t i 表示 intrabay i 处重试的 平均时间,则由重试环路的长度与传送带的平均运 输速度可得: t i = dii(x) v (14) 则由假设可知该 intrabay 的重试时间分布函数为: Ti(t) = 1 - e - t t i = 1 - e - vt dii (x) ,t逸0 (15) 则由 M/ G/ 1 重试排队的队长公式可得[14] : E(WIP O i (x)) = 姿 2 i 1 - 姿i茁 i ( 1 茁 i 1 dii(x) v + 茁 i 2 ) 2 (16) 其中 姿i = 移 2m j = 1 姿ji . 由于 intrabay 所产生的重试流的详细计算非常 困难,所以此处针对传送带各处的重试在制品数量 结合传送带长度进行了近似的计算,再通过宽放系 数来保证约束条件的有效性. 所以可由 E ( WIP O i (x))以及各传送带的长度与总路径长度的比值获 得捷径与闭环传送带上的重试在制品数量: 捷径上 WIP 数量: E(WIP n i (x)) = sn dii(x) E(WIP O i (x)) (17) 传送带上 WIP 数量: E(WIP n,n + 1 i (x)) = l n,n + 1 dii(x) E(WIP O i (x)) (18) ·264·
周炳海等：基于捷径重试规则晶圆带式搬运系统性能优化 ·265· 需重新进行遗传操作直到产生与父代不同的子代为 3NSGA-Ⅱ算法应用 止.以16个intrabay的系统为例，其遗传交叉过程 通过NSGA-Ⅱ算法对系统不同水平物流负荷 可如图2所示. 下的在制品数量与捷径成本进行优化计算，将得到 1o11o1o111o1010 的结果与启用全部捷径时的结果进行比较分析.以 平均在制品数量，各捷径上在制品数量的方差为指 标对模型进行综合分析.此外在计算过程中因为引 0101101001001001 入了宽放系数E,所以也需要考虑该系数对结果的 影响. 1001101011101000 代 3.1NSGA-Ⅱ遗传操作分析 0111101001001011 NSGA-Ⅱ算法是现阶段多目标算法中比较主流 图2交叉遗传操作 的一种算法.而在本文的算法设计过程中，需要结 Fig.2 Cross-genetic operation 合系统特点对算法中的遗传过程进行相应的针对性 3.2NSGA-Ⅱ算法分析 设计.系统中具有2m个intrabay的系统，就会有2m 个决策变量，其取值为0或1.在进行遗传操作的时 基于以上编码方式可以进行针对该系统的整体 候，考虑到系统布局的对称性，可以在进行遗传操作 NSGA-Ⅱ算法设计，其流程如图3所示 时将其分为两个部分进行单独的遗传操作.在两段 4 实验示例及结论 DNA上分别截取片段进行交叉遗传，交叉后将两段 新的子代与其父代进行比对，如果有相同的情况则 为了进行系统性能分析与优化，在数学模型建 开始 初始化种群g=0 生成第一代子群？ 决策在制品运输路径 是 计算在制品数量，捷径使用成本 进化代数g=1 计算约束惩罚，非支配解排序 g=8+1 合并父代，子代 选择，交叉，变异 生成新父代？ 决策在制品运输路径 计算在制品数量， 捷径使用成本的适应度 选择，交义，变异 计算约束惩罚，非支配解排序 拥挤度排序 选择合适个体组成新父代 是 g小于设置代数？ 结束 图3NSGA-I流程图 Fig.3 Flow chart of NSGA-II
周炳海等: 基于捷径重试规则晶圆带式搬运系统性能优化 3 NSGA鄄鄄II 算法应用 通过 NSGA鄄鄄II 算法对系统不同水平物流负荷 下的在制品数量与捷径成本进行优化计算,将得到 的结果与启用全部捷径时的结果进行比较分析. 以 平均在制品数量,各捷径上在制品数量的方差为指 标对模型进行综合分析. 此外在计算过程中因为引 入了宽放系数 着,所以也需要考虑该系数对结果的 影响. 3郾 1 NSGA鄄鄄II 遗传操作分析 图 3 NSGA鄄鄄II 流程图 Fig. 3 Flow chart of NSGA鄄鄄II NSGA鄄鄄II 算法是现阶段多目标算法中比较主流 的一种算法. 而在本文的算法设计过程中,需要结 合系统特点对算法中的遗传过程进行相应的针对性 设计. 系统中具有2m 个 intrabay 的系统,就会有2m 个决策变量,其取值为 0 或 1. 在进行遗传操作的时 候,考虑到系统布局的对称性,可以在进行遗传操作 时将其分为两个部分进行单独的遗传操作. 在两段 DNA 上分别截取片段进行交叉遗传,交叉后将两段 新的子代与其父代进行比对,如果有相同的情况则 需重新进行遗传操作直到产生与父代不同的子代为 止. 以 16 个 intrabay 的系统为例,其遗传交叉过程 可如图 2 所示. 图 2 交叉遗传操作 Fig. 2 Cross鄄genetic operation 3郾 2 NSGA鄄鄄II 算法分析 基于以上编码方式可以进行针对该系统的整体 NSGA鄄鄄II 算法设计,其流程如图 3 所示. 4 实验示例及结论 为了进行系统性能分析与优化,在数学模型建 ·265·