移动云计算多目标任务调度进化算法

发布时间：2024-02-24 05:17

　　研究了移动云环境中任务调度的多目标优化问题,提出一种多目标任务调度进化算法MTSEA.建立了截止时间、预算及能量约束下的任务调度多目标优化模型,模型引入执行跨度、执行代价及执行能耗三目标最优化;设计了一种进化算法对冲突三目标最优化进行求解,算法重点在种群初始化操作中引入了效率最高、代价最小以及能效最高的三个种群个体,以此代替随机个体生成;并利用交叉和变异操作对个体进化迭代,最终通过非占优排序形式得到满足帕累托最优的调度解集.通过仿真实验与两种多目标调度算法进行了性能对比.结果表明,MTSEA算法调度解的收敛性及解空间距离和分布上是更优的.

【文章页数】：8 页

【部分图文】：

图18个任务的任务DAG

系统提供的移动云资源表示为集合R,资源总量为m,表示为R={R1,R2,…,Rm}.所有资源间为完全连通拓扑结构,每种资源的处理能力与执行代价各不相同,且均有能力执行任务集中的每个任务.假设任务在移动云资源上执行过程中不能被其他任务抢占,直到任务完成为止.如图2为包括5个资源的结....

图25个资源的资源结构

图18个任务的任务DAG令EST(Ti,Rj)表示任务Ti在资源Rj上的最早开始执行时间,EFT(Ti,Rj)表示任务Ti在资源Rj上的最早完成时间.对于入口任务,

图3一个染色体个体

进化方法中每个染色体表示一个任务调度方案S.在DAG表示的任务结构中,一个任务调度方案S由任务的调度次序和任务与资源间的映射关系组成.因此,一个染色体由任务调度序列TSO和任务-资源映射序列TRM组成.以图1的任务图和图2的资源为例,图3所示为一个染色体个体(TSO,TRM).4....

图4任务调度序列TSO的交叉

种群个体进化包括个体交叉与变异操作.个体交叉包括染色体中任务调度序列TSO的交叉操作和任务-资源映射序列TRM的交叉操作.任务调度序列TSO的交叉操作的具体方法为:随机选择两个任务调度序列作为父代1和父代2,并在两个任务调度序列的相同位置随机选择一个交叉点,该交叉点将任务调度序列....

本文编号：3908587