(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111591912.7 (22)申请日 2021.12.23 (71)申请人 合肥工业大 学 地址 230000 安徽省合肥市包河区屯溪路 193号 (72)发明人 刘心报　陆少军　江涛　程浩　 周志平　钱晓飞　 (74)专利代理 机构 合肥市浩智运专利代理事务 所(普通合伙) 34124 专利代理师 朱文振 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 50/04(2012.01)G06F 111/04(2020.01) G06F 111/08(2020.01) (54)发明名称 一种考虑恶化效应和资源分配的芯片制造 智能调度方法 (57)摘要 本发明公开了一种考虑恶化效应和资源分 配的芯片制造智能调度方法和系统， 通过使用 Benders分解法， 根据主问题的结构性质设计了 启发式算法， 并通过将VNS算法和启发式算法相 结合的智能算法求解， 获得局部最优解。 本发明 通过设计启发式算法， 实现了在中小规模数据 下， 上述算法能够在较短的时间内快速收敛到近 似最优解。 同时本过程综合考虑工件、 机器以及 资源等因素的协 同调度， 能够为降低企业成本、 提高资源利用率提供了思路， 给生产管理者提供 了决策理论支持。 权利要求书3页 说明书10页 附图1页 CN 114462191 A 2022.05.10 CN 114462191 A 1.一种考虑恶化效应和资源分配的芯片制造智能调度方法， 建立数学模型， 基于 Benders分解原理将总问题分解 为主问题模型和子问题模型， 其特 征在于： 主问题模型中： 输入工件数量为N， 平行批机器数量为M， 平行批机器的容量为c， 资源数量为U； 并根据 上述参数随机生成工件分配方案的初始解 π； 优化初始解 π， 有两个方案供选择， 优化时选择其中任一个进行： 方案一、 使用启发式算法优化初始解 π， 再使用VNS算法； 方案二、 将启发式算法作为邻域结构放入VNS算法中， 并用改进的VNS算法优化初始解； 子问题模型中： 将主问题模型优化得到的初始解π带入子问题模型中， 求解得到约束条件并加入约束 集S及目标值Z； 将主问题模型和子问题模型过程依次循环多次， 提出的约束过滤挑选多个约束条件加 入原主问题中， 重新计算， 若计算结果不满足终止条件， 则 返回主问题重新计算； 若满足终 止条件， 则终止流 程； 输出最终调度方案 π和目标值Z。 2.根据权利要求1所述的考虑恶化效应和资源分配的芯片制造智能调度方法， 其特征 在于： 所述VNS算法包括： 步骤101、 输入初始解 π； 步骤102、 对初 始解π进行l1次交换操作得到优化的初始解π_new1， 若 π_new1＜ π， 则用 π_ new1替代 π作为 新的初始解 π 返回步骤102； 否则进行步骤10 3； 步骤103、 对步骤102传递过来初始解π进行l2次变异操作得到优化的初始解π_new2， 若 π_new2＜ π， 则用 π_new2替代 π作为 新的初始解 π 返回步骤102； 否则进行步骤104； 步骤104、 对步骤103传递过来初始解π进行l3次反向子列表操作得到优化的初始解π_ new3， 若π_new3＜π， 则用 π_new3替代π作为新的初始解π返回步骤102； 否则输出初始解π并 停止。 3.根据权利要求1所述的考虑恶化效应和资源分配的芯片制造智能调度方法， 其特征 在于： 所述启发式算法包括： 步骤201、 将一批次内的关键工件和其他批次内的非关键工件按照规定的规则进行比 较， 确定是否交换； 步骤202、 将容量不满的批次的关键工件和其他批次内的关键工件按照规定的规则进 行比较， 确定后者是否加入不满的批次； 步骤203、 每个机器的批次从前往后一个接一个的按照规定的规则重新打乱分配会实 现部分最优， 当目标不再 得到优化停止； 步骤204、 每个机器的批次从后往前一个接一个的按照规定的规则重新打乱分配会实 现部分最优， 当目标不再 得到优化停止； 步骤205、 固定批次内的工件分配方案， 将初始解π按照规定的规则进行批排序， 得到的 新解若不满足最优继续排序， 直到满足最优或达到一定的排序次数， 选取其中最优的分配 方案。 4.根据权利要求2或3所述的考虑恶化效应和资源分配的芯片制造智能调度方法， 其特权　利　要　求　书 1/3 页 2 CN 114462191 A 2征在于： 所述改进的VNS算法包括： 步骤301、 初始解 π； 步骤302、 对初始解π进行j1次步骤201的操作得到优化的初始解π_new1， 若π_new1＜π， 则用 π_new1替代 π作为 新的初始解 π 返回步骤3 02； 否则进行步骤3 03； 步骤303、 对初始解π进行j2次步骤202的操作得到优化的初始解π_new2， 若π_new2＜π， 则用 π_new2替代 π作为 新的初始解 π 返回步骤3 02； 否则进行步骤3 04； 步骤304、 对初始解π进行j3次步骤203的操作得到优化的初始解π_new3， 若π_new3＜π， 则用 π_new3替代 π作为 新的初始解 π 返回步骤3 02； 否则进行步骤3 05； 步骤305、 对初始解π进行j4次步骤204的操作得到优化的初始解π_new4， 若π_new4＜π， 则用 π_new 4替代 π作为 新的初始解 π 返回步骤3 02； 否则进行步骤3 05； 步骤306、 对初始解π进行j5次步骤205的操作得到优化的初始解π_new5， 若π_new5＜π， 则用 π_new5替代 π作为 新的初始解 π 返回步骤3 02； 否则输出初始解 π 并停止 。 5.根据权利要求1所述的考虑恶化效应和资源分配的芯片制造智能调度方法， 其特征 在于： 所述终止条件为重复次数达 到指定值或目标值 不再下降。 6.一种考虑恶化效应和资源分配的芯片制造智能调度系统， 其特 征在于： 包括 主问题模块包括： 初始化模块： 用于输入工件数量为N， 平行批机器数量为M， 平行批机器的容量为c， 资源 数量为U； 初始解生成模块， 用于根据上述 参数随机生成工件分配方案的初始解 π； 优化初始解模块， 用于优化初始解 π， 包括： 分配单元， 用于在优化时从两个单 元中选择其中任一个进行优化： 第一单元， 使用启发式算法单 元优化初始解 π， 再使用VNS算法单 元； 第二单元， 使用改进的VNS算法单 元优化初始解； 子问题模块包括： 计算模块， 将主问题模型优化得到的初始解π带入子问题模型中， 求解得到约束条件并 加入约束集S及目标值Z； 循环计算模块， 将主问题模型和子问题模型过程依次循环多次， 提出的约束过滤挑选 多个约束条件加入原主问题中， 重新计算； 循环判断模块， 若计算结果不满足终止条件， 则返回主问题重新计算； 若满足终止条 件， 则终止流 程； 输出模块， 用于 输出最终调度方案 π和目标值Z。 7.根据权利要求6所述的考虑恶化效应和资源分配的芯片制造智能调度系统， 其特征 在于： 所述VNS算法单 元执行下述操作： 步骤101、 输入初始解 π； 步骤102、 对初 始解π进行l1次交换操作得到优化的初始解π_new1， 若 π_new1＜ π， 则用 π_ new1替代 π作为 新的初始解 π 返回步骤102； 否则进行步骤10 3； 步骤103、 对步骤102传递过来初始解π进行l2次变异操作得到优化的初始解π_new2， 若 π_new2＜ π， 则用 π_new2替代 π作为 新的初始解 π 返回步骤102； 否则进行步骤104； 步骤104、 对步骤103传递过来初始解π进行l3次反向子列表操作得到优化的初始解π_权　利　要　求　书 2/3 页 3 CN 114462191 A 3