叶春明, 侯丰龙, 赵 静

(上海理工大学 管理学院，上海 200093)

0 序言

随着集成电路技术的迅猛发展与广泛应用，半导体产业得到蓬勃发展，并成为衡量一个国家科学进步和经济发展的重要指标之一。因此，研究探索提高半导体制造业的设备利用率及生产效率，对加强企业核心竞争力和国家综合实力都具有重要意义。半导体生产制造流程主要包括晶圆制备、晶圆制造、晶圆测试、装配及封装、最终测试[1]五个步骤，生产调度具有设备繁多，规模大，大批量生产，重入性高，工艺复杂等特点。Uzsoy[2]首先提出工件尺寸大小不同的半导体单批处理机调度问题，证明了求解这类问题的最小化最大完工时间为强NP-hard，并给出优化该类问题的启发式算法。Kumar等[3～5]提出了一系列应用于半导体生产过程实时调度的启发式规则。Hochbaum和Landy[6]研究了半导体最终测试阶段中存在m种类型待加工工件的批调度问题，优化目标为最小跨度时间，提出一种近似算法进行求解。马慧民等[7]针对半导体炉管区批调度问题，并设计了一种双层粒子群算法求解调度问题。郭乘涛等[8]构建了一种整合蚁群组批与规则调度的混合蚁群算法，求解半导体晶圆制造系统中并行批处理机的组批与调度问题，证明了混合蚁群算法的有效性和实用性。上述研究从未考虑操作者的行为因素，实际生产活动中，随着工人(机器)操作时间的增加，加工相似工件的效率不断提高，后续工件的加工时间相应的逐渐减少，该现象称为学习效应[9]。Biskup[10]首次将学习效应概念应用于调度领域，并提出与工件加工位置有关的学习效应模型。Mosheiov[11]把学习效应模型应用于平行机调度问题，证明了对于优化目标为最小化最大完工时间和最小化总完工时间的问题多项式时间可解，但算法的复杂度比经典调度问题高。Wang等[12]在基本学习效应模型基础上提出Dejong模型，并分别以最大完工时间和总完工时间为目标讨论基于学习效应的单机排序问题。实际生产过程中，工人或机器通过积累经验获得学习效应，缩短实际加工时间，然而由于加工工件的差异性、机器的退化以及加工过程的中断，工人或机器会产生遗忘效应，学习效应会减弱，使得实际加工时间延长。Lee[13]首次针对具有学习效应和遗忘效应的单机排序问题构建模型。王桂娜等[14]以成组生产的单机系统为对象，基于Chiu[15]的遗忘率模型，建立了同时考虑学习和遗忘因素的成组调度模型。当前研究学习效应的生产调度文献可知，学习模型的应用大多局限于单机环境，遗忘效应也容易被忽略。尽管已有学者分别对半导体批调度问题和具有学习遗忘效应的生产调度问题进行研究，但尚未见到将二者结合，考虑半导体批调度问题中学习遗忘效应的影响。

针对这一问题，以半导体最后测试阶段为研究对象，构建具有学习-遗忘效应的调度模型，结合最后测试阶段批调度问题的特点，提出一种结合了粒子群算法和萤火虫算法的双层算法对模型进行求解，通过仿真实验测试双层算法的有效性和可行性，并根据测试结果分析学习-遗忘效应对半导体批调度问题的影响程度。

1 问题描述

1.1 半导体最终测试阶段流程描述

半导体生产过程中的瓶颈设备往往是批处理设备，下文对半导体制造过程中采用批处理设备的典型最后总测试阶段进行描述建模。半导体最终测试阶段是指对完成封装后的产品统一进行性能测试，该环节是为了保证出厂产品性能指标的完整性，剔除不合格产品，并同时按照产品的电性功能对产品进行等级划分。最终测试阶段的流程如图1所示：

图1 最终测试阶段流程

由图1可知，半导体最终测试阶段流程包括以下几个步骤[16]：FT-1(或Room Test)，回温，FT-2(或Hot Test)，预烧炉，FT-3(或Cold Test)，扫描标记，加温烘烤，包装，运输。其中，主要的关键作业如下：测试机台测试、预烧炉测试(Burn-In Oven)、回温(Cycling)、加温烘烤(Baking)等。

