(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210842787.0 (22)申请日 2022.07.18 (71)申请人 广东工业大 学 地址 510062 广东省广州市越秀区东 风东 路729号 (72)发明人 刘强　曾创锋　张浩　魏丽军　 林利彬　 (74)专利代理 机构 佛山市禾才知识产权代理有 限公司 4 4379 专利代理师 刘羽波　陈嘉琦 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/06(2012.01) G06Q 10/10(2012.01) G06F 111/04(2020.01)G06F 111/08(2020.01) (54)发明名称 一种基于关键工序增强优化的流水线快速 优化方法 (57)摘要 一种基于关键工序增强优化的流水线快速 优化方法， 包括以下步骤： 步骤S1： 获取流水线上 的所有订单的信息数据， 其中所述订单的信息数 据包括流水线上作业的工序数量、 每一工序的可 用机器数量以及作业在每一个工序的加工工时； 根据生产要求、 订单的信息数据和约束条件构建 出以最小化最大完工时间为优化目标的流水线 数学模型； 步骤S2： 使用基于NEH启发式方法构造 初步的作业序列， 将所述作业序列作为流水线数 学模型的初始作业序列f(s)， 步骤S3： 对当前作 业序列f(scur)中作业排序进行破坏以及重构， 得 出更新作业序列f(snew)。 可以通过本发明量化衡 量排产结果， 还能给出全局最优排产方案， 极大 限度满足了产品的排产需求。 权利要求书3页 说明书8页 附图2页 CN 115186495 A 2022.10.14 CN 115186495 A 1.一种基于关键 工序增强优化的流水线快速优化方法， 其特 征在于， 包括以下步骤： 步骤S1： 获取流水线上的所有订单的信息数据， 其中所述订单的信息数据包括流水线 上作业的工序数量、 每一工序的可用机器数量以及作业在每一个工序的加工工时； 根据生 产要求、 订单的信息数据和约束 条件构建出以最小化最大完工时间为优化目标的流水线 数 学模型； 步骤S2： 使用基于NEH启发式方法构造初步的作业序列， 将所述作业序列作为流水线数 学模型的初始作业序列f(s)， 并对所述初始作业序列f(s)标记为当前作业序列f(scur)； 步骤S3： 对所述当前作业序列f(scur)中作业排序进行破坏以及重构， 得出更新作业序 列f(snew)； 步骤S4： 判断所述更新作业序列f(snew)是否优于所述初始作业序列f(s)， 若是， 则 使用 所述更新作业序列f(snew)代替所述当前作业序列f(scur)， 作为阶段作业序列， 若否， 将所述 前作业序列f(scur)作为阶段作业序列； 步骤S5： 重复步骤S3～S4， 直至迭代次数达到阈值， 停止算法运算， 将最后一个所述阶 段作业序列 作为全局最优排产方案 。 2.根据权利要求1所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 所述 步骤S2中通过基于NE H启发式方法构造初步的排产方案的步骤如下： 步骤S21： 所有作业按照总加工时间进行非增排序， 其中作业总工时的计算公式如下： 其中Pj表示第j个作业的总工时， Pij表示第j个作业第i个工序的加工时 间， 其中i∈{1， . ....,m}， m为作业的工序数量； 步骤S22： 在作业总加工时间的非增排序中第一个作业作为优化排序的初始序列， 并按 照所述非增排序的顺序将非增排序内的作业插逐个插入至 当前优化序列， 直至非增排序中 所有作业均插 入至所述优化 排序内， 将所述优化 排序作为所述初始作业序列f(s)； 其中当所述优化排序被插入时， 所述作业被插入至所述优化排序的所有可插入位置， 并获取所有新排序， 并将所有新排序 代入至所述流水线数学模型中获取具有最优目标函数 值的排序， 更新所述优化 排序。 3.根据权利要求2所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 所述 步骤S3中对当前作业序列f(scur)中作业排序进行破坏的过程如下： 设置破坏长度d， 其中破坏长度d大于1且小于n， n为作业总数量， 在工序的作业排序中 随机剔除d个作业， 得到被破坏作业排序， 并将剔除的作业按照剔除的顺序进 行保存至移除 序列内。 4.根据权利要求3所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 所述 步骤S3中对当前作业序列f(scur)中作业排序进行重构的过程如下： 移除序列的作业按照剔除的顺序插入至被破坏作业排序内， 其中当所述被破坏作业排 序被插入时， 所述被剔除的作业被插入至所述被破坏作业排序的所有可插入位置， 并获取 所述被破坏作业排序的所有新序列， 并被破坏作业排序的所有新序列分别代入至所述流水 线数学模型中获取最优目标函数值的排序， 更新得到更新作业序列f(snew)。 5.根据权利要求1所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征权　利　要　求　书 1/3 页 2 CN 115186495 A 2在于， 在获取得到所述当前作业序列f(scur)以及更新作业序列f(snew)后， 需要执行如下步 骤： 步骤A： 对所述当前作业序列f(scur)或更新作业序列f(snew)进行识别， 得到当前作业序 列f(scur)或更新作业序列f(snew)中能够减少最大完 工时间的工序， 并标记为关键 工序； 判断关键工序的邻域是否存在有其他工序， 若存在， 在将所述关键工序与邻域工序进 行交换， 得到优化作业序列 f(sg)， 并将所述优化作业序列 f(sg)输入所述流水线数学模型 中， 再次判断所述优化作业序列f(sg)是否优于所述当前作业序列f(scur)或更新作业序列f (snew)， 若是， 则使用所述优化作业序列f(sg)代替更新所述所述当前作业序列f(scur)或更 新作业序列f(snew)， 若否， 则保留所述当前作业序列f(scur)或更新作业序列f(snew)。 6.根据权利要求5所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 还包括以下步骤： 建立全局最优解集， 其中所述全局最优解集内存储的第一个作业序 列为第一个所述当前作业序列f(scur)； 当步骤A中得到优化作业序列f(sg)后， 将所述优化作业序列f(sg)与所述全局最优解集 内的作业序列进行比较， 若优化作业序列f(sg)优于所述局最优解集内 的作业序列， 则 清空 所述全局最优解 集， 将所述优化作业序列f(sg)添加至所述全局最优解 集内； 若优化作业序列f(sg)劣于所述局最优解集内的作业序列， 则将所述优化作业序列f (sg)存储在所述全局最优解 集内。 7.根据权利要求6所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 步骤S4中所述判断所述更新作业序列f(snew)是否优于所述前作业序列f(scur)的步骤 如下： 步骤B1： 将所述更新作业序列f(snew)以及所述前作业序列f(scur)分别输入至所述流水 线数学模型内计算两个排序方案的目标函数值， 判断所述更新作业序列f(snew)是否优于所 述前作业序列f(scur)， 若是， 则以所述更新作业序列f(snew)作为阶段作业序列， 若所述更新 作业序列f(snew)是否劣于所述初始作业序列f(s)， 则 计算Metropolis概率， 若Metropolis 概率大于U(0,1)， 其中U(0,1)为在0 ‑1的开区间中按均匀分布取随机数， 则所述更新作业序 列f(snew)代替前作业序列f(scur)， 作为所述流水线数学模型的阶段作业序列， 若 Metropolis概率小于U(0,1)， 则在所述全局最优解集内随机获取一个解作为所述流水线数 学模型的阶段作业序列， 其中Met ropolis概率的计算公式如下： 其中T为概率参数， 所述概率参数T随着迭代的次数增加而 减少。 8.根据权利要求5所述的一种基于关键工序增强优化的流水线快速优化方法， 其特征 在于， 所述关键 工序的获取 方法如下： 引入了一对虚拟节点Obegin和Oend来分别作业的第一个工序以及作业的最后一个工序， 故一个作业的最大完成时间可以表示 为L(Obegin,Oend)； 获取该工序的头部长度、 尾部长度以及加工工时， 若三者之和等于L(Obegin,Oend)， 则表 示该工序为关键 工序； 其中工序的头 部长度的获取公式如下： 权　利　要　求　书 2/3 页 3 CN 115186495 A 3