云计算环境下基于禁忌搜索的负载均衡任务调度优化算法  

Load Balancing Task Scheduling Algorithm Based on Tabu Search in Cloud Computing

作　　者：孙凌宇[1] 冷明[1,2] 朱平[1] 李金忠[1] 

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]加州大学洛杉矶分校电子工程系,美国加利福尼亚州90095

出　　处：《小型微型计算机系统》2015年第9期1948-1952,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61363014;61163062;61063007)资助;江西省科技厅支撑项目(20132BBE50048)资助;江西省自然科学基金项目(20132BAB201035)资助;江西省教育厅科学技术研究项目(GJJ13540;GJJ14561)资助

摘　　要：对云计算环境下的负载均衡任务调度问题进行了形式化描述.通过动态规划方法的形式化推导得到了最早完成时间的启发式优先分配策略,并给出了基于该策略的任务调度初始解求解步骤.进而引入了任务交换的收益值概念,提出了基于禁忌搜索的任务调度优化算法.该算法采用禁忌搜索和贪心原则选择任务交换,从而在优化任务调度初始解执行时间的同时改善负载均衡性能.最后,基于Cloud Sim云计算仿真实验平台下,进行了顺序调度算法、Min-Min算法、Max-Min算法和本文算法的对比实验,实验数据对比表明本文算法在减少任务执行时间的同时,优化了资源负载均衡性能.The formal description of load balancing task scheduling problem in cloud computing is presented. We make its formal derivation based on dynamic programming method and built the heuristic strategy of the earliest finish time（ EFT） for task scheduling.The detailed steps finding the initial solution of task scheduling by the strategy are given. Furthermore,w e propose the gain of task sw ap and the load balancing task scheduling algorithm based on tabu search in cloud computing. The proposed algorithm has better improvement in terms of task completing time and load balance of the initial solution,w hich adopts the tabu search and the greedy strategy to sw ap tasks. Finally,w e carry out the comparative experiments among the sequential scheduling algorithm,M in-M in algorithm,M ax-M in algorithm and the proposed algorithm based on Cloud Sim simulation platform of cloud computing. The experiment and analysis show the proposed algorithm has better performance in terms of the decreasing the task completing time and the improvement of resource load balancing.

关 键 词：云计算 任务调度 禁忌搜索 负载均衡 优化算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]