改进蛙跳算法的网格任务调度优化模型
|
摘要
为解决当前调度模型存在的局限性,以更好完成网格环境下的任务调度目标,结合网格任务调度的NP(Non-deterministic Polynomial)问题特点,提出了改进蛙跳算法的网格任务调度优化模型。首先以网格任务完成时间作为调度优化指标,然后采用蛙跳算法找到最优的网格任务调度方案,并对蛙跳算法存在不足进行改进,以改善算法工作性能,最后在网格仿真平台Grid Sim上进行性能验证分析。实验结果表明,改进蛙跳算法可较好完成网格任务调度,缩短了任务完成的时间,资源负载更加均衡,而且性能明显要优于其他算法。
In order to complete task scheduling in grid environment better,and overcome the limitation of the needle current scheduling model,combined with the characteristics of grid task scheduling is a NP(Nondeterministic Polynomial) problem,this paper proposes a novel grid task scheduling optimization model based on modified SFLA(Shuffled Frog Leaping Algorithm). First of all,grid task completion time is taken as optimization indicators to establish mathematical model,and then leapfrog algorithm is used to find the best scheme for grid task scheduling,and leapfrog algorithm is modified to solve defect and improve the algorithm speed,the grid performance analysis were validated by Grid Sim. The results show that modified shuffled frog leaping algorithm can complete task scheduling,shorten the task completion time,balance the load of resources, and the performance was obviously superior to the other algorithm.
In order to complete task scheduling in grid environment better,and overcome the limitation of the needle current scheduling model,combined with the characteristics of grid task scheduling is a NP(Nondeterministic Polynomial) problem,this paper proposes a novel grid task scheduling optimization model based on modified SFLA(Shuffled Frog Leaping Algorithm). First of all,grid task completion time is taken as optimization indicators to establish mathematical model,and then leapfrog algorithm is used to find the best scheme for grid task scheduling,and leapfrog algorithm is modified to solve defect and improve the algorithm speed,the grid performance analysis were validated by Grid Sim. The results show that modified shuffled frog leaping algorithm can complete task scheduling,shorten the task completion time,balance the load of resources, and the performance was obviously superior to the other algorithm.
引文
[1]罗红,慕德俊,邓智群,等.网格计算中任务调度研究综述[J].计算机应用研究,2005,22(5):16-19.LUO Hong,MU Dejun,DENG Zhiqun,et al.A Review of Job Scheduling for Grid Computing[J].Application Research of Computers,2005,22(5):16-19.
[2]王浩,李飞.基于Qos约束的网格任务调度算法[J].四川理工学院学报:自然科学版,2013,26(1):25-28.WANG Hao,LI Fei.Grid Task Scheduling Algorithm Based on Qo S Dimensions[J].Journal of Sichuan University of Science&Engineering:Natural Science Edition,2013,26(1):25-28.
[3]王成昌,陈闳中,方钰,等.基于混合粒子群算法的网格任务调度[J].计算机科学,2012,39(2):18-21.WANG Chengchang,CHEN Hongzhong,FANG Yu,et al.Task Scheduling in Grid Environment Based on Hybrid PSO Algorithm[J].Computer Science,2012,39(2):18-21.
[4]孙瑞志,杨璐,欧阳娅.基于改进遗传算法的网格任务调度[J].解放军理工大学学报:自然科学版,2012,13(4):388-392.SUN Ruizhi,YANG Lu,OUYANG Ya.On Grid Task Scheduling Based on Modified Genetic Algorithm[J].Journal of PLA University of Science and Technology:Natural Science Edition,2012,13(4):388-392.
[5]张京军,刘文娟,刘光远.基于改进免疫遗传算法的网格任务调度[J].河北工程大学学报:自然科学版,2013,30(2):81-84.ZHANG Jingjun,LIU Wenjuan,LIU Guangyuan.Task Scheduling in Grid Computing Based on Improved Immune Genetic Algorithm[J].Journal of Hebei University of Engineering:Natural Science Edition,2013,30(2):81-84.
[6]杨明,薛胜军,陈亮,等.自适应邻域的多目标网格任务调度算法[J].计算机应用,2012,32(3):599-602.YANG Ming,XUE Shengjun,CHEN Liang,et al.Multi-Objective Evolutionary Algorithm for Grid Job Scheduling Based on Adaptive Neighborhood[J].Journal of Computer Applications,2012,32(3):599-602.
[7]肖海蓉,李惠先.基于自适应遗传算法的网格任务调度优化[J].吉林大学学报:理学版,2015,53(2):297-302.XIAO Hairong,LI Huixian.Grid Task Scheduling Optimization Based on Adaptive Genetic Algorithm[J].Journal of Jilin University:Science Edition,2015,53(2):297-302.
[8]朱海,王宇平.融合安全的网格依赖任务调度双目标优化模型及算法[J].软件学报,2011,22(11):2729-2748.ZHU Hai,WANG Yuping.Integration of Security Grid Dependent Tasks Scheduling Double-Objective Optimization Model and Algorithm[J].Journal of Software,2011,22(11):2729-2748.
[9]乔楠楠,尤佳莉.一种面向网络边缘任务调度问题的多方向粒子群优化算法[J].计算机应用与软件,2017,34(4):309-314.QIAO Nannan,YOU Jiali.A Multi-Directional Particle Swarm Optimization Algorithm for Network Edge Task Scheduling[J].Computer Applications and Software,2017,34(4):309-314.
[10]张忠平,冯玉鹏,张雪楠.基于标准差及二次分配的启发式网格资源调度算法[J].小型微型计算机系统,2016,37(2):259-263.ZHANG Zhongping,FENG Yupeng,ZHANG Xuenan.Heuristic Grid Resource Scheduling Algorithm Based on Standard Deviations and Secondary Distribution[J].Journal of Chinese Computer Systems,2016,37(2):259-263.
[11]蒲汛,彭喜化,于显平,等.基于均匀离散PSO算法的多Qo S网格任务调度策略[J].控制与决策,2013,8(6):808-814.PU Xun,PENG Xihua,YU Xianping,et al.Jobs Scheduling Policy for Gird with Multi-Qo S Constraints Using Uniform-Design Discrete Particle Swarm Optimization[J].Control and Decision,2013,8(6):808-814.
[12]LEI D,GUO X.A Shuffled Frog-Leaping Algorithm for Job Shop Scheduling with Outsourcing Options[J].International Journal of Production Research,2016,54(16):1-12.
[13]于晓鹏,曹春红.一种新的改进的混合蛙跳算法[J].吉林大学学报:信息科学版,2012,30(2):203-206.YU Xiaopeng,CAO Chunhong.Geometric Constraint Solving Based on Shuffled Frog Leaping Algorithm and Particle Swarm Optimization[J].Journal of Jilin University:Information Science Editions,2012,30(2):203-206.
[2]王浩,李飞.基于Qos约束的网格任务调度算法[J].四川理工学院学报:自然科学版,2013,26(1):25-28.WANG Hao,LI Fei.Grid Task Scheduling Algorithm Based on Qo S Dimensions[J].Journal of Sichuan University of Science&Engineering:Natural Science Edition,2013,26(1):25-28.
[3]王成昌,陈闳中,方钰,等.基于混合粒子群算法的网格任务调度[J].计算机科学,2012,39(2):18-21.WANG Chengchang,CHEN Hongzhong,FANG Yu,et al.Task Scheduling in Grid Environment Based on Hybrid PSO Algorithm[J].Computer Science,2012,39(2):18-21.
[4]孙瑞志,杨璐,欧阳娅.基于改进遗传算法的网格任务调度[J].解放军理工大学学报:自然科学版,2012,13(4):388-392.SUN Ruizhi,YANG Lu,OUYANG Ya.On Grid Task Scheduling Based on Modified Genetic Algorithm[J].Journal of PLA University of Science and Technology:Natural Science Edition,2012,13(4):388-392.
[5]张京军,刘文娟,刘光远.基于改进免疫遗传算法的网格任务调度[J].河北工程大学学报:自然科学版,2013,30(2):81-84.ZHANG Jingjun,LIU Wenjuan,LIU Guangyuan.Task Scheduling in Grid Computing Based on Improved Immune Genetic Algorithm[J].Journal of Hebei University of Engineering:Natural Science Edition,2013,30(2):81-84.
[6]杨明,薛胜军,陈亮,等.自适应邻域的多目标网格任务调度算法[J].计算机应用,2012,32(3):599-602.YANG Ming,XUE Shengjun,CHEN Liang,et al.Multi-Objective Evolutionary Algorithm for Grid Job Scheduling Based on Adaptive Neighborhood[J].Journal of Computer Applications,2012,32(3):599-602.
[7]肖海蓉,李惠先.基于自适应遗传算法的网格任务调度优化[J].吉林大学学报:理学版,2015,53(2):297-302.XIAO Hairong,LI Huixian.Grid Task Scheduling Optimization Based on Adaptive Genetic Algorithm[J].Journal of Jilin University:Science Edition,2015,53(2):297-302.
[8]朱海,王宇平.融合安全的网格依赖任务调度双目标优化模型及算法[J].软件学报,2011,22(11):2729-2748.ZHU Hai,WANG Yuping.Integration of Security Grid Dependent Tasks Scheduling Double-Objective Optimization Model and Algorithm[J].Journal of Software,2011,22(11):2729-2748.
[9]乔楠楠,尤佳莉.一种面向网络边缘任务调度问题的多方向粒子群优化算法[J].计算机应用与软件,2017,34(4):309-314.QIAO Nannan,YOU Jiali.A Multi-Directional Particle Swarm Optimization Algorithm for Network Edge Task Scheduling[J].Computer Applications and Software,2017,34(4):309-314.
[10]张忠平,冯玉鹏,张雪楠.基于标准差及二次分配的启发式网格资源调度算法[J].小型微型计算机系统,2016,37(2):259-263.ZHANG Zhongping,FENG Yupeng,ZHANG Xuenan.Heuristic Grid Resource Scheduling Algorithm Based on Standard Deviations and Secondary Distribution[J].Journal of Chinese Computer Systems,2016,37(2):259-263.
[11]蒲汛,彭喜化,于显平,等.基于均匀离散PSO算法的多Qo S网格任务调度策略[J].控制与决策,2013,8(6):808-814.PU Xun,PENG Xihua,YU Xianping,et al.Jobs Scheduling Policy for Gird with Multi-Qo S Constraints Using Uniform-Design Discrete Particle Swarm Optimization[J].Control and Decision,2013,8(6):808-814.
[12]LEI D,GUO X.A Shuffled Frog-Leaping Algorithm for Job Shop Scheduling with Outsourcing Options[J].International Journal of Production Research,2016,54(16):1-12.
[13]于晓鹏,曹春红.一种新的改进的混合蛙跳算法[J].吉林大学学报:信息科学版,2012,30(2):203-206.YU Xiaopeng,CAO Chunhong.Geometric Constraint Solving Based on Shuffled Frog Leaping Algorithm and Particle Swarm Optimization[J].Journal of Jilin University:Information Science Editions,2012,30(2):203-206.