云环境中基于混合多目标粒子群的科学工作流调度算法

摘要

为了更高效地实现科学工作流任务的调度,研究了云环境中的工作流调度多目标优化问题,提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO.首先,建立了截止时间与预算约束下工作流调度的多目标优化模型,模型引入三目标最优化,包括工作流执行跨度、执行代价及执行能耗;其次,设计了一种混合粒子群算法对相互冲突的三目标最优化进行求解,算法通过非占优排序的形式可以得到满足Pareto最优的工作流调度解集合;最后,通过3种科学工作流案例的仿真实验,与同类多目标调度算法NSGA-Ⅱ,MOPSO和ε-Fuzzy进行了性能比较.实验结果表明,HPSO得到的调度解不仅收敛性更好,而且调度解的空间分布更加一致,更符合云环境中的工作流调度优化.%For realizing the more efficient scheduling of scientific workflow tasks,the multi-objective optimization problem of workflow scheduling in cloud environment was researched and a workflow scheduling algorithm HPSO of hybrid particle swarm optimization based on non-dominance sort was presented.First,the multi-objective optimization model of workflow scheduling under budget and deadline constraint is established,which introduces three optimizaiton objectives,including the execution makespan of workflow,the execution cost and the execution energy consumption.Second,a hybrid particle swarm optimizaiton algorithm is designed to solve this three conflicting objectives optimization.Our algorithm can obtain the solutions set of workflow scheduling satisfying Pareto optimal by non-dominance sort.Finally,through the simulation experiments of three types of scientific workflow case,we compared the proposed algorithm to the same types of multi-objective scheduling algorithms,such as NSGA-Ⅱ,MOPSO and ε-Fuzzy.The experimental results show that the scheduling solution obtained by HPSO not noly has better convergence,but also has better uniform spacing distribution among the solutions,which can better accord with the workflow scheduling optimization in cloud environment.