关键词: 云计算, 科学工作流, 调度算法, 多目标优化

Abstract:

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 monetary 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-objective 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-II* algorithm.

Key words: cloud computing, scientific workflow, scheduling algorithm, multi-objective optimization