没有合适的资源?快使用搜索试试~ 我知道了~
智能系统与应用18(2023)200219一种新的混合粒子群优化算法在分布式计算系统中的任务调度Karishma,Harendra Kumar*数学与统计系,Gurukula Kangri(被视为大学),Haridwar,Uttarakhand 249404,印度A R T I C L EI N FO保留字:粒子群优化任务调度响应时间集群质心分布式系统流程时间系统成本A B S T R A C T异构分布式多处理计算环境中的任务分配问题是一个非线性多目标NP-难问题,从研究的角度来看,它被认为是一个主要问题。执行指定任务集和枚举处理器的任何分配机制的基本目标都是最小化总成本。为了解决任务分配问题,许多元启发式技术已经被尝试和测试,但仍然有很多的范围有最佳策略。本文提出了一种基于粒子群优化算法(PSO)的分布式任务分配模型,该模型优化了分布式计算系统的响应时间、流程时间和成本。在本技术中,' r '个任务的聚类质心的考虑到实际情况,在给定的模型中,目标函数相互冲突,PSO算法的优点是它的准确性和速度。本文提出的基于粒子群算法的分布式计算系统中的分配问题的求解方法,由于粒子群算法结合了局部和全局搜索方法,在研究和应用之间取得了平衡,因此在收敛速度方面能够得到更好的结果。为了研究所开发的技术的功能,以及基于不同技术的调度政策进行了比较,并获得了更好的结果。开发的机制是可以接受的任务和处理器的数量不稳定1. 介绍分布式计算模型包含多个处理器,这些处理器分布在不同的位置,通过通信链路连接,需要多个计算资源,这些资源可以借助网络进行管理,以执行高性能和大规模的任务。分布式计算系统(DCS)的任务模型包括任务的数量,每个任务在单个处理器上执行并与其他任务通信。指派问题的两个重要阶段是将程序划分为若干任务,并在最小化总成本和总时间的前提下将这些任务分配给处理机。如果调度没有正确实现,那么系统中的处理器可能会浪费最大的时间等待另一个处理器,而不是计算更重要的任务。因此,在这种类型的NP-难问题,以最小化的系统(SC)的成本有效的任务分配是必要的。在分布式控制系统中,根据分配时间的不同,分配策略分为两类不同的类别,静态和动态。在给定的文章中,我们考虑静态任务分配,因为在这种调度中,有关成本和硬件配置的信息在执行之前是已知的。在这种分配中,当我们分配一个任务时, 在处理器上,当计算特性改变时,任务在那里持续。静态调度方法可以具有能够以可以确定性地执行的方式来规划的真实世界应用。与动态分配相比,静态分配具有一些优点,例如静态分配方法没有任何运行时悬置,并且它们可以用复杂的算法程序来准备,该算法程序完全利用了特定应用的少数众所周知的资格。许多研究都致力于对性能的基本关注管理标准,例如减少执行和通信成本的总量或减少应用程序完成时间。任务分配问题的解决方案是许多研究人员在他们的文章中使用各种技术。为了解决静电* 通讯作者。电子邮件地址:balyan. gmail.com(H.Kumar)。https://doi.org/10.1016/j.iswa.2023.200219接收日期:2022年7月31日;接收日期:2023年3月13日;接受日期:2023年3月24日2023年3月26日网上发售2667-3053/© 2023作者。由Elsevier Ltd.发布。这是CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。可在ScienceDirect上获得目录列表智能系统及其应用杂志主页:www.journals.elsevier.com/intelligent-systems-with-applicationsKarishma和H. Kumar智能系统与应用18(2023)2002192表1(续)几位作者使用的聚类方法。S.号参考文献考虑参数环境性质方法评价15Chauhan等人(2022年)可靠性、执行成本异构的一种方法最大化系统的可靠性2Elango等人(2011年)总代价异构利用k-均值聚类技术解决多机器人均衡任务分配问题任务分配(Bokhari,1987)使用图论方法来减少执行成本的总量。Ucar等人(2006年)建立了一种方法,将任务调度到处理器,以减少相同链路的执行和通信成本的总和。亚达夫等人(2011)解释了一种基于ANN的模型,该模型提供了最佳的3Yadav等(2012年)4Wang等人(二零一三年)503 The Dog(2014)6Liu等人(2017年)沟通成本、执行成本能耗和执行时间欧几里德距离和执行时间任务迁移、数据洗牌异构集群技术提出了一种降低通信代价的优化调度方法同质验证模型提出了能源消耗,DVFS-授权集群和预约束对齐的任务异构分析电信数据的计算提交了一个任务保载解决方案 和 使平衡的 负载 到 所有 处理器. 阿克巴里和Rashidi(2016)提出了一种任务调度算法来减少执行时间。动态任务分配问题使用一些规则在处理器之间转移任务。在动态分配中,任务在节点到达时或在任务运行时分配。孔 等人(2011)为虚拟化数据中心开发了一种规划良好的动态调度方案。Singh et al.(2012)提出了一种基于人工神经网络(ANN)的动态任务分配模型,用于将任务分配到处理器。Sriramdas et al.(2014)将分配因素视为模糊数,从而发展了一种任务分配方法。对于使用直接搜索优化的分配问题,Tripathy et al.(2015)提出了三种新模型。为了探索量子计算的枚举能力,Konar etal.(2017)提出了一种更动态的实时分配方法。必须部署一个组织良好的任务调度机制-nism在计算系统中,以获得更好的效率。任务调度涉及映射到7Janati等人(2017年)8Kumar等人(2018年)9Singh等人(2018年)10库马尔和Tyagi(2019)任务分配可靠性、成本费用、时间费用共计群集平衡提出了一种用于大规模任务和机器人分配的技术,给出了一种利用k-均值方法获得系统成本和可靠性的模型利用k-means聚类和划分问题解决资源的动态配置问题基于聚类的资源最小化算法随着提交执行的任务数量的增加,模型的复杂性显着增加。在这种情况下,从所有可能的任务映射中获得最优解是不可能的。作者Agarwal和Srivastava(2016)和Alameen和Gupta(2020)在他们的文章中对此进行了解释。因此,为了确保可用资源的最佳利用,始终需要一个有效的任务分配机制。基于著名的元启发式方法,作者Li等人(2011)采用蚁群优化(ACO),Agarwal和Srivastava(2018)采用PSO,Kumar等人(2019)采用遗传算法(GA)介绍了他们的任务调度策略。在所有这些方法中,元启发式方法PSO是最常用的,并优化了大多数分配问题,具有非常熟练的结果。它所需调整的参数较少,这是PSO技术比GA更容易实现的原因。粒子群算法的这一特性启发了我们将其应用到分配模型中在这篇文章中,作者将提出一个任务allo-11Kumar等人(2019年)12Cai等人(2019年)成本和响应时间地理距离、位置异构异构方法为了减少通信开销,引入了一种混合遗传算法来优选任务簇提出了一种新的聚类方法LC-G-P在标准粒子群优化算法的基础上,通过调度过程生成高通信量任务簇,以降低通信开销,并在此基础上提出了一种降低分布式系统执行开销的算法,用于在静态环境下将得到的任务簇分配到有能力的处理器上。在异构系统中,任务分配问题与诸如SC等性能指标有关,并且找到适当的任务分配给处理器以优化系统的性能响应时间(RT)和流动时间。拟议方案的主要贡献13Kumar和Tyagi(2020)可靠性,响应时间非均质建议最佳值基于遗传算法、BB算法和模糊算法的混合调度介绍了DCS技术:对于任务簇的形成,引入了基于粒子群优化的有组织调度过程,在这样一个静态环境下,14Jalalian和Sharifi(2022)制造周期,效率,通信成本异构c-means应用k-means算法基于粒子群算法的指派技术是有效的。一种启发式方法的进化,它提供了任务集群的最佳分配。粒子群算法··S.号引用所考虑参数环境性质方法102 The Dog(2010)集群异构提出了蚁群算法、模糊自适应粒子群算法和k-聚类方法·Karishma和H. Kumar智能系统与应用18(2023)2002193表2粒子群算法用于不同任务分配问题。现有的技术和工作的结论显示在第8节。S.号参考文献考虑参数环境性质方法2. 相关工作1Yin等人(二零零七年)可靠性异构开发了一种混合型粒子群优化模型,以确定最优的任务分配内,多年来,随着对多处理环境下任务分配的 作者Braun et al.(2001)和Zhang等人(2016)提出了用于2ChenandWang(2011)3Guo等人(2012年)任务调度成本和任务分配异构异构适当的时候采用标准粒子群算法,来解决任务分配问题以系统成本最小为目标,建立了任务调度模型计算系统。一些作者,如Shojafar et al.(2013)和Yousif et al.(2015)介绍了他们在网格计算领域的工作,Zhang et al.(2001)和作者Davisand Burns(2011)提出了他们在多处理系统上的工作。在DCS中,任务调度是一个重要的阶段。到目前为止所做的工作中更关注的部分是通过使用组织良好的任务调度过程来解决计算系统功能的改进4Raju等人(2016年)5Zhou等人(2018年)6Mapetu等人(2019年)期限约束任务分配成本和完工时间马凯斯潘,时间到开发了一个模型用于优化任务调度以最小化总时间和成本异质发达一种改进的PSO任务调度算法一种异构粒子群算法云计算(i) 涉及到基于分配算法的元分配或元分配的演变。(ii) 涉及基于混合的模型的演变。上述两组的一些工作将进一步讨论。任务分配问题属于NP难问题,用传统的方法是无法解决的。因此,这类问题可以通过启发式或元启发式算法来解决。Xu et al.(2014)提出了一种基于遗传算法的异构计算任务调度方案7哈桑和阿尔-里佐(2019)8Al-Turjman等人(2019年)9Agarwal和Srivastava(2020)Makespan、flowtime、tardiness延迟、延迟、吞吐量Makespan和任务调度同质&异质同质异质&异构提出了一种基于CPSO的任务调度算法,该算法能够在满足最大完工时间的前提下实现任务的最优调度。提出了一种有效的基于PSO的任务调度策略,该策略能够在保证较高QoS水平的前提下增强管理队列。系 统 作 者Patel 等 人 (2015 ) 提 出 了 一个 静 态 任 务 分配 的 模 型“ELBMM”。这些作者还比较了他们提出的ELBMM算法与基于时间的任务调度技术,如最小执行时间(MET),机会负载平衡(OLB),最大-最小和最小完成时间(MCT)。Jia等人(2021)开发了一种增强型鲸鱼优化(IWC)调度有效性算法。该方法的主要目的是提高WOA算法聚类(Clustering)是将一组数据分配到更小的组中的过程,以便同一组中的对象与其他组中的对象相互熟悉聚类是一种启发式的方法,它通过对高度通信的任务进行分组来最小化通信开销。详细的聚类方法用于不同类型的问题如表1所示。10Achary等人(2021年)11Pradhan和Bisoy(2022)费用,百分比偏差负载平衡、资源利用率、最大完工时间异构为了解决QAP,一个修改版本的离散粒子群算法是使用均匀开发了一个负载一种基于改进粒子群算法的然而,基于启发式算法是解决任务调度问题的常用算法,但由于数据集类型复杂、规模大,往往陷入局部最优。在这种类型的情况下,特别是当我们需要面对多样性时,元启发式方法,即ACO(Dorigo et al.1999),PSO(Kennedy and Eberhart1995)和GA(Goldberg 1989)作为更好的候选人。根据Kalra等人(2015)的说法,为了避免陷入局部最优,如果与其他方法相比,元启发式方法是最有效的。 除此之外,元启发式技术遵循问题独立机制,而问题依赖过程实验结果表明,该方法能较好地解决上述问题。采用方差分析检验对结果的质量进行统计学评价。这篇文章的其余部分被归类为给定。第2介绍了与这一领域有关的工作。PSO技术在第3中描述,而第4描述了整个文章中考虑的问题和数学符号的制定第5节定义了开发方法的方法。在第6节中用所提出的方法解决了五个例子。第7节显示了所建议的模型与其他模型其次是启发式方法。为了解决分布式环境中任务分配的相关问题,以优化结果,各种作者,如Rahmani和Vahedi(2008),研究人员Lu et al.(2013),Ahmad等人(2016),作者Kartik和Murthy(1997),Zhang 等人(2008),作者Kumar和Vidyarthi(2016),研究人员Kim等人(2016),(2011)和Pendharkar(2015)使用了这些元启发式算法。Mishra和Majhi(2021)介绍了一种BSOLB技术,该技术试图通过减少响应时间和保持系统平衡来提高系统性能。作者AbualigahAltalhi,2022&概述了一种新的方法,用于处理困难和大的问题,通过利用智能优化技术的一些组成部分。现在,让·Karishma和H. Kumar智能系统与应用18(2023)2002194∑=i、ji,k我j,kk=1i,k我j=1l闪烁=k我,我我0,否则我我我表3任务分配模式。任务t1t 2t 3t 4处理器p3p 2p 1p 2算法1:初始化r,n,ω,β β δ1δ,ITC M,E M包括完成时间、资源利用率、成本和能耗在内的各种度量。Haris和Zubair(2022)开发了一种称为MMHHO的有效混合优化技术,以增强云网络中的负载平衡。3. 粒子群优化为了获得肯尼迪优化问题的最优结果,2:01,2,,2C C我JREberhart(1995)提出了一种新的启发式算法PSO。这是一个3:≤最大值xcij-cij,ifiscin=j、、一种由鸟群NITCCM= [c′ ] ={i j和鱼群。 Marini等人(2015)将PSO定义为全局最优-4:结束i、j0,否则一种应用于解决问题的最佳解决方案的技术5:生成... 联系我们6:对于第k个聚类(1≤k≤n),7:通过使用等式(1)计算第k个聚类的初始聚类质心Cd,k。(12)8:结束9:初始化每个质心的初始速度。10:阶段I:使用PSO算法形成最终质心11:如果未达到PSO的停止标准,12:对于第k个粒子(1≤k≤n),图13:通过使用等式13来评估每个粒子的适应度值f Cd。(13) 14:根据适应度值计算每个粒子的gbest 15:根据适应度值计算每个粒子的pbest 16:通过使用等式16更新粒子的速度。(十五)17:通过使用等式17更新每个聚类质心的位置。(16)18:结束十九:end if二十:计算任务ti和更新的集群质心Cdk之间的距离di,k,如下:它是多功能空间中的一个点。粒子群算法中的粒子遵循自然相似性,具有速度和位置两个特征.根据它们的位置(考虑的解决方案)和速度,允许粒子在多功能搜索空间中移动,所有粒子都在可用的搜索空间中寻找食 物。 每个 粒子 的最 佳位 置(Pbest ) 和另 一个 粒子 的最 佳位 置(Gbest)都有助于确定每个粒子在搜索空间中的位置,并且一旦粒子发现其到食物位置的最佳路径,则它通过吸引其他粒子来确保其他粒子遵循相同的最佳路径。适应度函数确定最优路径。由于所有粒子都移动到最优解,因此它们的Pbest和Gbest结果会更新。现在,所有这些粒子都以最佳方式到达目的地。在这个过程中,每只鸟都被视为一个单独的粒子。所以,第二十一章:2i,krj=1(c′-cdk,j)2每个质点都有它的位置和速度。PSO是一个迭代的亲,cess,其中每个粒子更新其速度和位置二十二:通过将每个任务分配到其最近的集群质心来生成新的集群第二阶段:分配更新的组群根据其以往的经验和邻国的经验的23:获得新的执行成本矩阵XNECM= [e′ ]通过融合属于同一簇的任务。24:对T= {ti,t2,t3,...,tn},因此任务执行成本为每个粒子的位置yi通过在ui上加上粒子的速度来更新,如下所示:按降序排列这里,每个t i的执行成本计算如下:i=y i+ u i。(一)E′ =∑n(e′ . λk)25:将t j分配给处理器p k,其中e′ 在所有处理器上是最小的,并且没有违反系统约束。26:从NECM28:将ti分配给剩余的处理器pk,使得f(ti)=e′,kλk+∑i-1∑xj,l. c′j。μk,l在所有处理器上最小,每一个粒子的速度都以如下方式更新u(it +1)= ω × ui(t)+ β1× δ1×(Pi(t)-y(it))+ β2× δ2×(G(it)-y(it)).(二)其中,给定粒子的惯性权重ω用于限制先前速度对当前速度的影响;β1和β2分别表示认知和社会学习因子;δ1&δ2是[0,1]之间的随机数;u(t)表示时间t处的速度;P(t)和将Ti分配给处理器Pk不违反任何系统约束。其中,xj,l={1,如果tj被分配给处理器plG(it)分别表示第i个粒子的局部最佳和全局最佳适应度,时间t;y(t)表示粒子在时间t的位置;P(t)-y(t)表示29:结束30:存储任务集群及其分配位置。31:通过方程计算系统的SC、RT和F ti (5)、(8)和(10)。元分析学Ahmad et al.(2016)提出了一种结合启发式和GA的新调度方法。Babukartik和Dhavachelvan(2012)提出了一种蚁群算法和布谷鸟搜索的混合技术,以最小化最大完工时间。研究人员在工作中提出了一些混合PSO调度技术。表2列出了其中的一些。除此之外,作者Ferrandi等人(2010)使用ACO技术来映射异构系统上的任务和通信此外,他们确实将他们的方法与其他模拟退火,禁 忌 搜 索 和 GA 进 行 了 比 较 , 以 达 到 最 佳 值 。 在 云 计 算 中 ,Navimipour和Milani(2015)提出了一种新的基于布谷鸟搜索技术的任务Attiya和Hamam(2006)基于模拟退火技术提出了一种分布式环境下的任务分配模型,以提高系统的可靠性;Walia等(2021)基于GA和FPA技术提出了一种新的混合调度模型,并与现有的调度方法进行了性能认知成分和G(it)-y(it)是社会成分。 这些迭代由方程定义。(1) 以及(2)重复它们自己直到满足预扣标准。停止标准可以是数字-迭代的BER或解的收敛或预定义的适应值。PSO也有一些元参数,如其他元算法,如方程所示。(2)其控制其工作以解决任何优化问题。4. 符号和问题表述4.1. 符号使用的符号如下所述:指数i,j任务索引,i,j= 1,2,. Rk,l处理器/集群索引,k,l= 1,2,. n个参数程序中的第ii个任务i= 1,2,.. RDCS中的第pk个处理器,k= 1,2,. nT= {ti:i= 1,2,. r}r≥2个任务的集合P= {p,k:k= 1,2,. n}n≥2个处理器的集合ei,kti onpk的(接下页)DKarishma和H. Kumar智能系统与应用18(2023)2002195i、ji,k∑=为nRSCpmlR N RN∑∑(续)ci,jti和tj之间的任务间通信开销SC= ∑ ∑e i,k<$x i,k+ ∑c i,j<$x i,k <$x j,l。(五)i=1k=1i,j=1k=1ITCCM=[ci,j]任务间通信成本矩阵XNITCC M=[c′]新的任务间通信成本矩阵k闪烁=lnNE C M=[e′新的执行成本矩阵X第k个任务群集第k个簇质心PSO中粒子的适应度值受试者x i,k= 1i。(六)k=1xi,k∈ {0, 1}i,k(7)G(it)第i个粒子在时间t的全局最佳位置其中,xi k={1,如果任务ti被分配给pkP(t)第i个粒子在时间t的个人最佳位置,0,否则我4.2. 任务调度任务调度是一种由服务用户将所呈现的作业/任务分配或指派给高效且可访问的枚举网络(诸如处理器或虚拟机)以在授权的时间轴中执行调度参数的优化的技术。一个有效的任务分配机制是非常必要的,以提高生产力的情境计算模型。到为了更好地理解调度技术,让我们考虑,r根据约束(6),每个模块必须被分配给仅一个处理器,并且约束(7)保证xi,k是二进制变量。4.6. 响应时间(RT)系统的RT是每个处理器执行的计算量的函数。该函数考虑了处理器具有过多的计算和通信时间。系统的RT表示为:独立任务T= {t1,t2,. t r},并且在执行之前,不释放所分配的资源,并且P= {p1,p2,... pn}组可用的n个处理器RT=max∑rei,k<$xi,k+∑∑ci,j<$xi,k<$xj,l好吧(八)以执行由用户报告的这些任务。这将确保以nr种方式将报告的任务分配给可用的处理器。几位作者已经测试和证明了各种调度机制,以达到最佳解决方案。1≤k≤ni=14.7. 流动时间(Fti)i、j 1K1k闪烁=l完成任务的处理器对于可用机器或处理器内的重要映射起关键作用。在这个模型中,我们的动机是产生一个分配机制,将续集在底层计算资源的最佳利用率,并完成任务的执行,以更少的时间和成本。给定的表3表示由r个任务分配n个4.3. 执行费用(英、汉)执行成本是正在执行的任务ti在处理器pk上完成的总工作量。每个任务的清晰执行成本ei,k已经计划的任务的整个完成时间被称为流程时间(Hasan和Al-Rizzo,2019)。它是处理和等待时间的总和。因为它导致资源的公平使用,它已被发现是工业中一个重要的现实目标。Fti计算为:F ti =Cti- Rti(9)其中,Cti是任务执行完成的时间表示准备执行任务的时间平均流动时间定义为:F t= 1 ∑F t。(十)R任务ti在处理器pk上的成本(TEC)确定如下:我我i=1R nTE C=ei,k. x i,k.(三)i=1k=14.8. 相对百分比偏差(RPD)术语RPD(Kumar和Tyagi,2020)用于描述有效性。每个任务ti的成本取决于决策变量xi,k.其中,如果任务ti被调度为pk,则xi,k的值是一个单位。4.4. 通信费用(CC)任务间通信成本(ITCC)是指一个给定的算法的效率的基础上减少执行成本。它 是确定所提出算法性能的最基本参数之一RP Dl=.S Crml-S Cpml)×100。( 十一)其中,SCpm和SCrm 是第l个问题LlREC M=[ei,k]EX矩阵⎭Karishma和H. Kumar智能系统与应用18(2023)2002196C=Rni、ji,kj,lr}且P= {p1,p2,p3,...,pn},被考虑。其中,T表示指数,在任务ti和tj之间传输数据所需的成本(如果它们处于打开状态)单独的处理器。如果任务ti和tj被分配给同一个处理器,则它们之间的ITCC(ci ,j)为零。清晰通信成本ci ,j存储在矩阵XITCC M= [ci ,j]中。TITCC可计算为:分别由所提出的技术和参考技术接收4.9. 问题陈述TITC∑ ∑c. X. X.(四)=为不为了组织DCS中的任务调度问题,T ={t1,t2,t3,.,i、j 1K1k闪烁=l4.5. 系统成本(SC)分布式环境下的任务调度以系统总开销最小为目标,其计算方法为EC与ITCC之和。 具有系统资源约束的SC被公式化为:pendent其中r>n。DCS中最常用的三个参数是:(a)执行成本(b)总执行时间和(c)平均流程时间。这里的目标是创建和利用一个任务分配机制,能够将处理器的总成本、流程时间和执行时间减少到最小。在这项工作中,任务分配问题由以下大纲考虑Karishma和H. Kumar智能系统与应用18(2023)2002197{,t,t34{t,t}1222Fig. 1. 所提出的算法的流程图。表4输入参数和相应的值。表5上述实例与现有技术的结果比较系统参数值惯性权重ω0.4-0.9EX样本参考文献使用技术任务处理器SC RTδ1和δ 2[0,1]β1和β21.50处理器故障率pk,λk[0.0003-0.00010]连接pk和pl,μk,l的通信链路故障率[0.0002-0.00012]最大迭代次数100在分布式系统中,我们根据实际情况假设一组由于DCS中涉及的处理器是异构的,因此每个处理器上的每个任务如果一个任务在离散处理器上执行,那么它1Topcuoglu等人。(2002年)该模型2基于列表的调度算法粒子群优化遗传{t3,t7}p1{t4, t6,p3t8}p 2{t1, t2,t5,t9,t10}{t3, t7,p2t10}p 1{t2,t 4,p3t 8,t 9}{t1, t5,t6},t p230 172203 128170 111•也不同,如果数据量通过不同的通信链路,那么它因此,系统的RT依赖于commu-阿克巴里和Rashidi(2016)算法{t2 7}p1t5,t6,p3,t8}执行和执行时间。系统的总成本取决于通信和执行成本。任务挖掘平均流动时间。3该模型粒子群优化模拟{t1}{t4, t6,p3t8}p 1{t1,t 2,p2t 3}{t5,t7}p154 88145 51•随着任务分配给处理器,它在该处理器上持续,直到程序阿提亚和03 TheDog(2006)退火{t6}p1{t3,t4}p3对于可重构性,我们忽略了任务和处理器的其他本质系统,如内存要求,最后····Karishma和H. Kumar智能系统与应用18(2023)2002198期限和先行关系。该模型粒子群优化{t5}第4页{t1,t 4}p 1{t5}p2{t3,t 6}p 360 21{t2}p4Karishma和H. Kumar智能系统与应用18(2023)2002199图二、任务在处理器上的执行成本(e i,k)。图3.第三章。任务之间的任务间通信成本(c i,j)。见图4。生成示例1的任务集群。图五. 示例1的最优任务集群调度。通过从任务集合f:T → P中创建一个函数到处理器集合来适当地调整任务到处理器的分配。 主要本文的目标是得到一个最优分配,通过将任务适当地分配到适当的处理器上,同时最大限度地利用资源,来降低RT、Fti下一节将介绍如何使用我们开发的方法解决任务调度问题。见图6。 实施例1的溶液图。见图7。 处理器上的任务执行成本(ei,k图八、任务之间的任务间通信成本(c i,j)。见图9。生成示例2的任务集群。Karishma和H. Kumar智能系统与应用18(2023)20021910见图10。实例2的最优任务簇调度。见图11。 实施例2的溶液图。图12个。处理器上的任务执行成本(e i,k)。5. 所提出的技术所开发的技术侧重于解决任务调度问题,以减少RT,SC和Fti。我们考虑一个任务活动状态是当处理器被占用在执行某些任务时,空闲状态是当没有任务被分配给处理器时。通常,在分布式系统中,调度机制的目标是在处理器上分散负载及其利用率最大化,同时使总任务执行时间达到其最小值。该模型中的PSO技术被视为一个确定DCS中任务分配的优化目标。任务分配问题是一个NP完全问题,这就是为什么基于粒子群算法的开发,以提高系统的性能。本文选择PSO是因为它是解决以下问题的最佳方法图13岁任务之间的任务间通信成本(c i,j)。见图14。 已生成example3的任务集群。图15. 示例3的最优任务集群调度。图16. 实施例3的溶液图。任何尺寸(Brownlee,2011)。除了在大多数测试用例中提供比任何其他技术更好的解决方案质量之外,它在给定的模型中,为了使时间消耗最小化,在任务执行时间最小化的同时,最大任务执行时间也最小化。随着粒子的进化,群体Karishma和H. Kumar智能系统与应用18(2023)20021911RKFk表6将所提出的方法与Kumar和Tyagi(2020)的文章进行比较。Cd0=1∑c'. ν i,k,k=1,2,n(12)KS. 号模型的大小(r,n)Kumar和Tyagi(2020年)该模型RPDi、jnki,j=1其中,vi k={1,如果任务ti属于集群clk,0,否则得到了该模型便于在合理的时间内求解任意规模的DCS问题。在该算法中,初始质心被认为是粒子,粒子群算法升级,使最终的质心。然后,我们使用欧氏距离函数(ED)生成最终质心的任务簇,并通过启发式方法将它们分配给处理器。这种基于粒子群优化的任务分配方法寻求最优的任务分配模式,减少任务簇的执行时间和执行成本。所提出的模型的描述如下:5.1. 初始质心最初,我们随机生成nk表示第k个簇中的任务为了初始化初始任务集群的“n”个集群质心,将迭代次数设置为0并且创建初始质心Cd 0 =(cd k,1,cd k,2. cdk,r)∈Rr如下:5.2. 适应度函数粒子群算法中需要优化的目标函数称为适应度函数。该函数为种群中的每个粒子分配一个特定值,该值在解决方案中表现出Gbest和Pbest的优越性。在目前的工作中,质心被视为一个群体粒子和方程。(13),可以找到每个粒子的适应度值。fCd=ma x(1)。(十三)其中,表7比较粒子群算法、遗传算法和启发式算法之间的RT结果。S. 号问题的大小(r,n)不同方法图17. 表6的图示。SC RTSC RT1(三,二)151414137.1422(四、三)2719271903(10,4)154851547710.3894(9,3)109442396341513.6035(6,4)8036602133.3336(四、三)3023302307(10(3)22413020312810.3448(9,3)109442396341513.6039(10,4)15565154770.64910(6,4)8436602140启发式方法GAPSO1(三,二)2414132(四、三)2323233(10,4)20065774(9,3)4794234155(6,4)3621216(四、三)1919197(10(3)1721301288(8,3)88111889(10,4)200857710(8,3)54444611(8,4)37373512(5,3)706663Karishma和H. Kumar智能系统与应用18(2023)20021910图18. 表7的图示。表8不同探索性文章的输出比较。S. 号参考文献模型尺寸(r,n)使用的技术通过参考技术通过建议技术RPDSC RT SC RT1Lo(1988)(4,3)图论方法38 30 35 30 8.572Elsadek和Wells(1999)(9,3)启发式方法1372 479 963 415 42.473Akbari和Rashidi(2016)(8,3)遗传算法170 111 154 88 10.384Kopiddakis等人(1997)(3,2)启发式方法30241413114.285Sarje和Sagar(1991)(4,3)启发式方法30 23 30 23 06Shatz等人(1992)(4,4)启发式方法3321232143.477Attiya和Hamam(2006)(6,4)模拟退火方法145 51 60 21 141.668李等人。(1992)(6,4)Stone的网络流方法98 39 86 3913.959Kumar等人(2019)(6,4)遗传算法60 21 60 21 010Yadav等人。(2011)(9,3)启发式方法137247996341542.4711Kumar and Tyagi(2019)(6,4)聚类方法84 36 60 21 4012Kartik和Murthy(1997)(4,3)粒子群优化27 19 27 19 013Topcuoglu等人基于列表的调度算法23017220312813.3014Kaushal and Kumar(2013)(10,4)启发式方法400 200 154 77 159.7415Gupta and Yadav(2015)(9,3)启发式方法2525 1221.9 2475.70 1181.20 1.9916Kumar和Tyagi(2020)(6,4)遗传算法60 21 60 21 017Govil and Kumar(2011)(10,4)启发式方法163 89 154 77 5.8418Yadav等人。(2013)(9,3)启发法2563.91272.62475.701181.203.5619Kumar等人。(2018)(9,3)聚类方法109442296341513.6020Kumar and Yadav(2012)(8,3)启发式方法83 54 76 46 9.2121Safari and Khorsand(2018)(10,3)启发式方法188 159 156 96 20.5122Quan等人。(2019)(10,3)ISAECC23613120312816.2523Tian等人。(2020)(10,3)聚类方法38926132717818.9624Chauhan等人。(2022)(9,3)遗传算法109442296341513.6025Gupta等人。基于列表的调度算法23813621110912.792019年12月31日F∑r (∑r(一)C′CD(2)k1 2n(14)分别K=i=1j=1吉-k,j、=,、、......u(t+ 1)=ω×u(t)+β1×δ1×(P(t)-Cd(t))+β2×δ2×(G(t)-Cd(t))。k k k k在Karishma和H. Kumar智能系统与应用18(2023)20021910KKK使用粒子群算法更新这些初始质心之前,先初始化粒子的速度。根据适应度值,K K(十五)每个粒子,获得更新速度的Gbest和Pbest,Cd(t +1)=Cd(t)+u(t +1)。(十六)每个粒子的位置,即, 聚类质心,通过等式( 十五)及(十六)重复上述过程,直到达到终止条件Karishma和H. Kumar智能系统与应用18(2023)20021911D=R (c-图19. 表8的图示。初始化算法的基本要求,如惯性权重、加速常数、随机常数、聚类数等。为了解决这类特殊的分配问题,许多学者提出了基于粒子群算法的分配机制,在分配过程中,惯性权重(ω)要么线性递减,要么保持不变。根据这项研究,全局搜索和局部搜索是大规模搜索的结果惯性值,即ω>1和小的惯性值,即ω1分别。<作为已知的,在DCS中的任务分配已被认为是在NP-hard问题的划分和他们的复杂性进一步升级部署的处理器和提交的任务的增量。因此,平衡局部搜索和全局搜索被认为是重要的,并且为此,在本工作中,我们部署了惯性权重ω,如在等式中计算的。(十七)、5.4. 停止标准停止条件有助于永远停止PSO执行。 为了获得更好的解决方案的质量,PSO算法运行,直到它收敛,到目前为止找到的最终最佳解决方案是输出。为了确定这种收敛行为,需要一个停止准则。对于任何进化技术,流行的停止标准是:(a)一定且足够大的迭代次数(b)如果在两个连续的全局最佳解改进之间经历的迭代次数超过一定次数。在目前的工作中,我们确实使用了(a)和(b)类型的停止标准。本模型也详细作为一个算法。在所提出的算法中包括以下步骤:ω=ωmax-iter。马克西特。)(ωmax-ωmin)。(十七)最后给出了基于粒子群优化算法的流程图图1其中,ωmax=最终重量;ωmin=初始重量;Maxiter。为最大迭代次数; Iter. =当前迭代次数5.3. 任务组的形成和分配聚类是一种基于合适的相似性度量将组划分为不同聚类的方法,使得同一聚类内的数据具有高相似度,而不同聚类之间的数据具有弱相似度。分布式环境下集群系统开发的主要目标是降低集群系
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功