1. 背景：
云计算近年来逐步发展，云计算能够通过网络以便利的、按需的方式访问一个可配置的计算资源共享池的模式，这个资源共享池能以最少的管理开销和最少的完工时间完成与供应商的交互，迅速配置、提供或释放资源[1]。
云计算的主要优势在于：能够迅速地降低硬件成本和提升计算能力以及存储容量等；用户可以以极低的成本投入获得极高的计算品质，而不用再投资购买昂贵的硬件设备，进行频繁的保养与升级。云服务提供商向云服务用户提供资源租赁服务，云服务用户通过租赁其资源来组建自己的数据中心完成任务。云服务提供商和云服务用户之间通过云服务调度器来完成资源的分配，而且云服务调度器的执行需要相应的调度算法来满足不同用户的需求。
在云计算的实际应用中，通常涉及到虚拟机的设置时间、软件准备时间、数据传输时间、价格变动等多种因素的影响[2]，很难真正利用好空闲资源。
目前的可租赁虚拟机分为按需虚拟机和竞价虚拟机两种。按需虚拟机即价格稳定的虚拟机，而竞价虚拟机的价格随着时间的变化而波动，用户需要以投标的方式来租赁竞价虚拟机。目前已有的算法大多数都是针对按需虚拟机进行租赁或利用当前的虚拟机价格对竞价虚拟机进行租赁，前者虽然稳定但是价格高，后者由于没有结合竞价虚拟机价格预测的功能，往往无法达到应有的效果。
2.问题描述：
批处理任务工作流在数据分析中比传统工作流更加常见[3]，为了加快处理速度，数据被分片，且多道任务并行处理。典型的例子是用于检查车辆是否有假许可证Fake-License Plate Detecting application (FLPD)的平台。
批处理常见的是基于无向DAG图MapReduce的处理模型,尽管工作流被模型化，任务被分为多个MapReduce任务，但资源的利用率总是低，因此提出了新的基于DAGs的计算平台，通过DAGs描述不同任务间的逻辑来提高资源利用率。
通常，基于DAGbased的平台部署在本地集群上管理的固定数量资源，或其他集群管理器，会带来过提供过度，性能不佳的问题，但是，对于批任务工作流的计算能力是动态的，因此需要把现有的DAGs平台部署到公共云上来获得动态能力。[5]
云资源租金费用的最小化是DAGbased的平台需要考虑的，许多方法没用考虑批处理的结构将会使任务期限不平衡，紧迫的任务期限可能是分配到许多短任务组成的任务批或者分配给非常具有宽松的任务期限更少的长任务的任务批处理，这都导致较低的租期利用率。
