(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211120555.0 (22)申请日 2022.09.15 (71)申请人 史志 地址 410013 湖南省长 沙市高新 技术产业 开发区麓谷软件中心大楼6楼 (72)发明人 史志　刘贻任　吴奕隆　 (74)专利代理 机构 北京挺立专利事务所(普通 合伙) 11265 专利代理师 韩畅　耿彩红 (51)Int.Cl. G06F 9/455(2006.01) G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) (54)发明名称 基于蚁群算法优化的云计算任务调度方法 及系统 (57)摘要 本发明提供一种基于蚁群算法优化的云计 算任务调度方法及系统， 通过计算任务集中各任 务在不同虚拟机 上的执行时间来确定S ufferage 值， 按Sufferage值从高至低的优先级顺序逐一 为对应的任务预分配各自理想的虚拟机， 然后统 计虚拟机在每次预分配操作后的剩余资源， 接着 逐层构造各任务在不同剩余资源状态下的状态 转移概率， 对于在前处理的任务会获得更多的剩 余资源， 其在理想虚拟机上的状态 转移概率要高 于在后处理的任务， 进而使 得对时间损失度敏 感 的任务比非敏感任务具有更优的虚拟机选择条 件， 提高了蚁群算法对时间紧迫性任务计算最优 解的能力， 减少任务调度跨度， 将S ufferage算法 与蚁群算法融合， 在全局求解过程中融入了局部 解的优化能力。 权利要求书3页 说明书17页 附图3页 CN 115480876 A 2022.12.16 CN 115480876 A 1.基于蚁群算法优化的云计算任务调度方法， 其特 征在于， 该 方法包括： 步骤1)将所有虚拟机置为空闲状态， 计算任务集中各任务在不同虚拟机上的执行时间 并按升序排列， 将次短完成时间与最短完成时间之间的差值记 为sufferage值， 对 所有任务 的sufferage值按降序排列获得suf ferage序列； 步骤2)将所有任务分配到蚁群中待执行调度作业的蚂蚁节点上， 每个蚂蚁节点按 sufferage序列中sufferage值顺序依次提取对应的任务， 对于任意相邻的两个任务， 根据 执行时间择优原则先为前一任务分配虚拟机， 然后从已分配虚拟机总资源内减去 前一任务 对资源的消 耗量， 获得已分配虚拟机的资源剩余量， 利用各虚拟机资源剩余量计算其与后 一任务之间的初始状态转移概 率； 步骤3)每个蚂蚁节点利用初始状态转移概率对所有任务分别执行轮盘赌策略， 从任 务‑虚拟机分配矩阵中选择出对应的任务 ‑虚拟机分配方案， 当所有蚂蚁节点对每个任务均 完成虚拟机 分配后， 利用任务 ‑虚拟机分配方案对任务 ‑虚拟机分配矩阵进行全局信息素更 新， 生成全局信息素 更新矩阵； 步骤4)每个蚂 蚁利用全局信息素更新矩阵重新计算状态转移概率和执行轮盘赌策略， 利用重新选择 出的任务 ‑虚拟机分配方案生成新的全局信息素 更新矩阵； 步骤5)迭代执行步骤4)， 直至获得最优解的任务 ‑虚拟机分配方案， 利用该最优解对各 任务执行调度作业。 2.根据权利要求1所述的基于蚁群算法优化的云计算任务方法， 其特征在于， 根据 执行 时间择优原则为任务分配虚拟机的过程 为： 步骤211)提取当前任务最短完成时间所对应的虚拟机记为最优虚拟机， 判断最优虚拟 机上是否存在已分配的任务， 如果不存在， 则直接将该最优虚拟机分配给当前任务并执行 步骤213)， 否则将最优虚拟机上所有已分配的任务执行时间与当前任务最短完成时间求 和， 得到最优虚拟机的总执 行时间； 步骤212)将总执行时间与当前任务次短完成时间进行比较， 如果总执行时间不大于当 前任务次短完成时间， 则将最优虚拟机分配给当前任务并执行步骤213)， 否则提取当前任 务次短完成时间所对应的虚拟机记为次优虚拟机， 判断次优虚拟机上是否存在已分配的任 务， 如果不存在， 则直接将该次优虚拟 机分配给当前任务并执行步骤213)， 否则将次优虚拟 机上所有已分配的任务执行时间与当前任务次短完成时间求和， 得到次优虚拟机的总执行 时间并重复执 行当前步骤； 步骤213)根据sufferage序列中sufferage值顺序选择下一个任务并重新执行步骤 211)， 直至所有任务均完成虚拟机分配。 3.根据权利要求1所述的基于蚁群算法优化的云计算任务方法， 其特征在于， 所述初始 状态转移概 率的生成过程包括： 步骤221)计算第j个虚拟机VMj在执行第i个任务Ti调度前的资源剩余 量： 权　利　要　求　书 1/3 页 2 CN 115480876 A 2其中， cpj和bwj分别表示虚拟机VMj的总计算能力和总通信带宽， Lengthm和InputSizem 分别表示执行第 m个任务Tm需要消耗的计算量和传输的数据量， Taskij表示在执行第i个任 务Ti调度前已分配到虚拟机VMj上的所有任务集合， cp'ij和bw'ij分别表示虚拟机VMj在执行 第i个任务Ti调度前的剩余计算能力和剩余 通信带宽； 步骤222)利用资源剩余 量计算任务Ti分配给虚拟机VMj方案上的启发信息： 其中， ETCij表示任务Ti在虚拟机VMj资源剩余 量上的执 行时间， 表示 为： 其中， Lengthi和InputSizei分别表示执 行任务Ti需要消耗的计算 量和传输的数据量； 步骤223)利用虚拟机VMj的总资源计算初始信息素： 其中， τij(0)表示在初 始状态下任 务Ti分配给虚拟机VMj方案上的信息 素， a和b表示设定 的常数； 步骤224)利用启发信息 ηij和初始信息素τij(0)生成初始状态转移概 率： 其中， 表示在初始状态下， 第k个蚂蚁节点将任务Ti分配给虚拟机VMj的概率， K表 示蚁群中蚂蚁节点总数， J表示虚拟机总数， α和β 分别表示信息素权重因子和启发信息权重 因子。 4.根据权利要求1所述的基于蚁群算法优化的云计算任务方法， 其特征在于， 所述步骤 4)还包括采用以下公式执 行全局信息素 更新： τij(t+1)＝(1 ‑ρ )τij(t)+Δ τij,0≤t≤N 其中， τij(t)表示在执行第t次轮盘 赌策略前任 务Ti分配给虚拟机VMj方案上的信息素， ρ 表示信息素挥发因子， ρ ∈(0,1)， Δτij表示所有蚂蚁在任务Ti分配给虚拟机VMj方案上留下 的信息素增量之和， 表示 为： 其中， 表示第k个蚂蚁节点在任务Ti分配给虚拟机VMj方案上留下的信息素增量， 表 示为： 其中， Q表示常量， Lk(t)表示第k个蚂蚁节点在执行第t次任务 ‑虚拟机分配方案时的执权　利　要　求　书 2/3 页 3 CN 115480876 A 3