半导体芯片制造是当前我国数字化经济发展的核心，而晶圆制造系统在其中起着至关重要的作用．在晶圆制造系统中，包含以下作业区：氧化、沉积、扩散作业区，光刻作业区，刻蚀作业区，离子注入作业区和抛光作业区．受制于晶圆加工过程中产生的驻留时间和清洗工艺带来的多时间窗约束的影响，不利于生成可行的调度方案，需要频繁的人工干预[1]，从而导致交货期变长和生产成本上升，因此研究有效的晶圆跨区多目标调度方法，对提升晶圆制造系统的稳定性、提高生产效率和降低生产成本具有十分重要的意义．在进行晶圆制造跨区多目标调度中，根据晶圆制造系统的生产流程，可将其抽象成混合流水车间问题并进行求解，同时还须考虑以下几点．a．多目标优化，随着半导体市场竞争日趋激烈且以客户为导向，满足交货期已成为当今晶圆厂的一个关键指标[2]；另外，由于各类晶圆生产加工成本不一，为了确保晶圆按时交付和晶圆厂的利润率，以最小化总拖期和总生产成本为优化目标进行晶圆制造跨区多目标调度．b．机器专用性约束，由于晶圆制造系统中的特殊工艺要求，某些产品类型的晶圆被禁止在这些专用机器上进行加工，例如不同纳米制程的晶圆所需的光刻机不同，化学气相沉积和物理气相沉积所使用的机器也不同[3]．c．多时间窗约束，通过限制晶圆在不同作业区之间的等待时间[4]，从而保证产品质量和生产效率．以上这些要求极大地增加了晶圆制造跨区多目标调度的难度．晶圆制造跨区多目标调度问题本质上属于复杂约束下的多目标优化问题．近年来，进化算法[5-6]经过不断的发展已经成为一种成熟的全局优化方法，通过对种群进行优化，在问题的解空间全局范围内搜索，可以找到较启发式方法更好的解．但是当面对多时间窗约束下的晶圆制造跨区域多目标调度问题时，缺乏有效约束处理技术的进化算法效果较差，无法保证最终解集的可行性．当前使用的约束处理技术可分为以下三种：a．基于惩罚函数的方法，Zhou等[7]提出一种基于自适应惩罚函数的双档案进化算法来维持种群中有竞争性不可行的解，而不是简单地排除不可行解；b．基于目标和约束分离的方法，主要包括约束支配原则[8]和ε约束法[9]，Zeng等[10]提出了一种混合CHT，种群中每个个体具有两个排名(帕累托优势排名和约束支配排名)；c．基于协作优化的方法，王朝等[11]设计两个种群分别求解约束问题和无约束问题，每隔一定代数两个种群通过邻接矩阵进行信息交换．但是这些方法大多以可行性为优先，没有充分利用不可行解的信息来帮助种群实现更优的进化，尤其在复杂多约束的情况下，往往会导致种群无法跨越不可行区域，并且容易困在较小的可行区域中．因此，针对晶圆制造跨区多目标调度问题，分析问题特点和约束条件，并且针对现有的约束处理技术大多以可行性为优先，降低了种群对解空间探索的能力的问题，提出了基于自适应松弛因子的双种群协同进化(ARF-DP)算法．ARF-DP算法包括正常种群和收敛种群，正常种群在约束支配原则下选择个体，优先考虑个体的可行性；收敛种群在自适应松弛因子的作用下选择个体，优先考虑个体的收敛性和多样性．此外，针对晶圆制造跨区多目标调度问题的特点，设计了晶圆批次的加工工序排序和机器选择编码解码方法以及相关的进化算子．最后，设计了一种个体修复策略，对当前种群中的不可行解进行改进，以提高算法的多样性和收敛性．1 晶圆制造跨区多目标调度数学模型1.1　问题描述晶圆制造跨区多目标调度生产过程可以被建模为带复杂约束的混合流水车间多目标调度问题．如图1所示，总体可描述如下：有K种工艺类型的|I|个晶圆批次在五大作业区中完成加工，每个作业区包含若干非等效的机器，即机器可加工的工艺类型是确定的，且机器每次只能对一种工艺类型的晶圆进行加工．机器非抢占式加工，即当机器开始加工时不能中断．机器在切换加工工艺类型时会产生生产准备时间，时间长短由工艺类型决定．晶圆批次在加工过程中要避免违反多时间窗约束，通过为每个晶圆批次在不同作业区中的每道工序分配加工机器以及确定开始时间，实现对总拖期和总生产成本的多目标优化．10.13245/j.hust.250607.F001图1晶圆多作业区可重入流水车间模型示意图本研究假设如下：a．在零时刻，所有机器都处于空闲状态，所有批次都可以被加工；b．每种产品类型的晶圆批次的工艺步骤是已知的，工序之间存在严格的加工顺序约束；c．每道工序同一时刻只能在一台机器上加工，机器进行工艺类型切换所产生的准备时间是已知的；d．若每个工件一旦开始加工，则不能中断，批次在相应机器上的加工时间是已知的；e．对于每种产品类型的晶圆批次，作业区之间的时间窗约束是已知的；f．晶圆批次从当前作业区转移到另一作业区之间的转移时间忽略；g．不考虑机器在加工过程中因故障导致的停机．1.2　数学模型1.2.1　目标函数min  f1=∑i=1Imax(Ci-di,0); (1)min  f2=∑i=1ITCi, (2)式中：f1为总拖期；Ci为批次i的加工完成时间；di为批次i的交货期；f2为总加工成本；TCi为批次i的总加工成本．1.2.2　约束条件∑m=1MXi,w,m=1    (∀i,w); (3)Si,w+Xi,w,mPi,w,m+Ym,k,hTk,h=Ci,w(∀i,w,m,k,h); (4)Ci,w≤Si,w+1    (∀i,w,w+1W); (5)Si,w+Xi,w,mPi,w,m≤Ri,j,mSj,w    (∀i,j,w,m); (6)Si,q-Si,p+∑w=pq-1∑m=1MXi,w,mPi,w,m≤TWi,t,p,q(∀i,t;qp); (7)Si,1≥0    (∀i); (8)mk≥1    (∀k); (9)TCi=∑w=1W∑m=1MXi,w,mPoi,wCw,m    (∀i); (10)Ym,k,h=1  (机器m上发生了工艺切换,∀m,k,h),0  (没有发生工艺切换,∀m,k,h);                Xi,w,m∈{0,1}   (∀i,w,m);                Ri,j,m∈{0,1}    (∀i,j,m), (11)式中：Xi，w，m为决策变量，若工序Oi，w在机器m上加工则为1，否则为0，Oi，w为晶圆批次i的第w道工序，即在第w个作业区的加工工序；i为批次集合I的索引；m为机器集合M的索引；w为作业区集合W的索引；k，h为工艺集合K的索引；Pi，w，m为工序Oi，w在机器m上的加工时间；Ci，w为工序Oi，w的结束加工时间；Si，w为工序Oi，w开始加工时间；Ym，k，h为辅助变量，若机器m上发生了工艺切换则为1，否则为0；Tk，h为工艺类型k，h进行转换所需要的准备时间；Ri，j，m为决策变量，若在机器m上批次j在i后加工则为1，否则为0；TWi，t，p，q为批次i在时间窗约束t中的约束时间，t为时间窗约束集合T的索引，p为t的开始作业区索引，q为t的结束作业区索引，且qp；Cw，m为作业区w中机器m的单位时间加工成本．式(3)表示一个批次i在一个作业区内只能被分配到其中一台机器上进行加工；式(4)表示批次i在作业区w的加工完成时间Ci，w由所选择的机器和是否须要工艺转换决定；式(5)表示批次i必须完成当前作业区w的加工才能进入下一个作业区；式(6)表示同一机器上相邻两个工件的加工时间不重叠；式(7)为时间窗约束，任何批次在规定的时间窗内的加工时间不得违反设定值；式(8)表示确保满足初始工艺开始时间约束；式(9)表示每个工艺可选择加工的机器至少有一台；式(10)为批次i的加工成本计算公式；式(11)为辅助变量和决策变量的取值范围．1.3　问题复杂性分析晶圆制造跨区多目标调度问题的复杂性主要由待加工晶圆数量、机器数量、目标函数、约束条件类型及数量等因素决定．根据决策变量Xi，w，m和Ri，j，m，问题的决策变量总数D的计算公式为    D=IWM+II-1M= IMW+I-1. (12)当作业区和机器数量不变时，随着待加工晶圆数量|I|的增长，D呈二次增长；当|I|不变时，随着作业区数量|W|和机器数量|M|的增长，D呈线性增长．这会给问题带来搜索空间扩展、计算复杂度提高和难以寻找全局最优解等困难．根据式(3)～(10)的约束条件，问题的约束总数Dc随问题规模变化的计算公式为    Dc=IW+IW+IW-1+II-1M+IT+I+M+I=I2M+3IW+IT-IM+I+M. (13)可以看出Dc随|I|的增长，呈二次增长；随|M|，|W|和|T|的增长，呈线性增长．这会带来可行解空间缩小、不可行解数量增大和求解稳定性下降等困难．2 基于自适应松弛因子的双种群协同进化算法晶圆制造跨区多目标调度问题本质上是一种约束多目标优化问题，可以表示为ci,t(x)=max(gi,t(x),0)    (∀i,t); (14)CV(x)=∑t=1T∑i=1Ici,t(x), (15)式中：ci，t(x)为批次i违反时间窗约束t的程度；x为算法的解；gi，t(x)为时间窗表示的数学不等式约束；式(15)表示x的总约束违反程度，若CV(x)=0，则说明解可行，否则是不可行的；CV(x)的值越大，说明解对整体约束的违反程度也越大．因此，在解决约束多目标优化问题时，不仅要平衡各个目标函数，还须要考虑约束的影响．2.1　双种群协同进化框架保证解集的可行性是解决多时间窗约束下晶圆跨区多目标调度问题的最主要任务，大多数算法过于关注种群的可行性，而没有平衡收敛性和多样性．这些算法很难跨越不可行区域，因此提出了双种群协同进化算法，具体来说：正常种群在受强约束的情况下进化，即种群个体的选择方式为约束支配原则方法；收敛种群在自适应松弛约束因子的作用下进化，即保留种群中优秀的不可行，增强了种群的多样性．双种群在进化过程中会逐渐得到两种不同的帕累托前沿(受约束的前沿和松弛约束的前沿)，而真实的帕累托前沿介于二者之间．在进化过程中，当收敛种群中的非支配解的比例达到要求时，两个种群开始融合以进行协同进化．收敛种群帮助正常种群跨越不可行区域并增加种群多样性，正常种群则帮助收敛种群改善可行性．算法的具体伪代码如下．算法1 双种群协同进化算法输入 种群数量N，最大进化代数Emax输出 正常种群Pop1随机初始化正常种群Pop1和收敛种群Pop2，每个种群数量为N设置自适应松弛因子ε0=infWhile当前进化代数还未达到Emax，do:通过锦标赛选择从Pop1，Pop2中选择N个个体组成P1，P2从P1，P2中生成后代Off1，Off2．初始化空种群Off3更新自适应松弛因子εk，并计算Pop2中非支配解所占的比例NcIf Nc＞50%：通过P1和P2生成子代更新Off3End if：将Off1，Off2和Off3合并到Pop1中；将Off2合并到Pop2中使用约束支配原则方法和自适应松弛因子方法分别从Pop1和Pop2中选择N个个体End whileReturn Pop12.2　自适应的松弛因子当面临复杂约束时，多目标空间中存在大量不可行区域，约束支配原则方法会极大地限制种群的探索能力，影响多样性．为此，文献[9]对其进行了改进，提出ε方法，通过设定阈值来松弛约束：当CV小于阈值时，不可行解被视为可行解．ε方法的关键在于如何更新ε的值，常用的方式是随着种群的进化代数增加而不断减小，但是无法考虑到种群的实际进化状况，当面对不可行区域范围大的情况时表现不佳；因此，提出了一种自适应的松弛因子方法，当种群开始进化时，ε的值是种群中约束违反个体最大的CV(x)值，这样会在帮助收敛种群探索到更广阔的区域．然后，将按比例不断减小ε值，与此同时收敛种群和正常种群融合，帮助正常种群跨越不可行区域．松弛因子ε自适应更新步骤如下．步骤1 初始化ε的衰减速率为α．步骤2 判断收敛种群中非支配解的占比Nc是否达到50%．步骤3 若没有，则更新当前εk的值为种群中约束违反程度最大的个体的CV(x)；若达到，则更新εk=(1-α)εk-1，k为当前种群进化代数．步骤4 返回更新后的εk值．2.3　编码解码方案和进化算子针对晶圆跨区调度的任务即为每道工序确定在不同作业区加工的优先级顺序和为每道工序确定在不同作业区加工的机器．采用两段式编码解码方案．第一段染色体采用基于工序的整数编码，表示晶圆批次的工序优先级，其长度为N1=∑w=1W∑i=1Ioi,w.第二段染色体针对机器选择部分，采用实数编码方式，实数的范围为0～1的一位小数，表示为工序Oi,w分配的加工机器，其长度等于N1．解码过程：第一段染色体的每个基因位代表工序的优先级，例如图2中第一段染色体中的第一个2表示批次2的第一道工序．第二段染色体根据第一段染色体的工序Oi，w的备选机器总数MOi，w对1进行拆分得到若干范围，例如若MOi，w=3，则得到(0，0.33］，(0.33，0.67］和(0.67，1］三个集合．如图2所示，第二段染色体的第一个基因位为0.4，则解码该工序所选择加工机器为机器集合MOi，w中的第二个，区别于传统的整数编码，第二段染色体的编码解码方式避免了产生不可行的染色体．10.13245/j.hust.250607.F002图2染色体编码与解码示意图进化算子是指对染色体进行交叉、变异的方式，是进化算法的核心部分．针对第一部分整数编码的染色体，采用基于顺序的交叉算子OX4[12]，避免破坏工序的相对顺序，保留父代染色体中的优良基因序列．对于第二部分的实数编码，采用多点交叉算子[12]，通过在多个位置进行交叉操作，能够探索解空间，提高解的多样性．变异算子在进化算法中通过对个体的基因进行随机变化，从而引入新的个体差异，同时由于随机性，因此在一定程度上也帮助了种群脱离局部最优解．采用两种变异算子分别对工序优先级染色体和机器选择染色体进行变异．a．随机点交换变异：由于工序的总数是确定的，不能对其进行增减，因此随机选择若干基因，交换这些基因上的值，打破局部最优，增加解的多样性．b．非均匀变异算子：适用于实数编码，提高解的局部搜索能力．随机选取若干基因位，再从0～1范围内随机生成若干值，替换原有基因的值．2.4　个体修复策略交叉、变异算子虽然在进化算法中增加了种群的多样性，引入了新的基因组合，但是不能保证其产生新的解都是满足约束的．个体修复策略可以针对种群中的不可行解，对其染色体进行调整，使其约束违反程度降低，提高种群的多样性和加速种群的收敛．针对多时间窗约束，为了避免产生不可行解，设计的个体修复策略步骤如下．步骤1 遍历出在时间窗约束TWt内违反约束的工序．步骤2 针对该约束内的最后一道工序，在不增加作业区w结束加工时间的条件下，将其转移到其他机器上进行加工．步骤3 若调整后违反时间窗约束程度减小，则将该新个体保存至下一代．步骤4 否则，继续步骤1，直至修复完毕．一个具体的个体修复策略例子如图3所示，作业区1和2之间存在连续操作时间约束，时间为90 min．因为批次12和9违反了时间窗约束，所以对其进行调整，顺序从左往右，先调整O12，2至机器6上加工，O9，2和O7，2左移，调整后批次12和9均不违反时间约束，同时作业区2结束加工时间减少了25 min，在一定程度上也减少了总拖期．10.13245/j.hust.250607.F003图3不可行个体修复策略3 实验结果与分析首先通过正交实验确定关键参数的大小，然后将所提出的算法和其他算法在算例上进行对比实验．算法对比指标为集合覆盖率Cm和超体积(Hypervolume，HV)，其中：集合覆盖率Cm用于比较算法收敛性的单一类指标；HV为综合描述解集收敛性和多样性的重要指标．最后，通过晶圆制造仿真系统连续6个月的测试结果验证所提出算法的有效性．3.1　算例设置根据Monch等的研究[13]，本研究设计的算例如下：考虑三种时间窗约束，第一种存在于扩散区和光刻区之间及光刻区与注入区之间的连续时间窗约束；第二种又包含了刻蚀区和注入区之间的重叠时间窗约束；第三种则为扩散区与抛光作业区之间的时间窗约束．批次数量I的取值为{20，25，30}，五个作业区的机器数量固定设置为{3，4，2，3，3}．时间窗约束流量因子FT的取值为{1.1，1.3，1.5}，用来控制时间窗约束的程度．算例中时间窗约束的时间长度参考文献[14]设置．此外，用JWF1-27来表示通过组合批次数量I、三种时间窗约束(TWC 1～3)和时间窗约束流量因子FT所设计的27个算例．3.2　算法参数实验ARF-DP算法的关键参数包括种群数量Ps、交叉概率Pc、变异概率Pm和衰减因子α．各参数的设置范围为Ps∈{100，150，200}，Pc∈{0.75，0.80，0.85}，Pm∈{0.20，0.25，0.30}，α∈{0.1，0.2，0.3}．采用正交试验法进行参数实验，设置9组不同的参数组合，每组进行独立重复实验，计算每个组合的HV指标的平均值和标准偏差．根据正交表，各参数的响应值列于表1中，其中Ps对响应值的影响最大，各参数在水平2时的响应值最高．最后确定最优参数组合为：Ps=150，Pc=0.8，Pm=0.25和10.13245/j.hust.250607.T001表1参数的响应值和排名水平PsPmPcα10.1570.1640.1720.16720.1900.1800.1860.17730.1810.1610.1710.168α=0.2．算法的最大进化代数Emax则统一设置为200．3.3　算例实验由于本研究提出的ARF-DP算法是以NSGA-Ⅱ为基础，因此为了评价其在解决多时间窗约束下晶圆多目标调度问题的优越性，选用来自同类的约束多目标算法CDP-MOEA/D[15]，CDP-NSGA-Ⅱ[14]，PF-NSGA-Ⅱ[16]，PF-MOEA/D[17]与ARF-DP进行对比．其中CDP和PF代表两种约束处理技术，即约束支配原则方法和惩罚函数法．所有算法均在每个算例下运行20次，如表2所示，通过Wilcoxon秩和显著性检验所得到的结果，ARF-DP算法在所有算例上的集合覆盖率指标测试结果均优于其他算法．综合考虑解的收敛性和分布均匀性，ARF-DP算法在25个算例上的超体积指标表现均优于其他算法．另外，ARF-DP算法和四种对比算法对于所有算例的平均求解时间分别为188，177，182，183，179 s．虽然ARF-DP算法的求解时间较其他算法稍慢，但是求解质量却有着显著优势．10.13245/j.hust.250607.T002表227个算例上4种算法对比ARF-DP算法在指标集合覆盖率和超体积上胜/负/平的数量CDP-MOEA/DCDP-NSGA-ⅡPE-NSGA-ⅡPE-MOEA/D胜负平胜负平胜负平胜负平02700270027002700270027012510270为了验证所提出的算法在解决多时间窗约束下的晶圆跨区调度问题的有效性，用NSGA-Ⅱ算法在相同进化代数的情况下对无时间窗约束下的调度问题进行求解．根据图4(a)中无约束问题下的帕累托前沿解分布图可知，多时间窗约束的存在限制了解空间中解集的分布，并限制了种群的进化方向．另外，从图4(b)中可以看出ARF-DP算法在进化75代后，种群中的帕累托解的数量得到了较大幅度的提升，这是由于收敛种群开始和正常种群进行协同进化，引导正常种群逐渐跨越不可行区域．10.13245/j.hust.250607.F004图4算法有效性验证为了更直观地表现出ARF-DP算法与其他算法的对比结果，对其中的两个算例绘制了帕累托解的分布图，如图5所示，ARF-DP算法均取得了更优及更均匀的帕累托解集，这与数值分析的结果是一致的．10.13245/j.hust.250607.F005图5两组算例下ARF-DP算法与对比算法的帕累托前沿解分布3.4　仿真算例实验为了进一步验证所提出算法的有效性，基于仿真软件Plant Simulation 9.0建立Fab仿真模型[18]．设置模型运行时间为半年，最初两个月为系统从初始化到稳定生产的过渡期，不采集数据；两个月后开始第一次数据采集，后续每个月更新一次数据．通过算法和仿真系统的数据交互，对比连续4个月中，ARF-DP算法与以上4种算法在指标Cm和HV上的值．表3和表4显示：ARF-DP算法在仿真算例中依然较其他算法有较大的优势，且随着生产规模不断变大，这种优势更加明显．例如第二个月和第三个月仿真系统中须要调度的晶圆数量最大，ARF-DP算法与其他算法的差距进一步增大．由于ARF-DP算法对问题解空间的充分探索，得到了具有更好帕累托前沿的解集，因此使得晶圆制造仿真系统的总拖期和总生产成本较其他4种算法中表现最好的PE-NSGA-Ⅱ算法平均降低16.3%和9.1%，进一步验证了所提出算法的有效性．10.13245/j.hust.250607.T003表3不同算法在仿真算例中指标Cm上的结果对比时期A，BB，AA，CC，AA，DD，AA，EE，A第1个月0.370.140.420.170.470.230.390.19第2个月0.380.070.390.000.430.220.680.27第3个月0.410.140.650.180.520.170.530.15第4个月0.320.130.480.230.420.260.510.2310.13245/j.hust.250607.T004表4不同算法在仿真算例中指标HV上的结果对比时期ARF-DPCDP-MOEA/DCDP-NSGA-ⅡPE-NSGA-ⅡPE-MOEA/D第1个月0.1780.0850.1080.1130.117第2个月0.1920.0970.1270.1340.149第3个月0.1880.0830.1050.1030.109第4个月0.1730.0770.1160.1230.0964 结语本研究针对多时间窗约束下的晶圆制造跨区多目标调度问题，提出了一种自适应松弛因子的双种群协同进化算法．通过设计正常种群和收敛种群，确保算法的收敛性、多样性和可行性，并利用自适应松弛因子对收敛种群进行约束松弛，保留优秀的不可行解．双种群协同进化框架加强了解空间探索和种群多样性，设计的两段式编码解码方案、进化算子和个体修复策略加速算法收敛．实验结果表明：该算法在收敛性、均匀性和可行解数量上优于其他4种算法，且平衡了总拖期和总生产成本．未来研究可考虑更复杂的多时间窗约束和晶圆的动态到达，开发更有效的约束多目标进化算法．