基于多目标优化的云任务调度算法研究

发布时间：2018-10-30 07:45

【摘要】：云计算作为当前研究应用最广泛的商业化分布式计算技术,具有庞大的服务器规模和用户群体,系统需要频繁地对云环境下的各种任务进行调度以及管理。针对云环境下执行时间和执行费用的调度是一个NP-hard的多目标组合优化问题,而目前的云任务调度一般采用的是带有约束的执行费用或者执行时间的单目标优化的启发式调度方法,不能完全满足带有负载均衡的复杂云系统下的多用户执行时间和执行费用的多样化需求。因此,在多目标优化的基础上,对云环境下的任务调度算法进行研究,有着极其重要的意义。本文通过分析云任务的特点,改进了云任务模型,并选取执行时间、执行费用以及负载均衡为优化目标,对云任务的调度过程进行了优化,基于此多目标优化,在云环境下建立了云任务调度模型,主要的研究工作如下:1)针对云环境下任务需求多样化的特点,分析了云计算的概念、体系结构以及技术特点,改进了云任务模型,引入了多目标优化的概念。2)针对混合云任务的调度要求,选取云用户所关注的执行时间和执行费用以及云服务提供商所关注的负载均衡这三个目标,作为云环境下任务调度的优化目标,建立了能够处理此混合云任务的多目标优化的云任务调度模型。3)针对云环境的动态变化以及云任务调度的特点,对蚁群遗传算法进行了改进,在此基础上提出了基于自适应遗传蚁群算法的多目标云任务调度算法,该算法既发挥了遗传算法较好的全局搜索能力,又综合了蚁群算法较高的求解精度,避免了遗传算法后期局部求解能力的不足和蚁群优化算法初始信息素的缺乏而导致搜索效率低下的缺陷,通过Cloud Sim仿真平台验证了,该算法在云用户所关注的执行时间和执行费用这两个目标问题以及云服务提供商所关注的负载均衡方面均具有明显的优势。4)针对遗传算法和大规模云任务调度的问题,改进了文化基因算法,引入爬山和禁忌搜索这两种局部启发式算法,充分地利用遗传算法较好的全局寻优能力以及爬山算法和禁忌搜索算法较强的局部寻优能力的优势,避免了遗传算法后期局部求解能力的不足以及爬山算法和禁忌搜索算法较弱的全局寻优能力的缺点,最后在CloudSim仿真平台上验证了本文提出的基于禁忌搜索算法的文化基因算法,在大规模云任务调度环境中,表现出更高的执行效率和更好的负载均衡。
[Abstract]:Cloud computing, as the most widely used commercial distributed computing technology, has a large scale of servers and users, so the system needs to schedule and manage various tasks in the cloud environment frequently. The scheduling of execution time and execution cost in cloud environment is a multi-objective combinatorial optimization problem of NP-hard. However, the current cloud task scheduling generally adopts a heuristic method of single objective optimization with constrained execution cost or execution time. The multiuser execution time and execution cost of complex cloud systems with load balancing can not be fully satisfied. Therefore, on the basis of multi-objective optimization, it is of great significance to study the task scheduling algorithm in cloud environment. By analyzing the characteristics of cloud tasks, this paper improves the cloud task model, and selects execution time, execution cost and load balance as the optimization objectives, and optimizes the scheduling process of cloud tasks, based on this multi-objective optimization. A cloud task scheduling model is established in the cloud environment. The main research work is as follows: 1) aiming at the diversity of task requirements in the cloud environment, the concept, architecture and technical characteristics of cloud computing are analyzed, and the cloud task model is improved. This paper introduces the concept of multi-objective optimization. 2) aiming at the scheduling requirements of mixed cloud tasks, the paper selects the three objectives of cloud users' concern about the execution time and cost, and the load balancing that cloud service providers are concerned about. As the optimization objective of task scheduling in cloud environment, a multi-objective optimization model is established to deal with this mixed cloud task. 3) considering the dynamic change of cloud environment and the characteristics of cloud task scheduling, Ant colony genetic algorithm (AGA) is improved, and a multi-objective cloud task scheduling algorithm based on adaptive genetic ant colony algorithm (AGA) is proposed. The high precision of ant colony algorithm is integrated to avoid the deficiency of local solving ability of genetic algorithm and the lack of initial pheromone of ant colony optimization algorithm, which is proved by Cloud Sim simulation platform. The algorithm has obvious advantages in the two target problems of execution time and execution cost that cloud users are concerned about, and the load balancing concerned by cloud service providers. 4) aiming at the problem of genetic algorithm and large-scale cloud task scheduling, the algorithm has obvious advantages. Two local heuristic algorithms, mountain climbing and Tabu search, are introduced to make full use of the advantages of genetic algorithm (GA) for global optimization and for mountain climbing and Tabu search. The deficiency of the local solution ability of the genetic algorithm and the weak global optimization ability of the mountain climbing algorithm and the Tabu search algorithm are avoided. Finally, the cultural gene algorithm based on the Tabu search algorithm proposed in this paper is verified on the CloudSim simulation platform. In large scale cloud task scheduling environment, it shows higher execution efficiency and better load balance.
【学位授予单位】：兰州理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TP301.6

【参考文献】