基于多种云环境的任务调度算法综述

陈红华　崔翛龙　王耀杰

摘 要：任务调度算法是云计算资源分配部署的核心方法。针对当前云计算发展面临的任务需求和数据量指数级增长的问题，重点对任务调度算法进行了系统的梳理和归纳，以云环境为分类依据，研究分析了单云、联盟云、混合云、多云四类调度算法。在单云环境中，从传统启发式、元启发式以及混合式任务调度算法角度进行阐述。在联盟云、混合云、多云环境中，从工作流和独立任务调度算法角度进行阐述。通过比较，总结了现有算法的优点、缺点以及优化性能，并形成结论性意见和开放性问题，为未来对容器云、数据云以及兼顾资源分配与任务调度算法的研究奠定基础。

关键词：云计算； 任务调度； 单云； 联盟云； 混合云； 多云

中图分类号：TP393 文献标志码：A 文章编号：1001-3695（2023）10-002-2889-07

doi：10.19734/j.issn.1001-3695.2023.02.0076

Summary of task scheduling algorithms based on multiple cloud environments

Chen Honghua1a，1b， Cui Xiaolong1a，2， Wang Yaojie3

（1.a.Anti-Terrorism Command Information Engineering Research Team， b.Postgraduate Brigade， Engineering University of PAP， Xian 710086， China; 2.Urumqi Campus of Engineering University of PAP， Urumqi 830000， China; 3.Construction & Development Research Institute of the Armed Police Research Institute， Beijing 100000， China）

Abstract：Task scheduling algorithms are the core method for resource allocation and deployment in cloud computing. To meet the current task demand of cloud computing while the amount of data grows exponentially， the paper focused on systematically sorting and summarizing of task scheduling algorithms. Categorized by cloud environment， it studied and analyzed four types of scheduling algorithms， namely single cloud， federated cloud， hybrid cloud， and multi-cloud. For single cloud environment， the paper elaborated from the perspectives of traditional heuristics， meta heuristics， and hybrid task scheduling algorithms. For federated cloud， hybrid cloud， and multi-cloud environments， the paper elaborate from the perspectives of workflow and independent task scheduling algorithms. Through comparisons， this paper summarized the advantages， disadvantages， and optimization performance of existing algorithms， and formed conclusive opinions and open questions， laying the foundation for future research on container clouds， data clouds， and algorithms that balanced resource allocation and task scheduling.

Key words：cloud computing; task scheduling; single cloud; federated cloud; hybrid cloud; multi-cloud

0 引言

2006年，在Google的搜索引擎會议上，云计算（cloud computing）［1］概念被正式提出。2008年BingoCloudOS产品的发布成为中国第一个获得自主知识产权的基础架构云。我国高度重视云计算领域的发展，从“十二五”开始就将云计算作为专项计划，并视为重点产业进行建设。云计算领域的地位日益突显，也迎来崭新的发展。

发展至今，云计算在诸多领域有着重要运用和广泛研究，但仍没有统一的定义。美国国家标准与技术研究院（NIST）［2］、Google维基百科［3］、中国云计算网［4］都对云计算有各自的定义，其最本质的要素是以共享资源池的方式，通过调度算法，提供各种服务。从理论上来说，云计算可以提供无限的存储、计算能力和资源，但在现实运用中，由于资源需求激增和调度策略发展的限制，极易导致资源争用、服务中断、缺乏互操作性、QoS降级和SLA违规等问题［5］。从技术发展角度来看，从早期分布式系统到网格系统［6］进而云计算技术出现，一定程度解决异构网络资源共享与利用问题，但不同于集群系统与网格系统单一的调度目标，现有云服务需要充分考虑多种用户服务质量需求，而且还要维持动态变化的系统处于负载相对均衡的状态，达到既提高资源利用率和最大化经济效益，又为用户提供高质量服务的目标（两个目标呈相互制约关系）。总的来说，云计算发展难点可以概括如下：a）计算节点资源处于不断增减的动态变化中，包括新计算节点的扩展以及停止工作的计算节点的重新工作，从而需要对资源实时监控与统计；b）云计算规模非常大，对计算节点的监测需要占用大量计算资源［7］；c）在大规模的云计算中，常常发生节点失效与程序错误的现象，从而需要充分保障任务执行的可靠性与算法的鲁棒性。

此外，云环境由单云环境发展到多个云的云间环境，单一的云环境实现简单，但单点故障能够导致严重服务危机。2022年12月18日阿里云香港可用区C某机房设备异常，导致多个网站瘫痪，云服务器ECS、云数据库PolarDB等云产品无法使用，造成不可估量的损失。多种云间环境解决了单云环境容易故障和受到DDoS攻击问题，但是云种类与数量的增加对任务调度算法提出更大的挑战［8］。基于上述问题，本文通过收集、整理、对比、分析目前主流云计算调度算法，采取从单云、多云、混合云、联盟云等不同云间环境，对调度算法进行分类阐述。在单云环境中，根据求解优化问题的技术，将任务调度算法分为传统启发式、元启发式和混合式；云间环境的任务调度算法通常从单云调度算法的基础上优化发展而来，因此根据用户请求任务的相互关系，分为工作流调度算法和独立任务调度算法，并从算法策略、算法描述、优化目标、算法特征、存在问题等角度进行对比分析，为云计算调度算法未来研究重点提供理论支持。

