欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2019104266327
申请人: 湖南大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于遗传算法的云计算任务调度方法,其特征在于,包括以下步骤:(1)从客户端接收资源分配请求,该资源分配请求包括客户端的数量p、以及物理机的数量m、任务被划分成的多个任务单元{TD1,TD2,…,TDk},其中任务单元TDu中包括多个子任务{TSu1,TSu2,…,TSur},且有r<=m、以及任务依赖关系图,其中k表示任务单元的总数,r表示任务单元TDu中子任务的总数;(2)根据资源分配请求为所有子任务随机生成概率矩阵λ,其等于:

其中xiv表示子任务TSu分配到物理机PMv中的概率,其为随机产生,u∈[1,k],v∈[1,m];(3)采用广度优先搜索算法对步骤(1)中的任务依赖关系图进行处理,从而得到多个子任务序列η1、η2、…ηn,每个子任务序列中包括任务依赖关系图中所有按照任务处理优先级顺序从大到小排列的子任务,其中n表示得到的子任务序列的总数量;(4)依次将步骤(3)中得到的每个子任务序列中的每个子任务分配给步骤(2)得到的概率矩阵λ中该子任务所属任务单元所在行的最大随机概率值所对应的物理机,进而形成父种群S={S1,S2,…,Sn},其中种群中的元素Sz表示第z个子任务序列中的每个子任务被对应的物理机后形成的子任务与物理机的映射关系;(5)计算每个物理机处理对应的任务单元的时间开销和能量开销,根据该时间开销和能量开销获取步骤(4)得到的父种群S中每个元素所对应的所有物理机的总时间开销和总能量开销,从而构成向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)},其中ctx表示父种群S中的第x个元素所对应的所有物理机的总时间开销,cpx表示父种群S中的第x个元素所对应的所有物理机的总能量开销,且有x∈[1,n];(6)判断当前的迭代次数是否已经达到迭代阈值,如果是则过程结束,否则进入步骤(7);(7)通过匹配选择算法从父种群S中选择元素,并先后采用模拟二进制交叉算法和变异算法对选择的元素进行处理,从而产生新的子代种群Q;(8)根据步骤(5)得到的每个物理机处理对应的任务单元的时间开销和能量开销获取步骤(7)得到的子代种群Q中每个元素所对应的所有物理机的总时间开销和总能量开销,从而构成目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)},其中cty表示子代种群Q中的第y个元素所对应的所有物理机的总时间开销,cpx表示子代种群Q中的第y个元素所对应的所有物理机的总能量开销,且有y∈[1,n];(9)将步骤(8)得到的目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)}与步骤(5)得到的目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)}进行融合,并将子代种群Q与父种群S进行融合从而得到混合种群;(10)通过环境选择策略从步骤(9)得到的混合种群中选择n个优秀解集构成新的种群,并返回步骤(6),其中选择的过程中需考虑步骤(9)中融合后的目标向量集合在由物理机的总时间开销和总能量开销构成的二维目标空间上的收敛性和分布性。2.根据权利要求1所述的云计算任务调度方法,其特征在于,步骤(5)中计算时间开销是采用以下公式:CT(i)=Taux+Tex其中Taux为第i个任务单元传输到物理机所需的时间,而Tex为物理机对该任务单元进行处理所需要的时间;计算能量开销f2是采用以下公式:f2=EC+ECE其中EC表示物理机处理第i个任务单元的计算能耗,ECE表示处理第i个任务单元的物理机与另外一台物理机之间的通信能耗。3.根据权利要求1或2所述的云计算任务调度方法,其特征在于,步骤(10)具体包括以下子步骤:(10-1)使用非支配排序算法将混合种群划分为多层集合(F1、F2、… ,、FL、FL+1、…、FNumber),其中第一层集合F1的处理优先级高于第二层集合F2的处理优先级,第二层集合F2的处理优先级高于第三层集合F3的处理优先级,…,以此类推,Number表示总的层数,FL是多层集合中的中间一个元素且为临界层;(10-2)将步骤(10-1)中得到的多层集合中的所有元素根据处理优先级顺序从大到小依次放入空的下一代种群中,其中当下一代种群的大小超过子任务序列的总数量n时,则停止放入操作,并通过邻域惩罚方法从临界层FL中挑选多个元素添加到下一代种群中,直到下一代种群大小等于子任务序列的总数量n为止;(10-3)对步骤(10-2)中的临界层FL中各个元素对应的所有物理机的总时间开销和总能量开销求和,得到各个元素的收敛信息;并根据临界层FL中各个元素对应的总时间开销和总能量开销计算该元素与临界层FL中其他各个元素之间的欧氏距离,作为该元素的分布信息;(10-4)根据步骤(10-3)得到的临界层FL中各个元素的分布信息确定邻域阈值T;(10-5)使用邻域惩罚方法对临界层FL中的各个元素进行邻域惩罚操作。4.根据权利要求3所述的云计算任务调度方法,其特征在于,步骤(10-4)具体为,首先获取临界层FL中每个元素的所有分布信息中的最小值,然后从临界层FL中所有元素对应的最小值中选择最大值,作为邻域阈值T。5.根据权利要求4所述的云计算任务调度方法,其特征在于,步骤(10-5)具体包括以下子步骤:(10-5-1)根据步骤(10-3)得到的临界层FL中所有元素的收敛信息选择收敛信息最小的元素p,并将其放入下一代种群中;(10-5-2)根据步骤(10-3)得到的临界层FL中所有元素的分布信息将临界层FL中与元素p的欧式距离小于邻域阈值T的元素放入惩罚集合中;(10-5-3)判断惩罚集合中的元素个数是否超过惩罚阈值G,如果超过则转入步骤(10-5-4),否则转入步骤(10-5-5);(10-5-4)将惩罚集合分割成分布性好的元素集合和分布性差的元素集合,并将分布性好的元素集合中的元素移入临界层,将分布性差的元素集合中的元素移入惩罚集合中,然后转入步骤(10-5-5);(10-5-5)判断下一代种群的大小是否等于n,如果不等于则返回步骤(10-5-1),否则返回步骤(6)。6.根据权利要求5所述的云计算任务调度方法,其特征在于,步骤(10-5-4)具体为,首先计算惩罚集合中的各个元素与下一代种群中的元素的最小欧式距离,然后对惩罚集合中的元素根据这些欧式距离值从小到大进行排序,最后将前G个元素视为分布性差的元素移入分布性差的元素集合中,将其它元素视为分布性好的元素移入分布性好的元素集合中。7.一种基于遗传算法的云计算任务调度系统,其特征在于,包括:第一模块,用于从客户端接收资源分配请求,该资源分配请求包括客户端的数量p、以及物理机的数量m、任务被划分成的多个任务单元{TD1 ,TD2,…,TDk}其中任务单元TDu中包括多个子任务{TSu1,TSu2,…,TSur},且有r<=m、以及任务依赖关系图,其中k表示任务单元的总数,r表示任务单元TDu中子任务的总数;第二模块,用于根据资源分配请求为所有子任务随机生成概率矩阵λ,其等于:其中xuv表示子任务TSu分配到物理机PMv中的概率,其为随机产生,u∈[1,k],v∈[1,m];第三模块,用于采用广度优先搜索算法对第一模块中的任务依赖关系图进行处理,从而得到多个子任务序列η1、η2、…ηn,每个子任务序列中包括任务依赖关系图中所有按照任务处理优先级顺序从大到小排列的子任务,其中n表示得到的子任务序列的总数量;第四模块,用于依次将第三模块中得到的每个子任务序列中的每个子任务分配给第二模块得到的概率矩阵λ中该子任务所属任务单元所在行的最大随机概率值所对应的物理机,进而形成父种群S={S1,S2,…,Sn},其中种群中的元素Sz表示第z个子任务序列中的每个子任务被对应的物理机后形成的子任务与物理机的映射关系;第五模块,用于计算每个物理机处理对应的任务单元的时间开销和能量开销,根据该时间开销和能量开销获取第四模块得到的父种群S中每个元素所对应的所有物理机的总时间开销和总能量开销,从而构成向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)},其中ctx表示父种群S中的第x个元素所对应的所有物理机的总时间开销,cpx表示父种群S中的第x个元素所对应的所有物理机的总能量开销,且有x∈[1,n];第六模块,用于判断当前的迭代次数是否已经达到迭代阈值,如果是则过程结束,否则进入第七模块;第七模块,用于通过匹配选择算法从父种群S中选择元素,并先后采用模拟二进制交叉算法和变异算法对选择的元素进行处理,从而产生新的子代种群Q;第八模块,用于根据第五模块得到的每个物理机处理对应的任务单元的时间开销和能量开销获取第七模块得到的子代种群Q中每个元素所对应的所有物理机的总时间开销和总能量开销,从而构成目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)},其中cty表示子代种群Q中的第y个元素所对应的所有物理机的总时间开销,cpx表示子代种群Q中的第y个元素所对应的所有物理机的总能量开销,且有y∈[1,n];第九模块,用于将第八模块得到的目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)}与第五模块得到的目标向量集合{(ct1,cp1),(ct2,cp2),…,(ctn,cpn)}进行融合,并将子代种群Q与父种群S进行融合从而得到混合种群;第十模块,用于通过环境选择策略从第九模块得到的混合种群中选择n个优秀解集构成新的种群,并返回第六模块,其中选择的过程中需考虑第九模块中融合后的目标向量集合在由物理机的总时间开销和总能量开销构成的二维目标空间上的收敛性和分布性。