计算机科学

计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 211100139-7.doi: 10.11896/jsjkx.211100139

• 计算机网络 • 上一篇    下一篇

基于三支聚类的云任务优化调度

马新宇1, 姜春茂2, 黄春梅2   

  1. 1 黑龙江财经学院财经信息工程学院 哈尔滨150500
    2 哈尔滨师范大学计算机科学与信息工程学院 哈尔滨 150025
  • 出版日期:2022-11-10 发布日期:2022-11-21
  • 通讯作者: 姜春茂(hsdrose@126.com)
  • 作者简介:(1136760479@qq.com)
  • 基金资助:
    黑龙江省自然科学基金(LH2020F031)

Optimal Scheduling of Cloud Task Based on Three-way Clustering

MA Xin-yu1, JIANG Chun-mao2, HUANG Chun-mei2   

  1. 1 College of Finance and Information Engineering,Heilongjiang University of Finance and Economic,Harbin 150500,China
    2 School of Computer Science and Information Engineering,Harbin Normal University,Harbin 150025,China
  • Online:2022-11-10 Published:2022-11-21
  • About author:MA Xin-yu,born in 1996,postgraduate.His main research interests include cloud computing three-way decision and so on.
    JIANG Chun-mao,born in 1972,Ph.D,professor,is a member of China Computer Federation.His main research interests include cloud computing and big data,intelligent data decision making.
  • Supported by:
    Natural Science Foundation of Heilongjiang Province,China(LH2020F031).

PDF (PC)

308

摘要： 云平台是支撑当今诸多高新技术发展的重要基础设施之一。作为云计算系统体系规划的一个重要组成部分,调度技术直接关系着云计算组成系统中的任务完成时间和能耗问题。为保证基础设施及服务模式下的云任务高效调度,提出了一种基于三支聚类的云任务优化调度算法(Three-Way Clustering Optimal scheduling Programming,TWOCP)。针对云任务属性的多样化特点,结合三支聚类算法对重叠任务和模糊任务进行粒化,并依次调度每个类簇的核心域任务和边界域任务;通过结合动态规划算法对粒化任务进行优化调度,以期实现最少任务完成时间。Cloudsimplus实验仿真结果表明,所提算法可以降低任务完成时间和能源消耗,有效保障云数据中心的可用性。

关键词: 三支决策, 三支聚类, 任务调度, 动态规划, 云计算

Abstract: Cloud computing is an important infrastructure supporting many high-tech developments.Furthermore,cloud task scheduling technology is directly related to the task completion time and energy consumption in the cloud computing system.In order to ensure the efficient scheduling of cloud tasks in the infrastructure and services mode,this paper proposes a three-way clustering optimal scheduling programming algorithm(TWOCP).According to the diversified characteristics of cloud task attri-butes,the overlapping and fuzzy tasks are granularly combined with three-way clustering algorithms,and the core region and boundary region tasks of each cluster are scheduled in turn.A dynamic programming algorithm is used to optimize the scheduling of granular-task to minimize the task completion time.Experimental simulation results in Cloudsimplus show that the proposed algorithm can reduce task completion time,energy consumption and effectively guarantee the availability of cloud data center.

Key words: Three-way decisions, Three-way clustering, Task scheduling, Dynamic programming, Cloud computing

中图分类号: 

  • TP301
