最小化总惩罚代价的批量MapReduce作业调度

摘要

MapReduce框架由于其大数据处理的优势逐渐流行起来，并与其它行业逐渐产生关联，近年来也受到很多研究者的关注。批量带有服务质量要求的离线作业被提交给云服务商，可以通过离线分析技术对某种目标最优的调度来进行优化，帮助管理者对当前的服务请求进行分析决策。
　　本文把离线MapReduce作业调度问题建模成一个泛化的两阶段混合流水调度问题，在此基础上建立整数规划模型。模型中把任务的数据准备时间考虑成待处理数据的传输时间，并考虑数据本地化减少传输成本。问题的优化目标是最小化一批离线作业的总拖期惩罚代价。本文提出了基于作业序列的初始解生成算法和迭代贪心算法来解决该问题并优化解的质量。一般情况下迭代贪心算法在MapReduce环境下的适用场景较少，但在本文的问题环境中，即集群资源固定，优化目标为最小化总惩罚代价的情况下迭代贪心算法有较好的效果。
　　在实验部分采用方差分析技术进行分析，首先对算法中的相关参数进行测定，并分析上述参数对算法解的质量的影响。然后把本实验算法与其它相似算法在相同实例上以最小化总惩罚代价为目标进行结果比较，对算法的有效性进行验证。实验结果表明，本文提出的算法对解决最小化总惩罚代价具有较好的效果。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．1．1 应用场景

1．1．2 MapReduce工作流程

1．1．3 多阶段混合流水作业调度

1．2 研究现状

1．3 论文组织结构

第2章 问题描述与模型

2．1 问题假设

2．2 批量离线MapReduce作业调度问题描述

2．3 数学模型

2．4 本章小结

第3章 算法描述

3．1 算法框架

3．2 初始解生成算法

3．3 惩罚代价计算方法

3．4 本章小结

第4章 实验分析

4．1 实验环境

4．2 参数测定

4．3 实验评价和分析

4．4 本章小结

第5章 结论与展望

致谢

参考文献