田文洪，陈 瑜，王心阳，薛瑞尼，赵 勇

（1.电子科技大学信息与软件工程学院，四川 成都 610054；2.电子科技大学计算机科学与工程学院，四川 成都 611731）

1 引言

在云计算和大数据处理时代，MapReduce的开源实现Hadoop以其通用性和方便实用等特征得到了迄今为止最为广泛的应用。在云计算研究中，MapReduce环境的作业调度带来了一个新的课题和挑战，引起了越来越多的重视。最初，Hadoop默认的FIFO（先入先出）调度器是专为周期性执行大规模批量作业而设计的。随着MapReduce集群的用户数量的增加，计算能力调度器［1］和Hadoop公平调度器HFS（Hadoop Fair Scheduling）［2］的出现，提供了更高效的集群共享方式。业界已有少数研究Hadoop的调度原型的研究小组，旨在优化一些明确给定的调度标准，例如FLEX［3］、ARIA［4］。MapReduce的模拟器SimMR［5］也被开发出用于模拟不同的工作量下MapReduce的性能。但是，正如文献［6］中指出的，现有的调度器还不能提供对最小化作业集完工时间的支持。Tian等［7］针对离线多任务调度提出了几种高效的最小化总完工时间的调度算法并进行了对比分析，文献［8］针对在线多任务节能调度提出了一种高效动态划分算法，以最小化总完工时间。Tian等［9］提出了一种云数据中心动态负载均衡调度算法，该算法同时考虑CPU内存和网络带宽的利用率。

Herodotou H等［10］提出了一种工作流－感知调度器，通过把数据位置与任务调度相结合，优化工作流完工时间。Moseley B等［11］将MapReduce调度转化为经典的具有相同机器的两阶段工作车间作业问题，在离线情况下，他们提出了一个对于最小化总完成时间近似比为12的近似算法。……