1 云环境与任务调度

1.1 任务调度

任务调度旨在满足用户服务需求，提高资源的使用效率并且保持均衡的资源负载，降低整个数据中心的能耗，驱动绿色发展。任务调度策略一般分为资源配置策略［9］和任务调度两个部分。资源分配从服务提供商角度出发，按照规则拆分和配给资源；任务调度是从用户提交的任务角度出发，把任务拆分并投放到合适的资源模块的过程，但是对于任何一个具体场景来说，资源往往是有限的，调度优化问题旨在实现任务请求与资源的最佳匹配。由于资源的重新分配与调度往往带来巨大的系统开销，所以本文主要从任务调度角度出发对算法进行分析与讨论。任务调度是一个 NP-hard［10］优化问题，调度目标函数为基于QoS参数的适应度函数（FFQoS），进行资源合理分配。资源分配与任务调度成正比，資源分配得越合理，任务调度实行的效率越高。而如何实现任务请求与资源的最佳匹配，即选择最合适的资源对任务处理，是云算法发展面临的最大难题。资源调配与调度（RPS）［11］过程如图1所示。

资源供应与调度（RPS）的目标是最大程度地满足用户的QoS需求以及与资源提供商协定的SLA，进行资源合理分配与均衡负载。具体流程为：首先根据任务实际，确定用户的需求与目标，结合工作负载情况分析用户与云服务提供商定义服务级别协议（SLA）；其次，基于QoS来计算适应度函数［12］（FFQoS）以及不考虑QoS参数的值（FFnonQoS），并进行比较；再次，如果FFQoS

为了让用户获得更好的服务体验并最大化提供商的利益，在资源有限的情况下设计更好的调度方案，通常通过设置不同的调度目标［13］来描述云服务提供商的服务质量和效果。常见调度目标有完成时间（makespan）、成本、能源消耗量、吞吐量、负载平衡、服务质量（QoS）、资源利用率。而对于云服务提供商提供的服务，用户通常有不同的约束条件，主要有任务完成截止时间、预算、可靠性和任务执行的具体优先级以及整个过程的安全性。

1.2 单云与云间环境

云计算广泛应用于各个领域，其云环境也由单云逐渐发展到云间环境，单云主要包括彼此没有关联的单一公有云或私有云构成。私有云和公共云在各自领域都有其特定运用，能够实现有效资源利用，但是随着日益复杂的云环境体系以及日益增长的服务需求，需要更具体和更广泛地共享信息和数据［14］。因此多种云间环境应运而生，实现了资源之间的跨云使用，降低了对单云的依赖性，提升应对故障的能力。云间环境包括联盟云环境［15］、混合云环境［16］和多云环境［17］。Gartner在《中国混合云运营的三个重要经验》报告中指出，多云以及混合云的云策略得到了企业和市场的喜爱，并将逐步成为研究热点。

云计算有各种类型的调度算法，可按静态和动态、集中和分布式、在线和离线（批处理模式）、抢占式和非抢占式和协作与非协作调度等进行分类［18］。静态调度算法需要预先获取有关任务的相关信息，当工作负载不频繁变化且系统行为变化很小时，静态算法的性能更好且易于实现。然而，在云环境中，资源实时变化，负载不断波动，因此动态调度算法是应对波动需求的关键技术。当任何节点发生增减变化时，算法会对任务进行合理的转移和再分配。事实上，所有元启发式调度方法本质上都是动态的［19］。这也意味着，动态算法和元启发式算法更适用于目前云计算的复杂环境。

2 任务调度算法分类

不同的云环境适用于不同的场合，因此根据云环境的四种不同类型（单云环境、联盟云环境、多云环境和混合云环境）进行任务调度算法分类。在单云环境中，根据求解优化问题的技术，将任务调度算法分为传统启发式算法、元启发式算法和混合式算法。由于云间环境的任务调度算法通常在单云调度算法的基础上发展而来，并结合各自云环境特点，完成不同目标并满足各种约束，进行优化升级，因此从任务间的依赖关系分类工作流调度算法和独立任务调度算法。图2展示了云计算任务调度的分类。

2.1 单云环境

单云环境部署简单，是出现形式最早的云算法环境，其任务调度算法的发展也最悠久，有大量的研究。本文主要从传统启发式算法、元启发式算法和混合式算法三个类别进行分类比较分析。

2.1.1 传统启发式算法

启发式算法是指在一个寻求最优解的过程中能够根据个体或者全局的经验来解决问题的方法。

