(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111539028.9 (22)申请日 2021.12.15 (71)申请人 聊城大学 地址 252000 山东省聊城市东昌府区聊城 大学 (72)发明人 曾清清　李俊青　牛奔　韩玉艳　 李荣昊　耿雅典　 (74)专利代理 机构 湖北创融蓝图知识产权代理 事务所 (特殊普通合伙) 42276 专利代理师 何龙 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/10(2012.01) G06Q 50/04(2012.01)G06N 3/12(2006.01) (54)发明名称 一种带准备时间分布式零等待流水车间调 度方法与系统 (57)摘要 本发明研究了一种具有序列相关准备时间 和无等待约束的节能分布式置换流水车间调度 问题(EEDNWFSP)， 该问题在实际中有着重要的应 用。 同时考虑了最大完工时间(makespan)和总能 耗(TEC)两个目标。 为了解决这个问题， 首先建立 了一个整数规划数学模型用于精确求解。 然后针 对求解大规模实例的不足， 进一步提出了一种改 进的非支配排序遗传算 法(INSGA ‑II)。 该算 法利 用两种扩展的分布式NEH启发式生成高质量的个 体构造初始种群。 接着， 基于问题的特定知识提 出了两种速度调整启发式算法， 它们可以提高所 获得的非支配解的质量。 此外， 设计了四个局部 搜索算子和两个全局搜索算子， 提高了算法的搜 索和开发能力。 权利要求书3页 说明书17页 附图8页 CN 115249113 A 2022.10.28 CN 115249113 A 1.一种带准备时间分布式零等待流水车间调度方法与系统， 其特征在于： 所述方法包 括： S1： 研究了考虑序列相关准备时间的分布式零等待流水车间调度问题， 在这个问题中 同时考虑了对调度 的最大完工时间和机器的加工能耗、 待机能耗以及准备能耗的目标优 化； S2： 确定优化的目标及约束条件； S3： 采用改进的非支配排序遗传算法(I NSGA‑II)优化两个总目标； S4： 构造了两个邻域结构搜索高质量的解； S5： 提出四种变异算子和两种交叉算子提高算法的整体性能； S6： 所提出的算法对研究的问题进行了有效的验证。 2.根据权利要求1所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其 特征在于： 所述S1考虑序列相关准备时间的节能分布式零等待流水车间调度问题中， 有n个工件 可以在g个工厂中加工， 每个工厂都有m台机器。 每个工件由h个独立的操作组成， 按照相同 的顺序进 行加工， 且连续的操作之间要 无间断地进 行， 保证零等待的约束。 每台机器都有几 种不同的加工速度s， 速度越高导致加工能耗越多。 我们需要将工件分配给工厂， 并确定分 配工厂的调度顺序， 然后选择适当的加工速度以同时优化最小化最大完工时间和总能耗。 问题的约束 条件是： 不同工厂的机器数量和加工能力相同； 所有机器在零时刻可用， 所有工 件都可以在这个时间开始加工； 每个工件一次只能在同一工厂的一台机器上加工； 每台机 器一次只能加工一个工件； 一个工件应在指 定的机器上完成， 且无任何中 断； 每台机器的加 工速度可以调整， 因此实际加工时间和机器能耗随速度变化； 在工件加工过程中， 机器的速 度不能改变； 对于同一台机器上 的两个连续操作， 后续操作的开始加工时间应该大于或等 于前一操作的完成时间； 在完成前一阶段后， 工件要立即开始下一阶段加工， 不能等待。 3.根据权利要求2所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其 特征在于： 所述S2中的生产优化的目标为： min Cmax                                        (1) min TEC                                         (2) Cmax表示工件最大完 工时间的一个连续变量。 TEC表示所有工厂中的加工能耗、 待机能耗和准备能耗总和。 4.根据权利要求3所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其 特征在于： 所述S3是这样实现的： 在改进的非支配排序遗传算法(INSGA ‑II)中， 在随机初始化的同时， 使用了两个分布 式NEH启发式的变体用于产生良好的初始个体引导种群进化， 然后执行原始的环境选择函 数构造父代种群， 接着利用遗传算法(GA)生成新的子代种群。 在GA中， 嵌入了基于问题特定 知识设计的速度调整启发式， 与考虑分布式特性设计的四种变异算子一起提高了算法的局 部搜索能力； 设计了基于帕累托知识利用的两种交叉算子， 提高算法在 全局上的搜索能力。 然后进行快速非支配排序和拥挤度选择计算， 选出优秀个体， 最后得到一组较好的帕累托 解。 5.根据权利要求4所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其权　利　要　求　书 1/3 页 2 CN 115249113 A 2特征在于： 所述S4是这样实现的： 通过深入思考研究问题特征， 发现了问题特有的邻域结构， 据此提出了基于动态速度 缩放技术的调速启发式， 能够有效降低总能耗， 减少最大完工时间。 首先找到含有 可调空闲 时间的工件， 其中空闲时间分为左侧和右侧两种情况考虑， 根据这两种不同的邻域结构分 别从前往后和从后往前遍历所选中工件的操作， 找到符合降速条件的操作并进行调速。 显 然， 这种策略的主要思想是通过降速减少加工能耗， 减少空闲时间降低待机能耗， 以及符合 特定条件时还能减小最大完 工时间。 这些 方法的提出使研究的问题更符合实际。 6.根据权利要求5所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其 特征在于： 所述S5是这样实现的： 变异算子： 第一种方法是基于工厂间的分配。 具体步骤如下： (1)从关键工厂(即含有最 大完工时间的工厂)中随机删除一个工件， 并将其插入另一工厂的随机位置。 被插入工厂根 据完工时间从小到大选择。 (2)分别从两个工厂中随机选择两个工件i和i'， 然后交换这两 个工件。 首先， 根据完工时间将工厂按降序排列。 然后在交换时， 第一个工厂与最后一个工 厂交换， 第二个工厂与倒数第二个工厂交换， 依此类推。 第二种 方法是某一工厂内的分配。 具体步骤如下： (1)从同一工厂中随机选择两个工件， 然后 将后面的工件插入前面的工件之 前的位置 。 (2)从同一工厂中随机 选择两个工件， 然后交换它 们。 交叉算子： 第一种是基于非支配解信息的相同基因对保留策略， 具体步骤如下： (1)对 于每个工件， 统计在当前非支配解集中后续工件的数量， 找到出现次数最多的工件， 由这些 基因对组成了一个临 时集合。 (2)从父代种群中随机选出两个父代个体。 (3)对每一父代， 对 于每个位置的工件， 将与其后续工件一起形成一个基因对， 并在临 时集合中搜索该基因对。 (4)如果父代和临 时集合具有共同的基因对， 则相同的基因对将 被放置在子代的相同位置。 (5)否则， 比较处于相同位置的两个父代基因， 并将共同基因分别置于相应后代的相同位 置。 (6)最后使用基于双亲的单点顺序交叉(OP)填充后代空余的基因位。 第二种是基于非支 配解信息的相同基因位保留策略， 具体步骤如下： (1)统计当前非支配解集中每个位置出现 次数最多的工件， 生成一个临时个体。 (2)  从父代种群中随机选出两个父代个体。 (3)将每 一父代的基因与处于同一位置的临时个体的基因进行对比， 如果相同则将该基因置于子代 的相同位置。 (4)如果两个父代之间具有相同的基因， 则该基因将被放置在子代的相同位 置。 (5)最后使用基于双亲的单点 顺序交叉(OP)填充后代空余的基因位。 7.根据权利要求6所述的一种带准备时间分布式零等待流水车间调度方法与系统， 其 特征在于： 所述S6是这样实现的： 首先我们将改进算法与之前算法进行对比。 我们使用相同的实例， 每个实例独立运行 30次， 使用同一迭代次数200次作为停止标准。 我们选用最具代表性的多目标评价指标， 反 转世代距离和超体积指标 的平均值进行比较， 来验证改进算法的有效性。 其次通过实验验 证调速启发 式和局部搜索策略的有效性。 最后为了验证INSGAII的良好性能， 我们将其与两 种最新的多目标算法ARMOEA和hpaEA以及经典的NSGAII进行了比较。 我们对上述算法进行 了编码， 并在相同的环境下运行。 对于每种比较算法， 在考虑准备时间和机器速度可调的前 提下， 使用相同的例子在相同的条件 下迭代200次并独立运行30次， 得到每种算法的帕累托 前沿和评价指标值。 所有的比较算法都采用相同的停止准则， 在实际生产系统中具有很强 的实用性。 对不同算法生成的数据进 行了测试， 通过多因素方差 分析证明了算法的优越性，权　利　要　求　书 2/3 页 3 CN 115249113 A 3