计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 90-94.doi: 10.11896/j.issn.1002-137X.2018.07.014
钟志峰,张田田,张,易明星,曾张帆
ZHONG Zhi-feng, ZHANG Tian-tian,ZHANG Yan, YI Ming-xing ,ZENG Zhang-fan
摘要: 高效的任务调度是云服务提供商高效处理业务并降低运营成本的关键。针对云环境下的任务调度问题,提出一种贪心模拟退火的新型算法。首先,利用贪心算法求出局部最优解,并用它来初始化所提新型算法的当前最优解及模拟退火算法的初始解;然后,采用模拟退火算法来不断更新当前最优解。实验结果表明,与传统调度算法相比,所提算法能够更快地达到全局收敛,并得到更加稳定的寻优结果,提高了寻优的质量和效率;同时,该算法不仅减少了总任务时间开销,而且使虚拟机的平均资源利用率稳定在99%以上,负载也更加均衡。
中图分类号:
[1]YOUNGE A J,HENSCHEL R,BROWN J T,et al.Analysis of Virtualization Technologies for High Performance Computing Environments[C]∥IEEE International Conference on Cloud Computing.IEEE Computer Society,2011:9-16. [2]ERGU D,KOU G,PENG Y,et al.The Analytic HierarchyProcess:Task Scheduling and Resource Allocation in Cloud Computing Environment[J].The Journal of Supercomputing,2013,64(3):1-14. [3]BOURGUIBA M,El KORBI I,HADDADOU K,et al.Impro-ving Virtual Machines Networking Performance for Cloud Computing[C]∥IEEE International Symposium on Integrated Network Management.IEEE,2013:513-519. [4]CHEN H Y.Task Scheduling in Cloud Computing Based onSwarm Intelligence Algorithm[J].Computer Science,2014,41(s1):83-86.(in Chinese) 陈海燕.基于多群智能算法的云计算任务调度策略[J].计算机科学,2014,41(s1):83-86. [5]GAN G N,HUANG T L,GAO S.Genetic Simulated Annealing Algorithm for Task Scheduling based on Cloud computing environment[C]∥International Conference on Intelligent Computing and Integrated Systems.IEEE,2010:60-63. [6]ZHANG X L.Application of Improved Artificial Fish SwarmAlgorithm in Cloud Computing Task Schedule[J].Electronic Design Engineering,2017,25(6):14-18.(in Chinese) 张晓丽.改进鱼群算法在云计算任务调度中的应用[J].电子设计工程,2017,25(6):14-18. [7]TIAN L W,TIAN L.A hybrid clustering algorithm based on improved artificial fish swarm[J].Telkomnika Indonesian Journal of Electrical Engineering,2014,12(5). [8]DONG Z Q,LIU N,ROJAS-CESSA R.Greedy Scheduling ofTasks with Time Constraints for Energy-efficient Cloud-computing Data Centers[J].Journal of Cloud Computing,2015,4(1):1-14. [9]XU Y M,LI K L,HU J T,et al.A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems using Multiple Priority Queues[J].Information Sciences,2014,270(6):255-287. [10]SHI J Y,HU X T,ZOU X B,et al.A Heuristic and Parallel Simu-lated Annealing Algorithm for Variable Selection in Nearin-frared Spectroscopy Analysis[J].Journal of Chemometrics,2016,30(8):442-450. [11]ZHOU L J,WANG C Y.Cloud Computing Resource Scheduling in Mobile Internet Based on Particle Swarm Optimization Algori-thm[J].Computer Science,2015,42(6):279 -281.(in Chinese) 周丽娟,王春影.基于粒子群优化算法的云计算资源调度策略研究[J].计算机科学,2015,42(6):279-281. [12]DAMODARAN PURUSHOTHAMAN,VELEZ-GALLEGO MA-RIO C.A Simulated Annealing Algorithm to Minimize makespan of Parallel Batch Processing Machines with Unequal Job Ready Times[J].Expert Systems with Applications,2012,39(1):1451-1458. [13]GOYAL T,SINGH A,AGRAWAL A.Cloudsim:Simulator for Cloud Computing Infrastructure and Modeling[J].Procedia Engineering,2012,38(4):3566-3572. |
[1] | 田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071 |
[2] | 高捷, 刘沙, 黄则强, 郑天宇, 刘鑫, 漆锋滨. 基于国产众核处理器的深度神经网络算子加速库优化 Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor 计算机科学, 2022, 49(5): 355-362. https://doi.org/10.11896/jsjkx.210500226 |
[3] | 田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117 |
[4] | 高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214 |
[5] | 谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126 |
[6] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
[7] | 夏中, 向敏, 黄春梅. 基于CHBL的P2P视频监控网络分层管理机制 Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL 计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056 |
[8] | 宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212 |
[9] | 王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023 |
[10] | 郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131 |
[11] | 潘瑞杰, 王高才, 黄珩逸. 云计算下基于动态用户信任度的属性访问控制 Attribute Access Control Based on Dynamic User Trust in Cloud Computing 计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013 |
[12] | 陈玉平, 刘波, 林伟伟, 程慧雯. 云边协同综述 Survey of Cloud-edge Collaboration 计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109 |
[13] | 蒋慧敏, 蒋哲远. 企业云服务体系结构的参考模型与开发方法 Reference Model and Development Methodology for Enterprise Cloud Service Architecture 计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044 |
[14] | 王文娟, 杜学绘, 任志宇, 单棣斌. 基于因果知识和时空关联的云平台攻击场景重构 Reconstruction of Cloud Platform Attack Scenario Based on Causal Knowledge and Temporal- Spatial Correlation 计算机科学, 2021, 48(2): 317-323. https://doi.org/10.11896/jsjkx.191200172 |
[15] | 姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191 |
|