1.2 具有学习-遗忘效应的调度模型描述

Biskup[10]最早提出一种与工件加工位置有关的单机环境下学习效应调度模型，该模型中工件的实际加工时间是其位置的递减函数，工件Jj在第r个加工位置的实际加工时间为Pjr=Pjra,(j,r=1,2,…,n)，其中Pj和Pjr分别为工件Jj的基本加工时间和实际加工时间；a≤0是学习因子，设为常数。a=lgl/lg2，l为学习率。由于学习效应的存在，当某种产品的产量增加一倍时，加工单个产品所需的加工时间会降为原来加工时间的一个百分数，这个百分数即被称为学习率，它说明了工人和机器在生产中获得的学习效果。

Dejong[17]在Biskup学习模型基础上，研究了机器和工人在生产过程中具有不同影响的学习效应。该模型的数学描述如式(1)所示：

Y=a[M+(1-M)Xn]

(1)

其中，Y表示加工工件数为X时的累计平均时间，a表示第一个工件加工的时间，n为学习因子，M为不可压缩的程度。该模型主要用来描述自动化程度对学习效应的影响，M取值越大则表示自动化程度越高，学习效应对生产时间的影响就越小。

下文在Biskup学习模型基础上，采用Dejong模型结构，构建与工件加工位置有关的学习-遗忘调度模型：

(2)

(3)

其中，β>0为遗忘参数，t为批与批之间的中断时间。

1.3 具有学习-遗忘效应的半导体最终测试阶段批调度模型构建

考虑基于学习-遗忘效应，工件同时到达情况下的最终测试阶段流水线批处理机调度问题，具体问题描述如下：

(1)同一批的工件同时被处理；

(2)一批工件开始加工就不容许被中断；

(3)每个工件都有自己的尺寸和在每台机器上的基本加工时间；

(4)每批工件的加工时间等于该批中工件加工时间的最大值；

(5)决策变量Xib被描述为

根据上述约束条件，最终测试阶段并行批处理机调度问题的数学模型如下：

目标函数：

min(Cmax)=min(Ck,m)

(4)

式(4)表示目标函数为所有待加工工件的最大完工时间最短，即最小化makespan；式(5)限定每一个工件只能被分到一个批中；式(6)限定每一批所有工件的尺寸之和不超过机器容量，si为工件i的尺寸，B为机器的最大容量；式(7)表示每一批工件的加工时间为该批中所有工件加工时间的最大值，Pbj为批b在机器j上的加工时间，pij为工件i在机器j上的加工时间；式(8)表示求解第1批的工件在第1台机器上的加工时间C1,1；式(9)表示求解在机器1上每批工件的加工时间Cb,1；式(10)表示求解第1批的工件在每台机器上的加工时间C1,j；式(11)表示求解每批工件在每台机器上的加工时间Cb,j。

2 基本双层算法设计

针对批调度的特点，设计一种双层算法，外层采用粒子群算法用来选择机器，内层采用萤火虫算法对外层选择机器上的工件批进行排序。

2.1 外层算法描述

粒子群算法(Particle Swarm Optimization，PSO)[18]的思想来源于鸟类觅食行为，初始化一群随机粒子，然后粒子通过综合分析个体和群体的飞行经验来动态调整各自的速度，在解空间中进行搜索，迭代以寻求最优解。在每一次迭代过程中，粒子通过对比两个“极值”来不断更新，这两个极值分别代表粒子本身当前最优解以及种群当前最优解。粒子群算法的数学描述如下：

在一个n维的搜索空间中，由m个粒子组成的种群X={x1,…,xi,…,xm}，其中第i个粒子的位置为x1=(xi1,xi2,…,xin)T，速度为vi=(vi1,vi2,…,vin)T。粒子的个体极值pi=(pi1,pi2,…,pin)T，种群的全局极值pg=(pg1,pg2,…,pgn)T，粒子通过式(12)(13)(14)来更新自己的速度和位置:

(12)

(13)

(14)