min-min算法［20］的基本思想是先将小的任务分配到性能最好的机器上执行，实现简单，但是容易出现饥饿现象与负载不均衡问题。max-min算法改进min-min算法，保证长任务的执行，但该算法面临部分资源过度利用和部分未充分利用，无法改善参数等问题。

HEFT算法［21］基于优先级进行任务的分配执行，Dubey等人提出了改进的HEFT算法，一定程度上缓解负载压力，但该算法未能改善各种QoS参数。

先来先服务算法（FCFS）按照用户的任务请求到达的先后顺序执行，导致短作业等待时间长。Mondal等人（2015）提出最短作业优先（SJF）调度算法，但节点负载不均匀，引发饥饿现象。因此，Devi等人［22］基于增强加权循环（WRR）进行资源分配，改善了QoS，但频繁的任务切换导致额外的开销。

Sheikhalishahi等人［23］提出了多容量感知资源调度算法，减少等待时间，但未考虑任何QoS限制，算法的性能效低。为克服能效问题，Sheikhalishahi等人［24］提出Bin Packing算法，改进关键性能指标。文献［25］提出了最佳拟合算法（best fit algorithm），使得最快完成任务同时减少资源浪费。传统启发式算法还包括最小完成时间（MET）、机会负载均衡（OLB）［26］ 、最小执行时间（MCT）、爬山算法、sufferage算法、主成分分析［27］等。

传统启发式算法存在可行解与最优解的偏离，即能够求得可行解，但是并不一定是最优解，并且多数算法依赖于某个特定问题，从而在普适性上性能较差。

2.1.2 元启发式算法

元启发式是启发式与随机化的结合，它不借助于问题的特定条件，生成或选择启发式（部分搜索算法）可行的解决方案。其优势在于用更少的计算量找到好的解决方案，主要从自然界中获得灵感，并注重防止搜索陷入局部最优解的问题。由于元启发式算法的优势，目前，元启发式算法成为云环境任务调度算法的主流，这些算法用于在短时间内获得NP完全问题的次优（近似）解。通常将元启发式调度算法基于具有简单通信和交互行为的大种群/群体的集体智能、生物进化机制和物理过程分为群体智能优化算法、进化优化算法和物理优化算法，同时随着技术发展，产生了新兴算法和混合算法。

1）群体智能（swarm intelligence，SI）优化算法

a）蚁群优化（ACO）。该算法由“蚂蚁系统”［28］发展而来。为了解决云计算中的瞬时峰值负载问题，Duan等人［29］提出了基于ACO的改进算法，称为Pre-Ant Policy，该算法由预测模型组成，改进了各种QoS参数。

b）人工蜂群（ABC）［30］。最初由Karaboga于2005年提出，其基本原理是通过观察蜜蜂搜索和采蜜的行为，找到最优采蜜路径。Babu和Krishna提出了一种基于ABC算法的行为负载平衡算法，该算法不断地平衡工作负载，并改进各种关键性能指标参数。

c）细菌饲料优化（BFO）。其由Muller等人于2002年提出，主要原理是细菌觅食的集体行为，包括群居、趋化、繁殖和消除/扩散四个过程。Tang等人［31］通过在线处理实时应用程序，以少量资源来平衡负载，通过离线使用BFO算法进行全局调度，增加整个系统的稳定性和性能。

d）粒子群优化（PSO）。由Eberhart等人［32］于1995年提出，其主要思想是利用粒子的集体行为找到食物。PSO发展迅速，如标准PSO、改良粒子群算法［33］和二元粒子群算法及其变体等。

2）进化优化算法

进化算法（EA）是进化计算的算法分支，最初由Holland［34］于1975年提出，通过开发一组初始候选解决方案来找到最佳解决方案。

遗传算法（GA）由约翰·霍兰德于1960年提出，算法基于适应度值选择染色体，进行交叉和突变产生新的解决方案，直到求得可行解。Shishido等人［35］提出的一种主要针对截止时间作为约束的遗传算法，有效提升成本效益和确保安全方面。遗传算法被证明是计算机科学中解决的NP難题的有效工具。Tsai等人［36］基于GA，使用差分策略实现变异操作，提出改进的差分进化算法（IDEA），以提升性能。

3）物理算法

物理算法是由物理学定律启发而来。物理环境复杂多变，具有随机性，算法混合全局和局部（基于邻域的）搜索方法，使得在解决任务调度优化问题时表现得非常出色。

a）模拟退火（SA）。其由Kirk于1984年引入，主要原理是模拟了材料的退火过程，属于无记忆算法，即在搜索过程中不存储任何信息。Wang等人［37］提出了一种名为SA的高效物理资源分配算法，其性能优于GA和PSO算法，并克服了具有成本意识的VNE问题。

b）和谐搜索（HS）。Geem等人［38］提出HS进化算法，通过模仿音乐即兴创作，和声即代表可能的解决方案。此外，还有引力搜索算法（GSA）和Tabu搜索算法等（TS）。

4）新兴算法

