一种DAG云任务多目标调度算法
A Multi-objective Scheduling Algorithm of DAG Cloud Tasks
-
摘要: 提出了一种基于模糊占优排序的DAG任务调度离散粒子群算法FDS-PSO.首先, 构建了预算与截止期限双QoS约束的多目标调度优化模型, 模型构建了任务执行时间、执行代价及调度可靠性的多目标优化指标; 然后, 设计了一种离散PSO算法求解多冲突目标的均衡最优化问题, 算法通过模糊占优排序的形式量化多目标解的相对适应度, 进而得到满足帕累托最优的调度均衡解集合; 最后, 通过随机工作流结构实验仿真, 与同类智能群体多目标调度算法进行性能比较.仿真结果证明, FDS-PSO算法不仅求解调度解的收敛速度更快, 且解空间分布更均匀, 能以更高的效率实现多目标的均衡优化.Abstract: 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.
下载:
