基于指标预测和在线学的微电子生产线调度方法

摘要

基于指标预测和在线学的微电子生产线调度方法，属于先进制造、自动化和信息领域，其特征在于，采用基于预测机制的迭代式分解算法，将待求解的微电子生产线调度问题迭代分解为各阶段的调度子问题和用于全局指标预测的剩余调度子问题，采用基于资源冲突程度特征值的自适应差分进化方法对当前阶段多目标调度子问题进行求解，采用多模糊规则对当前阶段剩余调度子问题进行求解获得该调度子问题对应的全局指标。利用之前若干阶段调度子问题求解过程中所获得的相关数据，采用多模糊规则在线学框架对多模糊规则进行在线学。将本发明应用于以最小化平均流经时间和最大化瓶颈机器利用率为调度目标的微电子生产线可产生较好的调度效果。

主权项

1.基于指标预测和在线学习的微电子生产线调度方法，其特征在于，该方法是针对一类以最小化平均流经时间和最大化瓶颈机器利用率为调度目标的较大规模微电子生产线的一种调度方法，且所述方法是在计算机上依次按如下步骤实现的： 步骤(1)：初始化，设定如下基本变量 设定问题变量： N：微电子生产线中的工序总数 C_n：第n个工序的机器组总数，n＝1，2，…，N μ_nl：第n个工序第l个机器组包含的机器总数，n＝1，2，…，N；l＝1，2，…，C_nL：产品类型总数 V_l：属于第l类产品的lot总数，l＝1，2，…，L Q：lot的总数，J_q：第q个lot，q＝1，2，…，Q G_q：lot J_q所包含的操作总数 O_qg：lot J_q的第g个操作，g＝1，2，…，G_qlot J_q的工艺路径操作O_qg在第n个工序第c个机器组上的加工时间U_qg：操作O_qg的可加工机器组集合 T_qg：操作O_qg的可加工机器组总数，即T_qg＝||U_qg|| b_nc：第n个工序第c个机器组缓存 设定算法相关参数： W：用于迭代式分解的时间窗口长度 κ：每个当前阶段调度子问题需固定加工开始时间和加工机器的操作与当前阶段调度子问题包含操作的比例 M：用于多模糊规则MFRs学习的训练数据规模 M1：每次进行多模糊规则在线学习时需增加和移除的数据规模 min FS：模糊规则的最小支撑度 步骤(2)：采集包括上述工序数、品种数、各Lot的工艺路径和所包含的lot数、各工序的机器组数、各机器组中的机器个数、各操作在各机器组上的加工时间在内的调度相关信息并存储至调度数据库中，并形成待求解的微电子生产线调度问题实例； 步骤(3)：微电子生产线调度问题迭代分解 在当前调度时刻，基于时间窗口长度W及各lot的工艺路径按如下方法将整个待调度问题 的操作分解为已调度操作集B、当前阶段调度子问题的操作集H和当前阶段剩余调度子问题对应的操作集R； 步骤(3.1)：确定已调度操作集B 所有已被确定加工机器及加工开始时间的操作构成操作集B； 步骤(3.2)：确定当前阶段调度子问题的操作集H 设h_q为lot J_q在操作集B中的最大操作号，即 h_q＝max{g|O_qg∈B}q＝1，2，…，Q 操作集H根据下式确定 其中， 步骤(3.3)：确定用于预测的当前阶段剩余调度子问题对应的操作集R 操作集R由调度问题中不属于操作集B或H的操作组成，即 步骤(4)：采用基于资源冲突程度特征值的自适应差分进化方法SDEH求解当前阶段多目标调度子问题 针对上述微电子生产线调度问题，采用如下SDEH算法求解当前阶段多目标调度子问题，形成当前阶段全局调度解； 步骤(4.1)：个体编码和种群初始化 个体由在负载较大的前几个机器上加工的若干个操作串组成，每个操作串对应一个基因串，即个体由若干个基因串组成。 采用启发式规则：最短剩余加工时间优先(Shortest Remaining Processing Time，SRPT)、最先进入队列的优先(First Come First Served，FCFS)，最短加工时间优先(Shortest ProcessingTime，SPT)、最长剩余加工时间优先(Maximum Remaining Processing Time，MRPT)及上述规则的随机加权规则，求解当前阶段调度子问题，根据下述方法获得负载较大的前几个机器，并形成由Z个个体组成的初始种群P： 设Ψ为预先给定的个体基因长度的最大值，为当前迭代阶段第n个工序第c个机器组缓存b_nc中等待加工操作的总数，是当前调度子问题中在第n个工序第c个机器组上加工操作的总数；根据的大小对b_nc进行排序，，设排列结果为b_η1，b_η2，…，b_ηΓ，其中，Γ为缓存的 总数；然后，令 则个体由当前调度子问题中在与缓存b_η1，b_η2，…，b_ηγ对应的机器组上加工的操作串组成；每个基因串中的基因表示对应操作在相应机器组上的加工优先级，越靠前其加工优先级越高； 步骤(4.2)初始化 设总迭代步数为Λ，令θ＝1，初始复制概率为Rep； 步骤(4.3)：交叉 采用顺序交叉方法对随机配对的Z/2个体对进行交叉操作，形成子代种群P₁，其中，对配对的两个个体的对应基因串单独进行顺序交叉； 步骤(4.4)：变异 基于变异概率λ，对需变异的父代个体基因串S，从当前种群随机选择3个不同个体，与S对应的基因串分别设为S₁、S₂和S₃，产生随机整数r∈{1，2，...，m}，m为基因串S的基因长度；然后，根据下述流程生成子代个体对应的基因串S′： 步骤(4.4.1)：生成取值在区间[0，1]内的m个随机数； 步骤(4.4.2)：若上述第j(j＝1，2，...，m)个随机数不小于基因复制概率Rep_ij，且j≠r，则复制基因串S中的第j个基因作为子代个体相应基因串S′的第j个基因，设被复制基因的总数为Υ，将所有Υ个被复制基因从S删除，同时删除S₁、S₂和S₃中对应位置的基因，那么基因串S、S₁、S₂和S₃的长度均为m-Υ；Rep_ij为对应基因的复制概率，根据下式自适应调整： Rep_ij＝Rep ×β_ij其中，β_ij为相应基因通过预测获得的资源冲突程度值，其定义为：设与基因x_ij对应的操作为O_uv，Δ为通过求解前一迭代阶段剩余调度子问题获得的调度问题解的总数，其中在δ_uv个解中，操作O_uv与其它操作间存在资源冲突，则 β_ij＝δ_uv/Δ 步骤(4.4.3)：设迭代次数i＝1； 步骤(4.4.4)：令新基因值x_k表示基因串S的第k个基因，x_1，i，x_2，i和x_3，i分别为基因串S₁，S₂和S₃的第i个基因值，mod为取余运算符；步骤(4.4.5)：将填入到S′最左边的空白位置；步骤(4.4.6)：若i＜m-Υ，则令i＝i+1，执行步骤(4.4.4)；否则，执行步骤(4.5)； 步骤(4.5)：轮盘赌选择，其中，对当前调度子问题中的每个个体，基于预测机制，针对当前阶段剩余调度子问题，采用所提出的MFRs对当前阶段剩余调度子问题求解，获得每个个体对应的全局调度目标函数值； 步骤(4.6)：迭代终止条件判别 若θ≤Λ，则执行第5.3步，否则执行步骤(4.7)； 步骤(4.7)：构成当前阶段的全局调度解 由第四步所得到的当前阶段调度子问题的优化解F₁和当前阶段剩余调度子问题相应的优化解F₂共同构成当前阶段全局调度解F＝F₁∪F₂； 第五步：固定当前阶段调度子问题中部分操作的加工机器和加工开始时间 步骤(5.1)：若当前阶段全局调度解F优于迄今已获得的全局优化解F^o，则令F^o＝F； 步骤(5.2)：根据迄今已获得的全局优化解F^o和预先给定的待固定操作的比例κ，基于时间轴依次固定当前阶段调度子问题中部分操作的加工机器和加工开始时间； 步骤(6)：采用两阶段增量式学习方法TILM对多模糊规则MFRs进行在线学习 在当前阶段调度子问题求解完成后，按下述方法利用相关调度数据采用两阶段增量式学习方法TILM对多模糊规则MFRs进行在线学习； 步骤(6.1)：生成训练数据 按下述方法，根据当前阶段调度子问题具有最好全局调度性能的解F₁生成用于MFRs自适应调整的M₁个数据对，若当前阶段为第一阶段，则生成M个数据对；第m个数据对具有如下形式： 其中，和分别为调度决策时两个竞争上机的操作第k个属性对应的归一化属性值，k＝1，2，…，K；为只有两个取值为0或1的标签，表示上述两个操作中哪一个具有更高的调度优先级：步骤(6.1.1)：从F₁中多个决策时刻，连续保留M个决策时刻任两个操作的K个属性值，设第m个时刻保留的属性值为其中，为高优 先级操作对应的第k个属性值；步骤(6.1.2)：对上述M个决策时刻两个操作的每个个属性值按如下方法进行归一化处理，获得用于MFRs自适应调整的数据对： m＝1，2，…，M；k＝1，2，…，K；j＝1，2 步骤(6.2)：若为第一阶段，则根据生成的M个数据对生成有效的MFRs；否则根据下述提出的调整方法TILM对用于求解剩余调度子问题的MFRs进行在线调整，其中，MFRs中每条规则具有如下形式： …， 上述模糊规则具有多个前件和一个后件，是k个条件属性，k＝1，2，…，K，为的第i_kp个语言变量值，Y_q是属性的语言变量值总数；当p＝1，对应于需要排序的两个操作中的第一个操作；当p＝2，对应于第二个；是由同一属性两个操作的不同取值对应的2维模糊网格。D是结论属性，表示两个操作那个具有更高的调度优先级，从而，分类标签只有两个取值，i_R＝1表示第一个操作具有更高的调度优先级，i_R＝2表示第二个操作具有更高的调度优先级；CF(R)为规则R的确信度； 步骤(6.3)：初始化 计算min FS_amin FS_a＝(minFS×M-M₁)/M 步骤(6.4)：数据移除 按下述方法更新保留的模糊网格； 步骤(6.4.1)：从M个训练数据中移除最先生成的M₁个训练数据： 步骤(6.4.2)：对由M个训练数据生成的每一个模糊支撑度大于或等于min FS_a的模糊网格， 计算其在剩余M-M₁个训练数据下的模糊支撑度FS_r； 其中：是第m(m＝1，2，…，M-M₁)个训练数据的输入数据对，∏是算术连乘符；步骤(6.4.3)：若FS_r≥min FS_a，则保留相应的模糊网格；否则，移除相应的模糊网格； 步骤(6.5)：数据新增 按下述方法更新保留的模糊网格； 步骤(6.5.1)：将求解当前阶段调度子问题过程中新生成的M₁个训练数据增加到剩余的训练数据中： 步骤(6.5.2)：对由剩余的M-M₁个训练数据生成的每一个模糊支撑度大于或等于min FS_a的模糊网格，计算其在加入新生成数据后的M个训练数据下的模糊支撑度FS_a； 步骤(6.5.3)：若FS_a≥min FS_a，则保留相应的模糊网格；否则，移除相应的模糊网格； 步骤(6.6)：增加新的模糊网格 根据新生成的M₁个训练数据，增加新的模糊网格： 步骤(6.6.1)：根据新生成的M₁个训练数据，生成模糊支撑度大于或等于min FS的模糊网格： 步骤(6.6.2)：对于生成的模糊网格，基于M个训练数据，按步骤(6.5.2)计算其模糊支撑度FS_a； 步骤(6.6.3)：若FS_a≥min FS_a，则保留相应的模糊网格；否则，移除相应的模糊网格； 步骤(6.7)：获得有效的MFRs 将所保留的模糊网格生成对应的多模糊规则MFRs； 步骤(6.7.1)：根据上述保留的模糊网格获得有效的MFRs；其中，每条模糊分类规则R的模糊支撑度FS(R)作为其确信度，即： CF(R)＝FS(R) 步骤(6.7.2)：考虑到两个操作在输入顺序改变的情形下，其调度优先级应该是不变的，从而，在多模糊规则中，每条规则R均生成一条逆规则R′与其对应，逆规则具有如下形式： …， 其中，CF(R′)为规则R′的确信度，本发明中令CF(R′)＝CF(R) 步骤(7)：判定算法是否结束 若待调度问题的所有操作均已调度完成，则结束算法；否则，执行步骤(3)。