云环境下基于模板遗传算法的任务调度方法

doi:10.11772/j.issn.1001-9081.2016.03.633

计算机应用 ›› 2016, Vol. 36 ›› Issue (3): 633-636.DOI: 10.11772/j.issn.1001-9081.2016.03.633

云环境下基于模板遗传算法的任务调度方法

盛小东, 李强, 刘昭昭

四川大学计算机学院, 成都 610065

收稿日期:2015-07-24 修回日期:2015-10-15 出版日期:2016-03-10 发布日期:2016-03-17
通讯作者: 李强
作者简介:盛小东(1991-),男,安徽巢湖人,硕士研究生,CCF会员,主要研究方向:移动计算、云计算;李强(1963-),男,四川成都人,副教授,博士,主要研究方向:分布式计算、云计算、移动计算、移动互联网、大数据;刘昭昭(1991-),女,湖北恩施人,硕士,主要研究方向:云计算、移动云计算。
基金资助:
四川省科技厅应用基础研究项目(2014JY0095)。

Task scheduling method based on template genetic algorithm in cloud environment

SHENG Xiaodong, LI Qiang, LIU Zhaozhao

College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China

Received:2015-07-24 Revised:2015-10-15 Online:2016-03-10 Published:2016-03-17
Supported by:
This work is partially supported by the Applied Basic Research Programs of Science and Technology Department of Sichuan Province (2014JY0095).

摘要/Abstract

摘要： 云任务调度是云计算研究的一个热点。云任务调度方法的好坏直接影响云平台的整体性能。提出一种基于模板遗传算法(TBGA)的任务调度方法。首先,根据处理机的运算速度和带宽等条件,计算出每个处理机应分配的任务量模板大小;然后,根据模板大小将任务集合中的任务划分为多个子集合;最后,利用遗传算法将集合中的任务分配到对应的处理机。实验证明通过此方法能得到总任务完成时间较短的调度结果。通过仿真实验将TBGA算法与Min-Min算法和遗传算法(GA)进行比较,实验结果表明,TBGA算法与Min-Min算法相比任务集合完成时间降低了20%左右,与遗传算法相比任务集合完成时间降低了30%左右,是一种有效的任务调度算法。

关键词: 云计算, 模板, 组合优化, 遗传算法, 任务调度

Abstract: Cloud task scheduling is a hot issue in the research of cloud computing. The cloud task scheduling method directly affects the overall performance of the cloud platform. A task scheduling method Template-Based Genetic Algorithm (TBGA) was proposed. Firstly, according to the processor's CPU speed, bandwidth and etc., the amount of tasks that should be allocated to each processor was calculated. andwas called allocation template. Secondly, according to the template, the tasks were combined into multiple subsets and finally each subset of tasks was allocated to the corresponding processor by using genetic algorithm. Experimental results show that the method can obtain shorter time scheduling for total tasks. TBGA reduced 20% of task set completion time compared with Min-Min algorithm and 30% of task set completion time compared with Genetic Algorithm (GA). Therefore, the TBGA is an effective task scheduling algorithm.

Key words: cloud computing, template, combinatorial optimization, Genetic Algorithm (GA), task scheduling

中图分类号:

TP393

盛小东, 李强, 刘昭昭. 云环境下基于模板遗传算法的任务调度方法[J]. 计算机应用, 2016, 36(3): 633-636.

SHENG Xiaodong, LI Qiang, LIU Zhaozhao. Task scheduling method based on template genetic algorithm in cloud environment[J]. Journal of Computer Applications, 2016, 36(3): 633-636.

参考文献

[1] GEELAN J. Twenty-one experts define cloud computing [EB/OL]. [2015-03-08]. http://www.ulitzer.com/?q=node/612375.
[2] MELL P M, GRANCE T. The NIST definition of cloud computing [J]. Communications of the ACM, 2011,53(6):50.
[3] 熊聪聪,冯龙,陈丽仙,等.云计算中基于遗传算法的任务调度算法研究[J].华中科技大学学报(自然科学版),2012,40(S1):1-4. (XIONG C C, FENG L, CHEN L X, et al. Study on task scheduling algorithm based on genetic algorithm in cloud computing [J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2012,40(S1):1-4.)
[4] ZHANG S, CHEN X, ZHANG S, et al. The comparison between cloud computing and grid computing [C]//Proceedings of the 2010 International Conference on Computer Application and System Modeling. Piscataway, NJ: IEEE, 2010,11:72-75.
[5] SADASHIV N, KUMAR S M D. Cluster, grid and cloud computing: a detailed comparison [C]//Proceedings of the 2011 6th International Conference on Computer Science and Education. Piscataway, NJ: IEEE, 2011:477-482.
[6] VERMA A, KUMAR P. Independent task scheduling in cloud computing by improved genetic algorithm [J]. International Journal of Advanced Research in Computer Science and Software Engineering, 2012,2(5):111-114.
[7] 叶菁,陈国龙,俞建家.基于改进型免疫遗传算法对网格中独立任务调度问题的研究[J].福州大学学报(自然科学版), 2010,38(6):830-835. (YE J, CHEN G L, YU J J. Independent task scheduling based on improved immune genetic algorithm in grid [J]. Journal of Fuzhou University (Natural Science Edition), 2010, 38(6):830-835.)
[8] 马立肖,王江晴.遗传算法在组合优化问题中的应用[J].计算机工程与科学,2005,27(7):72-73. (MA L X, WANG J Q. Application of genetic algorithms in solving the optimal combination problem [J]. Computer Engineering and Science, 2005, 27(7): 72-73.)
[9] CHENG Y C, ROBERTAZZI T G. Distributed computation with communication delay (distributed intelligent sensor networks) [J]. IEEE Transactions on Aerospace and Electronic Systems, 1988,24(6):700-712.
[10] Divisible (partitonable) loading scheduling research [EB/OL]. [2015-10-12]. http://www.ee.sunysb.edu/~tom/dlt.html.
[11] ILIC A, SOUSA L. On realistic divisible load scheduling in highly heterogeneous distributed systems [C]//Proceedings of the 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Washington, DC: IEEE Computer Society, 2012:426-433.
[12] 尚明生.网格计算中的任务调度算法研究[D].成都:电子科技大学,2007:42.(SHANG M S. Algorithm for task scheduling on grid computing [D]. Chengdu: University of Electronic Science and Technology of China, 2007:42.)
[13] 李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用, 2011,31(1):184-186.(LI J F, PENG J. Task scheduling algorithm based on improved genetic algorithm in cloud computing environment [J]. Journal of Computer Applications, 2011,31(1):184-186.)
[14] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software—Practice and Experience, 2011,41(1):23-50.
[15] GU J, HU J, ZHAO T, et al. A new resource scheduling strategy based on genetic algorithm in cloud computing environment [J]. Journal of Computers, 2012,7(1):42-52.
[16] 邓见光.云计算任务调度策略研究[D].广州:华南理工大学,2014:18.(ZHENG J G. Research on task scheduling strategy of cloud computing [D]. Guangzhou: South China University of Technology, 2014:18.)
[17] LIU G, LI J, XU J. An improved min-min algorithm in cloud computing [C]//Proceedings of the 2012 International Conference of Modern Computer Science and Applications. Berlin: Springer, 2013:47-52.
[18] BRAUN T D, SIEGEL H J, BECK N, et al. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems [J]. Journal of Parallel and Distributed Computing, 2001,61(6):810-837.

云环境下基于模板遗传算法的任务调度方法

Task scheduling method based on template genetic algorithm in cloud environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[4]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[7]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[8]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[9]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[10]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[11]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[12]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[13]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[14]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[15]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.