[1]BETH W,DEBORAH A,AMIP S,et al.Assessing the environmental impact of data centres part 1:Background,energy use and metrics[J].Building and Environment,2014,82:151-159.
[2]WEI Y,BLAKE M B.Service-Oriented Computing and Cloud Computing:Challenges and Opportunities[J].IEEE Internet Computing,2010,14(6):72-75.
[3]ARORA N,BANYAL R K.An Overview of Traditional and Intelligent Task Scheduling Algorithms in a Cloud Computing Environment[C]//International Conference on Intelligent Machines(ICIM’19).2019.
[4]MAHMOOD I,SADEEQ M,ZEEBAREE S,et al.Task Scheduling Algorithms in Cloud Computing:A Review[J].Turkish Journal of Computer and Mathematics Education(TURCOMAT),2021,12(4):1041-1053.
[5]R DAHAN F,HINDI K E,GHONEIM A,et al.An adapted antinspired algorithm for enhancing Web service composition[J].Nternational Journal on Semantic Web & Information Systems,2017,13(4):181-197.
[6]WANG P W,DING Z J,JIANG C J,et al.Automatic web ser-vice composition based on uncertainty execution effects[J].IEEE Transactions on Services Computing,2016,9(4):551-565.
[7]FU X.Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence Optimization Algorithm in Cloud Computing[J].Computer Science.2018,45(S1):303-307.
[8]LIU J Z,SUN B,ZHU C G.Application of fuzzy C-means algorithm in task scheduling problem[C]//The 10th Annual Conference of China Institute of Communications.2014:310-313.
[9]LI J L,DING D,LI T.Multi-objective hybrid cloud task scheduling using twice clustering[J].Journal of Zhejiang University(Engineering Science),2017,51(6):1233-1241.
[10]JIANG C M,WANG K X.Real-time cloud task energy-saving scheduling algorithm based on three queues [J].Journal of Zhengzhou University(Natural Science Edition),2019,51(2):66-71.
[11]JIAO P,YU H.Overlapping Types in Soft Clustering[J].Journal of Kunming University of Science and Technology(Natural Science Edition),2015,40(3):64-69.
[12]YU H.Tree-way Cluster Analysis [J].Peak Data Csioence,2016,5(1):31-35.
[13]YU H,CHU S,YANG D.Autonomous Knowledge-orientedClustering Using Decision-Theoretic Rough Set Theory[C]//Rough Set & Knowledge Technology-international Conference.DBLP,2012.
[14]HONG Y,LIU Z,WANG G.An automatic method to determine the number of clusters using decision-theoretic rough set[J].Acoustic Bulletin,2014,55(1pt.2):101-115.
[15]WEN P,LI Y,POLKOWSKI L,et al.Three-Way Decision:An Interpretation of Rules in Rough Set Theory[C]//International Conference on Rough Sets & Knowledge Technology.Berlin:Springer-Verlag,2009:642-649.
[16]GUO D D,JIANG C M,YANG L.An effectiveness measure approach for movement-based three-way decision model[J].Journal of Chinese Computer Systems,2021,42(12):2511-2518.
[17]YAO Y.The superiority of three-way decisions in probabilistic rough set models[J].Information Sciences,2011,181(6):1080-1096.
[18]GUO D D,JIANG C M.Multi-stage Regional Transformation Strategy in Move-based Three-way Decisions Model[J].Computer Science,2019,46(10):279-285.
[19]WU J W,JIANG C M.Load-aware score scheduling of three-way clustering for cloud task[J].CAAI Transactions on Intelligent Systems,2019,14(2):316-322.
[20]WANG Z,JIANG C M.Cloud Task Scheduling Algorithm Based on Three-way Decisions[J].Computer Science,2021,48(S1):420-426.
[21]LIU Y L,TAO Y,CHEN Z F,et al.Research on the Selective Task Scheduling Algorithm Based on K-maens[J].Journal of Chang University of Science and Technology(Natural Science Edition),2019,42(5):109-115.
[22]YAO Y Y.Three-Way Decisions and Cognitive Computing[J].Cognitive Computation,2016,8:543-554.
[23]GUO D D.The TAO Model and Acting Measures of Three-way Decision under Granular Computing Perspective[D].Harbin:Harbin Normal University,2021.
[24]YAO Y.Tri-level thinking:models of three-way decision[J].International Journal of Machine Learning and Cybernetics,2020,11(5):947-959.
[25]YU H,MAO C K.Automatic three-way decision clustering algorithm based on k-means[J].Journal of Computer Applications,2016,36(8):2061-2065.
[26]LARSON R,CASTI J.Principles of Dynamic Programming[M].Dekker M,1982.
[27]SHI S F,LIU Y B.Cloud computing task scheduling researchbased on dynamic programming[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2012,24(6):687-692.
[28]ZHOU P,WANG Z M,LI Z N,et al.Complete Coverage Path Planning of Mobile Robot Based on Dynamic Programming Algorithm[C]//Proceedings of the 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT 2012).2012.
[29]NI L,SUN X,LI X,et al.GCWOAS2:Multiobjective TaskScheduling Strategy Based on Gaussian Cloud-Whale Optimization in Cloud Computing[J].Computational Intelligence and Neuroscience,2021,2021:1-17.
[30]ZHNAG K Q,TU Z Y,CHU D H,et al.Survey on Service Resource Availability Forecast Based on Queuing Theory[J].Computer Science,2021,48(1):26-33.
[31]PARK K S,PAI V S.CoMon:A mostly-scalable monitoring system for PlanetLab[J].Acm Sigops Operating Systems Review,2006,40(1):65-74.
[32]SONG J,PAN H.DDBS:a Data Dependency Based Virtual Machine Selection Strategy for Cloud Data Centers[J].Journal of Chinese Computer Systems,2020,41(2):350-355.
[1] 陈莹, 郝应光, 王洪玉, 王坤.
基于局部梯度强度图的动态规划检测前跟踪算法
Dynamic Programming Track-Before-Detect Algorithm Based on Local Gradient and Intensity Map
计算机科学, 2022, 49(8): 150-156. https://doi.org/10.11896/jsjkx.210700135
[2] 王志成, 高灿, 邢金明.
一种基于正域的三支近似约简
Three-way Approximate Reduction Based on Positive Region
计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067
[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] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[6] 谭双杰, 林宝军, 刘迎春, 赵帅.
基于机器学习的分布式星载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
[7] 林宝玲, 贾日恒, 林飞龙, 郑忠龙, 李明禄.
基于预算时变的多臂赌博机模型
Multi-armed Bandit Model Based on Time-variant Budgets
计算机科学, 2022, 49(11A): 210800212-6. https://doi.org/10.11896/jsjkx.210800212
[8] 刘文文, 熊伟, 韩驰.
基于改进超启发算法的通信卫星任务松弛调度方法
Communication Satellite Task Relaxation Scheduling Method Based on Improved Hyper-heuristic Algorithm
计算机科学, 2022, 49(11A): 210900125-6. https://doi.org/10.11896/jsjkx.210900125
[9] 周倩, 戴华, 盛文杰, 胡正, 杨庚.
云环境下可验证关键词密文检索研究综述
Research on Verifiable Keyword Search over Encrypted Cloud Data:A Survey
计算机科学, 2022, 49(10): 272-278. https://doi.org/10.11896/jsjkx.220500285
[10] 张师鹏, 李永忠.
基于降噪自编码器和三支决策的入侵检测方法
Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions
计算机科学, 2021, 48(9): 345-351. https://doi.org/10.11896/jsjkx.200500059
[11] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[12] 潘瑞杰, 王高才, 黄珩逸.
云计算下基于动态用户信任度的属性访问控制
Attribute Access Control Based on Dynamic User Trust in Cloud Computing
计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[13] 陈玉平, 刘波, 林伟伟, 程慧雯.
云边协同综述
Survey of Cloud-edge Collaboration
计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[14] 蒋慧敏, 蒋哲远.
企业云服务体系结构的参考模型与开发方法
Reference Model and Development Methodology for Enterprise Cloud Service Architecture
计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
[15] 王文娟, 杜学绘, 任志宇, 单棣斌.
基于因果知识和时空关联的云平台攻击场景重构
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
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发