基于离散人工蜂群算法的云任务调度优化

doi:10.11772/j.issn.1001-9081.2016.01.0107

计算机应用 ›› 2016, Vol. 36 ›› Issue (1): 107-112.DOI: 10.11772/j.issn.1001-9081.2016.01.0107

基于离散人工蜂群算法的云任务调度优化

倪志伟^1,2, 李蓉蓉^1,2, 方清华^1,2, 庞闪闪^1,2

1. 合肥工业大学管理学院, 合肥 230009;
2. 过程优化与智能决策教育部重点实验室(合肥工业大学), 合肥 230009

收稿日期:2015-07-06 修回日期:2015-09-08 出版日期:2016-01-10 发布日期:2016-01-09
通讯作者: 李蓉蓉(1990-),女,福建泉州人,硕士研究生,主要研究方向:群智能算法、云计算
作者简介:倪志伟(1963-),男,安徽合肥人,教授,博士生导师,博士,主要研究方向:人工智能、机器学习、云计算;方清华(1990-),女,广西南宁人,硕士研究生,主要研究方向:群智能算法、数据挖掘;庞闪闪(1989-),女,河南开封人,硕士研究生,主要研究方向:群智能算法、数据挖掘。
基金资助:
国家自然科学基金资助项目(71271071);国家自然科学基金重点资助项目(71490725);国家863计划项目(2011AA040501)。

Optimization of cloud task scheduling based on discrete artificial bee colony algorithm

NI Zhiwei^1,2, LI Rongrong^1,2, FANG Qinghua^1,2, PANG Shanshan^1,2

1. School of Management, Hefei University of Technology, Hefei Anhui 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education (Hefei University of Technology), Hefei Anhui 230009, China

Received:2015-07-06 Revised:2015-09-08 Online:2016-01-10 Published:2016-01-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (71271071), the Key Project of National Natural Science Foundation of China (71490725) and the National High Technology Research and Development Program (863 Program) of China (2011AA040501).

摘要/Abstract

摘要： 针对现今云计算任务调度只考虑单目标和云计算应用对虚拟资源的服务的质量要求高等问题,综合考虑了用户最短等待时间、资源负载均衡和经济原则,提出一种离散人工蜂群(ABC)算法的云任务调度优化策略。首先,从理论上建立了云任务调度的多目标数学模型;然后,结合偏好满意度策略并引入局部搜索算子和改变侦察蜂搜索方式,提出多目标离散型人工蜂群(MDABC)算法的优化策略。通过不同的云任务调度仿真实验,显示了改进离散人工蜂群算法相对于基础离散人工蜂群算法、遗传算法以及经典贪心算法,能够得到较高的综合满意度,表明了改进离散人工蜂群算法能够更好地改善虚拟资源中云任务调度系统的性能,具有一定的普适性。

关键词: 云任务调度, 离散型人工蜂群算法, 云计算, 优化策略, 偏好满意度策略

Abstract: To meet high quality requirement of virtual resource service in cloud computing applications and solve the problem that cloud computing task scheduling only consider single objective currently, a Discrete Artificial Bee Colony (DABC) algorithm for cloud task scheduling optimization was proposed by considering the users' shortest waiting time, resource load balancing and economic principle. First, the multi-objective mathematical model of cloud task scheduling was established in theory. Second, by combining with preference satisfaction policy, introducing the local search operator and changing the searching way of scout bee, an optimizing strategy based on the Multi-objective DABC (MDABC) algorithm was proposed to solve the problem. Different cloud task scheduling simulation experimental results show that the proposed MDABC algorithm can obtain higher comprehensive satisfaction than the basic DABC algorithm, Genetic Algorithm (GA) and classical greedy algorithm. Thus, the proposed MDABC algorithm can better improve the performance of cloud task scheduling in virtual resource system, and its universality is better.

Key words: cloud task scheduling, Discrete Artificial Bee Colony (DABC) algorithm, cloud computing, optimization strategy, preference satisfaction policy

中图分类号:

TP393
TP18

倪志伟, 李蓉蓉, 方清华, 庞闪闪. 基于离散人工蜂群算法的云任务调度优化[J]. 计算机应用, 2016, 36(1): 107-112.

NI Zhiwei, LI Rongrong, FANG Qinghua, PANG Shanshan. Optimization of cloud task scheduling based on discrete artificial bee colony algorithm[J]. Journal of Computer Applications, 2016, 36(1): 107-112.

参考文献