同时，为了改善粒子群算法的局部搜索能力，采用基于Pairwise[19]的局部搜索策略针对当前全局极值gbest进行寻优。依次交换当前全局极值对应的位置序列，也即批工件选择的机器，对比交换前后优化目标适应度，也即待加工工件的总完工时间，如果适应度得到改善，则更新位置，否则保留当前位置，最后，更新当前最优全局极值gbest。

2.2 内层算法描述

萤火虫算法(Firefly Algorithm，FA)[20]是通过模拟自然界中萤火虫发光的生物特性构建的基于种群搜索的新型智能优化算法。在该算法中，萤火虫彼此间吸引的原因主要取决于其自身亮度和吸引度。利用该算法寻优过程中，将自然界中的萤火虫个体模拟成搜索空间中的点，则搜索和寻优过程也即萤火虫个体相互吸引和移动的过程，萤火虫个体移动过后的位置就是算法迭代后更新的目标函数值，通过个体的优胜劣汰来达到寻求最优可行解的目的。利用数学公式对萤火虫算法描述如下[21]：

定义1萤火虫个体的相对亮度：

I(r)=I0×e-γrij

(15)

其中，I0(r=0)表示自身荧光亮度，也是最大个体亮度，随着其目标函数值变化而变化；γ是光强吸收系数，在此设为常数，用来反映萤火虫个体发出的荧光由于距离和介质的原因而导致传递过程中的衰弱现象；rij是萤火虫i与j之间的距离。

定义2萤火虫个体的相对吸引度：

(16)

其中，β0(r=0)表示光源处的吸引度，也是最大吸引度。

定义3萤火虫i被j吸引并向其移动的位置更新公式：

xi=xi+β(r)×(xj-xi)+α×(rand-1/2)

(17)

其中，xi、xj分别为萤火虫个体i和j所处的位置；α表示步长因子，是[0,1]间的常数；rand是在[0,1]上均匀分布的随机数；α×(rand-1/2)的设置是为了防止在搜索过程中陷入局部最优。

3 双层算法改进

3.1 初始化设置

为了提高工件的分批质量，在BF分批之前首先对待加工工件序列利用Palmer算法初始化。Palmer算法优化过程是按照斜度顺序指标依据工件的加工时间对待加工工件进行排序。工件i的斜度指标(Slope Index)SIi定义为：

(18)

其中，pij表示工件i在机器j上的加工时间，m表示可选择机器数。按照斜度递减对工件序列进行初始化，然后采用BF分批方法对初始序列进行分批，得到初始的分批结果。

3.2 算法编码

利用外层粒子群算法求解工件分批问题，采用ROV规则将位置矢量Xi=[xi,1,xi,2,…,xi,n]转换为离散的加工顺序π=(j1,j2,…,jn)。将初始工件序列转换为粒子的位置矢量，转换公式如下：

xi=xmin+(xmax-xmin)(πi-1+r)/n,i=1,…,n

(19)

式中，xi为粒子第i维的位置值；πi为通过Palmer算法得到的初始解的第i维工件序号；xmin和xmax分别为粒子位置的最大值和最小值；r为0到1的随机数。将转换后的xi作为初始化粒子群位置时第一个粒子的位置，其余粒子的位置随机生成。

3.3 BF分批描述

采用最优化分批(Batch First Fit，BF)方法对工件进行分批，具体分批步骤如下：

Step1创建第一批，即批次b1。工件1属于批次b1，如果工件2和工件1的尺寸大小之和小于机器容量B，则工件2也属于批次b1，否则创建批次b2，工件2在第二批中。

Step2假设已创建批次b1，b2，…，bk，待分批的工件为工件i，将工件i依次放入已创建的k批中。如果放入批次bi(1≤i≤k)中，第i批工件的总尺寸大小仍小于容量B，则工件i属于批次bi；如果工件i不能被任何已创建批次容纳，则创建批次bk+1，工件i属于第k+1批。

Step3将所有待加工工件按照上述步骤进行分批，即可得到分批结果。

在半导体制造业中，批处理设备都比较昂贵，设备利用率是重要的优化指标。由上述可知，BF分批方法充分考虑了设备的利用率问题。

3.4 双层算法具体流程

Step1确定算法参数。设定粒子群算法和萤火虫算法的种群规模、迭代次数，粒子位置和速度的最值、加速常数c1、c2及惯性权重ω，萤火虫个体最大吸引度β0，步长因子α，光强吸收系数γ。

