随着云计算技术的快速发展,越来越多的复杂工作流被转移到云系统中处理。云系统中具有丰富多类型的计算资源,可以帮助用户解决多种类的数据处理和任务计算问题,但是,计算资源即付即用的计费模式为云计算环境下的工作流调度问题带来了新的挑战。本文基于云计算环境,研究在有限预算下多个DAG工作流(Directed Acyclic Graph,有向无环图)的调度优化问题。云计算下的工作流调度是一个NP完全问题,而DAG工作流节点间复杂的优先约束和资源计费模式将使调度问题更为复杂。本文将云计算预算约束下的DAG工作流调度建模成整数规划问题。基于问题模型,将马尔科夫链的稳态概率作为任务的重要性度量,提出了一种升秩加权的优先级排序策略;其次,设计了一种额外预算的均匀分配方法;再次,完成了排序策略和预算分配方法的仿真,并在多种工作流上进行了全面的测试与性能对比分析;最后,在开源分布式计算框架Spark中实现了本文设计的任务级调度策略,并完成了典型工作流的测试与性能评估。本文的主要创新点和贡献如下:1.为预算约束下DAG拓扑结构的工作流调度问题建立整数规划模型。因此,用整数规划优化器可以方便的求解该问题。2.为任务的调度优先级设计了一种以马尔科夫链的稳态概率作为权重值的加权排序策略,使无约束关系的任务可以分配到更合理的优先级,同时保持了原来具有优先约束的任务之间的执行顺序。3.采用了一种为各个任务均匀分配额外预算的方案,试图在调度过程中维持预算在任务之间分配的均匀、稳定,实验表明该方案缩短了整体任务的执行时间。4.将建立的整数规划模型、任务的加权排序策略以及额外预算分配方案应用到Spark调度算法中,实现了Spark的任务级调度。算法的仿真实验表明,在大部分应用案例下,设计的算法在完工时间和执行费用上都优于对比算法,额外预算均分方案的平均性能优于比例分配方案,且基于马尔科夫链稳态概率加权的优先级策略进一步缩短了工作流的完工时间。工程实验结果表明,相比Spark默认的两种作业级调度方案,本文实现的方案在完工时间、调度公平性和调度成功率等方面均取得了更好的表现。