大数据驱动的云计算批处理排序问题研究

Scientific cloud computing will reduce computational cost, enhance data accuracy, improve service efficiency and service quality. This issue has become one of the hot topic of business computing model and has been received wildly attention by researchers of global industry, business and academic. Using the theory and methods of combinatorial optimization, we will study some schedule problems of the cloud computing. The four topics of this project are as follows: Btch schedule problem of mapreduce, flow-shop schedule problem, and power save and game schedule problems of cloud computing with considering on energy, cost, quality of service etc. The main contribution of this project is to study and formulate several combinatorial optimization models under different cloud computing environment, and solve the above models by designing some efficient algorithms. The results obtained in this project can provide theoretical guidance and decision support for decision makers. Our research will further enrich combinatorial optimization theory and cloud computing theory.

科学的云计算方法，能降低计算成本，提升数据精准性，进而提高服务效率和服务质量，已成为近期商业计算模式关注的焦点，受到全球业界、商界、学界的高度重视。本项目拟应用组合优化理论与方法开展云计算研究，主要研究内容如下：(1) Mapreduce流程中的批排序问题，(2) 基于能源（energy）、成本（cost）、时间（time）、利益（profit）、服务质量（quality of service）、优先权（priority）等因素的流水调度问题，(3) 云计算中的节能优化问题，(4) 云计算中的博弈调度问题。本课题的创新之处在于研究并建立不同云计算环境下的组合优化模型，通过有效算法的设计与分析求解上述模型。研究结论能够为决策者提供理论指导和决策支持，进一步丰富组合优化理论和云计算理论。

本项目主要对于以下方面内容开展研究：.1、云计算中的博弈排序.2、云计算中的重要计算框架-映射归约（Mapreduce）中的重要排序.3、大数据下的在线排序模型.4、云计算的节能优化模型.5、云计算中的可拒绝排序..成果如下：.1、我们还研究了机器具有协调机制（机器按照某种规则加工工件，例如机器按照Shortest Processing Time First（SPT）加工工件）的博弈排序问题。工件效用是工件完工时间（机器负载）的相反数，评价标准是总完工时间。.代表性成果发表在Journal of Combinatorial Optimization 等刊物上。.2、针对本项目研究内容中的（2）云计算的计算框架-映射归约（Mapreduce）流程中的批排序问题，对极小化最大完工时间，研究了两工序MapReduce排序问题，在这里map任务可以并行加工，而reduce任务不能并行加工.对每个工件的reduce任务又分成两道工序，极小化最大完工时间问题达到最优；当工序大于两道时，得出了问题的上界为2-1/m，并且这个界是紧的。.3、在云计算中，客户的服务需求往往是随机的，预先不知道所需的时间多少、是否可以中断等特性，只有客户到达时才知道，这是在线问题。对于多个服务资源多客户，优化客户的等待时间总和（极小化能源消耗）的调度问题（相当于问题模型3）。并且对于二次服务选题的限额与交易（Cap-and-trade ）策略进行优化（模型4），成果发表在 Annals of Operations Research 和 Applied Mathmatics and Computation 等学术刊物上。.4、针对本项目研究内容中的（5）云计算中对于客户的要求可以转包服务，也叫“外包”，排序理论中称为可拒绝的排序问题，成果发表在European Journal of Operational Research 等运筹学知名期刊上。项目负责人张玉忠教授参考了100篇国内外参考资料，形成了2万余字的关于可拒绝排序的综述报告发表在《运筹学学报》上。