粒子群优化算法在云计算环境下的调度策略综述及未来发展方向

制作和主办：Elsevier沙特国王大学学报云计算环境Arabinda Pradhana，Sukant Kishoro Bisoya，Amardeep Dasba计算机科学与工程系，C.V. 拉曼全球大学，Bidya Nagar，Mahura，Janla，Bhubaneswar，Odisha 752054，印度b计算机科学和信息技术系，C.V. 拉曼全球大学，Bidya Nagar，Mahura，Janla，Bhubaneswar，Odisha 752054，印度阿提奇莱因福奥文章历史记录：收到2020年2020年12月22日修订2021年1月4日接受2021年1月13日在线提供关键词：调度虚拟机云计算元启发式A B S T R A C T随着任务或请求规模的增大以及云资源的动态性，给负载均衡、资源利用率、任务分配以及系统性能等带来了重要的问题为了解决这些问题，许多研究人员应用了不同类型的调度技术。但相对于传统的启发式算法和混合调度算法，Meta启发式调度算法是目前最成功的调度算法.在众多的元启发式算法中，粒子群优化算法是一种著名的解决优化问题的元启发式算法。粒子群算法适用于动态任务调度、工作流调度和负载均衡。粒子群优化算法具有较强的全局搜索能力，在运行的起点和运行的最远点附近因此，它已被广泛应用于不同的应用领域，并取得了令人难以置信的进展。本文对基于粒子群优化算法的调度策略进行了系统的综述，并提出了挑战和未来的发展方向。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。内容1.导言48892.第4890章目的3.问题说明48904.资源管理48904.1.资源供应48904.2.资源监测48904.2.1.负载均衡算法48904.3.资源调度48915.调度方法的类型5.1.启发调度算法48915.2.元启发式调度算法48935.3.混合调度算法48936.粒子群优化48937.PSO调度的类型7.1.标准PSO 48937.2.跳PSO 4894*通讯作者。电子邮件地址：arabindapradhan1@gmail.com（A. Pradhan），sukantabisoyi@yahoo.com（S.K. Bisoy），amardeep. cvrce.edu.in（A. Das）。沙特国王大学负责同行审查https://doi.org/10.1016/j.jksuci.2021.01.0031319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报48897.3.学习PSO 48947.4.双目标PSO 48957.5.多目标粒子群算法48957.6.修改的PSO 48967.7.二进制PSO，7.8.混合PSO 48977.9.并行PSO 48988.讨论48999.结论4900竞争利益声明参考文献，1. 介绍云计算是一种基于Web的创新系统，它处理来自云的各种请求，并向其客户提供快速的服务。它是一种计算和处理模型，在全球不同的地方使用。云计算可用于使用高速计算快速增强预测过程。 在最近的COVID-19疫情中，基于机器学习（ML）模型的预测方案可以在远程云节点中用于实时预测，允许政府和公民主动回应。机器学习模型可以在云数据中心（CDC）上持续运行，以便政府和公民进行准确的传播在基于云的环境中，政府医院和私人健康中心不断发送其阳性患者计数、人口密度、平均和中位年龄、天气条件、健康设施等，还将被整合以提高预测的准确性（Tuli等人，2020年）。 由于与云计算相结合的几个概念，它成为最强大的技术，并用于不同的业务部门或IT行业。它提供了方便和按需访问大量的计算资源，如CPU，内存，网络，工作，服务器，存储，应用程序等，而且，这些资源经常分配给客户端以最小的服务费。当请求的数量在特定时间增加时，在最有限的反应时间和满意的管理性质中管理整个请求就变成了一个麻烦的活动。云服务提供 商 （ CSP ） 的 工 作 是 将 这 些 传 入 的 任 务 分 配 给 合 适 的 虚 拟 机（VM），以便没有机器过载，并在这些机器或资源之间资源是韩--图二. 云计算中的任务分配（Mandarin等人， 2019年）的报告。在取决于资源信息、任务信息和适当调度算法的属性的传入任务中进行dled（Kumar等人，2019年）的报告。因此，需要更好的调度技术来避免云系统中的分配问题。调度主要用于云环境中不同级别的资源共享。它是通过虚拟化来完成的，其中单个物理机或服务器以有效的方式虚拟地分离为多个虚拟机（VM）。每一台虚拟机都被用来分配不同的任务。调度的主要目标是通过分配来处理来自用户的请求Fig. 1.云计算中的任务分配（Masdari et al. 2016年）。图3. 资源管理计划（Singh和Chana，2016）。A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4890合适的资源，并在VM之间平衡负载。此外，它是用来升级的性质管理（QoS）参数，如任务解散比例，资源利用率，可靠性，重要的，表1静态和动态方法。静态方法动态方法利用率、执行成本、最小执行时间以及有限的制作跨度和提高吞吐量（Kumar等人，2019年）的报告。图1示出了如何将任务分配给VM以完成目的地（Masdari等人， 2016年）。2. 调度目标● 需要事先了解系统● 不依赖于节点的当前状态。● 决定是制成在请求的时间。● 载荷已预先定义。● 不考虑系统的先验信息。● 取决于节点的当前状态。● 决策是在运行时做出的。● 之前未定义载荷。各种目标讨论如下（Vijayalakshmi和● 减少复杂性。●更复杂。Prathibha，2013）。● 在节点负载非常小的情况下显示尽力而为。● 多余的荷载从超载节点转移到欠载节点.1. 资源查找：数据中心代理制作一个列表，以发现所有可用的资源及其信息。2. 资源确定：根据任务需求，选择合适的资源.3. 分配适应性：将任务分配到选定的资源中。图 2、调度器或数据中心代理尝试将任务映射到适当的虚拟机以满足用户需求。在（Mandarin等人，2019）调度算法可以分为两个部分，如：最优和次优策略。a. 最优调度策略：虚拟机知道关于虚拟机状态的所有详细信息，例如硬件的负载和能力如果有任务到达系统，调度器会将其放入可用的VM。b. 次优调度策略：每当任何任务没有分配或没有足够的机会分配任务时，调度器就会选择次优方法。3. 问题陈述本文的目的是回顾Meta启发式算法的云计算负载均衡。基于PSO的调度算法是最好的元启发式算法之一，它将即将到来的负载，应用程序或任务调度到云资源，以使客户端可以在最短的时间内完成任务并最大化吞吐量。简要地说，本文的主要辅助工具如下：研究了云计算环境下基于粒子群优化的调度算法。介绍了元启发式算法，重点解决任务调度和负载均衡问题。定义了不同的PSO调度方案之间的深远的相关性，并描述了不同的适应度函数，已被应用在每个计划。见图4。 负载平衡算法的不同策略（Golchi等人，2019年）的报告。● 易于实施。●难以实施。● 复杂度低●复杂度高例如：SJF、FIFO、RR等。例如：ACO、HBF、GA等。4. 资源管理在云环境中管理资源涉及各种云操作。有各种方法来分配调查中确认的资源（Kumar例如， 2019年）的报告。云计算的资源管理方法如图3所示（Singh和Chana，2016）。4.1. 资源供应它是在虚拟化技术的帮助下将云中的资源分配给传入任务的方法。在云控制器确认来自客户端的作业时，它找到合适的虚拟机（VM）并根据兴趣或按需将其分发给客户端（Kumar等人，2019年）的报告。资源配置是指查找、分配、部署和安装各种软件和硬件资源，以实现高性能。4.2. 资源监测在这种方法中，所有的信息在云中维护的云控制器，并检查有多少数量的任务分配给虚拟机在特定的时间或在一个系统。VM或资源的使用由管理员定期检查4.2.1. 负载平衡算法负载均衡器执行特定类型的算法，以确定适当的调度或负载均衡选择。该选项指定必须发送的远程服务器一份新工作根据框架环境，将计算分为两部分：静态方法和动态方法（Golchi等人，2019年）的报告。图4示出了负载均衡算法的类别。4.2.1.1. 静态算法。静态算法适用于同类环境，它不能改变其属性，负载分布在服务器之间是预定义的。它表明系统预先知道关于作业和资源的所有信息。荷载移动方式的选择不依赖于框架的现状。因此，静态算法不适合分布式计算。静态计算的实例是先进先出（FIFO）、循环调度（RR）和最短作业优先（SJF）等（Golchi等人，2019; Alguliyev等人， 2019年）的报告。4.2.1.2. 动态算法。动态算法反复检查系统当前的工作负载，并在资源之间重新分配工作负载。该算法用于改进●●●A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4891图五、 各种调度算法（Kumar等人， 2019年）的报告。表2各种启发式算法与有利的环境和约束。作者算法技术优点缺点Mao等人，（ 2014）●最大最小●任务分配以高速度。● 减少反应时间和完工时间。● 资源不平衡的机会。Elzekiet等人，2012年●改进的 最大-最小值●计算例外的exe-时间到了。● 缩短最大跨度时间。资源没有得到合理的平衡。Mondalet等人，（2015年）● SJF●选择任务的最短执行时间。● 减少执行时间和周转时间。● 可能会有饥饿和负载不平衡的情况。Alworthy等人（2016年）Pasare等人，（2019年）● 改进SJF●计算任务长度。●尽量减少完成时间最大的，充分利用资源。● DHSJF●任务大小的优先级●减少反应时间，提高VM的可访问性● 要求更加注重截止日期约束。● 很难预测任务执行的突发时间Li等人04 The Famous Women（2009）将任务分配给VM。● 降低时间复杂度。●虚拟机之间的负载不平衡机械.Khurma等人，（2018年）● 修改RR ●任务调度。●减少等待时间。●短时间切片原因开关-ing问题。Chawda等人（2016年）● 改进的负载平衡最小-最小● 资源不足更多的使用。● 减少完工时间和增量资源的使用。● SLA违规率很高。德维和03 TheFantasy（2016）● WRR●负载是中分配圆形图案● 提高资源利用率。●工作负载是不妥善平衡Kanani和Maniyar，（2015）● 改进Max-Min ●执行的任务取决于优先级。● 最小化最大化资源利用率。● 低优先级任务不平衡。Pasha等人，（2014年）● RR●检查VM的●减少迁移时间并增加资源利用● 可扩展性更低提高资源利用率、性能并缩短响应时间。不需要系统的早期信息。因此，它优于静态方法（Acharya等人，2016年）。图4显示了两种独特的动态负载均衡算法，如分布式和集中式。在分布式方法中，负载在所有可用VM之间分布。如果任何VM过载，则额外的负载被转移到欠载的VM。在集中式策略中，中心节点负责在VM之间分发所有作业。它控制、协调和管理整个系统（Golchi等人，2019; Acharya等人，2016年 ） 。动 态 算 法 的 一些 例 子 是 ： 蚁群 优 化 （ ACO ） ， 蜜蜂 觅 食（HBF）和有偏随机采样（BRS）等。静态和动态方法之间的比较如表1所示。4.3. 资源调度它是将任务分配给合适的资源执行并提供良好服务质量的方法需要一种有效的调度技术来选择最佳的A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4892来自物理机器的资源（Kumar等人，2019年）的报告。资源调度带来的主要好处是：减少应用程序的执行周期，提高云资源的利用率，降低能耗，提高QoS。5. 调度方法由于任务的动态性，启发式、元启发式和混合启发式策略成为研究的热点。调度方案分为三种类型，如启发式，元启发式和混合，如图所示。 五、5.1. 启发式调度算法启发式算法被用来解决这个问题，在一个快速和有效的方式。当经典方法失败时，它提供了更好的解决方案。通常，启发式算法给出了一个适当的结果，A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4893表3各种元启发式算法，具有有利的环境和约束条件。（2017年）Tawfeek等人，（2014年）蚁群优化算法● ACO● VMPACS算法中显示的虚拟内存布局。资源利用● 尽量减少内存资源浪费。●最后期限限制。Tawfeek等人，（2015年）● 蚁群算法●任务调度●最小化完工时间●最后期限约束。Nilesh & Patel（2017）● ACO●计算预期执行时间和任务的转移时间● 减少最大 完工时间●仅算法工作对于inde-待决任务Xiang等人，（2017年）● ACO：任务按优先级分配。·QoS参数得到满足。·不太安全。Li等人（ 2011）●LBACO●任务调度。●缩短完工时间。●弹性和可靠性较低。Jena（2017）●ABC●利用ABC进行多目标计算●减少成本和增加资源利用率● 计算中的冲突Yao and He（2013）● ABC●取决于资源的●提高系统吞吐量。●不具有可扩展性，可靠性Dasguptaetal.，（二零一三年）● GA●基于NIC的负载均衡算法MIPS。● 缩短完工时间，反应● 不满足所有QoS。哈马德和奥马拉（2016）● GA ●TS-GA●最小化的完成时间和任务的成本。● 少参数是采取实现QoS。Wei等人，（2017）● SAMPGA● MVMP算法使用SA。●最小化两个完成时间和负载不平衡程度。● 虚拟机迁移方法是时间消耗。Liu &Liu（2016）● SA●贪婪算法●降低时间复杂度。·效率较低表4具有有利环境和约束条件的混合算法。资源利用。Raju等人，（ 2013）● Hybrid●ACO andCS。●缩短完工时间。·更加复杂。Kaur and Kaur（2019）●Hybrid●任务根据其要务● 尽量减少两完工时间时间和成本。●可靠性较低Sobhanayak等人（2018年）● 混合算法● GA和BFO的组合●最小化完工时间。●时间复杂度图六、PSO中粒子的搜索位置（Allaoua等人，2008; Tran，2018）。在固定时间段内的特定问题域，但不能解决硬优化问题（Kenny等人，2014;启发式（计算机科学），2019）。针对负载均衡和任务调度问题，已经提出了许多启发式算法。一些启发式算法如表2所示。作者算法技术优势缺点Kumar和Sharma，2018年Lin等人（2016年）● PSO-COGENT● BPSO● ACO● 使用APSO-VI对粒子群算法进行了改进。● 改进的sigmoid传递函数。● 两级云调度器方法利用● 减少执行时间和成本，但最大化吞吐量。● 优化速度比率，最小化完工时间并降低成本。● 最小的成本并增加● 容错性差，可扩展性差，开销高。● 可靠性低，执行时间长。● Makespan不减少。作者算法技术优势缺点Thanka等人，（2019年）● ABPS● ABC和PSO。● 有限完工时间，成本，和扩大● 更少的安全。A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4894见图7。PSO算法的程序（Allaoua等人，2008; Tran，2018）。A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4895我VÞXX我表5表示术语和含义。术语含义术语含义i粒子r随机数m维V速度k迭代Xk当前位置w权重因子Xk1修改位置X位置Vk当前速度P最佳个人最佳Vk1修正速度有价值。粒子群优化算法的目标是在一个群体中，通过粒子或分子之间的协作和数据共享来粒子是种群的一个组成部分或一部分，我们称之为群体。Swarm需要飞越狩猎空间，以找到场景中有希望的区域。每个粒子都有一个搜索空间，通过它它们搜索食物，每个粒子随机初始化，并包含速度和位置。每个粒子都知道自己的最佳位置P最佳和最佳位置Gbest全球最佳VPbestc系数G最佳i5.2. 元启发式调度算法速度P最好速度G最好在粒子群G中表现最好。在每次迭代中，使用以下等式刷新每个粒子的速度和位置。(1)和（2）。图6示出了在PSO中搜索粒子位置的概念，图7示出了PSO的过程（Allaoua等人，2008;Tran，2018）。PSO中使用的不同术语及其含义见表5。元启发式是一种更重要的技术，旨在Vk 1½ wω Vkc1ωr1ω。PK— Xkc2ωr2ω.GK— Xk发现、产生或选择针对增强问题的出色答案它具有解决大型计算和复杂问题的能力（Milan等人， 2019年）的报告。使用不同的元启发式在云环境下解决NP难问题，如表3所示。imXk1¼X kimVk最好的;im im最好的;imimð1Þð2Þ现有的元启发式算法有：蜂群算法（ABC）、粒子群算法（PSO）、蚁群算法（ACO）、差分进化算法（DEA）、遗传算法（GA）、模拟退火算法（SA）、细菌觅食优化算法（BFO）、BAT优化算法、猫优化算法、萤火虫优化算法、布谷鸟搜索算法（CS）等，这些算法都被用来处理优化问题。 但其中GA和PSO是应用于COVID-19大流行情况的最可预测的算法（Babukarthik等人，2020; Tuli等人，2020年）。大多数荟萃分析实现的结局优于传统荟萃分析（Xu et al. 2017）。Meta启发式算法的一些有用的特性，例如：它引导搜索问题，在搜索空间内找到 最 优 值 ， 它 不 是 特 定 于 问 题 的 ， 并 解 决 NP- 难 优 化 问 题（MetaQuotics，2020）。5.3. 混合调度算法混合调度算法是将两种计划计算（以上两种方案）相结合来处理云计算中的资产规划问题。在云环境中使用各种混合调度来解决NP难问题，如表4所示。6. 粒子群优化粒子群优化算法是一种智能进化计算技术，受鸟群等生物群体行为的影响，寻找食物来源它是由Kennedy和Eberheart（Kennedy和Eberhart，1995）提出的。它是一种计算技术，通过迭代尝试改进关于给定比例的申请人安排来表6标准PSO。伊姆伊姆当不满足以下停止标准时，迭代PSO算法（Chitra等人， 2014年）：● 找出每个粒子的适应度值计算Pbest和Gbest，并更新每个粒子的位置和速度。7. PSO调度基于粒子群优化技术，各种类型的调度算法被提出，如标准粒子群优化算法、跳跃粒子群优化算法、学习粒子群优化算法、双目标粒子群优化算法、多目标粒子群优化算法、改进粒子群优化算法、二进制粒子群优化算法、混合粒子群优化算法和并行粒子群优化算法。7.1. 标准PSO在标准的PSO算法中，群中的每个粒子都被看作是m维搜索空间中的一个分子，每个粒子都包含了位置和速度。此外，它们还包含个人最佳（P最佳）和全局最佳（G最佳）。在本节中，各种任务和负载平衡调度基于常见或标准的PSO进行调度。该方法适用于资源优化规划，并根据适应度值找到最优解不同的研究人员提出了标准PSO，见表6。作者（Guo et al.，2012）提出了一种优化任务调度的方法，该方法显示了如何将所有任务分配给可用资源，从而使总执行时间和传输时间最小化。拟定目标见Eq.（3），其中Eq.（4）给出了执行时间和Eq.（5）显示了传输时间。所提出的粒子群算法中的每个粒子的初始位置和速度表示在方程中。（6）及（7）分别。最后，更新速度和位置表示为方程。（8）、（9）。总流量管理程序Cexe作者目标计划n m类型CexeXxikωDEikð4ÞGuo等人（2012年）最大限度地减少执行时间和传输时间。任务调度1/1k¼ 1PmωPc张左最大化利润和QoS支持。任务n- 1n（二零一三年）Yang等人（二零一三年）缩短完工时间，提高加工能力任务调度Cti< $1 j<$ i<$1DTijωBijð5ÞHuang等人（二零一三年）限制成本和完工时间。工作流调度x1¼ x min 最大值-xmin Þ ωrand ð6Þ●A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4896我关于我们我X11123最好的我我我我我我我我我v1¼ vmin最大值vmax- vmin最大值v k =1/4 wv k= 1 rand 1ω。pbest i-xk= 2 rand 2ω.gbest- xk标准粒子群算法的主要缺点是存在局部极小问题或收敛速度慢.它是由种群中的G最好或全球最好引起的。在每次迭代中，如果G最佳值不改变，则出现局部极小值问题为了克服这个xk1¼xkv kð9Þ问题，另一种称为跳跃PSO的方法（Chitra等人，（2014）我我我其中，CexeM是执行时间，CtM是传输时间，xik表示任务i被分配给处理器k，DEik是数据量，Pm是存储器，Pc是CPU，yijkl给出任务i和j都被分配对于处理器k和l，DTij是任务i和j之间的数据交换，Bij是带宽，rand是0和1之间的随机数。这里，xmax vmax 4： 0; xmin vmin 0： 4作者在（Zhang和Zuo，2013）中提出了一种混合云架构，可用资源不足以处理所有传入任务的架构。该算法采用标准粒子群算法计算各任务的优先级，并对任务进行降序排序，以使收益最大化。（十一）、提出了一种基于粒子群算法（JPSO）的工作流调度算法，该算法利用粒子从一个坐标移动到另一个坐标的知识，提高了工作流的负载平衡性、加速比和最大完工时间。一种改进的技术，用于确定G最好的是Eq。（十八）、KGPI18K1/ 1其中，p是获得个人最佳的排名，k是迭代。7.3. 学习PSOw l wTJL N利润<$X XTj b pv rj-X X X Xyjlkbc rj10在这种方法中，每个粒子都可以学习它们的位置和速度。第1页v1/4第1页l¼1v< $1k<$1为了达到最优解并满足所有QoS参数，表7示出了LPS0的性质其中，Tj是第j个应用程序中的任务数，bj是第j个应用程序中的VM，pv是云提供商，rj是第j个应用的运行时，yjlk是二进制决策变量，cv是成本，并且CPk表示云提供商的k个数量。在云计算中，资源之间的负载平衡是一个主要问题。采用适当的任务调度方法可以解决这一问题。为了解决这个问题，作者在（Yang et al.，2013）提出了一种基于粒子群算法的任务调度算法，该算法将任务集划分为若干个子任务，并将每个子任务按照随机的顺序分配给合适的资源，该顺序可以取决于适应度值。此外，它减少了makespan时间。适合度值、完工时间和总完工时间用方程表示（十一）、（十二）基 于 调 度 方 案 。 Zuo 等 人 提 出 了 一 种 称 为 基 于 自 适 应 学 习 PSO（SLPSO）的调度方法的资源分配框架，2014年）。它处理本地资源不足的外部云资源。所有传入的任务都必须遵循期限约束的任务调度，以获得最大的利润，并为IaaS云提供更大的弹性。为了达到目标，该方法采用四速度更新策略。当量（19）表示初始速度。当量（20）、（21）、（22）和（23）分别示出了每个粒子的更新速度。vid xkd- xjd19（13）.F.XtpOtjXt11vid联系我们最后一个半pid简体中文[2019 - 04- 22] 2019 - 04-22最大工作时间¼最大工作时间总计12小时vidt1xvidtc1r1 ½xidt-pidt]c2r2 ½ xidt-gdt]ð21ÞTtotal i¼TreceiveTexecexecutitwait13分钟其中，f Xt是适应度值，Ot是观测值，Xt是部分，vidt1vidtcrpkdt-xidt]22其中，Ttotali是总完成时间，Trece是总接收时间，Texec是总执行时间，Twait是总等待时间。作者（Huang等人，2013）提出了基于PSO的工作流调度，其中使用可调的适应度函数来降低成本和最大完工时间，如等式（1）所示。（14）、（15）和（16）。Fitnessfunction1¼最大值总成本约为14 美元vidt1vidt0：5c½pkdt-xidtpidt-xidt]23其中，i是0和1之间的随机值。xkd粒子和xjd粒子是在t次迭代中随机选择的粒子。pkdt是个人最好的解决方案。gdt是全球最佳解决方案。表7健身功能2¼最大跨度总15世纪的中国LPSO中的目标和调度策略作者目标计划类型健身功能3¼a总成本100万美元1-a最大跨度160万美元7.2. 跳跃粒子群算法在JPSO中，粒子通过影响其经验反弹到另一个位置来刷新其当前 位 置 对 于 他 们 的 改 进 ， 他 们 可 以 跳 转 到 新 的 事 件 。 根 据（Masdari）例如，2016; Ismail和Jeng，2013）跳跃PSO中每个粒子的情况将由Eq. （十七）、Zuo等人， 2014实现利润最大化并为IaaS云提供弹性。Chen and Zhang，2012降低完工时间和成本。同时，为优化问题提供可靠性。表8双目标粒子群算法任务调度工作流调度xt1¼c1ω xtc2ωbc3ωg17作者目标计划类型其中，xt是当前位置，xt = 1是更新位置，b是Verma和Kaushal，2014年最小化总执行时间工作流程和成本调度个人最佳，G是全局最佳。这里，c1，c 2和c3是范围，DOM参数，并且具有值1。Beegom和Rajasree，2014年最小化成本和最大完工时间任务调度A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4897ð Þ ð Þ第1页1/1我J第1页1/1J我Ji;j表9多目标粒子群算法作者目标计划类型7.5.多目标粒子群优化该方法由几个目标组成，以找出Alkayal等人，（2016）最大限度地减少等待时间，最大化吞吐量Jena，（2015）优化能源和加工时间。任务调度任务调度解决每个目标独立工作的优化问题的方法。在第一种方法中，每个粒子都假设它们在一个目标函数下的最佳位置。随后的方法，创建一个具有非主导最佳位置的领导粒子，其他粒子跟随领导粒子（Parsopoulos和Vrahatis，2008）。基于多目标粒子群优化算法的性质作者在（Chen and Zhang，2012）中提出了一种名为S-CLPSO的方法来表征基于惩罚的目标容量，并利用通用计划来控制现有启发式技术的利用。S-CLPSO定义了三个适应度函数来优化问题，如：可靠性，完工时间和成本。为了提高系统性能，提出了一种基于集合粒子群算法（S-PSO）的综合学习粒子群算法（CLPSO）来解决云工作流调度问题该方法首先任意引入M个粒子的初始位置，并给出M个在S-CLPSO算法的每个计算周期中，每个粒子都严格遵守CLPSO算法的速度更新准则，以更新自身的速度。在刷新速度之后，每个分子都遵循位置刷新技术来刷新位置。7.4.双目标粒子群算法双目标粒子群优化算法是一种优化任意两个QoS参数目标的粒子群优化算法例如，通过应用任务调度或工作流调度或任何其他调度来降低成本和完工时间。表8显示了这些特性基于PSO的双目标规划在（Verma and Kaushal，2014）中，作者提出了基于双标准优先级的粒子群优化算法（BPSO），以在给定的预算和截止期限约束下优化执行成本和执行时间。两个目标函数，即执行时间，表示在方程中。（24）和执行成本表示在方程。（25）分别。ETiωbxωb =MIPSofrp24 Ω欧洲共同体（ EC）：第25页其中，ET_i;p_i是任务i在资源p上的执行时间，EC_i; p_i是执行成本，Z_i是服务类型，b_x是标准执行时间，r_p是资源，l_p是资源价格。作者在（Beegom and Rajasree，2014）中提出了基于整数PSO的双目标方法，该方法用于基于最小位置值的PSO技术，以同时优化最大完工时间和成本等式（26）和（27）显示了最小化完工时间和成本。调度方案在表9中示出。作者（Alkayal等人， 2016年）提出了多目标PSO（MOPSO）任务调度算法，优化了等待时间并增加了吞吐量。在该算法中，调度器试图找到最佳VM并将任务分配给最佳VM。 为了实现这一目标，MOPSO算法集中了三个目标，例如：处理时间（PT），任务执行成本（TEC）和任务处理成本（TPC），所有这些都在等式中示出。（28）、（29）和（30）。PTV= PSV= 28V技术合作伙伴;日本TPC公司;日本IOCost公司TPCOi;juvenile PTOi;juvenile VMPl其中，i是任务，j是VM，IOCosti是成本，TLCosti是任务长度，PSV j是处理速度，VMP j VM的价格作者（Jena，2015）提出了TSPSO技术来优化参数能量和加工时间或最大完工时间。该算法的主要目标是整个任务必须在截止日期前完成，并且每个任务只能分配给一个数据中心。提出的算法需要三个主要目标，以达到目标最小化最大跨度fn¼Xk XnTωPfωxForsomejsI 26最小化成本fn¼Xk XnCωTωPfωx fororsome jsI27其中，Pfj是处理能力，Cj是成本，Ti是任务的数量，j是VM，i是VM实例，k是完成所有任务的执行所需的时期图8.第八条。改进的PSO算法的流程图（Abdi等人， 2014年）。表10各种改进PSO的总结。作者目标调度类型Zhou等人，（2018年）降低能耗任务调度Abdi等人（2014年）最小化完工时间任务调度Kumar & Sharma（2018）减少执行时间、执行成本和能耗PSO-COGENT调度Zhao，（2014）限制处理时间和成本，提高资源利用率任务调度Miglani & Sharma（2019）缩短完工时间，提高成功率任务调度i;jA. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4898--联系我们Jð Þk¼1KK在Eq. （36）。2015年12月31日x¼a×tmax1/1RRR如：完工时间、最大完工时间和能耗。它显示在Eq。（31）、（32）和（33）：菲尼斯湾开始。TjTj31Makespa nj¼ma xfFinis h.Tjg32E¼XNTωp阳离子时间和现有的处理器正在安排，这取决于他们的处理能力。改进的PSO算法给出了任务分配到最快处理器的平衡映射。 图图8示出了该修改的PSO计算的流程图。如果超过截止时间的任务数大于截止时间，则此时任务被解雇的程度更大，会发生SLA侵权。因此，（Kumar和Sharma，2018）提出了PSO-COGENT方法来改善不同的QoS特征。特征因此，创建适应度函数以减少所有的约束。其中，Tj为任务，Tj为执行所有任务所需的时间，Tk为如图所示，Eq. （三十七）：处理器执行所有任务所需的时间和处理器的pk7.6. 改进PSO是适应度函数f.rjaωEETa/b/c/1TirjTi spB.E.B.ωEECTirjTi sp cωECTirjTi spð37Þ现在，可以使用在通常称为修改的调度扇区内，其中，EETTirjtisp是预期的执行时间，EECTirjtisp是PSO。在该算法中，对速度刷新、超越极限控制、全局最优等进行了一些改进（Masdariet al.，2016年）。表10中示出了修改的基于PSO的调度的主要特征。作者（Zhou et al.，2018）提出了M PSO任务调度方法来处理处理器的最小能量消耗，其表示为Eq. （三十四）。针对现有PSO算法收敛速度慢和易陷入局部最优的问题，采用M PSO算法，采用改进的惯性权重法求解目标。（35）。本文介绍了M-PSO算法中的适应度函数，期望执行成本，ECTirjisp是执行成本，a是执行成本，执行时间，b是执行成本，c是能量消耗。作者（Zhao，2014）执行了一种改进的PSO计算，可用于最小化处理时间以及处理所有任务的成本，以达到全局最优解。处理所有任务的时间表示为Eq。（38）.处理所有任务的总成本表示为Eq。（39）。提出的算法定义了两个适应度函数，并在MPSO中实现，如等式2所示。（40）和（41）。XEMXnEMXmEð34Þk¼ 1exki¼ 1tri成本¼XmT ωERCð39Þ.联系我们t cmaxF i11 i S 40健身房1ttð36Þ埃什·穆什其中，Eex_Mk是资源k的总执行消耗，Fi1成本计算;1 ≤i ≤S 41其中，EtrMi是任务i之间的总传输消耗，x是惯性权重，tmax是最大迭代次数，c是加速因子，a和b是常数参数。作者（Abdi等人，2014）提出了一种新的改进的PSO方法，可以用来减少所有传入任务的最大完工时间。提出的方法的主要目标是巩固合并最小作业最快的处理器（SJFP）与粒子群算法。在SJFP算法中，所有传入的任务都被安排在它们的allo-表11二进制PSO。作者参数目标其中，i是任务，r是资源，Tr是总时间，Costr是总成本，Ttotal i是处理所有任务的总时间。作者（Miglani和Sharma，2019）提出了一种改进的PSO算法，该算法通过采用VM的MIPS和带宽因子来减少完工时间并更有效地平衡负载，而不是随机考虑种群。7.7. 二进制PSO从以前的版本的PSO是基于连续空间，其中整个粒子已经改变了他们的位置，根据他们的邻居。但这是一个离散空间的优化问题，可以用二进制粒子群算法来解决作者：Kennedy肯尼迪和埃伯哈特（1995）Bansal和Deep（2012年）灵活、健壮的离散二进制版本Solve Knapsack的可靠性、成本和质量溶液问题和Eberhart，1997年）提出的计算工作的离散双重因素。在双重形式中，粒子在可能性中改变它们的位置，0和1中间的一个点数。事实上，表12混合粒子群算法。作者目标调度类型耶拿等人，（2020年）最大限度地缩短完工时间、提高虚拟机性能并最大限度地提高吞吐量任务调度Jacob & Pradeep（2019）降低成本和最大完工时间价值任务调度Merly & Jayalekshmi（2016）最小化执行成本和完工时间工作流调度Huang和Chen，（2009）缩短完工时间Flow-shop调度Mandarin等人，（2019年）减少执行时间和完工时间任务调度Sardaraz和Tahir（2019）减少执行时间、完工时间和成本工作流调度MTr¼T r;i38A. Pradhan，Sukant Kishoro Bisoy和A.Das沙特国王大学学报4899X..XX.ΣΣMNIPSX.Ti;J这是程序的唱歌时间。J12NPE× VMmipsn粒子移动如等式所示。（42）和粒子通过等式（44）改变它们的位置。（43）。Vid¼ ViduPid- XiduPgd- Xid42Xid¼ XidVid43其中，u是随机正数，vid是粒子速度，Xid是位置。Bansal 和 Deep 在 2012 年 提 出 了 改 进 的 二 进 制 粒 子 群 算 法（MBPSO）来解决0-1背包问题和多维背包问题。利用Sigmoid函数对质点的速度进行归一化，使质点在离散空间中运动。表11显示了改进的基于PSO的技术的性质。7.8. 混合PSO它是将两种或两种以上不同类型的PSO调度算法相结合，