近年来，随着MapReduce分布式计算框架的提出，一场席卷全球的变革正在互联网领域内悄然发生。作为MapReduce的开源实现，Hadoop分布式系统得到了国内外各大互联网公司的广泛应用。多用户共享式集群环境是Hadoop系统应用的典型场景。其中，Hadoop系统下作业调度器性能的优劣，即能否在保证作业调度过程公平性的同时最大限度的提升共享集群的整体吞吐效率，是决定Hadoop系统能否充分发挥分布式计算优势的关键。　　 目前Hadoop下已有的各种作业调度器无一例外的都是基于各种队列进行作业调度的。其本质是一种“基于队列”的贪心算法，即在不了解共享集群全局信息的情况下，就“草率”的以实现作业任务“本地性执行”最大化为目的进行作业任务调度。共享集群的整体吞吐效率往往在片面追求任务执行本地性的过程中被消耗。本文为了克服“基于队列”贪心算法的弊端，在Hadoop下的作业调度器中引入了“最小代价流图”的思想，提出了“基于最小代价流”的作业调度算法，并针对在多用户共享式集群环境下作业调度过程如何进行“流图”建模的问题，进行了系统、详细的理论研究。本文还在理论建模基础上实现了一个Hadoop分布式系统下的、“基于最小代价流”的作业调度器。　　 通过与Hadoop下已有作业调度器进行比较实验，本文验证了在多用户共享式集群环境下，“基于最小代价流”的作业调度算法在保证作业调度过程公平性的同时，对于提升共享集群整体吞吐效率方面性能的有效性。