CN117707078A - 基于超启发式算法的半导体封测键合工序快响应调度方法及系统 - Google Patents

Abstract

本发明涉及一种基于超启发式算法的半导体封测车间键合工序快响应调度方法及系统，方法包括建立半导体封测键合工序调度优化模型；通过分批策略对大批量订单进行订单拆分；通过超启发式算法自适应生成调度方案，其中强化学习算法用作高级选择策略，启发式算子用作底层问题域的方法；输出最优调度方案，安排生产。本发明的调度方法及系统，针对半导体封测键合工序调度问题特点，设计简易启发式方法，用以构建LLH方法集合，从而实现对半导体封测键合工序调度问题的优化求解，既保留了元启发式算法良好的全局寻优性能，又避免了元启发式算法中凭人工经验调整算法参数带来的不确定性，可以有效提高算法设计的效率和键合工序调度效率。

Description

基于超启发式算法的半导体封测键合工序快响应调度方法及 系统

技术领域

本发明涉及车间作业调度技术领域，具体涉及一种基于超启发式算法的半导体封测键合工序快响应调度方法。

背景技术

半导体封装测试工艺流程主要包含划片、装片、键合、塑封、去飞边、电镀、打印、切筋和成型、外观检查、成品测试、包装出货等工序，其中，引线键合工序在众多电子产品中具有广泛的应用，是晶圆制造系统的关键技术。研究高效的键合区调度方法对于改善晶圆制造系统的性能、提高企业效益、增强企业响应市场的速度具有十分重要的意义。在晶圆制造系统中，引线键合加工区包含若干个设备单元，每个设备单元包含多台引线键合机，以由几百个晶圆组成的弹夹为最小生产单位进入设备单元进行引线键合。在实际生产中，引线键合工序以面对订单模式(MTO)组织生产，由于订单品种类型多，规模大，须采取高效的调度方法。

在生产调度领域，半导体封测键合工序的生产调度通常被归纳为大规模的(PMSP)并行机调度问题，是一个经典的NP-hard问题。对于并行机调度问题，现有研究通常采用简单规则或启发式算法。

发明者指出了上述算法存在的问题：首先，尽管简单规则和启发式算法在解决问题上都有一定优势，但它们的性能仍有提升空间。基于规则的调度算法具有性能稳定和易于实现的优点，但对于大规模的键合工序生产调度问题来说，它们表现不佳。启发式算法通常在解决复杂问题方面表现出色，它们可以在合理的时间内找到接近最优解，而无需穷尽所有可能的组合。然而，启发式算法通常不能提供全局最优解的保证，而只提供局部最优解或接近最优解的策略。这意味着在某些情况下，它们可能无法找到最佳解决方案，在实际应用中由于场景的变化导致适应性较差。此外，启发式算法的性能高度依赖于所选择的启发性信息或规则，不同的启发性信息可能导致不同的结果，因此需要仔细选择或调整这些信息。

发明内容

为解决现有技术中存在的技术问题，本发明提供了一种基于超启发式算法的半导体封测键合工序快响应调度方法，可以提高键合工序的调度效率。

为达到上述目的，本发明的技术解决方案如下:

一种基于超启发式算法的半导体封测键合工序快响应调度方法，包括以下步骤：

步骤一，建立半导体封测键合工序调度优化模型；

步骤二，筛选出大批量订单，通过分批策略对大批量订单进行订单拆分；

步骤三，通过超启发式算法自适应生成调度方案，将dqn深度强化学习算法用作高级选择策略，启发式算子用作底层问题域的方法；

步骤四，输出键合工序最优调度方案，包括待加工订单的加工优先级排序方案以及加工设备单元的选择优先级排序方案，安排生产。

步骤一中建立的半导体封测键合工序调度优化模型包括：符号定义、目标函数、约束条件及决策变量。

步骤二中的分批策略是采用最小批量分批策略，将弹夹工件数量大于最大批量约束的订单进行订单拆分，直到满足批量区间。

作为优选的技术方案，步骤三包括：生成N组个体的种群，随机挑选生成可行解组P并计算种群适应度f；初始化；操作上个动作，通过计算生成个体和相应的适应度值，根据适应度值，确定即时奖励，此时，当前状态被视为"下一个状态"，然后确定当前状态所属的状态，并计算出新状态的值；解的接受保留；确定奖励及新状态；判断算法是否结束，若满足终止条件，则算法结束，输出最优解，否则更新目标网络，将新的状态送入网络并获得动作，返回到初始化以后，操作上个动作及接下来的步骤。

