(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110541129.3 (22)申请日 2021.05.18 (65)同一申请的已公布的文献号 申请公布号 CN 113159642 A (43)申请公布日 2021.07.23 (73)专利权人 聊城大学 地址 252000 山东省聊城市东昌府区湖南 路1号 (72)发明人 桑红燕　郭恒伟　潘全科　李俊青　 韩玉艳　 (74)专利代理 机构 北京中创博腾知识产权代理 事务所(普通 合伙) 11636 代理人 孙福岭 (51)Int.Cl. G06Q 10/06(2012.01)G06Q 10/04(2012.01) G06Q 50/04(2012.01) G06N 3/00(2006.01) G06F 30/27(2020.01) (56)对比文件 CN 111414935 A,2020.07.14 殷生旺.“作业车间调度问题的自适应步进 值果蝇算法研究 ”. 《测控技 术》 .2018,第37 卷(第 1期),第120 -124页. 审查员 耿玲 (54)发明名称 基于改进果蝇算法的分布式流水车间调度 方法 (57)摘要 基于改进果蝇算法的分布式流水车间调度 方法， 涉及作业车间调度技术领域， 特别是属于 一种基于差异飞行策略改进果蝇算法的分布式 流水车间调度方法。 包括： 步骤1： 参数初始化； 步 骤2： 果蝇种群的初始化； 步骤3： 利用嗅觉探索机 制指导果蝇进行邻域扰动， 步骤4： 利用差异飞行 策略指导果蝇进行视觉飞行； 步骤5： 更新最佳解 决方案， 判断是否达到终止 条件， 若满足， 则进 化 结束， 输出当前最佳解决方案及其对应的最大完 工时间， 反之转至步骤3。 本发明解决了带有设置 时间的分布式置换流水车间调度问题， 具有降低 企业生产成本、 提高效率的积极效果。 权利要求书2页 说明书5页 附图3页 CN 113159642 B 2022.04.01 CN 113159642 B 1.一种基于改进果蝇算法的分布式流水 车间调度方法， 包括以下步骤： 步骤1： 参数初始化； 设置种群大小PSize、 种群最优果蝇个体未更新次数的阈值G以及 算法的停止时间T， 其中， 种群中包含的果蝇个体数量对应车间调度可选用的解决方案数 量； 阈值G表示最大完工时间最小的果蝇个体未改变的次数的上限值； 停止时间T＝10*m*n (m为机器数量， n为工件 数量)， 其中， 上述最大完工时间为每一个工厂中最后一个工件完成 时间的最大值； 步骤2： 果蝇种群的初始化； 通过基于工件序列的表示方法进行编码， 使用构造性启发 式方法生 成2个果蝇个体， 使用随机方法生成剩余PSize ‑2个果蝇个体， 形成包含PSize个果 蝇的初始种群P＝{π(1), π(2),... π(PSize)}， 从种群P中选择最大完工时间最小的果蝇个 体， 对最佳 方案进行 更新； 步骤3： 利用嗅觉探索机制指导果蝇进行邻域扰动， 并形成新果蝇种群P1＝{π(1), π (2),... π(PSize)}； 步骤4： 利用差异飞行 策略指导 果蝇进行视 觉飞行； 步骤5： 更新最佳解决方案， 判断是否达到终止条件， 若满足， 则进化结束， 输出当前最 佳解决方案及其对应的最大完 工时间， 反 之转至步骤3； 其特 征在于， 所述的嗅觉 探索机制包括 一次交换扰动、 二次交换扰动， 其中： 一次交换扰动的具体步骤如下： 从完工时间最大的工厂中随机提取一个工件， 记作 Jcri， 剩余的f ‑1个工厂， 每间工厂随机提取一个工件， 记作Jtar， 将Jcri与Jtar交换位置， 产生 f‑1个新方案， 从中选择最大完 工时间最小的方案； 二次交换扰动的具体步骤如下： 在一次交换扰动得到的方案中， 从完工时间最大的工 厂中随机选择b个不重复的工件， 其中， b的范围设定为大于3， 且小于完工时间最大的工厂 中的工件数目的一半， 从b个工件中随机选择一个工件记作Jori， 将Jori与剩余b‑1个工件进 行交换， 则产生b ‑1个新方案， 从中选择最大完 工时间最小的方案， 作为 新果蝇种群； 所述的差异飞行 策略包括以下步骤： a.根据果蝇种群中最小的最大完工时间未发生变化的次数， 判断种群是否 陷入局部最 优， 如果种群中最小的最大完工时间未发生变化的次数达到G次， 则认为种群此时陷入局部 最优， 执行步骤b1， 反 之认为种群未陷入局部最优， 执 行步骤b2； b1.若种群 陷入局部最优， 种群内的果蝇按照最大完工时间由小到大排序， 排序后的种 群中， 前20％的果蝇因为有着 较小的最大完工时间而被直接 保留； 剩余8 0％果蝇中， 前50％ 果蝇通过相邻工件互换方法， 向当前种群中最大完工时间最小的果蝇进行学习， 即对最大 完工时间最小的果蝇执行相邻工件互换方法； 剩余50％果蝇使用随机方法生成， 最终生成 一个包含PSize个果蝇的新种群P2； 从种群P2中随机选择PSize/2个果蝇， 更新种群P中最大 完工时间较大的PSize/2个果蝇(即果蝇种群P中较差的一半个体向果蝇群P2中的部分个体 飞行)； b2.若种群未陷入局部最优， 则将嗅觉探索阶段生成的种群P1与嗅觉探索阶段前的种群 P组合， 并从中选择最大完工时间较小的PSize个果蝇进行下一次迭代(即果蝇个体向种群 P1和P中最好的PSize个果蝇飞行)； 其中， 相邻 工件互换方法的具体步骤为： 首先寻找完工时间最大的工厂为关键工厂,若 关键工厂只有一个， 则对该工厂内的工件执行相邻工件互换操作， 即每相邻的两个工件互权　利　要　求　书 1/2 页 2 CN 113159642 B 2换位置， 从中选择完工时间最小的一组互换， 生成新方案； 若关键工厂数量存在多个， 则多 个关键工厂中的每个工厂中的工件， 均执行相邻工件互换操作， 从中选择完工时间最小的 一组互换， 生成新方案 。 2.根据权利要求1所述的基于改进果蝇算法的分布式流水车间调度方法， 其特征还在 于， 在步骤2中， 基于工件序列的表示方法进 行编码的步骤如下： 一个果蝇为一种解决方案， 以二维向量的形式表 示一个果蝇， 二 维向量由f个一 维向量构成， f为分布式工厂的数量， 一 个工厂对应一个一维向量， 每个一维向量中包含多个工件， 工件的排列顺序和加工顺序一 致， 基于上述编码规则， 一个果蝇个体可以表示为π＝{π1, π2,... πf}， 其中， 第k个工厂中的 工件序列 nk表示第k个工厂中待加工工件的 数目。 3.根据权利要求1所述的基于改进果蝇算法的分布式流水车间调度方法， 其特征还在 于， 在步骤2中， 构造性启发式方法的具体步骤如下： 首先， 计算每个工件的总加工时间， 按 照总加工时间从大到小排序， 前f个工件按随机方式， 依次分配到f个工厂中(工件 数量≥工 厂数量)； 剩余的工件逐一提取， 插入到最佳位置中， 直至所有工件都被提取并插入， 最 终生 成一个果蝇个体， 所述的最佳位置是在工件尝试插入到每一个工厂所有可能位置后， 所选 取的完工时间最小的位置 。 4.根据权利要求1所述的基于改进果蝇算法的分布式流水车间调度方法， 其特征还在 于， 在步骤2 中， 随机方法 的具体步骤如下： 随机选择f个工件， 按随机方式， 依次分配到f个 工厂中(工件 数量≥工厂 数量)； 剩余的工件随机提取， 一次提取一个工件， 将其插入到最佳 位置， 生成一个果蝇个体， 其中， 所述的最佳位置是在工件尝试插入到每一个工厂 所有可能 位置后， 所选取的完 工时间最小的位置 。权　利　要　求　书 2/2 页 3 CN 113159642 B 3