基于改进禁忌搜索的云任务负载均衡调度策略研究

Research on the Load Balancing Scheduling Policy of Tasks in Cloud Computing Environments Based on Improved Tabu Search

云计算是一种管理和提供服务的互联网新平台,而云计算环境下的任务调度是一个NP-hard问题,任务的合理分配、虚拟机资源的负载均衡是云任务调度的重要方面.在本文中,提出了一种基于改进禁忌搜索的云任务负载均衡调度策略.该策略综合考虑任务总完成时间及虚拟机负载均衡度,提出基于时间贪心的初始解求解步骤,进而引入结合多因素优值函数的禁忌搜索算法优化任务调度的负载均衡,再进一步给出跳出局部最优的惩戒策略.为了验证提出的算法的有效性,使用CloudSim作为仿真平台,与RR算法、Min-Max算法、ACO算法等进行对比,以有限元分析计算过程中的任务调度为背景进行模拟实验,结果表明,此算法不仅缩短了任务总体完成时间,同时优化了虚拟资源负载均衡度.

Cloud computing is a new platform to manage and provide services on the intemet. Cloud task scheduling is an NP-hard optimization problem, and many algorithms have been proposed to solve it. Reasonable allocation of tasks and load balancing of virtual machines are important aspects of cloud task scheduling. In this paper, we propose a cloud task scheduling policy based on improved Tabu Search algorithm which focuses on the makespan of all tasks and load balancing of virtual machines. This scheduling policy uses time greedy algorithm as the initial solution step and combines an improved Tabu Search with multi-factor benefit function to optimize load balancing of tasks. Futhermore, by using punishment strategy, the proposed algorithm could escape from the local optimal. To verify the effectiveness of our approach, we choose Finite Element Analysis as background and carry out the comparative experiments among RR algorithm, Min-Max algorithm, ACO algorithm, Tabu algorithm and the proposed algorithm based on CloudSim simulation platform of cloud computing. The experimental results show that the proposed algorithm has a significant improvement in makespan of the tasks and optimization in load balancing of virtual machines.