(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111597668.5 (22)申请日 2021.12.24 (71)申请人 昆明理工大 学 地址 650093 云南省昆明市五华区学府路 253号 (72)发明人 胡蓉　伍星　罗文冲　钱斌　 (74)专利代理 机构 昆明人从众知识产权代理有 限公司 5 3204 代理人 陈波 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 50/04(2012.01) G06N 3/12(2006.01) G06Q 10/04(2012.01) (54)发明名称 一种用于分布式作业车间调度的超启发式 差分进化方法 (57)摘要 本发明公开了一种用于分布式作业车间调 度的超启发 式差分进化方法， 属于作业车间调度 技术领域。 本发 明采用超启发式差分进化算法实 现对分布式作业车间调度的问题优化， 将结构简 单、 记忆能力强的差分进化算法作为超启发式框 架下的高层策略， 用以动态操作一系列简单有效 的低层启发式操作间接地实现对原问题目标求 解过程的优化。 使用本发明提出的方法， 一方面 可以保留启发 式算法较好的全局搜索能力， 另一 方面又可以有效地增强算法深度搜索的能力， 并 且可以有效地提高算法在调度优化问题中的稳 定性。 权利要求书3页 说明书7页 附图2页 CN 114037361 A 2022.02.11 CN 114037361 A 1.一种用于分布式作业车间调度的超启发式差分进化方法， 其特 征在于： 包括： 步骤1： 设置关键参数： 种群 大小ps， 缩 放因子Fs， 交叉概率CR， 低层启发式方法中的操作 数N； 个体边界包括下界lower(xb,d)， 上界upper(xb,d)， d＝1,2,...,N且b＝1,2,...,ps； 算 法最大迭代次数maxG； 步骤2： 采用N种邻域操作设计启发式规则， 构建面向分布式作业车间调度的低层启发 式方法集合， 并将ps种低层启发式方法编号； 种群 分为高层策略域种群X和低层问题域种群 Y， 高层策略域种群和低层问题域种群的种群大小都相同； 高层策略域种群中的每一个个体 就是一种低层启发式方法， 低层问题域种群中的每一个个体就是分布式作业车间调 度中的 一个解； 步骤3： 初始化种群； 对于高层策略域种群， 当迭代次数G＝0时， 令随机参数 并根据 生成初始的高层策略域 种群X； 对于低层问题域种群Y， 统一采用随机方式生产ps个个体的三个子序列； 将高层策略 域种群的个体和低层问题 域种群的个体一一对应； 其中， 三个子序列为工厂分配序列、 工序 排列序列和机器选择序列； 步骤4： 采用分布式作业车间调度模型评价低层问题域种群的个体， 得到每个个体的适 应度； 步骤5： 将高层策略域种群个体Xb中的低层启发式方法依次对应更新低层问题域种群Yb 个体， 根据分布式作业车间调 度模型求解适应度值； 每次更新时， 若产生的新解的适应度值 优于旧解， 则用新解替换旧解， 并不再执行后续低层启发式方法中的剩余操作； 否则继续执 行后续低层启发式方法中的剩余操作； 执行完 一个高层策略域种群个体Xb后， 该高层个体Xb 的适应度值即为对应的低层个 体Xb的适应度值； 步骤6： 根据适应度值的大小， 将高层策略域种群、 低层 问题域种群分别按照适应度值 从小到大排序； 步骤7： 进化阶段； 令b＝2， G＝1； 步骤8： 在高层策略域种群X中， 令个体X1为最优个体best； 令测试向量tmp＝Xb且计算变 量D＝0； 随机产生参数l1、 l2且满足l1,l2∈{1,2,...,ps}， 其中l1≠l2≠b； 随机选择d， d∈ {1,2,...,N}； 步骤9： 对best 依次差分进化变异操作和交叉操作； 步骤10： 对best进行差分进化选择操作； 使用tmp更新低层问题域种群Y中的个体Yb， 并 计算Yb的目标值， 以此 得到tmp的适应度值； 如果tmp的适应度值小于Xb， 则令Xb＝tmp； 步骤11： 根据适应度值的大小， 将高层策略域种群、 低层问题域种群分别按照适应度值 从小到大排序； 步骤12： 令G＝G+1； 若G≤MaxG， 则跳转至步骤7； 否则输出Y1作为调度最优解， 从而完成 对分布式作业车间调度的优化 求解。 2.根据权利要求1所述的用于分布式作业车间调度的超启发式差分进化方法， 其特征 在于： 所述分布式作业车间调度模型如下： Ci＝Ci,m； (1) Si,j+1≥Ci,j,j＝1,2,. ..,m； (2)权　利　要　求　书 1/3 页 2 CN 114037361 A 2Cmax( π )＝maxCi,i＝1,2,...,n；  (8) 式中， Ci表示工件i的最终完工时间， m表示工厂中的机器总数且该值等于工件的加工工 序数量， Ci,m表示工件i在机器m上的完工时间， 工件总数为n； Si,j表示工件i的第j道工序的 开始加工时间； 表示工件i的第j道工序在工厂a中的第k台机器上的加工时间； 为决 策变量， 如果工件i的第j道工序在工厂a中的第k台机器上加工， 则为1， 否则为0； Ea,k,r为工 厂a中第k台机器上加工顺序索引号为r的工件的起始加工时间； 为决策变量， 如果工件 i的第j道工序在工厂a中的第k台机器上的加工顺序索引为r， 则等于1， 否则等于0； qa,k表示 工厂a中第k台机器上加工的工序数量； 式(4)表 示工件i在工厂a的m台机器上被加工m次； 式 (6)表示工件i的第 j道工序在所有工厂的所有机器中只会被加工一次； 式(7)表 示一道工序 只能被所选择的机器加工一次； 式(8)表示分布式作业车间调 度的目标是在所有 可行调度 π 中寻找最大完工时间最小的调度 π*， 可行调度 π 由三个子序列构成， 包括： 工厂分配序列 πF、 工序排列序列 πO和机器选择序列 πM。 3.根据权利要求1所述的用于分布式作业车间调度的超启发式差分进化方法， 其特征 在于： 所述N种邻域操作包括全局交换操作、 工厂分配序列交换操作、 工厂分配序列变异操 作、 工厂内交换操作和工厂内插 入操作。 4.根据权利要求3所述的用于分布式作业车间调度的超启发式差分进化方法， 其特征 在于： 所述面向分布式作业车间调度的低层启发式方法集合包括ps种低层启发式方法， 每 种低层启发 式方法选择由全局交换操作、 工厂分配序列交换操作、 工厂分配序列变异操作、 工厂内交换操作和工厂内插 入操作中的一种或者多种操作按照排序构成长度为 N的个体。 5.根据权利要求3所述的用于分布式作业车间调度的超启发式差分进化方法， 其特征 在于： 所述全局交换操作为： 在工序排列序列中随机选择一个元素h1， 将其替换为一个不等 于h1的工件号h2； 然后在工序排列序列中所有等于h2的元素中随机选择一个替换成h1； 并 交换参与改变的这两个元 素对应的机器选择序列中的机器号。 6.根据权利要求3所述的用于分布式作业车间调度的超启发式差分进化方法， 其特征 在于： 所述工厂分配序列 交换操作为： 在工厂分配序列中所有工件中随机选择两个不相同 的工件h3和h4， 将 工件h3对应的工厂号替换为工件h4对应的工厂号； 同理， 将工件h4对应的权　利　要　求　书 2/3 页 3 CN 114037361 A 3