(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210963223.2 (22)申请日 2022.08.11 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市下沙高教园区2 号大街 (72)发明人 袁友伟　高一鸣　黄笑成　邱仁志　 洪宇杰　鄢腊梅　 (74)专利代理 机构 杭州君度专利代理事务所 (特殊普通 合伙) 33240 专利代理师 朱亚冠 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/10(2012.01) G06N 3/00(2006.01) (54)发明名称 一种基于改进飞蛾火焰算法的工作流优化 调度方法 (57)摘要 本发明公开一种基于改进飞蛾火焰算法的 工作流优化调度方法。 该方法在工作流任务期限 约束下， 通过计算工作流调度方案中的能耗与时 延建立适应度函数作为系统成本， 并对飞蛾火焰 优化算法进行改进， 通过适当的突变过程与动态 交叉机制更新火焰的位置， 并引入适应度相关的 权重因子对飞蛾的位置进行更新， 使算法在期限 约束下充分利用基于服务器能耗与时延信息对 工作流调度方案进行迭代更新， 飞蛾根据与自身 对应的唯一火焰更新位置， 引导算法向约束优化 方向发展， 增强算法全局优化搜索能力， 最小化 边缘服务器能耗与时延， 从而得到最优的工作流 调度方案 。 权利要求书5页 说明书13页 附图5页 CN 115330189 A 2022.11.11 CN 115330189 A 1.一种基于改进飞蛾火焰算法的工作流优化调度方法， 其特 征在于包括以下步骤： 步骤(1)： 定义 边缘环境下的工作流和服 务器； 步骤(2)： 建立期限模型； 步骤(3)： 对所有任务进行编码； 记录工作流中每个任务所分配的服务器， 将一个飞蛾定义为一种工作流调度方案； 一 个工作流中， 任务数量为n， 服务器数量为m； 令R表示一个飞蛾， ri表示第i个任务分配的位 置； 则调度方案为： R＝[r1 r2 ... rn]               式(5) 调度方案中每 个任务在相应服 务器上完 工时间满足期限约束， 即： Tf(ri)≤Dr                       式(6) 其中Tf(ri)表示级别r中的任务ti的完工时间； Dr表示级别r的截止日期； 步骤(4)： 初始化种群及参数； 遍历整个任务集合， 对每个任务所分配的服务器生成一个随机整数rdi， rdi∈[1,m]， 直 到所有工作流子任务均分配至相应服务器， 从而得到一种工作流调度方案R； 初始 化飞蛾种 群为矩阵P＝[R1,R2,...,RN]T， 其中种群数量 为N， 上标T表示转置； 步骤(5)： 计算种群中每 个飞蛾的适应度： 5.1计算工作流调度过程中消耗的总时间， 包括任务执 行时间、 传输时间与等待时间； 当工作流任务ti被分配到服 务器sj时， 其任务执 行时间为： 其中l(ti)为任务ti的计算荷载， SC(sj)为服务器sj的处理能力； 假设在同一物理区域包含所有服务器， 因此服务器之间的平均带宽大致相等； 存在依 赖关系的任务ti与tj之间的数据传输时间取决于数据传输量cij， 故传输时间具体计算如 下： 其中ti为tj的前驱任务， bw为服务器平均带宽， ser(ti)、 ser(tj)分别为任务ti与tj分配 的服务器； 任务ti在服务器sl上运行的等待时间为： Tf(ti,sl)＝Tw(ti,sl)+Te(ti,sl)                 式(10) 其中Tr(ti,sl)为服务器sl准备好执行任务ti所需的时间， pre(ti)为任务ti的所有前驱 任务的集 合， Tf(ti,sl)表示服务器sl执行任务ti的完工时间。 工作流执 行的总时间为： 权　利　要　求　书 1/5 页 2 CN 115330189 A 25.2工作流总能耗主 要由服务器执行任务消耗的能耗与传输任务时消耗的能耗组成； 5.3适应度由工作流执 行总时间与总能耗决定， 具体 计算如下： L(w)＝T(w)+α E(w)                    式(15) 其中α 为权 重因子； E(w)表示工作流总能耗； 步骤(6)： 初始化 最优位置矩阵； 记第i个飞蛾的适应度 信息为ORi， 则种群的初始适应度矩阵为OP＝[OR1,OR2,...,ORN]T， 定义γ为初始种群的平均适应度， 具体 计算如下： 为避免工作流调度方案陷入局部最优， 每个飞蛾使用与自身对应的唯一火焰更新位 置， 在搜索空间中， 初始火焰 数量与飞蛾数量一致； 定义最优位置矩阵为F＝[FR1,FR2,..., FRN]T， 其中FRi表示第i个火焰， 为当前工作流最优的调度方案， 每一个飞蛾对应一个火焰； 为初始化F， 将种群P按其适应度矩阵OP中所记录的适应度进行升序排序， 将排序后的种群 进行对应赋值给最优位置矩阵F， 并记录F的适应度矩阵为OF＝[OFR1,OFR2,...,OFRN]T， 其 中OFRi为第i个火焰的适应度； 步骤(7)： 通过不断迭代创建工作流调度方案并进行 更新， 具体如下： 7.1判断种群中是否存在精英种群与精英个体， 若是则进行步骤7.3， 若是否则进行步 骤7.2； 7.2初始化定义精英种 群H＝[HR1,HR2,...,HRN]T， 即H＝P； 精英个体Rbest为适应度矩阵 OP中最优适应度对应的飞蛾； 并设置最大迭代次数 K； 其中HRi为第i个飞蛾； 7.3将当前迭代次数k下种群 中最优飞蛾与精英种群进行对应位置替换更新； 然后根据 更新后的精英种群筛 选出最优飞蛾， 并更新精英个 体； 7.4变异操作； 设置变异概率为θ， θ∈[0,1]， 遍历最优 位置矩阵中的每个火焰F Ri， 在[0,1]范围内随机 生成一个数， 若该随机数 大于θ， 则对火焰FRi进行变异操作， 具体操作如下： 其中dom为均匀分布在[0,1]之间的随机数， li为在[1,N]之间生成的随机整数， 且l1≠ l2≠l3≠l4； 7.5交叉操作； 交叉操作为工作流调度方案搜索提供了多样性， 使精英个体信 息能够传递至当前最优 工作流调度方案中； 将变异后的火焰FRi与精英个体Rbest通过交叉进行 混合， 具体操作是： 遍 历火焰FRi， 设置当前迭代次数下交叉率η(k)， 在均匀分布的[0,1]中生成随机数， 若随机数 大于 η(k)， 则将该任务分配的位置替换为精英个 体Rbest中相应的位置； 交叉操作取决于交叉率η(k)， 为细化对最优解的搜索， 将 η(k)设置为动态交叉率， 随着 迭代次数k的增大而 线性递减， 具体 计算如下： 其中， ηmax与 ηmin分别为 η 的最大值与最小值；权　利　要　求　书 2/5 页 3 CN 115330189 A 3