大规模云计算服务器优化调度问题的最优二元交换算法研究

王万良; 臧泽林; 陈国棋; 屠杭垚; 王宇乐; 陆琳彦

doi:10.11959/j.issn.1000-436x.2019105

您当前的位置：

首页 >

文章列表页 >

大规模云计算服务器优化调度问题的最优二元交换算法研究

学术通信 | 更新时间：2024-06-05

- 大规模云计算服务器优化调度问题的最优二元交换算法研究
- Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem
- 通信学报 2019年40卷第5期页码：180-191
- 作者机构：
  
  1. 浙江工业大学计算机科学与技术学院，浙江杭州 310027
  2. 伦敦大学国王学院工程科学学院，英国伦敦 WC2R 2LS
- 作者简介：
  
  [ "王万良（1957-），男，江苏高邮人，博士，浙江工业大学教授，主要研究方向为人工智能、运筹优化、大数据。" ]
  [ "臧泽林（1994-），男，河北秦皇岛人，浙江工业大学硕士生，主要研究方向为人工智能、运筹优化、深度学习。" ]
  [ "陈国棋（1996-），男，浙江温州人，浙江工业大学硕士生，主要研究方向为深度学习、增强学习。" ]
  [ "屠杭垚（1996- ），男，浙江杭州人，浙江工业大学硕士生，主要研究方向为智能算法、人工智能、多目标优化。" ]
  [ "王宇乐（1990- ），男，江苏常州人，浙江工业大学博士生，主要研究方向为演化计算、多目标优化。" ]
  [ "陆琳彦（1996- ），女，浙江杭州人，伦敦大学国王学院硕士生，主要研究方向为通信网络技术。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61873240);国家自然科学基金资助项目(51875524)
- DOI：10.11959/j.issn.1000-436x.2019105
  中图分类号： TP302
- 网络出版日期：2019-05，
  
  纸质出版日期：2019-05-25
- 稿件说明：
移动端阅览
王万良, 臧泽林, 陈国棋, 等. 大规模云计算服务器优化调度问题的最优二元交换算法研究[J]. 通信学报, 2019,40(5):180-191.

Wanliang WANG, Zelin ZANG, Guoqi CHEN, et al. Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem[J]. Journal on communications, 2019, 40(5): 180-191.
王万良, 臧泽林, 陈国棋, 等. 大规模云计算服务器优化调度问题的最优二元交换算法研究[J]. 通信学报, 2019,40(5):180-191. DOI： 10.11959/j.issn.1000-436x.2019105.

Wanliang WANG, Zelin ZANG, Guoqi CHEN, et al. Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem[J]. Journal on communications, 2019, 40(5): 180-191. DOI： 10.11959/j.issn.1000-436x.2019105.

摘要

随着云计算产业的不断兴盛，云计算服务器的合理管理与科学调度成为了一个重要的课题。在模型方面，提出了一个新的携带亲和约束与反亲和约束的混合整数规划（MIP）模型，并将其用于描述大规模云计算服务器调度问题。考虑到求解大规模MIP问题的时间成本，在分枝定界法与局部搜索算法的基础上提出了最优二元交换算法。该算法通过不断地从完整的调度问题中提取MIP子问题，并使用分支定界法解决该子问题的思想，不断地对服务器调度方案进行优化，从而使调度方案接近最优解。实验结果表明，所提算法在测试数据集ALISS上与其他方法相比有较大优势，在完成相同任务的情况下，可以使云计算中心的资源消耗减少4%以上。

Abstract

With the flourishing of cloud computing industry

the rational management and scientific scheduling of cloud computing servers has become an important issue.In terms of model

a new mixed integer programming (MIP) model with affinity constraints and anti-affinity constraints was proposed to describe the scheduling problem of large scale cloud computing server.Considering the time cost of solving large-scale MIP problems

an optimal two element exchange algorithm was designed with the basics of branch and bound method and local search algorithm.By constantly extracting MIP sub-problems from completing scheduling problems and using branch and bound method to solve the sub-problems

the algorithm continuously optimized the server scheduling schemes

so that the scheduling schemes approached the optimal solution.The experimental results show that the algorithm has great advantages over the other methods in testing data set ALISS

and can reduce the resource consumption of cloud computing center by more than 4% when the same task is completed.

关键词

Keywords

references

MARINESCU D C . Cloud computing:theory and practice [M ] . Morgan Kaufmann , 2017 .

HASSAN M M , SONG B , HUH E N . A market-oriented dynamic collaborative cloud services platform [J ] . Annals of Telecommunications , 2010 , 65 ( 11-12 ): 669 - 688 .

AL-DHURAIBI Y , PARAISO F , DJARALLAH N , et al . Elasticity in cloud computing:state of the art and research challenges [J ] . IEEE Transactions on Services Computing , 2017 , 12 ( 5 ):e0176321.

ADAN I , KLEINER I , RIGHTER R , et al . FCFS parallel service systems and matching models [J ] . arXiv Preprint,arXiv:1805.04266 , 2018 .

LI J , MA T , TANG M , et al . Improved FIFO scheduling algorithm based on fuzzy clustering in cloud computing [J ] . Information , 2017 , 8 ( 1 ):25.

BURNS B , GRANT B , OPPENHEIMER D , et al . Borg,omega,and kubernetes [J ] . Queue , 2016 , 14 ( 1 ): 70 - 93 .

MIJUMBI R , SERRAT J , GORRICHO J , et al . Network function virtualization:state-of-the-art and research challenges [J ] . IEEE Communications Surveys ＆ Tutorials , 2015 , 18 ( c ): 236 - 262 .

VERMA A , PEDROSA L , KORUPOLU M , et al . Large-scale cluster management at Google with Borg [C ] // The Tenth European Conference on Computer Systems . ACM , 2015 :18.

CHENG Y , CHAI Z , ANWAR A . Characterizing co-located datacenter workloads:an alibaba case study [J ] . arXiv Preprint.arXiv:1808.02919 , 2018 .

TSAI W , SHAO Q , SUN X , et al . Real-time service-oriented cloud computing [C ] // 2010 6th World Congress on Services . 2010 : 473 - 478 .

ZHU X , YANG L T , CHEN H , et al . Real-time tasks oriented energy-aware scheduling in virtualized clouds [J ] . IEEE Transactions on Cloud Computing , 2014 , 2 ( 2 ): 168 - 180 .

王吉 , 包卫东 , 朱晓敏 . 虚拟化云平台中实时任务容错调度算法研究 [J ] . 通信学报 , 2014 , 35 ( 10 ): 171 - 180 .

WANG J , BAO W D , ZHU X M . Fault tolerant scheduling algorithm for real time tasks in virtualized cloud [J ] . Journal on Communications , 2014 , 35 ( 10 ): 171 - 180 .

郭平 , 宁立江 , 陈海珠 , 等 . 满足本地化计算的集群资源调度策略 [J ] . 通信学报 , 2014 , 35 ( Z2 ): 1 - 8 .

GUO P , NING L J , CHEN H Z , et al . Scheduling strategy for achiev-ing locality in cluster [J ] . Journal on Communications , 2014 , 35 ( Z2 ): 1 - 8 .

PENG Y , BAO Y , CHEN Y , et al . Optimus:an efficient dynamic resource scheduler for deep learning clusters [C ] // The Thirteenth EuroSys Conference on EuroSys’18 . 2018 : 1 - 14 .

SINGH S , CHANA I . A survey on resource scheduling in cloud computing:issues and challenges [J ] . Journal of Grid Computing , 2016 , 14 ( 2 ): 217 - 264 .

RIMAL B P , MAIER M . Workflow scheduling in multi-tenant cloud computing environments [J ] . IEEE Transactions on Parallel and Distributed Systems , 2017 , 28 ( 1 ): 290 - 304 .

PETEGHEM V V , VANHOUCKE M . A genetic algorithm for the preemptive and non preemptive multi mode resource constrained project scheduling problem [J ] . European Journal of Operational Research , 2010 , 201 ( 2 ): 409 - 418 .

PAGNOZZI F , STUTZLE T . Speeding up local search for the insert neighborhood in the weighted tardiness permutation flowshop problem [J ] . Optimization Letters , 2017 , 11 ( 7 ): 1283 - 1292 .

林伟伟 , 刘波 , 朱良昌 , 等 . 基于CSP的能耗高效云计算资源调度模型与算法 [J ] . 通信学报 , 2013 , 34 ( 12 ): 33 - 41 .

LIN W W , LIU B , ZHU L C , et al . CSP-based resource allocation model and algorithms for energy-efficient cloud computing [J ] . Journal on Communications , 2013 , 34 ( 12 ): 33 - 41 .

LI J , SU S , CHENG X , et al . Cost-efficient coordinated scheduling for leasing cloud resources on hybrid workloads [J ] . Parallel Computing , 2015 , 44 : 1 - 17 .

DONG Z , LIU N,ROJAS-CESSA R . Greedy scheduling of tasks with time constraints for energy-efficient cloud-computing data centers [J ] . Journal of Cloud Computing , 2015 , 4 ( 1 ):5.

KRAMER O . Briefs in applied sciences and technology [M ] . London : SpringerPress , 2014 .

糜培培 . 基于云计算的改进差分进化算法的研究与实现 [D ] . 成都:电子科技大学 , 2018 .

MI P P . Research and implementation of improved differential evolu-tion evolution algorithm based on cloud computing [D ] . Chengdu:University of Electronic Science and Technology of China , 2018 .

DAS S , MULLICK S S , SUGANTHAN P N . Recent advances in differential evolution – an updated survey [J ] . Swarm and Evolutionary Computation , 2016 , 11 ( 9 ): 30 - 45 .

浏览量

709

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

云环境下协同作业的密码服务优化调度算法

M-RSF：面向Unikernel的一种多级反馈队列任务调度机制

基于强化学习的在线离线混部云环境下的调度框架

云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案

公有云中身份基多源IoT终端数据PDP方案