近年来，许多新的元启发式算法已经被设计用于适应复杂的云计算环境，以应用于云计算中的不同复杂优化问题。如树生长算法（TGA）、飞饿扑火优化算法（MFO）和珊瑚礁优化［39］等。元启发算法无须特定条件，但模块聚合复杂，搜索易过早陷入局部最优解。

2.1.3 混合式算法

单独的调度算法对于特定领域的效果有着较好的反响，但面对实际任务调度中用户需求动态多变的现状，产生了将不同算法融合的混合式算法，有效提高时间与效果方面的性能，成为目前重要的研究方向。Saravanan等人［40］提出了IWHOLF-TSC算法，改进带有Lévy飞行算法的野马优化。实验结果表明，该算法的性能优于其他最先进的调度算法。何婧媛等人［41］将布谷鸟搜索（CS）和粒子群优化（PSO）两种算法相结合，提出多目标布谷鸟粒子群优化算法（MO-CPSO）。CloudSim评估表明，与CS、ACO、和min-min算法相比，MO-CPSO算法使完成时间、开销和截止时间违背率均最小。表1是单云环境下任务调度算法的对比总结。

对比发现，启发式算法的研究与发展历史最为悠久，其通常能够实现某一方面的性能最优，如SJF算法在独立性上表现出色。但是，相对于FCFS、RR、SJF等靜态调度算法，min-min、RR、OLB、MCT、MET等动态算法更适应于动态变化的云环境。此外，传统的调度算法无法找到多维调度问题的最优结果。因此，元启发式任务调度算法成为解决云计算任务调度算法的主流选择，但是往往实现更加复杂，难以广泛应用，实用性较差。而混合式算法通过保留传统式启发算法部署简单的特点与启发式算法的高性能，实现算法优化升级，实验数据表明，混合算法产生1+1>2的效果，在不同程度上获得了较好的性能结果。但是也会导致额外开销、利用率不高等现象。

2.2 联盟云环境

联盟云环境［15］是指各用户独立拥有自己的云服务提供商或私有云环境，同时在联盟云中的每一个用户彼此之间互联基础设施实现资源共享。在政府机关、教育机构或学术组织中较为常见。通常分为对等联盟和集中式联盟两种联盟方式。对等联盟是指联合中的每个参与者云都是一个对等云，在没有任何中介的情况下与其他人协作。在这种类型的云联盟中，没有中央组件，通常使用某个参与者云作为代理处理。集中式联盟指联合中的所有参与者云通过一个中央实体完成事物处理。本节从任务的依赖关系出发将任务调度算法分为工作流调度和独立任务调度。

2.2.1 云联盟中的工作流调度

文献［42］提出一种基于QoS权重的联盟云工作流的调度算法，在SmartFed的实验中，它为联合DC、分配器、队列管理和存储添加所需的包，使用循环算法对DC中的VM进行分配，并取得较好的效果。

Coutinho等人［43］提出了 GraspCC-fed，基于贪婪随机自适应搜索程序（GRASP），有效处理联邦云中的工作流执行，并与Sci-Cumulus工作流程引擎相结合。

文献［44］提出了MOHEFT，算法扩展了异构最早完成时间（HEFT）工作流调度算法，处理多个冲突目标并逼近帕累托前沿最优调度。实验表明，当具有几个并行任务以及多个并行工作流时，MOHEFT性能最优。

2.2.2 云联盟中的任务调度

文献［45］提出了一种在联邦云中执行大规模分布式计算的通用框架，通过引入云计算能力（GWcloud）改进的试点系统（GWpilot），可以根据可用资源实例化VM，允许用户整合其资源调配，但模型不支持公共服务提供商。

文献［46］提出一种基于FDMR（federated distributed Map-educe）的分布式算法，以在云联盟中跨地理分布地调度作业。性能评估证明，FDMR解决方案非常接近精确方法，并提高了资源的利用率、数据传输性能、和资源可用性等因素，但是成本巨大。

Gouasmi等人［47］提出了一种分布式调度方案FedSCD，用于处理联盟分布式集群中的MapReduce应用程序。它通过减少空闲VM和防止资源浪费来提供更好的资源管理和调度响应时间，降低执行成本，提高性能。表2对联盟云环境下任务调度算法进行总结归纳。

对比发现，联盟云是学术与政府等机构的常见形式，其中开发了大量科学技术结合任务调度算法，并通常将多目标优化作为目标函数，主要针对完成时间和成本进行优化，同时也充分考虑了网络带宽资源利用率等。但是由于计算需求的激增以及云环境的特殊性，需要对各云用户进行规范，目前的联盟云任务调度算法仍然无法满足数据密集和计算密集型的需求，极大地制约了联盟云任务调度算法的研究与发展。

2.3 混合云环境

混合云指包含公有云和私有云的两个或两个以上的云，用户往往将其敏感工作流程分配给私有云，当私有云缺乏执行用户任务所需的资源时，可以从公有云获得共享资源，充分利用两者优势，得到价格便宜又优质的服务，但对不同服务提供商以及云类型的统一纳管和高效运维难度加大。混合云是目前工业市场主流的选择，也是学术界的研究热点。

