云环境中基于分解的多目标工作流调度算法

A decomposition-based multi-objective workflow scheduling algorithm in cloud environment

云服务提供商在给用户提供海量虚拟资源的同时,也面临着一个现实的问题,即怎样调度这些资源,以最小的代价(完工时间、执行费用、资源利用率等)完成工作流的执行。针对IaaS环境下的工作流调度问题,以完工时间和执行费用作为目标,提出了一种基于分解的多目标工作流调度算法。该算法结合了基于列表的启发式算法和多目标进化算法的选择过程,采用一种分解方法,将多目标优化问题分解为一组单目标优化子问题,然后同时求解这些单目标子问题,使得调度过程更为简单有效。算法利用天马项目发布的现实世界中的工作流进行实验,结果表明,和MOHEFT算法以及NSGA-II*算法相比较,所提出的算法能得到更优的Pareto解集,同时具有更低的时间复杂度。

Cloud service providers can provide large-scale virtual computing resources to users, but at the same time they are also facing a scheduling problem, that is how to schedule the computing resources with minimum cost （including makespan, monetary cost, resource utilization rate, etc. ） to complete workflow execution. To address the workflow scheduling problem in IaaS, we propose a multi-objective workflow scheduling algorithm based on decomposition which optimizes both the makespan and the mo- netary cost simultaneously. This algorithm combines the designs of the list-based heuristic algorithm and the multi-objective evolutionary algorithm. Using a decomposition method, it decomposes the multi-ob- jective optimization problem into a set of single objective optimization problems. Then the algorithm focuses on solving single-objective problems, in which way the scheduling process becomes more effective. The experiments based on the real-world applications published by the Pegasus project show that the proposed algorithm can achieve better Pareto fronts and at the same time has lower time complexity in comparison with the MOHEFT algorithm and the NSGA-Ⅱ algorithm.