Step2初始化第一层所有粒子的位置和速度。第一个粒子的位置通过Palmer算法由公式(19)生成，其余粒子的位置和速度分别由公式(20)(21)随机生成，rand(0,1)表示产生(0,1)之间的随机数。

x=xmin+rand(0,1)(xmax-xmin)

(20)

v=vmin+rand(0,1)(vmax-vmin)

(21)

Step3通过BF分批方法进行分批。通过ROV规则将每个粒子位置转换为工件序列，然后采用BF分批方法对工件进行分批，得到分批结果。

Step4初始化第二层所有萤火虫的位置。根据step3的分批结果确定萤火虫位置矢量的维数，随机初始化萤火虫的位置，利用随机键编码方式结合ROV规则，把连续的萤火虫个体位置转换成可操作的离散批调度顺序。

Step5计算第二层各萤火虫的适应度值。第二层各萤火虫的适应度值即为所有工件的最大完工时间，并将其作为各自的最大荧光亮度。如果第二层萤火虫迭代次数达到最大迭代次数，则转step7，否则转step6。

Step6更新第二层萤火虫个体位置。计算当前萤火虫个体相对亮度I和吸引度β，并据此判断萤火虫个体移动方向，更新当前位置，转step5。

(22)

Step8更新第一层粒子的位置和速度。根据公式(12)(13)更新粒子的速度和位置，并检查粒子的速度和位置是否超出各自的取值范围，若超出范围，则按公式(23)(24)重新确定粒子的速度和位置，然后转step3。

(23)

(24)

PSO-FA双层算法的流程图如图2所示：

图2 PSO-FA双层算法流程图

4 仿真实验与分析

4.1 参数设置

参考半导体实际生产中最后测试阶段数据，设定模拟数据进行仿真实验。设工件数为20，流水车间有3台批处理机，机器的最大容量均为10，批与批之间的间隔时间为10，表1列出了工件对应的尺寸大小以及在每台机器上的基本加工时间。算法参数设置：外层粒子群算法的种群规模为50，迭代次数为100，位置x的取值区间为[0,3]，速度v的取值区间为[-3,3]，学习因子c1=c2=2，惯性权重ωmax=0.9,ωmin=0.5；内层萤火虫算法的种群规模为30，迭代次数为20，最大吸引度β0和光强吸收系数γ均为1.0，步长因子α为0.2。不同学习率对应的学习因子如表2所示。

表1 工件尺寸及加工时间表

表2 不同学习率对应的学习因子

4.2 基于学习-遗忘效应的调度模型实验分析

根据上述参数设定，对基于学习-遗忘效应的调度模型进行仿真实验。通过测试不同学习因子和遗忘参数下的优化目标，分析流水线批调度问题中学习因子和遗忘参数对优化目标的影响。表3列出了在100%、90%、80%、70%、60%和50%学习率，0，0.05，0.1,0.15，0.2，0.25和0.3遗忘参数下，算法各独立运行20次的测试结果。

表3 各参数下算法的测试结果

由表3可知随着学习因子的降低也即学习效应的增加，最大完工时间逐渐减小，表明学习效应能够提高生产效率，降低目标函数值；但是，随着遗忘参数变大，最大完工时间也逐渐增加，说明遗忘效应会减弱学习效应的效果，延长完工时间。学习率为80%时，各遗忘参数下目标函数值较经典模式的变化率分别为29.00%，17.56%，10.66%，6.48%，3.93%，2.38%，1.44%；遗忘参数为0.1时，各学习率下目标函数值较经典模式的变化率分别为5.79%，10.66%，14.75%，18.01%，20.97%。因此，学习效应和遗忘效应对目标函数值均有显著影响，在实际生产活动中同时考虑学习和遗忘效应十分重要。

图3 算法寻优结果图

在学习率和遗忘参数分别取值80%和0.1情况下，PSO-FA双层算法求解基于学习-遗忘效应的调度模型，最终测试阶段批调度问题的寻优图如图3所示：

输出如果如下：

总完工时间是：728.1149

工件排序是：6 7 12 20 17 11 16 4 8 1 10 14 18 9 13 3 2 19 5 15

