光刻区是晶圆制造系统中重入次数最多、资金投入最大、设备利用率最高的区域，是系统的主要瓶颈之一．研究高效的光刻区调度方法对于改善晶圆制造系统的性能、提高企业效益、增强企业响应市场的速度具有十分重要的意义．在晶圆制造系统中，光刻区由若干台不同型号的光刻机组成，主要完成晶圆制造中的光刻工艺．当晶圆到达光刻区时，须为其分配可用于对应层次加工的光刻机和掩膜版．具体来说，光刻区的调度须要考虑以下几点：第一，多目标，除了生产周期和晶圆准时交付率等晶圆制造系统常用目标，光刻机的高昂价格决定了必须提高设备利用率，降低光刻生产成本；第二，设备专用性约束，为保证产品质量，一片晶圆的所有关键层必须在同一台设备上加工；第三，掩膜版数量约束，每道光刻工序均须搭配数量唯一的掩膜版；第四，设备加工能力约束，不同光刻机的加工范围、加工时间和设备折旧成本均不同．以上这些要求极大增加了光刻区调度的难度．国内外学者对光刻区调度方法展开了广泛研究，可分为精确类算法[1]、调度规则[2-4]及智能算法[5-6]，且以光刻区的单目标调度为主．针对光刻区多目标调度问题，文献[7-8]均展开了相关研究，但对于多目标优化均是以加权求和的方式进行，最终只能得到一组多目标优化解．Pareto排序法可以得到问题的所有非支配解，越来越多的应用到生产调度问题中[9-11]；但当目标数量增多时，当前的Pareto排序法存在前沿点数量爆炸的问题，此时的解难以均匀覆盖到整个前沿面．分解多目标进化算法(MOEA/D[12]和C-MOGA[13])是一种通过参考点将多目标分解为一系列单目标的优化方法．研究表明[14]：MOEA/D对于四个以上目标的问题优势明显，因此也越来越多地应用于多目标优化问题[15-16]．当前的研究主要还是集中在连续域的优化问题，对于生产调度这类离散域问题的研究尚较少．特别地，离散域优化问题的前沿点分布存在很大的不均匀性，MOEA/D的参考点生成方法不再适用，有待进一步研究．为解决晶圆制造系统光刻区多目标调度问题，本研究提出了一种改进分解多目标进化算法(IMOEA/D)，通过聚类分析生成有代表性的参考点，并针对光刻区的调度特点，设计相应的编码/解码、聚合函数及局部搜索算子，提高算法的收敛性和非支配解的多样性．1 光刻区多目标调度问题建模1.1　问题描述晶圆制造系统中的光刻区有若干台光刻机，不同设备由于精度不同加工范围也不同；价格不同也导致单位时间的设备折旧成本不同；同时，设备的加工速度也存在差异．光刻区调度主要为到达光刻区的晶圆分配可用于加工的光刻机和配套的掩膜版，并为光刻机进行加工任务排序．调度过程中主要考虑的约束包括设备专用性约束、掩膜版数量约束及设备加工能力约束．光刻区调度的优化目标包括晶圆总完工时间和光刻生产成本的最小化，以及订单准时交付率和设备利用率的最大化，因此光刻区调度问题是一种带复杂约束的非等效并行机多目标调度问题．1.2　符号与变量定义模型所用参数如下：J为待光刻的晶圆集合，J={1,2,…,j,…,n}；L为所有光刻工序集合，L={1,2,…,l,…,m}；δl为须要进行光刻工序l的晶圆集合；K为光刻机集合，K={1,2,…,k,…}；Kj为可用于晶圆j加工的光刻机集合；tpjk为晶圆j在光刻机k上的加工时间，k∈Kj；当晶圆i和晶圆j为同一加工工艺时，θij为1，否则为0；trj为晶圆j的到达时间；tsj为晶圆j的调整时间；tdj为晶圆j的交付时间；vj为晶圆j专用加工设备，若当前工序为晶圆j第一层关键层加工，则vj=0；tzj为晶圆j的剩余完工时间；M为一个无限大的正数；rf为调度的时间窗长度；y1,y2,y3,y4分别为四个优化目标．模型中的决策变量如下：tCj为晶圆j前光刻工序的完工时间；若晶圆i是晶圆j在光刻机k上加工的紧前晶圆，则xijk为1，否则为0，i,j∈J，k∈K；若晶圆i在晶圆j开始加工前完成光刻加工，则eij为1，否者为0，∀i,j∈δl，∀l∈L，i≠j．1.3　数学模型1.3.1　目标函数a. 最小化总完工时间为min  y1=∑j∈J(tCj+tzj).b. 最大化设备利用率为max  y2=1-∑i∈J∑j∈J;j≠i∑k∈Kxijkθijtsi/(mrf).c. 最大化晶圆准时交付率为max  y3=∑j∈Jsgn[(tdj-tCj)/tzj-1]/n.d. 最小化光刻加工成本．不同精度光刻机由于价格差异巨大，因此在加工成本(主要是设备折旧成本)上存在着数百倍的差异，均摊在所生产的每一片晶圆上，光刻机加工成本的计算公式为min  y4=∑i∈J∑j∈J;j≠i∑k∈Kxijkcik，式中cik为晶圆i在设备k上的加工成本．1.3.2　约束条件∑j∈J:j≠0∑k∈Kx0jk≤K    (∀i∈J,i≠0)；(1)∑j∈J:j≠0  ∑k∈Kxj0k≤K    (∀i∈J,i≠0); (2)∑j∈J:j≠i  ∑k∈Kxjik=1    (∀i∈J,i≠0); (3)∑j∈J:j≠i  ∑k∈Kxijk=1    (∀i∈J,i≠0); (4)∑j∈J:j≠i  ∑k∈K,k∉Kixjik=0    (∀i∈J,i≠0); (5)∑j∈J:j≠ixjivi=1    (∀i∈J,i≠0,vi≠0); (6)tCi-tCj+xijk(M+tpijk+θijtsi)≤M(∀i,j∈J,∀k∈K,j≠0,i≠j)；(7)tCi≥tri+tpik+θijtsi+∑j∈J,i≠j(max(0,tCj-tri))xjik(∀i∈J,i≠0,∀k∈K)；(8)eij+eji≥1    (∀i,j∈δl,∀l∈L,j≠0,i≠j)；(9)xijk∈{0,1}；(10)eij∈{0,1}；(11)cik=sEDk/(TkiUk)    (∀i∈J,i≠0,∀k∈K)，(12)式中：sEDk为设备k每小时的损耗成本；Tki为设备k每小时加工晶圆i的数量；Uk为设备k的利用率．在以上约束条件中，式(1)和(2)表示每台光刻机的第一个和最后一个lot(晶圆加工单位，24片晶圆为一个lot)均为虚拟晶圆0；式(3)和(4)表示每个lot只能被分配一台光刻机上加工，且只有一个紧前和紧后lot；式(5)表示每个lot只能被分配到可加工光刻机集的其中一台上加工；式(6)表示所有晶圆的关键层必须在同一台光刻机上加工；式(7)表示每台设备在加工完一个lot后必须马上开始下一个lot的加工，不允许出现非正常闲置；式(8)表示每个晶圆lot只有在到达，且所需掩膜版可用后才可以开始加工；式(9)表示同一时刻须要相同掩膜版的所有晶圆lot只有一个可以被加工；式(10)和(11)表示决策变量；式(12)表示晶圆i在设备k上的加工成本．2 分解多目标进化算法改进MOEA/D算法在目标较多的连续域多目标优化问题上表现出了非常好的优化性能，但在光刻区调度这类离散优化问题上，参考点的选择及选择压力算子的设计还有待解决．MOEA/D方法的基本步骤为：均匀分布参考点的生成；聚合函数设计；进化算子设计．本研究在基本的MOEA/D算法基础上，考虑光刻区调度问题的相关特征，提出了改进分解多目标进化算法．2.1　基于聚类分析的参考点生成MOEA/D是在超平面上均匀取点生成参考点，如图1所示，对于离散域优化问题，各目标之间存在复杂的非线性关系，且前沿面点非均匀分布，超平面上的均匀点映射到前沿面后不能得到具有多样性的前沿点；因此本研究提出基于聚类分析的参考点生成方法，通过聚类分析将前沿点划分为若干区域，各区域参考点的数量与区域内点的密度正相关．10.13245/j.hust.220403.F001图1超平面上均匀采样映射到Pareto前沿面变得不均匀按照NSGAII的帕雷托(Pareto)快速排序方法对N个点进行分层．取处于前面三层的点，分别计算各点的局部密度为ρo1=∑χ(do1o2-dc)；(13)χ(x)=1    (x0),0    (x≥0), (14)式中：ρo1为点o1的局部密度值；do1o2为任意一点o2与点o1的欧几里得距离；dc为定义的截止距离，超出这个距离则不列入点i的密度计算．然后计算各点到高密度点的距离为δo1=mino2:ρo2ρo1do1o2．最后选取距离最大的若干个点作为聚类中心，并进行参考点的生成，有gu=RNu/∑Nv；(15)wu=(bu-au)/gu，(16)式中：Nu为第u类的点数量；R为总的参考点数量；gu为第u类所属区间分配到的参考点数量；bu为第u类的在某一维度的上边界；au为第u类在某一维度的的下边界；wu为第u类在某一维度的参考点间距．基于聚合分析的参考点生成结果如图2所示．10.13245/j.hust.220403.F002图2基于聚合分析的参考点生成结果在参考点生成以后，根据各个体与权重向量的夹角，以夹角最小原则将所有个体分配到各权重向量，用于聚合函数值的计算．2.2　聚合函数惩罚边界交叉聚合函数[17]综合考虑了解的分布均匀性与收敛性，但是由于各个权重向量所属个体在每次进化过程中参与计算，因此会导致收敛速度过慢．本研究在考虑各权重向量所属个体在每次迭代中解的质量改进程度的不同，修正聚合函数值，增加每次迭代中改进更大个体的选中概率，从而达到合理分配计算资源，加快算法搜索速度的目的．修正聚合函数值计算流程如下．a. 更新理想点．通过将设备利用率和晶圆准时交付率取负，将最大化目标函数变为最小化目标函数，定义fqmin(q∈{1,2,3,4})为转化后目标q的最小值，取4个目标的当前已知极值点，组成理想z*=(f1min,f2min,f3min,f4min)点，即晶圆总完工时间、总光刻机加工成本的最小值与设备利用率和晶圆准时交付率的最大值．b. 目标函数值归一化．有fq0=fq-fqminfqmax-fqmin，(17)式中fqmax为转化后目标q的最大值．通过式(17)将个体F=(f1,f2,f3,f4)的四个目标值均归一化为F0=(f10,f20,f30,f40)．c. 图3为聚合函数中的距离计算方法．根据图3有10.13245/j.hust.220403.F003图3聚合函数中的距离计算方法f=d1+Hfd2；(18)d1=||(z*-F0)Tλ||/||λ||；(19)d2=||F0-(z*-d1λ)||，(20)式中：d1和d2分别为点到参考方向的投影距离和垂直距离；Hf为惩罚因子．d. 修正系数η=exp[-(f'-f)/f']，(21)式中f'为当前个体所在权重向量上一代的聚合函数值．e. 计算修正后聚合函数值，即f″=ηf．(22)2.3　进化算法算子2.3.1　编码光刻区调度须要同时涉及到设备的选择及设备上晶圆的排序，这里采用两段编码方式．第一段编码完成设备的选择．采用[0，1]实数区间编码方式，如x=[x1,x2,…,xn]，0.0xi1.0，其中n为调度任务集中lot的个数，则晶圆j的加工设备为其可行设备集中第[xj|Kj|]个设备．第二段编码y=[y1,y2,…,yn]，yi∈{1,2,…,n}，若yi=k，则晶圆j第k个被加工．2.3.2　解码步骤a. j=1初始化．b. 判断j≤n，若不成立，则终止解码．从第二段编码中找到yi=j，得到被调度的晶圆i．根据对应位置的第一段编码xi，计算晶圆i分配到的光刻机[xi|Ki|]．c. 判断晶圆i的当前加工是否为关键层，若是，且非第一层关键层，则选择专用设备vi进行加工，即晶圆i分配的的光刻机vi=mi；否则根据对应位置的第一段编码xi，计算晶圆i分配到的光刻机mi=[xi|Ki|]；若晶圆i的加工层为第一层关键层，则设置vi=mi．d. 计算光刻机mi加工完前一个晶圆的时刻t，判断t时刻晶圆i所需的掩膜版是否可用，若是则计算晶圆i的当前工序完工时间Ci=t+pimi，j=j+1；否则从第二段编码中选择yk=j+1，设置yk=j，yi=j+1，返回步骤b．e. 有σmi=σmi+εi-1    (加工层为第一层关键层);σmi-1    (加工层为非第一层的关键层);σmi    (其他), (23)式中：σmi为光刻机mi考虑设备专用性约束后已分配到的加工负载量；εi为晶圆i的关键层层数．更新设备负载，根据式(23)更新各光刻机的负载量，返回步骤b．2.3.3　选择本研究在算法进化的过程设置了外部档案，用来存储种群获得的非支配解集，并用于选择算子中．外部档案在MOEA/D算法进化的过程中须要不断更新，设外部档案子群规模为N1，第一代外部档案取自初始解中的所有前沿点，若非支配解个数大于N1，则取前N1个个体，否则选取所有个体．在进化过程中，当出现新的非支配解时，若当前外部档案未满，则继续加入；若外部档案已满，则新的点加入外部档案，然后按照式(17)和(18)计算各点的密度值，将距离密度最大中心点最近的个体剔除．选择操作首先按照轮盘赌机制从当前种群中选择一个个体，然后以概率p0按照轮盘赌在原种群中选择第二个个体，以概率1-p0从外部档案中选取任一个体．2.3.4　交叉这里采用多点交叉方法．首先随机生成一个与两段编码同等长度的0/1序列；对于第一段编码，父代中0对应位置的基因互换，1对应位置的基因直接继承；对于第二段编码，父代中0对应位置的基因互换，1对应位置的基因按照剩余优先级在父代中出现的次序一次填入．这样既保证了子代不违背关键层的设备专用性约束，又可以使子代继承父代中部分晶圆的加工设备以及加工优先级，同时保留一定的搜索能力，有利于提高种群的多样性，如图4所示．10.13245/j.hust.220403.F004图4交叉算子示例2.3.5　外部档案变邻域局部搜索外部档案在每次进化结束后，按照变邻域搜索算法进行搜索，这里采用以下4种邻域结构，前3种领域机构中都对于第一段编码中有设备专用性约束要求的基因保持不变．a. 逆序．随机选取两个位置，对两段编码中处于所选位置中间的基因序列逆向排序，生成新的个体．b. 交换．随机选取两个位置，交换两段编码中两个位置的基因．c. 插入．随机选取两个位置，将两段编码中两个位置的基因．d. 突变．选择任意一个工序，在其可选光刻机集合中选择加工时间最短的光刻机．3 实验验证实验验证分为算法参数实验、基准算例测试和仿真模拟测试三部分．本研究采用集合覆盖率[18](C)及反向世代距离[19](IGD)这两个指标来评价多目标优化算法的性能．其中集合覆盖率C描述两个非支配解集的互相支配关系，是用于比较算法收敛性的单一类指标．设IGD为综合描述综合解集收敛性和多样性的指标．3.1　算法参数实验IMOEA/D算法中的参数设置会对算法性能造成重要影响，其中关键参数包括：种群数量Npop、聚合函数惩罚因子Hf、外部档案选择概率β0及外部档案变邻域搜索次数Nnb．特别地，参考点数量与种群数量相同．本研究采用响应曲面法进行参数实验，各参数的范围设置为Npop∈[100,200]，Hf∈[0,1]，β0∈[0,1]，Nnb∈[5,20]，算法迭代次数上限为1 000，响应变量选择指标IGD．综合考虑计算时间与求解质量，IMOEA/D算法最终的参数设置为Npop=190，Hf=0.56，β0=0.44，Nnb=16．3.2　基准算例测试为了评价提出的IMOEA/D算法，参考文献[20]，生成小、中、大规模共24组基准算例．选择经典帕累托(Pareto)排序算法中的NSGAII[21]、SPEA2[22]及前沿研究较多的分解多目标进化算法NSGAIII[23]和一般分解进化算法MOEA/D[24]与提出的IMOEA/D算法进行对比验证，所有算法运行20次，取20次实验的平均值作为比较，并采用t检验法对20次结果进行检验，显著水平设为0.05．结果显示：在指标C上，IMOEA/D算法18次取得最优，NSGAIII 4次取得最优，MOEA/D 1次取得最优，SPEA2 1次取得最优．同时，随着问题规模的增大，IMOEA/D算法相对于其他算法的优势也越来越稳定．在指标IGD上，IMOEA/D算法21次取得最优，其余3组算例NSGAIII取得最优．由此可见：对于非等效并行机多目标调度问题，IMOEA/D算法所求得的非支配解在收敛性和均匀性上均存在明显优势，且随着问题规模增大，这种优势更为显著．3.3　仿真算例对比实验以上海某晶圆代工厂车间为原型，建立晶圆制造系统仿真模型，仿真系统硬件配置见文献[25]，其中光刻机的加工时间服从V[10，30]，加工层数服从V[20，40]．通过算法和仿真系统的数据交互，对比连续6个月中，IMOEA/D算法与以上４种算法在C和IGD指标上的值，并采用t检验法进行检验．采用符号+，-，~分别表示IMOEA/D优于、显著差于及近似于所对比的算法．指标C的对比结果如表1所示，表中：Ⅰ为A，B算法对比组；Ⅱ为A，C算法对比组；Ⅲ为A，D算法对比组；Ⅳ为A，E算法对比组．结果显示：在不同算法求得解集的相互支配关系上，IMOEA/D算法有较大优势；同时分解进化类算法性能上要优于传统的帕累托排序算法．综合所有算法的计算结果，在指标Ｃ上，算法性能从优到劣的排列顺序依次为：IMOEA/D，NSGAIII，MOEA/D，SPEA2，NSGAII，且这种优势相较于在基准算例上要更为显著，表明设计的相关算子的有效性．10.13245/j.hust.220403.T001表1仿真算例不同算法在指标C上的结果对比月份ⅠⅡⅢⅣA，BB，At检验法A，CC，At检验法A，DD，At检验法A，EE，At检验法10.620.04+0.790.08+0.950.00+0.340.10+20.590.13+0.840.05+0.910.02+0.400.11+30.550.15+0.890.02+0.920.00+0.370.09+40.570.07+0.910.01+0.970.00+0.300.13+50.500.17+0.850.04+0.890.04+0.310.10+60.480.21+0.770.10+0.970.01+0.280.14+注：A为IMOEA/D，B为MOEA/D，C为SPEA2，D为NSGAII，E为NSGAIII(下同)．指标IGD的对比结果如表2所示．结果显示：综合考虑解的收敛性和分布均匀性，IMOEA/D算法除了第4个月表现与NSGAIII算法表现相当之外，其余情况均要优于其他4种算法；同时，IMOEA/D算法在性能的稳定性方面也要优于其他算法．10.13245/j.hust.220403.T002表2仿真算例不同算法在指标IGD上的结果对比月份ABCDEIGDIGDt检验法IGDt检验法IGDt检验法IGDt检验法10.020 750.129 53+0.155 78+0.177 48+0.073 52+20.019 520.137 43+0.129 54+0.216 30+0.055 62+30.018 450.106 75+0.185 85+0.157 73+0.035 62+40.024 750.094 53+0.174 77+0.183 69+0.024 46~50.019 150.084 15+0.135 95+0.193 86+0.060 83+60.022 520.142 56+0.156 63+0.163 87+0.095 29+4 结语本研究针对晶圆制造系统光刻区调度问题，提出了一种分解多目标进化算法．通过基于聚类分析的参考点生成方法优化前沿解的分布均匀性；通过综合考虑解的均匀性、收敛性及搜索效率设计了聚合函数；设计外部档案变邻域搜索策略，提高算法搜索速度．最后，通过基准算例测试和仿真实验验证了提出算法的性能，实验结果表明：提出算法在综合性能上明显优于其他几种多目标优化算法，能有效降低晶圆加工周期和光刻成本，提高光刻机设备利用率和晶圆准时交付率．