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.

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

MapReduce是处理和生成大数据集的一种编程模型。本项目针对MapReduce框架中作业调度的特点，系统研究MapReduce排序问题的模型与优化算法，具有一定的理论意义和应用价值。具体研究内容和成果如下：(a)关于平行机调度问题，给出了m台同类机情形的不可中断与可中断近似算法；分别给出了两台同型机与两台同类机的最优可中断在线算法；给出了MapReduce机器覆盖问题的两(三)台同型机最优可中断算法和不可中断近似算法。 (b) 关于MapReduce流水作业问题，给出了两阶段流水作业问题的近似算法以及一个参数界近似算法，并给出了数据实验；给出了一类混合车间调度问题的最优解算法。(c) 关于三阶段的类MapReduce调度问题，主要研究了带有两个服务装置的装、卸载调度问题，给出了装载和卸载均为单位时间情形的经典LS算法和LPT算法的最坏情况界。(d) 关于极小化总完工时间的带等级服务的在线调度问题，给出了m台机情形的下界，并分别给出了两台同型机和两台同类机情形的最优在线算法。上述问题的解决，理论上进一步丰富和完善了调度问题的研究内容，同时也在实际中为MapReduce框架提供理论基础和技术支持。