作为优选的技术方案，在步骤三中，初始化是从可行解组中随机选择一组可行解，设这一组可行解为p_i，其适应度值为f_i，设P_B为最优解个体，F_B是最优解的适应度值，令P_B等于p_i，F_B等于f_i，状态设置为0，随机选择动作空间中的一个动作。

作为优选的技术方案，在步骤三中，解的接受保留是将新解的适应度值与旧解的适应度值进行比较，如果新解的适应度值大于旧解的适应度值，则将新解及其适应度值保存，并更新状态为新解；如果新解的适应度值小于旧解的适应度值，则考虑采用模拟退火算法来重新评估；如果计算出的概率大于一个随机值，那么同样保存新解并更新状态，反之，则放弃该解。

作为优选的技术方案，采用基于超启发式算法的半导体封测键合工序快响应调度方法的系统包括数据交互模块、数据预处理模块、调度方案生成与优化模块，数据交互模块包括调度信息获取、导入子模块和调度结果输出子模块，调度信息获取、导入子模块接收用户输入的待加工订单数据信息与设备单元数据信息，并输出给数据预处理模块；并在最后接收调度结果，将调度结果输出；数据预处理模块包括订单拆分子模块和拆批订单输出子模块，订单拆分子模块用于对导入的待加工订单进行拆分，采用分批策略，分批完成后输出给拆批订单输出子模块，并将订单拆分后的订单数据由拆批订单输出子模块输出给调度方案生成与优化模块；调度方案生成与优化模块用于接收输入的订单数据和调度模型，生成调度方案并通过超启发式算法对调度方案进行优化，最后将调度结果输出给数据交互模块。

作为优选的技术方案，采用基于超启发式算法的半导体封测键合工序快响应调度方法的系统还包括存储器和处理器。

与现有技术相比，本发明的有益效果为：

本发明的一种基于超启发式算法的半导体封测键合工序快响应调度方法，高级启发式策略采用DQN深度强化学习算法，低级启发式候选池由六种简单高效的启发式方法组成，针对不同规模的半导体封测键合工序订单，超启发式算法总能在可计算的时间内提供一个满意解，解决勒现有方法难以求解不同订单规模的问题，提高了键合工序的调度效率。

附图说明

图1是本发明的基于超启发式算法的半导体封测键合工序快响应调度方法的流程图；

图2是本发明的调度方法中超启发式算法的框架图；

图3是本发明的实施例的调度结果对比图；

图4是本发明的实施例的调度结果折线图；

图5是本发明的实施例的调度结果对比图；

图6是本发明的实施例的调度时间对比图；

图7是本发明的调度系统的结构示意图。

具体实施方式

下面结合具体实施方式对本发明的技术方案进行进一步的描述：

如图1所示，一种基于超启发式算法的半导体封测键合工序快响应调度方法，包括以下步骤：

步骤一，建立半导体封测键合工序调度优化模型；

具体地，对相应的调度优化模型作出如下设定：

键合工序调度的前提条件为：

1)所有设备单元与订单任务在0时刻均处于可加工状态；

2)每个批次订单中仅有一种晶圆产品；

3)加工过程中作业不可中断，一台机器同一时间内只能加工一个子批；

4)所有订单只需要一道工序即可完工；

5)同种晶圆产品组成的子批订单在不同设备单元上的加工时间不同；

定义相关符号，具体定义如下：

O为待加工晶圆订单的集合，O＝{O₁,O₂,…,O_n}；n为订单总数量；M为键合机设备集合，M＝{M₁,M₂,…,M_m}；O_ij为第i批次订单的第j个子批订单；C_max为最大完工时间,B_max为每批次订单的最大分批数，n为订单总数量，m为设备总数量，P_i,Mj为订单i在设备M_j上的加工时间，X_1b，_i，_j为订单i的子批b在设备m_j上的指派变量，若订单i的子批b分配到设备M_j上值为1，否则为0；B_bi为子批订单O_bi的弹夹数量，B_num为所有分批后的子批订单总数，B_max为每批次订单的最大分批数，B_min为每批次订单的最小分批数，M_o为模具总数；以最小化最大完工时间为优化目标，目标函数如下：

min(C_max) (1)

优化目标的约束条件如下：

各设备单元的完工时间不大于最大完工时间：

各订单分批后的总量不变：

各订单的每个子批只能在一个设备单元上加工：

分批后所有的子批订单都要进行加工：

分批后所有批次订单的总子批订单数：

B_num＝KB_max (6)

各订单每个子批的批量大小应满足最大批量约束和最小批量约束：

B_min≤B_bi≤B_max (7)

工件的最大分批数不大于对应最大模具数：

B_max≤M_o (8)