2.3.1 混合云中的工作流调度

文献［48］提出通信链路可用性的不确定性调度算法。在云中，由于通信链路中的并发性，很难获得精确数据，导致制造时间和成本增加。Lin等人［49］提出HIAP，这是一种混合云上SWF的在线调度方法，将应用程序划分为一组相关任务，并考虑带宽、数据传输成本和计算成本等约束，提升执行时间的准确。

2.3.2 混合云中的任务调度

Yuan等人［50］提出一种利润最大化算法（PMA），PMA提供的临时任务调度可以动态调度所有到达任务。通过混合启发式优化算法模拟退火粒子群优化（SAPSO）来解决PMA每次迭代中的子问题。大量的仿真实验表明，算法在保证服务延迟的同时，大大提高了私有云的吞吐量和利润。

文献［51］提出TTSA调度算法，通过混合整数线性程序求解成本问题，并通过混合模拟退火粒子群来优化。实验结果表明，TTSA生成的最优或次优调度策略可以有效地提高私有CDC的吞吐量并降低成本，满足任务响应时间的要求。表3对混合云环境下任务调度算法进行总结归纳。

对比发现，混合云环境的任务调度算法通常是对单云环境任务调度算法的优化，主要集中于对完成时间与成本上的优化，但总体仍是对多目标的优化。但目前多数任务调度算法无法在真实环境中进行部署与测试，限制了算法的发展。

2.4 多云环境

多云环境是指由不同云服务提供商CSP（cloud service provider）提供的公有云的混合。多个公有云服务提供商的竞争提供了更好的服务，但构建复杂，管理困难。

2.4.1 多云中的工作流调度

Gupta等人［52］提出了一种基于传输时间意识的多云环境下的高效工作流调度算法。算法包括计算任务的优先级和基于优先级进行虚拟机（VM）选择两个阶段，仿真结果表明，算法在生成时间和利用率方面都优于其他算法。文献［53］提出一种基于多目标PSO的调度方法，在PSO算法基础上，对每个CSP应用定价模型和一些性能指标，进行工作流调度。实验表明，算法性能优于CMOHEFT和随机调度算法。

2.4.2 多云中的任务调度

文献［54］针对异构多云环境提出了三种任务划分调度算法，分别是CTPS、CMMTPS和CMAXMTPS，它包括預处理和处理步骤两个程序，达到缩短调度时间并提高资源利用率的效果，但是对于预处理和处理阶段之间的通信时间以及传输和执行时间的成本考虑不够。文献［55］提出一种用于多云系统的自适应调度方法（DSS），它结合了可分割负载理论和节点可用性预测方法，提出的多云架构支持几个地理分散的网关，具有各种计算和通信功能的资源池，可以使用具有各种容量的链路连接到所有节点。结果表明，算法能够有效减少任务的处理时间。表4对多云环境下任务调度算法进行总结归纳。

对比发现，多云环境越来越被应用于实际中，但是不同云之间进行大量的信息传输与共享，导致时间开销加大，而任务调度算法容易时间复杂度过高，因此，大量算法对时间复杂度进行优化，但是对优化目标的优化上没有考虑多种优化目标。

综合对任务调度算法的分类与评价发现，目前任务调度算法的发展逐步向更适用于复杂云环境与满足多目标的QoS优化。但云计算通过资源虚拟化与容器等技术，能够对各类资源进行统一管理，通常有基本资源分配算法（basic resource allocation，BRA）、公平调度算法（fair scheduler）、容量调度算法（capacity scheduker）以及基于用户资源配额的资源弹性分配算法（QREA）等［55］，各类资源分配算法能够提升多目标优化效果，此外，基于资源组合预测的云计算任务调度算法［56］综合考虑资源的分布情况与任务的调度，避免盲目调度，但资源未能根据任务情况动态改变。因此，目前算法中缺乏同时兼顾资源分配与任务调度的算法。

3 挑战与展望

未来应从以下四个方面进行进一步研究。

a）本文通过整理调度算法相关文章，发现现有算法都以单云任务调度算法改进优化为主，缺少对云间环境的架构研究，导致算法的普适性差，无法适应多种多样的云间环境。下一步应从云间环境本身出发，以统一的API屏蔽底层基础设施导致的差异，设计更普适的算法。

b）通过整理发现，无论是单云环境还是云间环境，用户对于云服务的需求快速增长，不但要考虑多种优化目标，同时很多优化目标之间存在彼消此涨问题，导致多目标优化无法兼顾的问题，下一步应综合考量多种优化目标，并根据重要程度赋权重，提出满足多个维度优化目标的任务调度算法。

c）随着人工智能、物联网、雾计算以及基于纳米计算/量子、非传统体系结构等多种新兴技术兴起，今后的云计算环境将更加复杂多样，下一步应将新兴技术与传统云计算进行融合，实现任务调度智能化、轻量化，推动云计算实现跨越式发展。

