《MapReduce框架中的排序模型與算法》是依託浙江工商大學，由蔣義偉擔任項目負責人的面上項目。
基本介紹
- 中文名：MapReduce框架中的排序模型與算法
- 項目類別：面上項目
- 項目負責人：蔣義偉
- 依託單位：浙江工商大學
項目摘要,結題摘要,
項目摘要
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框架提供理論基礎和技術支持。