订单i中的第b个子批订单是否在设备单元M_j上加工的0，1变量：

x_1bij，x_2bij∈{0，1} (9)

步骤二，筛选出大批量订单，通过分批策略对大批量订单进行订单拆分；

分批策略是指：采用最小批量分批策略，将弹夹工件数量大于最大批量约束的订单进行订单拆分，直到满足批量区间。

步骤三，通过超启发式算法自适应生成调度方案，将dqn深度强化学习算法用作高级选择策略，启发式算子用作底层问题域的方法；

具体地，状态信息：状态设计的目的是在动作执行后，可以体现对环境的影响，以及为选择下一个动作进行预测选择。将状态表示为前后两代最优适应度值的变化程度与新产生的优质适应度值的解数量在新产生的解中所占的比例，其中当前代的最优适应度值为fit，下一代的最优适应度值为fit’，前后两代最优适应度值的变化程度用state＝(fit’-fit)/fit来表示；

动作空间：本方法中，动作空间为整数(1，2，3，…，N^A)，其中每个整数为每个低层启发式算子的指代，选择哪个整数即为选择哪个低层启发式算子；

奖励函数：利用奖励函数代表立即回报值，本问题的目标函数为最小化最大完工时间，若当前解的最大完工时间小于上一代解，则当前解更优，reward＝1；若解没有提升则reward＝0，质量下降则reward＝-1；

其中的低层启发式操作，具体方法如下：

LLH1：随机选择订单编码字符串中的一位，将其改变为对应订单可选设备单元的另一个随机设备单元；

LLH2：随机选择设备单元编码字符串中的两位，将其互相交换；

LLH3：随机选择订单编码字符串中的两位，将其互相交换；

LLH4：随机选择订单编码字符串中的两位，将这两位之间的字符串子串的顺序反转，得到新的订单编码序列；

LLH5：随机选择订单编码字符串中的两位，将这两位之间的字符串子串移动到订单编码最前；

LLH6：随机选择订单编码中的两位，将这两位之间的子串顺序随机打乱；

采用上述方法构建半导体封测键合工序调度问题的LLH方法集合；

步骤3.1：生成N组个体的种群，随机挑选生成可行解组P并计算种群适应度f。

步骤3.2：初始化。

从可行解组中随机选择一组可行解，设这一组可行解为p_i，其适应度值为f_i。设P_B为最优解个体，F_B是最优解的适应度值fit。令P_B等于p_i，F_B等于f_i，状态设置为0，随机选择动作空间中的一个动作；

步骤3.3：操作上个动作action，通过计算生成个体和相应的适应度值。根据适应度值，我们可以确定即时奖励reward。此时，当前状态被视为"下一个状态"。接下来，我们需要确定该状态state所属的状态，并计算出新的状态state'的值；

步骤3.4：解的接受保留。将新解的适应度值与旧解的适应度值进行比较。如果新解的适应度值(fit')大于旧解的适应度值(fit)，则将新解及其适应度值保存，并更新状态为新解(state'＝state,fit'＝fit)。如果新解的适应度值小于旧解的适应度值(fit'<fit)，则考虑采用模拟退火算法来重新评估。如果计算出的概率(p)大于一个随机值，那么同样保存新解并更新状态(state'＝state,fit'＝fit)，反之，则放弃该解。

步骤3.5：确定奖励及新状态state’，设EP代表经验池，将上述值存入，则EP_nE＝[state,action,reward,state’]，其中nE代表经验池中数据组数；

步骤3.6：判断算法是否结束，若满足终止条件，则算法结束，输出最优解，否则更新目标网络，将新的状态送入网络并获得动作，返回步骤3.3。

步骤四，输出键合工序最优调度方案，包括待加工订单的加工优先级排序方案以及加工设备单元的选择优先级排序方案，安排生产。

本实施例中，键合工序订单相关数据如下表1所示，记录了8个订单的投产量，以及每个订单的弹夹在不同设备单元上的加工时间。

表1键合工序车间调度订单加工时间数据

本发明采用的基于强化学习的超启发式算法(RL-HH)与三种简单规则和遗传算法进行性能对比，经过6次独立的实验验证，可以看出RL-HH在性能上优于简单规则和传统的遗传算法，如图4所示；

图5为各算法的调度结果标准差柱形图，可以看出RL-HH算法在稳定性上均优于简单规则和传统的遗传算法。

图6是本实施例的调度时间对比图，可以看出超启发式算法的响应时间较短。