d）目前的调度优化算法主要从任务调度角度出发进行优化，往往忽略资源分配的重要性，但在现有系统中，对资源优化分配所取得的微弱效果往往带来巨大的系统开销。容器技术的提出，其轻量化和弹性扩缩容的性能，为兼顾资源分配与任务调度提供可行的方案。下一步应从容器技术出发，对资源进行更加有效的纳管与弹性分配并实现资源根据任务量变化的动态调度，同时将用户提交的任务请求与资源进行最佳映射，达到多QoS优化，实现云环境下任务调度性能的进一步优化。

e）目前，大多数企业、政府、军队等机构对于行业云、数据云的需求越来越大，位于Pass层的大量软件下沉到Iass层，任务调度算法不再局限于传统对算力、存储、网络等基础资源调度，还要对应用的资源进行智能化调度，为数据云全域内的虚拟化资源和容器化资源实现自动及自主调度。目前，针对行业云、数据云的算法研究仍然存在大量空白，下一步应基于行业云、数据云架构，提出适用的任务调度算法。

4 结束语

本文主要完成了任务调度与云环境的概念明确。通过梳理现有的云计算任务调度算法，提出一种新的任务调度算法分类方法。根据云环境的不同，将云环境分为单云环境、联盟云环境、混合云环境、多云环境，并基于不同环境进行了分类和比较。对比发现，传统启发式任务调度算法对某一特定目标优化效果较好，但是用户往往提出多种优化目标，因此提出元启发式算法，但由于其实现复杂，难以应用部署。混合式算法是传统启发式算法与混合式算法的结合，保留了两者的优势，是目前主流的任务调度算法，但是存在额外开销以及资源负载不均衡等问题，因此仍值得进一步研究优化。此外，云环境中任务复杂多样，任务间的关系也相互交叠，独立任务调度无法再适应现有环境，目前，任务调度算法研究主要以工作流调度为主。

总的来说，本文提供了调度算法的全面理解，未来在数据云、行业云的调度算法研究中，应注重对混合式工作流调度的研究。

参考文献：

[1]许子明，田杨锋.云计算的发展历史及其应用［J］.信息记录材料，2018，19（8）：66-67.（Xu Ziming， Tian Yangfeng. The development history and applications of cloud computing［J］.Information Recor-ding Materials，2018，19（8）：66-67.）

［2]Mell P M， Grance T. The NIST definition of cloud computing， 800-145［R］.Gaithersburg，MD：National Institute of Standards and Technology，2011.

［3]Wikipedia.Cloud computing［EB/OL］.（2009-03-10）.http：//en.wikipedia.org/wiki/Cloud_computing.

［4]中国云计算网.什么是云计算？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.（Cloud Computing Network of China.What is cloud computing？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.）

［5]Amin R， Kumar N， Biswas G P， et al. A light weight authentication protocol for IoT-enabled devices in distributed cloud computing environment［J］.Future Generation Computer Systems，2018;78：1005-1019.

［6]羅红，慕德俊，邓智群，等.网格计算中任务调度研究综述［J］.计算机应用研究，2005，22（5）：16-19.（Luo Hong， Mu Dejun， Deng Zhiqun， et al. A review of job scheduling for grid computing［J］.Application Research of Computers，2005，22（5）：16-19.）

［7]Juarez F， Ejarque J， Badia R M. Dynamic energy-aware scheduling for parallel task-based application in cloud computing［J］.Future Generation Computer Systems，2018，78：257-271.

［8]Madni S H H， Latiff M S A， Coulibaly Y， et al. Recent advancements in resource allocation techniques for cloud computing environment： a systematic review［J］.Cluster Computing，2017，20（3）：2489-2533.

［9]Mikavica B， Kostic＇-Ljubisavljevic＇ A. Pricing and bidding strategies for cloud spot block instances［C］//Proc of the 41st International Convention on Information and Communication Technology， Electronics and Microelectronics.Piscataway，NJ：IEEE Press，2018：0384-0389.

［10]Ullman J D. NP-complete scheduling problems［J］.Journal of Computer and System Sciences，1975，10（3）：384-393.

［11]Singh S， Chana I. Resource provisioning and scheduling in clouds： QoS perspective［J］.The Journal of Supercomputing，2016，72（3）：926-960.

［12]Wu Kaiyue， Lu Ping， Zhu Zuqing. Distributed online scheduling and routing of multicast-oriented tasks for profit-driven cloud computing［J］.IEEE Communications Letters，2016，20（4）：684-687.

［13]Hosseini Shirvani M， Rahmani A M， Sahafi A. An iterative mathema-tical decision model for cloud migration： a cost and security risk approach［J］.Software： Practice Experience，2018，48（3）：449-485.

