云计算环境下任务调度优化算法的研究

发布时间：2018-07-04 19:22

本文选题：云计算 + 任务调度　；参考：《中国科学技术大学》2017年硕士论文

【摘要】：当今时代对海量数据处理能力的迫切需求和网络技术的迅猛发展直接促使了云计算的产生。云计算通过互联网将计算能力等服务以商品的形式提供给用户,使得用户可按需获取计算资源然后依照相应的计价模式按用付费。云计算环境下的任务调度关乎云数据中心的运行效率并且直接影响到用户的服务体验。为促进云计算的可持续发展、提升用户的服务体验,制定真正满足用户需求的高效合理的任务调度策略是十分必要的。为改善调度系统的调度性能,本文分别研究了云计算环境下独立及关联任务调度中的常用算法。并针对最受用户关心的调度时间和调度费用问题,在常用任务调度算法的基础上提出了相应的改进算法。首先,分别对云计算中常用的独立任务调度和关联任务调度算法进行了研究和对比,并详细分析了其各自的应用特性和优缺点。其次,针对云环境中的独立任务调度,综合对任务集合调度时间、调度成本和系统资源利用率的考虑,提出了一种基于多种群遗传算法的独立任务调度策略。其以多种群遗传算法代替传统遗传算法,避免早熟收敛,并以min-min及max-min算法初始化种群,以提高最优解的搜索效率。对于经遗传操作产生的子代,使用Metropolis准则对其进行筛选,使算法能以一定的概率接受差解,避免陷入局部最优。与其他算法的对比实验结果表明,该算法可有效减少任务集合调度时间和调度成本,且能兼顾到系统的负载均衡,是云环境下一种行之有效的任务调度方法,且比其他算法更适应于对大数量任务集合的处理。最后,针对待调度任务之间存在优先级约束的情况,本文从提高任务调度的性价比出发,提出了一种基于成本效益的改进关联任务调度算法,并将对关联任务的调度转换为了对大规模图状数据的处理。为了探索更多可能被确定式算法忽略的高质量解集,该算法采用多种群遗传算法扩大最优解的搜索范围,并以任务集合的调度时间和调度成本设计适应度函数。此外,为避免因盲目复制冗余任务导致费用的过度增长,本文对传统任务复制技术进行了改进。对比实验结果表明,通过两方面的改进,该算法相较于确定式调度算法可以有效降低任务集合的调度成本,同时保证合理的调度长度。
[Abstract]:Nowadays, the urgent demand for mass data processing ability and the rapid development of network technology directly promote the generation of cloud computing. Cloud computing provides services such as computing power to users in the form of goods through the Internet, which enables users to obtain computing resources on demand and then pay according to the corresponding pricing model. Task scheduling in cloud computing environment relates to the efficiency of cloud data center and directly affects the service experience of users. In order to promote the sustainable development of cloud computing, enhance the service experience of users, and formulate an efficient and reasonable task scheduling strategy to meet the needs of users, it is very necessary. In order to improve the scheduling performance of the scheduling system, the common algorithms of independent and associated task scheduling in cloud computing environment are studied in this paper. Aiming at the problem of scheduling time and scheduling cost which are most concerned by users, this paper proposes an improved algorithm based on the commonly used task scheduling algorithms. First of all, the common algorithms of independent task scheduling and associated task scheduling in cloud computing are studied and compared, and their application characteristics, advantages and disadvantages are analyzed in detail. Secondly, an independent task scheduling strategy based on multi-population genetic algorithm is proposed for independent task scheduling in cloud environment, considering the scheduling time, scheduling cost and system resource utilization. Multi-population genetic algorithm is used to replace traditional genetic algorithm to avoid premature convergence and min-min and max-min algorithms are used to initialize the population so as to improve the search efficiency of the optimal solution. For the offspring generated by genetic operation, Metropolis criterion is used to screen them, so that the algorithm can accept the differential solution with a certain probability and avoid falling into local optimum. Compared with other algorithms, the experimental results show that the algorithm can effectively reduce the task set scheduling time and scheduling cost, and can take into account the load balance of the system. It is an effective task scheduling method in the cloud environment. And it is more suitable to deal with large number of task sets than other algorithms. Finally, in view of the priority constraints between tasks to be scheduled, this paper proposes an improved algorithm for scheduling associated tasks based on cost-benefit, which is based on improving the performance and price ratio of task scheduling. The scheduling of associated tasks is converted to the processing of large scale graph data. In order to explore more high quality solution sets which may be neglected by deterministic algorithms, this algorithm uses multi-population genetic algorithm to expand the search range of optimal solutions, and designs fitness functions based on scheduling time and scheduling cost of task sets. In addition, in order to avoid excessive increase of cost caused by blind duplication of redundant tasks, the traditional task replication technology is improved in this paper. The experimental results show that compared with the deterministic scheduling algorithm, the proposed algorithm can effectively reduce the scheduling cost of the task set and ensure a reasonable scheduling length.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6

【参考文献】