批排序是：5 8 4 3 1 6 9 2 7

由图3可知，算法在100代之内能够收敛，验证了算法的可行性和有效性；输出结果包括算法求得的最优最大完工时间以及最优解对应的工件的排序和通过BF分批后所有批的排序结果。

对不同学习率及不同遗忘参数下的测试结果进行拟合分析，图4中变量为学习率，图5中变量为遗忘参数。

由图4可知，随着学习率的降低，各遗忘参数下的目标函数值都呈减小趋势，即学习效果越强，完工时间越短。对比不同遗忘参数下的拟合曲线可知，随着遗忘参数的增大，拟合曲线越平缓，说明遗忘参数越大，即遗忘效应越强时，学习率对目标函数的影响越不明显。

由图5可知，随着遗忘参数的增加，各学习率下的目标函数值都呈增大趋势，即遗忘效应越强，完工时间越长。对比不同学习率下的拟合曲线可知，随着学习率的增大，拟合曲线越平缓，说明学习率越大，即学习效果越弱时，遗忘参数对目标函数的影响越不明显。从学习遗忘调度模型可见，各因素导致学习效果的减弱即被称为遗忘效应，因此遗忘效应的影响与学习效果的强弱直接相关，同样验证上述结论。

图4 学习率为变量时的拟合曲线

图5 遗忘参数为变量时的拟合曲线

4.3 敏感性分析

敏感性分析是从定量分析的角度出发，研究某些因素发生变化时对目标值的影响程度，是一种不确定分析技术，通常用敏感度系数来表示。敏感度系数计算公式如下[22]：

(25)

其中，SAF表示目标值A对敏感因素F的敏感度系数；ΔF/F表示敏感因素F的变化率；ΔA/A表示敏感因素F发生ΔF的变化时，目标值A相应的变化率。SAF的绝对值越大，说明目标值A对因素F的变化越敏感，反之越不敏感。

由表4可知，当仅考虑学习效应，即β=0时，不同学习率下的敏感度系数均大于1，说明学习率属于较敏感的因素；随着学习率的降低，各情况下学习率的敏感度系数均逐渐减小，说明学习效应对目标函数值的影响随着学习率的较低也逐渐减小；然而随着遗忘参数的增大，学习率的敏感度系数也逐渐减小，说明考虑遗忘效应的情况下，学习率变化对目标函数值的影响会减小，即遗忘效应减弱了学习效应的影响；当遗忘参数β取值大于0.1时，学习率的敏感度系数均小于0.5，甚至当β=0.3时，学习率的敏感度系数还不到0.1，说明β大于0.1的情况下，学习效应对目标函数值的影响已经很小，因此需将遗忘参数β控制在0.1以下。

表4 不同学习率下敏感度系数

5 结论与展望

半导体生产调度问题是区别于经典调度问题的一类新型调度问题，而批处理加工设备往往会成为此类生产过程中的瓶颈设备，研究半导体批调度问题具有很重要的理论价值和实践意义。学习效应和遗忘效应在半导体生产调度中客观存在，对最大完工时间有显著影响，考虑学习遗忘效应，使得企业在制定生产计划时更符合实际生产情况。文章从半导体最终测试阶段批调度问题入手，构建基于学习-遗忘效应的调度模型，结合批调度问题的特点设计了PSO-FA双层算法，并基于仿真结果验证了在实际生产活动中同时考虑学习-遗忘效应具有实践价值。

有关具有学习遗忘效应的生产调度问题的探讨才刚刚起步，文章尝试将学习遗忘效应理论和智能算法应用于半导体生产的一些具体问题，取得了相应的优化结果。未来需要更进一步的研究：

(1)半导体生产制造系统具有设备繁多、规模庞大的特点，需要针对其大规模构建模型，以及考虑工件动态到达、工件重入性等复杂情况。

(2)设计的PSO-FA双层算法仅适用于规模有限的调度系统，对于大规模调度问题需要的智能优化算法设计方面有待进一步探索。

(3)实际生产中环境复杂，需要对多重目标综合考虑，因此下一步可对具有学习遗忘效应的多目标半导体批调度优化问题进行深入研究。