［14]Zhang Bo， Zeng Zeng， Shi Xiupeng， et al. A novel cooperative resource provisioning strategy for multi-cloud load balancing［J］.Journal of Parallel and Distributed Computing，2021，152：98-107.

［15]Chauhan1 S S， Pilli E S， Joshi R C. A broker based framework for federated cloud environment［C］//Proc of International Conference on Emerging Trends in Communication Technologies.Piscataway，NJ：IEEE Press，2016：1-5.

［16]Linthicum D S. Emerging hybrid cloud patterns［J］.IEEE Cloud Computing，2016，3（1）：88-91.

［17]Li Xiaoyong， Ma Huadong， Yao Wenbin， et al. Data-driven and feedback-enhanced trust computing pattern for large-scale multi-cloud collaborative services［J］.IEEE Trans on Services Computing，2018，11（4）：671-684.

［18]Shi Yang， Chen Zhaoyun， Quan Wei， et al. A performance study of static task scheduling heuristics on cloud-scale acceleration architecture［C］//Proc of the 5th International Conference on Computing and Data Engineering.New York：ACM Press，2019：81-85.

［19]Xhafa F， Abraham A. Meta-heuristics for grid scheduling problems［M］//Xhafa F， Abraham A. Metaheuristics for scheduling in distri-buted computing environments.Berlin：Springer，2008：1-37.

［20]Liu Juefu， Liu Peng. The research of load imbalance based on min-min in grid［C］//Proc of International Conference on Computer Design and Applications.Piscataway，NJ：IEEE Press，2010：V4-1-V4-4.

［21]童釗，邓小妹，陈洪剑，等.云环境下基于强化学习的多目标任务调度算法［J］.小型微型计算机系统，2020，41（2）：285-290.（Tong Zhao， Deng Xiaomei， Chen Hongjian， et al. A multi-objective task scheduling algorithm based on reinforcement learning in cloud environments［J］.Journal of Chinese Computer Systems，2020，41（2）：285-290.）

［22]Devi D C. Load balancing in cloud computing environment using improved weighted round robin algorithm for non-preemptive dependent tasks［J］.The Scientific World Journal，2016，2016：article ID 3896065.

［23]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A multi-dimensional job scheduling[J].Future Generation Computer Systems， 2016，54：123-131.

［24]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A packing problem approaches to energy-aware load distribution in clouds［J］.Future Generation Computer Systems，2016，54：123-131.

［25]Shyam G K， Manvi S S. Resource allocation in cloud computing using agents［C］//Proc of IEEE International Advance Computing Confe-rence.Piscataway，NJ：IEEE Press，2015：458-463.

［26]Lavanya M， Shanthi B， Saravanan S. Multi objective task scheduling algorithm based on SLA and processing time suitable for cloud environment［J］.Computer Communications，2020，151：183-195.

［27]Al-Maytami B A， Fan P， Hussain A， et al. A task scheduling algorithm with improved makespan based on prediction of tasks computation time algorithm for cloud computing［J］.IEEE Access，2019，7：916-926.

［28]Dorigo M. Optimization， learning and natural algorithms［D］.Italy：Politecnico di Milano，1992.

［29]Duan Hancong， Chen Chao， Min Geyong， et al. Energy-aware scheduling of virtual machines in heterogeneous cloud computing systems［J］.Future Generation Computer Systems，2017，74：142-150.

［30]Hajimirzaei B， Navimipour N J. Intrusion detection for cloud computing using neural networks and artificial bee colony optimization algorithm［J］.ICT Express，2019，5（1）：56-59.

［31]Tang Linlin， Li Zuohua， Ren Pingfei. et al. Online and offline based load balance algorithm in cloud computing［J］.Knowledge-Based Systems，2017，138：91-104.

［32]Eberhart R， Kennedy J. A new optimizer using particle swarm theory［C］//Proc of the 6th International Symposium on Micro Machine and Human Science.Piscataway，NJ：IEEE Press，1995：39-43.

［33]Kumar M， Sharma S C. PSO-COGENT： cost and energy efficient scheduling in cloud environment with deadline constraint［J］.Sustai-nable Computing：Informatics and Systems，2018，19：147-164.

［34]Holland J H. Adaptation in natural and artificial systems：an introductory analysis with applications to biology， control， and artificial intelligence［M］.Cambridge，MA：MIT Press，1992.

［35]Shishido H Y， Estrella J C， Toledo C F M， et al. Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds［J］.Computers & Electrical Engineering，2018，69：378-394.

［36]Tsai J T， Feng Jiacen， Chou J H， et al. Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm［J］.Computers & Operations Research，2013，40（12）：3045-3055.

［37]Wang Wenbo， Chang Xiaolin， Liu Jiqiang， et al. Simulated annealing based resource allocation for cloud data centers［C］//Proc of the 15th Annual Conference Companion on Genetic and Evolutionary Computation.New York：ACM Press，2013：81-82.

［38]Geem Z W， Kim J H， Loganathan G V. A new heuristic optimization algorithm：harmony search［J］.Simulation，2001，76（2）：60-68.

