MapReduce框架中的排序模型与算法

MapReduce是处理和生成大数据集的一种编程模型。本项目针对MapReduce框架中作业调度的特点，系统研究MapReduce排序问题的模型与优化算法。具体研究内容如下：MapReduce平行机排序问题的不可中断与可中断情形；MapReduce流水作业以及混合车间排序问题的离线与在线情形；考虑Shuffle过程的相关排序问题，包括带有传输时间的MapReduce排序问题和类MapReduce的三阶段集成排序问题。对离线问题，研究其计算复杂性，设计高性能的近似算法或近似方案。对在线问题，用竞争比分析给出问题的下界并设计在线算法。针对复杂模型，通过设计启发式算法和智能算法进行数值计算和实验分析。通过本项目对MapReduce排序问题进行系统的理论研究和相关问题的算法设计与应用研究，在理论上将进一步丰富和完善排序问题的研究内容，在实际中为MapReduce框架提供理论基础和技术支持。

MapReduce is a programming model for processing and generating large data sets. This project systematically studies MapReduce scheduling models and its optimization algorithms according to the characteristic of the job scheduling in MapReduce framework. The problems under consideration in this project are as follows: Non-preemptive and preemptive variants of MapReduce scheduling on parallel machines, online and offline versions of flow shop and mixed shop problems in MapReduce framework, MapReduce scheduling with Shuffle operation including the MapReduce scheduling with transfer time and three-stage scheduling problem in MapReduce-like system. For the offline problem, we consider its computational complexity and present approximation algorithm with high performance or PTAS. For the online problem, we present its the lower bound and design online algorithm by using competitive analysis. In this project, the systematically and deeply theory research of MapReduce scheduling and the design of the algorithms for the problems under consideration, as well as the application study, will enrich and perfect the research content of scheduling theory and provide theoretical basis and technical support.