一种云环境下基于混合型BBO的任务调度算法

计算机工程与科学

一种云环境下基于混合型BBO的任务调度算法

童钊1,2，陈洪剑1,2，陈明1,2，梅晶1,2，刘宏1,2

（1.湖南师范大学信息科学与工程学院，湖南长沙 410012;

2.高性能计算与随机信息处理省部共建教育部重点实验室，湖南长沙 410012）

收稿日期:2017-05-15 修回日期:2017-08-15 出版日期:2018-05-25 发布日期:2018-05-25
基金资助:
国家自然科学基金（61502165）；湖南省教育厅一般项目（17C0959）

A hybrid biogeography-based optimization

algorithm for task scheduling in cloud computing

TONG Zhao1,2，CHEN Hong-jian1,2，CHEN Ming1,2，MEI Jing1,2,LIU Hong1,2

（1.College of Information Science and Engineering,Hunan Normal University,Changsha 410012;

2.Key Laboratory of High Performance Computing and Stochastic Information

Processing（HPCSIP）（Ministry of Education of China）,Changsha 410012,China)

Received:2017-05-15 Revised:2017-08-15 Online:2018-05-25 Published:2018-05-25

摘要/Abstract

摘要：

任务调度在云计算中占有重要地位，是影响云计算性能的关键因素，被证明是NP问题。启发式算法是解决该问题的最有效方法之一，针对近年来出现的一种新型启发式算法——BBO算法展开研究，由于BBO算法在求解过程中收敛速度较慢，因此结合粒子群算法提出了一种新型算法的任务调度算法——HMBBO，并结合Cloudsim云仿真平台，进行了以Makespan为目标函数的比对实验。实验结果表明，与几种经典的启发式算法相比，HMBBO算法具有寻优能力强、收敛速度快、求解质量高的特点，为解决云计算环境中任务调度问题提供了一种新思路。

关键词: 云计算, 任务调度, BBO, Makespan

Abstract:

Task scheduling plays a critical role in cloud computing and is a key factor affecting the performance of cloud computing. It has been proved to be an NP problem. Heuristic algorithm is one of the most effective methods to solve this problem. This paper focuses on the Biogeography-Based Optimization (BBO) algorithm, which serves in recent years as a new heuristic algorithm. Because the BBO algorithm converges slowly in the solution process, by combining Particle Swarm Optimization (PSO) algorithm, we propose a novel task scheduling algorithm, named Hybrid Migrating Biogeography-Based Optimization (HMBBO). A comparison experiment using Makespan as the objective function is performed on the Cloudsim cloud simulation platform. The experiment results show that, compared with several classical heuristic algorithms, HMBBO has the advantages of strong optimization ability, fast convergence speed and high-quality solution, and provides a new way to solving the task scheduling problem in cloud computing environment.

Key words: cloud computing, task scheduling, BBO, Makespan

中图分类号:

null

童钊1,2，陈洪剑1,2，陈明1,2，梅晶1,2，刘宏1,2. 一种云环境下基于混合型BBO的任务调度算法[J]. 计算机工程与科学.

TONG Zhao1,2，CHEN Hong-jian1,2，CHEN Ming1,2，MEI Jing1,2,LIU Hong1,2.

A hybrid biogeography-based optimization

algorithm for task scheduling in cloud computing

[J]. Computer Engineering & Science.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	徐嘉, 张骥先, 王喆民, 刘林杰. 基于NUMA云计算架构的多资源分配可信拍卖机制[J]. 计算机工程与科学, 2024, 46(05): 761-775.
[3]	马柯帆, 李宝峰, 周悦锦, 武园园, 余永兰, 多瑞华. 基于ZYNQ 芯片的基板管理控制器设计与实现[J]. 计算机工程与科学, 2024, 46(02): 217-223.
[4]	孙庆骁, 刘轶, 杨海龙, 王一晴, 贾婕, 栾钟治, 钱德沛. GNNSched：面向GPU的图神经网络推理任务调度框架[J]. 计算机工程与科学, 2024, 46(01): 1-11.
[5]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[6]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[7]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[8]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[9]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[10]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[11]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[12]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[13]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[14]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[15]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.