关键词: 云计算, 科学工作流, 截止期限约束, 代价优化

Abstract: To solve the cost optimization problem of scientific workflow scheduling in heterogeneous cloud envir-onment, a cost-optimized scheduling algorithm based on constrained critical path is proposed, named CSACCP. With the goal of meeting the deadline constraint while minimizing the execution cost, the algorithm takes full account of the unique characteristics of the cloud environment and scientific workflow, and decomposes the workflow into constrained critical path (CCP) using the improved upward rank. Combined with the first fit algorithm to reduce the idle time gap and improve the cost optimization effect, the virtual machine selection strategy of timely completion and minimum cost increase is adopted to form the alternative resource set. The algorithm allocates the CCP to the cheapest virtual machine instance, compressing data communication overhead and reducing workflow execution costs. Through the simulation tests of four well-known scientific workflows, the results show that CSACCP can not only get lower execution cost under the deadline constraint, but also achieve higher success rate of task scheduling compared with existing heuristic algorithms.

Key words: cloud computing, scientific workflow, deadline constraint, cost optimization