(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211042893.7 (22)申请日 2022.08.29 (71)申请人 山东财经大学 地址 250014 山东省济南市历下区二环东 路7366号 (72)发明人 杨成伟　祝翠玲　马慧娴　王颖彬　 (74)专利代理 机构 北京华清迪源知识产权代理 有限公司 1 1577 专利代理师 胡乐 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) (54)发明名称 一种分布式多目标云任务的调度方法、 装置 及云服务系统 (57)摘要 本发明公开了一种分布式多目标云任务的 调度方法、 装置及云服务系统。 方法包括： 构建适 应度函数； 使用微生物遗传算法缩小最优调度方 案的求解范围， 得到相应的种群并平分为第一种 群和第二种群； 第一种群上使用粒子群优化算 法， 得到第一最优解； 第二种群上使用布谷鸟搜 索算法， 得到第二最优解； 在共享时刻共享第一 最优解与第二最优解的优秀个体； 比较第一最优 解中适应度最小的个体与第二最优解中适应度 最小的个体， 将适应度更小的一个 保存为全局最 优解； 完成迭代输出全局最优解。 该方法在使用 微生物遗传算法后的种群上同时使用粒子群优 化算法和布谷鸟搜索算法， 避免了粒子群优化算 法陷入局部最优的可能性， 同时克服布谷鸟搜索 算法收敛速度慢的缺 点。 权利要求书5页 说明书15页 附图9页 CN 115421885 A 2022.12.02 CN 115421885 A 1.一种分布式多目标云任务的调度方法， 其特 征在于， 包括： 步骤A， 获取待调度的分布式多目标云任务的任务参数， 以及 云服务系统 的可用虚拟机 的虚拟机参数， 并构建适应度函数； 步骤B， 基于步骤A构建的适应度函数， 使用微生物遗传算法缩小多目标云任务在云服 务系统的最优调度方案的求 解范围， 得到相应的种群； 步骤C， 将步骤B得到的种群随机分为染色体数量相等的第一种群和第二种群； 步骤D， 在所述第一种群上使用粒子群优化算法， 得到第 一种群中的调度 方案的当前最 优解并记为第一 最优解； 步骤E， 在所述第二种群上使用布谷鸟搜索算法， 得到第 二种群中的调度 方案的当前最 优解并记为第二 最优解； 步骤F， 判断是否到达第 一最优解和第二最优解进行共享的时刻； 当算法整体迭代次数 达到预设的次数时， 则判定对第一最优解和第二最优解进行共享， 并执行步骤G； 当算法迭 代次数未达到预设的次数时， 则判定对第一最优解和第二最优解不进行共享， 并跳过步骤 G， 直接执 行步骤H； 步骤G， 共享第一最优解与第二最优解中的优秀个体， 更新第一最优解与第二最优解， 相应第一种群和第二种群也得到更新； 步骤H， 将第一最优解中适应度最小的个体与第二最优解中适应度最小的个体进行比 较， 保存比较结果中适应度更小的一个个体， 并将比较结果中适应度更小的一个个体作为 全局最优解； 步骤I， 重复步骤D至步骤H， 直至算法整体迭代次数达到预设的最大算法整体迭代次 数； 步骤J， 输出所述全局最优解， 所述全局最优解即为多目标云任务在云服务系统 的最优 调度方案 。 2.根据权利要求1所述的调度方法， 其特征在于， 所述分布式多目标云任务的任务参数 包括所述分布式多目标云任务的子任务数目以及每个子任务的任务大小； 所述可用虚拟机 的虚拟机参数包括可用虚拟机数目以及每个虚拟机的处理 能力； 所述可用虚拟机数目是由 所述云服务系统的资源决策器根据云任务的任务信息和云服务系统的资源使用机器学习 算法来分配的。 3.根据权利要求2所述的调度方法， 其特征在于， 所述云任务的任务信 息包括云任务的 预算、 开销、 内存和截止日期； 所述云服务系统的资源包括计算资源、 网络 资源和存储资源； 所述机器学习算法包括循环神经网络算法和深度神经网络算法。 4.根据权利要求2所述的调度方法， 其特征在于， 步骤A中所述构建适应度函数具体包 括： 设获取到的多目标云任 务的子任务数目为n， A＝{α1， α2， ...， αn}， 其中αi表示第i个子任 务， 0≤i≤n， 每个子任务的任务大小为SIZEi； 另设云服务系统的可用虚拟机数目为p， B＝ {β1， β2， ...， βp}， 其中βj代表第j个可用虚拟机， 0≤j≤p， 每个虚拟机的处理能力为MIPSj； n 个子任务被调度到P个虚拟机上 执行， n＞p； (1)基于各子任务在各虚拟机上的执 行时间计算执 行全部子任务所花费的最大时间： 任务i在虚拟机j上的执 行时间Tij的计算公式如下：权　利　要　求　书 1/5 页 2 CN 115421885 A 2Tij＝SIZEi/MIPSj 虚拟机j的释放时间RTj初始化为0， 当有任务i在虚拟机j上执行时， RTj的计算公式如 下： RTj＝RTj+Tij 任务i是虚拟机j上的第一个任务时， 其开始 执行时间STIj定义为0， 否则定义为虚拟机j 的释放时间RTj： STij＝RTj 任务i在虚拟机j上的完成时间FTij为任务i在虚拟机j上的开始执行时间STij与执行时 间Tij之和， FTij的计算公式如下： FTij＝STij+Tij 任务的最大完工时间Makespan为所有虚拟机释放时间的最大值， Makespan的计算公式 如下： (2)根据各虚拟机的执 行成本计算总执 行成本： 为云服务系统 的内存、 带宽、 处理器和存储空间预先设置相应的单位价格， 通过统计任 务调度过程中各虚拟 机对内存、 带宽、 处理器和存储空间的使用量， 计算P 个虚拟机对n个子 任务的总执 行成本Cost； (3)基于所有虚拟机的释放时间计算云环境的负载均衡： 云服务系统 的负载均衡定义为所有虚拟机释放 时间的标准差， 负载均衡的计算公式如 下： 其中 是所有虚拟机释放时间的平均值； 云服务系统中虚拟机使用得 越均衡， 虚拟机释放时间的标准差越小， 云服 务系统负载均衡的值越小； (4)基于所述执行全部子任务所花费的最大时间、 所述总执行成本以及负载均衡构建 适应度函数， 所述适应度函数为任务完工时间、 总执行成本及云环境负载均衡的加权和， 用 于衡量云计算任务调度的性能， 适应度函数的公式表示如下： fitness＝ λ1×Makespan+λ2×LB+λ3×Cost 式中λ1+λ2+λ3＝1， λ1、 λ2和 λ3的取值根据云任务需求调整； 适应度越小， 对应的多目标云 任务的调度方案越 优， 最小适应度对应的调度方案为所述多目标云任务的最优调度方案 。 5.根据权利要求1所述的调度方法， 其特 征在于， 所述 步骤B具体包括： 步骤B1， 通过随机创建X个染色体对种群进行初始化， 每个染色体为云任务在云服务系 统的可用虚拟机上的一种调度方案， 种群表示云任务的一系列调度方案； 步骤B2， 在种群上使用微生物遗传算法， 在种群每次迭代过程中， 随机抽取两个染色体 作为父染色体并比较两个父染色体的适应度， 对适应度小的一个父染色体不作任何处理，权　利　要　求　书 2/5 页 3 CN 115421885 A 3