［39]Wan Shuzhen， Qi Lixin. An improved coral reef optimization-based scheduling algorithm for cloud computing［J］.Journal of Mathema-tics，2021，2021：article ID 5532288.

［40]Saravanan G， Neelakandan S， Ezhumalai P， et al. Improved wild horse optimization with Lévy flight algorithm for effective task scheduling in cloud computing［J］.Journal of Cloud Computing，2023，12（1）：1-14.

［41]何婧媛，孫乾坤.布谷鸟粒子群优化算法的多目标任务调度［J］.信息技术，2020，44（5）：37-40.（He Jingyuan， Sun Qiankun. Multi objective task scheduling of Cuckoo particle swarm optimization［J］.Information Technology，2020，44（5）：37-40.）

［42]Chudasama V， Shah J， Bhavsar M. Weight based workflow scheduling in cloud federation［M］//Satapathy S， Joshi A. Information and Communication Technology for Intelligent Systems.Cham：Springer，2017：405-411.

［43]Coutinho R D C， Drummond L M， Frota Y， et al. Optimizing virtual machine allocation for parallel scientifc workflows in federated clouds［J］.Future Generation Computer Systems，2015，46：51-68.

［44]Durillo J J， Prodan R， Barbosa J G. Pareto tradeoff scheduling of workflows on federated commercial clouds［J］.Simulation Modelling Practice and Theory，2015，58：95-111.

［45]Rubio-Montero A J， Huedo E， Mayo-García R. Scheduling multiple virtual environments in cloud federations for distributed calculations［J］.Future Generation Computer Systems，2017，74：90-103.

［46]Gouasmi T， Louati W， Kacem A H. Exact and heuristic MapReduce scheduling algorithms for cloud federation［J］.Computers & Electrical Engineering，2018，69：274-286.

［47]Gouasmi T， Louati W， Kacem A H. Cost-efficient distributed mapreduce job scheduling across cloud federation［C］//Proc of IEEE International Conference on Services Computing.Piscataway，NJ：IEEE Press，2017：289-296.

［48]Bittencourt L F， Madeira E R M， Da Fonseca N L S. Impact of com-munication uncertainties on workflow scheduling in hybrid clouds［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2012：1623-1628.

［49]Lin Bing， Guo Wenzhong， Lin Xiuyan. Online optimization scheduling for scientifc workflows with deadline constraint on hybrid clouds［J］.Concurrency and Computation，2016，28（11）：3079-3095.

［50]Yuan Haitao， Bi Jing， Tan Wei， et al. Temporal task scheduling with constrained service delay for profit maximization in hybrid clouds［J］.IEEE Trans on Automation Science and Engineering，2017，14（1）：337-348.

［51]Yuan Haitao， Bi Jing， Tan Wei， et al. TTSA： an effective scheduling approach for delay bounded tasks in hybrid clouds［J］.IEEE Trans on Cybernetics，2017，47（11）：3658-3668.

［52]Gupta I， Kumar M S， Jana P K. Transfer time-aware workflow sche-duling for multi-cloud environment［C］//Proc of International Confe-rence on Computing，Communication and Automation.Piscataway，NJ：IEEE Press，2016：732-737.

［53]Hu Haiyang， Li Zhongjin， Hu Hua， et al. Multi-objective scheduling for scientifc workflow in multicloud environment［J］.Journal of Network and Computer Applications，2018，114：108-122.

［54]Panda S K， Pande S K， Das S. Task partitioning scheduling algorithms for heterogeneous multi-cloud environment［J］.Arabian Journal for Science and Engineering，2018，43（2）：913-933.

［55]Kang S， Veeravalli B， Aung K M M. Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems［J］.Journal of Parallel and Distributed Computing，2018，113：1-16.

［56]劉晓东，赵晓芳，金岩，等.企业私有云环境下面向高性能计算的资源弹性分配算法［J］.高技术通信，2018，28（8）：669-676.（Liu Xiao-dong， Zhao Xiaofang， Jin Yan， et al. Resource elastic allocation algorithm for high performance computing in enterprise private cloud environment［J］.High Technology Letters，2018，28（8）：669-676.）

［57]程宏兵.基于资源预测的网格任务调度模型［J］.计算机应用，2010，30（9）：2530-2534，2544.（Cheng Hongbing. Grid task sche-duling model based on resource prediction［J］.Journal of Computer Application，2010，30（9）：2530-2534，2544.）

收稿日期：2023-02-28；修回日期：2023-04-20

基金项目：军委网信科研资助项目

作者简介：陈红华（1998-），女，浙江桐乡人，硕士研究生，主要研究方向为面向多样化任务的云计算；崔翛龙（1973-），男（通信作者），安徽长丰人，教授，博导，主要研究方向为智能化指挥、任务大数据（xlspace@hotmail.com）；王耀杰（1990-），男，河南洛阳人，博士，主要研究方向为反恐预警、信息安全、深度学习.