一种DAG云任务多目标调度算法  

A Multi-objective Scheduling Algorithm of DAG Cloud Tasks

作　　者：郑宇超[1] 夏学文[1] 艾冬梅[2] ZHENG Yu-chao;XIA Xue-wen;AI Dong-mei(School of software,East China Jiaotong University,Nanchang 330013,China;School of Mathematics and Physics,University of Science and Technology Beijing,Beijing 100083,)

机构地区：[1]华东交通大学软件学院,江西南昌330013 [2]北京科技大学数理学院,北京100083

出　　处：《微电子学与计算机》2018年第8期48-54,共7页Microelectronics & Computer

基　　金：江西省教育厅科研项目(批准号:GJJ150539)

摘　　要：提出了一种基于模糊占优排序的DAG任务调度离散粒子群算法FDS-PSO.首先,构建了预算与截止期限双QoS约束的多目标调度优化模型,模型构建了任务执行时间、执行代价及调度可靠性的多目标优化指标;然后,设计了一种离散PSO算法求解多冲突目标的均衡最优化问题,算法通过模糊占优排序的形式量化多目标解的相对适应度,进而得到满足帕累托最优的调度均衡解集合;最后,通过随机工作流结构实验仿真,与同类智能群体多目标调度算法进行性能比较.仿真结果证明,FDS-PSO算法不仅求解调度解的收敛速度更快,且解空间分布更均匀,能以更高的效率实现多目标的均衡优化.A DAG tasks scheduling algorithm FDS-PSO of discrete particle swarm optimization based on the fuzzy dominance sort is presented.First,the multi-objective optimization model of workflow scheduling under bi-QoS with the budget and deadline constraint is established,which introduces three optimizaiton objectives,including the execution makespan,the execution cost and the scheduling reliability.Second,a discrete particle swarm optimizaiton algorithm is designed to solve this three conflicting objectives optimization.FDS-PSO can quantify the relative fitness of multi-objective solutions through the fuzzy dominance sorting and obtain the solutions set of workflow scheduling satisfying Pareto optimal.Finally,through the simulation experiments of generated randomly workflow,compared with the same types of intelligent swarm multi-objective scheduling algorithms.Experimental results show that the scheduling solution obtained by FDS-PSO not noly has better convergence,but has better and uniform spacing distribution among solutions,which can better achieve multi-objective trade-off optimization.

关 键 词：云计算 任务调度 粒子群算法 模糊占优排序 多目标优化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]