[1] ARMBRUST M, FOX A, GRIFFITH R, et al. Above the clouds: a Berkeley view of cloud computing [EB/OL]. [2015-02-10]. http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.
[2] FOSTER I, KESSELMAN C, TUECKE S. The anatomy of grid:enabling scalable virtual organizations [J]. Internation journal of high performance compution application, 2001, 15(3): 1-4.
[3] 邓见光.云计算任务调度策略研究[D].广州:华南理工大学,2014:3-4.(DENG J G. Research on task scheduling strategy of cloud computing [D]. Guangzhou: South China University of Technology, 2014: 3-4.)
[4] ERGU D, KOU G, PENG Y, et al. The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment [J]. The journal of supercomputing, 2011, 64(3): 835-848.
[5] XU M, CUI L, WANG H, et al. A multiple QoS constrained scheduling strategy of multiple workflows for cloud computing [C]// Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications. Piscataway, NJ: IEEE, 2009: 629-634.
[6] JIN J, LUO J, SONG A, et al. BAR: an efficient data locality driven task scheduling algorithm for cloud computing [C]// Proceedings of the 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2011: 295-304.
[7] LI K, XU G, ZHAO G, et al. Cloud task scheduling based on load balancing ant colony optimization [C]// Proceedings of the 2011 Sixth Annual ChinaGrid Conference. Piscataway, NJ: IEEE, 2011: 3-9.
[8] 罗贺,汪永康,胡笑旋,等.基于负载均衡的云服务资源配置策略研究[J].中国管理科学,2013,21(11):121-126.(LUO H, WANG Y K, HU X X, et al. Cloud service resource disposition strategy based on load balancing [J]. Chinese journal of management science, 2013, 21(11): 121-126.)
[9] KARABOGA D. An idea based on honey bee swarm for numerical optimization [R]. Kayseri, Turkey: Erciyes University, 2005: 5.
[10] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm [J]. Journal of global optimization, 2007, 39(3): 459-471.
[11] 葛宇,梁静,王学平,等.求解函数优化问题的改进的人工蜂群算法[J].计算机科学,2013,40(8):252-257.(GE Y, LIANG J, WANG X P, et al. Improved artificial bee colony algorithms for function optimization [J] Computer science, 2013, 40(8): 252-257.)
[12] KARABOGA D, AKAY B, OZTURK C. Artificial Bee Colony (ABC) optimization algorithm for training feed forward neural networks [C]// Proceedings of the 4th International Conference on Modeling Decisions for Artificial Intelligence, LNCS 4617. Berlin: Springer, 2007: 318-328.
[13] KARABOGA D, OZTURK C. Fuzzy clustering with artificial bee colony algorithm [J]. Scientific research and essays, 2010, 5(14): 1899-1902.
[14] HAN Y Y, DUAN J H, ZHANG M. Apply the discrete artificial bee colony algorithm to the blocking flow shop problem with makespan criterion [C]// Proceedings of the 2011 Chinese Control and Decision Conference. Piscataway, NJ: IEEE, 2011: 2131-2135.
[15] TASGETIREN M F, PAN Q, SUGANTHAN P N, et al. A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion [J]. Applied mathematical modelling, 2013, 37(10/11): 6758-6779.
[16] PAN Q, TASGETIREN M, SUGANTHAN P, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem [J]. Journal of information science, 2011, 181(12): 2455-2468.
[17] TASGETIREN M, BULUT O, FADILOGLU M. A discrete artificial bee colony algorithm for the economic lot scheduling problem [C]// Proceedings of the 2011 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2011: 347-353.
[18] NCALHEIROS R, RANJAN R, ROSE A, et al. CloudSim: a novel framework for modeling and simulation of cloud computing infrastructures and services [EB/OL]. [2015-04-21]. http://www.chinacloud.cn/upload/2009-04/temp_09042121312333.pdf.
[19] 匡桂娟,曾国荪,曹洁,等.基于图配理论的云任务与云资源满意"婚配"方法[J].电子学报,2014,42(8):1582-1586.(KUANG G J, ZENG G S, CAO J, et al. Satisfactory marriage method between cloud tasks and resources based on graph theory [J]. Acta electronica sinica, 2014, 42(8): 1582-1586.)
[20] 孙大为,常桂然,李风云,等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报,2011,39(8):1824-1830.(SUN D W, CHUANG G R, LI F Y, et al. Optimizing multi-dimensional QoS cloud resource scheduling by immune clonal with preference [J]. Acta electronica sinica, 2014, 39(8): 1824-1830.)
[21] 熊聪聪,冯龙,陈丽仙,等.云计算中基于遗传算法的任务调度算法研究[J].华中科技大学学报(自然科学版),2012,40(S1):1-4.(XIONG C C, FENG L,CHEN L X, et al. Study on scheduling algorithm based on genetic algorithm in cloud computing [J]. Journal of Huazhong university of science and technology (nature science), 2012, 40(S1): 1-4.)
[22] SINGH M, SURI P K. QPSMax-MinMin-Min: a QoS based predictive Max-Min, Min-Min switcher algorithm for job scheduling in a grid [J]. Information technology journal, 2008, 7(8): 1176-1181.
[23] 涂雪芹.基于蜂群算法的多目标加权优化负荷频率控制研究[J].计算机测量与控制,2015,32(2):648-651.(TU X Q. Research of multi-objective weighted sum optimization for load frequency control based on artificial bee colony algorithm [J]. Computer measurement and control, 2015, 32(2): 648-651.)

基于离散人工蜂群算法的云任务调度优化

Optimization of cloud task scheduling based on discrete artificial bee colony algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[2]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[3]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[4]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[5]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[6]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[7]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[8]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[9]	王庆永, 毛莺池, 王绎超, 王龙宝. 基于多微云协作的计算任务卸载[J]. 计算机应用, 2020, 40(2): 328-334.
[10]	刘福鑫, 李劲巍, 王熠弘, 李琳. 基于Kubernetes的云原生海量数据存储系统设计与实现[J]. 计算机应用, 2020, 40(2): 547-552.
[11]	杨哂哂, 吴慧珍, 庄黎丽, 吕宏武. 基于Markov过程的IaaS系统可用性建模与分析方法[J]. 计算机应用, 2020, 40(10): 3013-3018.
[12]	林立, 熊金波, 肖如良, 林铭炜, 陈秀华. Gaming@Edge:基于边缘节点的低延迟云游戏系统[J]. 计算机应用, 2019, 39(7): 2001-2007.
[13]	徐雅斌, 彭宏恩. 基于需求预测的PaaS平台资源分配方法[J]. 计算机应用, 2019, 39(6): 1583-1588.
[14]	李启锐, 彭志平, 崔得龙, 何杰光. 容器云环境虚拟资源配置策略的优化[J]. 计算机应用, 2019, 39(3): 784-789.
[15]	李磊, 薛洋, 吕念玲, 冯敏. 基于李雅普诺夫优化的容器云队列在线任务和资源调度设计[J]. 计算机应用, 2019, 39(2): 494-500.