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

摘要： 针对异构云环境下科学工作流调度的代价优化问题，提出一种基于约束关键路径的代价优化调度算法（CSACCP）。算法以满足截止期限约束同时最小化执行代价为目标，充分考虑云环境和科学工作流的独有特性，设定任务的向上权值，将工作流分解成约束关键路径（CCP）集合。结合首次适应插入算法以减少空闲时隙，改善费用优化效果，采用及时完成和最小费用增长代价的虚拟机选择策略形成备选资源集合。整体分配CCP到最便宜的虚拟机实例，压缩数据通信开销减少工作流的执行代价。通过四种著名的科学工作流仿真测试，结果表明与现有启发式算法相比，CSACCP不仅可以在满足截止期限的约束下得到更小的执行代价，还拥有更高的任务调度成功率。

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