基于同样的发明构思，本发明实施例还提供一种基于超启发式算法的半导体封测键合工序快响应调度系统，如图7所示，系统包括数据交互模块、数据预处理模块、调度方案生成与优化模块，数据交互模块包括调度信息获取、导入子模块和调度结果输出子模块，调度信息获取、导入子模块接收用户输入的待加工订单数据信息与设备单元数据信息，并输出给数据预处理模块；并在最后接收调度结果，将调度结果输出；

数据预处理模块包括订单拆分子模块和拆批订单输出子模块，订单拆分子模块用于对导入的待加工订单进行拆分，采用分批策略，分批完成后输出给拆批订单输出子模块，并将订单拆分后的订单数据由拆批订单输出子模块输出给调度方案生成与优化模块；

调度方案生成与优化模块用于接收输入的订单数据和调度模型，生成调度方案并通过超启发式算法对调度方案进行优化，最后将调度结果输出给数据交互模块。

调度系统还包括存储器和处理器，处理器执行计算机程序实现基于超启发式算法的半导体封测键合工序快响应调度方法中的步骤。

本实施例只是对本发明的进一步解释，并不是对本发明的限制，本领域技术人员在阅读完本说明书后可以根据需要对本实施例做出没有创造性的修改，但是只要在本发明的权利要求范围内都受到专利法的保护。

Claims (8)

1.一种基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，所述方法包括以下步骤：

步骤一，建立半导体封测键合工序调度优化模型；

步骤二，筛选出大批量订单，通过分批策略对所述大批量订单进行订单拆分；

步骤三，通过超启发式算法自适应生成调度方案，将dqn深度强化学习算法用作高级选择策略，启发式算子用作底层问题域的方法；

步骤四，输出键合工序最优调度方案，包括待加工订单的加工优先级排序方案以及加工设备单元的选择优先级排序方案，安排生产。

2.根据权利要求1所述的基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，所述步骤一中建立的半导体封测键合工序调度优化模型包括：符号定义、目标函数、约束条件及决策变量。

3.根据权利要求1所述的一种基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，所述步骤二中的分批策略是采用最小批量分批策略，将弹夹工件数量大于最大批量约束的订单进行订单拆分，直到满足批量区间。

4.根据权利要求1所述的基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，所述步骤三包括：生成N组个体的种群，随机挑选生成可行解组P并计算种群适应度f；初始化；操作上个动作，通过计算生成个体和相应的适应度值，根据适应度值，确定即时奖励，此时，当前状态被视为"下一个状态"，然后确定当前状态所属的状态，并计算出新状态的值；解的接受保留；确定奖励及新状态；判断算法是否结束，若满足终止条件，则算法结束，输出最优解，否则更新目标网络，将新的状态送入网络并获得动作，返回到初始化以后，操作上个动作及接下来的步骤。

5.根据权利要求4所述的基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，在所述步骤三中，初始化是从可行解组中随机选择一组可行解，设这一组可行解为p_i，其适应度值为f_i，设P_B为最优解个体，F_B是最优解的适应度值，令P_B等于p_i，F_B等于f_i，状态设置为0，随机选择动作空间中的一个动作。

6.根据权利要求4所述的基于超启发式算法的半导体封测键合工序快响应调度方法，其特征在于，在所述步骤三中，解的接受保留是将新解的适应度值与旧解的适应度值进行比较，如果新解的适应度值大于旧解的适应度值，则将新解及其适应度值保存，并更新状态为新解；如果新解的适应度值小于旧解的适应度值，则考虑采用模拟退火算法来重新评估；如果计算出的概率大于一个随机值，那么同样保存新解并更新状态，反之，则放弃该解。

7.根据权利要求1所述的采用基于超启发式算法的半导体封测键合工序快响应调度方法的系统，其特征在于，所述系统包括数据交互模块、数据预处理模块、调度方案生成与优化模块，所述数据交互模块包括调度信息获取、导入子模块和调度结果输出子模块，所述调度信息获取、导入子模块接收用户输入的待加工订单数据信息与设备单元数据信息，并输出给数据预处理模块；并在最后接收调度结果，将调度结果输出；所述数据预处理模块包括订单拆分子模块和拆批订单输出子模块，所述订单拆分子模块用于对导入的待加工订单进行拆分，采用分批策略，分批完成后输出给拆批订单输出子模块，并将订单拆分后的订单数据由拆批订单输出子模块输出给调度方案生成与优化模块；调度方案生成与优化模块用于接收输入的订单数据和调度模型，生成调度方案并通过超启发式算法对调度方案进行优化，最后将调度结果输出给数据交互模块。

8.根据权利要求7所述的采用基于超启发式算法的半导体封测键合工序快响应调度方法的系统，其特征在于，所述系统还包括存储器和处理器。