云计算中最小化任务完工时间的多资源调度算法  

A MULTI-RESOURCE SCHEDULING ALGORITHM FOR MINIMIZING MAKESPAN IN CLOUD COMPUTING

作　　者：杨鹏[1] 靳丹[1] 张晟[2] 徐鑫[2] 姚建国[2] 

机构地区：[1]国网甘肃省电力公司信息通信公司,甘肃兰州730050 [2]上海交通大学,上海200240

出　　处：《计算机应用与软件》2017年第7期1-6,10,共7页Computer Applications and Software

基　　金：国家自然科学基金项目(61303013)

摘　　要：云计算中Hadoop平台上默认调度方式FIFO是以公平性为目标,然而考虑单一因素会使资源利用率低下以及任务完成时间过长。在公平性和完成时间的权衡中,运行时间指标更为重要。据此,建立云计算下多资源和应用程序任务以及调度的数学模型和其目标函数,运用归约方法和具有强大计算能力的工具MINI SAT SOLVER去求解问题。仿真实验结果表明,在不同的资源供给条件下,基于MINI SAT SOLVER的次优算法比YARN(Yet Another Resource Negotiator)中默认的调度算法FIFO缩短了任务的完工时间,优化比率最高可以达到30%。The default FIFO scheduling on the Hadoop platform in cloud computing is targeted at fairness, however, considering a single factor will make the resource utilization is low and the task is completed too long. The makespan is more important in trade-off between fairness and makespan. On this basis, we established the multi-resource and application tasks and the scheduling mathematical model and its objective function under cloud computing, and we used the reduction method and MINI SAT SOLVER with powerful computing ability to solve the problem. The simulation results show that the suboptimal algorithm based on MINI SAT SOLVER is shorter than the default scheduling algorithm FIFO in YARN under different resource supply conditions, and the optimization ratio can reach 30%.

关 键 词：云计算 调度算法 NP 完全问题 完工时间 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]