一种基于蚁群算法的实时云任务多目标优化调度方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113986518A(43)申请公布日2022.01.28(21)申请号202111617335.4(22)申请日2021.12.28(71)申请人华南理工大学地址510640广东省广州市天河区五山路381号(72)发明人刘发贵沈俊敏(74)专利代理机构广州粤高专利商标代理有限公司44102代理人周春丽(51)Int.Cl.G06F9/48(2006.01)G06F9/455(2006.01)G06N3/00(2006.01)权利要求书3页说明书9页附图2页(54)发明名称一种基于蚁群算法的实时云任务多目标优化调度方法(57)摘要本发明公开了一种基于蚁群算法的实时云任务多目标优化调度方法。所述方法包括以下步骤：建立云任务调度的多目标函数；将任务的截止时间约束条件引入蚁群算法的信息素更新规则中，得到改进的蚁群算法，根据多目标函数，采用改进的蚁群算法进行迭代寻优，找到任务与云系统的虚拟机之间最优的映射方案，根据该方案将任务调度到对应的虚拟机上；在虚拟机的等待队列中，基于回填算法的特性，根据任务的截止时间约束条件，对虚拟机队列中的任务进行重新排序，进一步满足实时任务的截止时间要求，完成实时云任务多目标优化调度。本发明保障任务的截止时间要求的同时最小化数据中心产生的能耗，实现多个目标的平衡。CN113986518ACN113986518A权利要求书1/3页1.一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，包括以下步骤：S1、建立云任务调度的多目标函数；S2、将任务的截止时间约束条件引入蚁群算法的信息素更新规则中，得到改进的蚁群算法，根据多目标函数，采用改进的蚁群算法进行迭代寻优，找到任务与云系统的虚拟机之间最优的映射方案，根据该方案将任务调度到对应的虚拟机上；S3、在虚拟机的等待队列中，基于回填算法的特性，根据任务的截止时间约束条件，对虚拟机队列中的任务进行重新排序，进一步满足实时任务的截止时间要求，完成实时云任务多目标优化调度。2.根据权利要求1所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，步骤S1中，所述云任务调度的多目标函数由完工时间和云数据中心的能耗加权组成，所述完工时间为所有虚拟机执行完任务所需时间；云任务调度的多目标函数F的定义公式如下：其中，是权重因子；表示完工时间，表示可能的最大完工时间，表示任务i的截止时间，用于归一化完工时间，表示任务数量；表示所有虚拟机执行完所有任务云系统的总能耗，表示云系统可能产生的最大能耗，表示任务i在虚拟机j上执行所需能耗，用于归一化总能耗，表示云系统中虚拟机的数量。3.根据权利要求2所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，所有虚拟机执行完所有任务云系统的总能耗的计算公式如下：其中，表示云系统中第j台虚拟机产生的能耗。4.根据权利要求2所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，权重因子根据实际应用场景需求进行调整；设置>0.5时，满足用户的服务质量需求，提高任务的响应时间；设置<0.5时，满足能耗感知的场景需求；2CN113986518A权利要求书2/3页设置等于0或者1时，多目标优化调度问题退化为单目标优化调度。5.根据权利要求3所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，虚拟机产生的能耗由活动状态时的能耗和空闲状态时的能耗组成；活动状态时的能耗表示虚拟机执行任务时产生的能耗，空闲状态时的能耗表示虚拟机没有执行任务时产生的能耗；云系统中第j台虚拟机产生的能耗定义如下：其中，表示虚拟机j活动状态时的能耗，表示虚拟机j空闲状态时的能耗。6.根据权利要求1所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，步骤S2中，将任务的截止时间约束条件引入蚁群算法的信息素更新规则中，得到改进后的信息素更新规则，进而得到改进的蚁群算法；通过改进后的信息素更新规则，使得改进的蚁群算法在迭代寻优过程中不仅根据目标函数进行寻优，同时蚂蚁的寻优方向将受到改进的信息素的约束，使得蚁群算法能够找到一种最优的任务与虚拟机之间的映射方案，满足任务截止时间条件的同时减少虚拟机产生的能耗。7.根据权利要求6所述的一种基于蚁群算法的实时云任务多目标优化调度方法，其特征在于，改进后的信息素更新规则具体如下：其中，公式（6）是局部信息素更新公式，公式（7）是全局信息素更新公式；是信息素蒸发系数；表示任务i分配到虚拟机j的信息素值，表示初始信息素值；是惩罚系数，；表示任务i在虚拟机j上执行完的时间；表示任务i的截止时间；局部信息素更新公式（6）表示，将任务i分配到虚拟机j上时，若虚拟机j执行完任务i的时间能够满足任务i的截止时间要求，则根据