混合自适应粒子群工作流调度优化算法  

Hybrid adaptive particle swarm optimization algorithm for workflow scheduling

作　　者：马学森[1,2] 许雪梅 蒋功辉 乔焰 周天保 MA Xuesen;XU Xuemei;JIANG Gonghui;QIAO Yan;ZHOU Tianbao(School of Computer Science and Information Engineering,Hefei University of Technology,Hefei Anhui 230601,China;Engineering Research Center of Safety Critical Industrial Measurement and Control Technology,Ministry of Education(Hefei University of Technology),Hefei Anhui 230009,China)

机构地区：[1]合肥工业大学计算机与信息学院,合肥230601 [2]安全关键工业测控技术教育部工程研究中心(合肥工业大学),合肥230009

出　　处：《计算机应用》2023年第2期474-483,共10页journal of Computer Applications

基　　金：国家重点研发计划项目(2020YFC1512601)。

摘　　要：针对具有截止期的云工作流完成时间与执行成本冲突的问题,提出一种混合自适应粒子群工作流调度优化算法(HAPSO)。首先,基于截止期建立有向无环图(DAG)云工作流调度模型;然后,通过范数理想点与自适应权重的结合,将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题;最后,在粒子群优化(PSO)算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法(FA)和粒子越界处理方法,从而平衡粒子群的全局搜索与局部搜索能力,进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法(WPSO)、蚁群算法(ACO)和HAPSO的优化结果。实验结果表明,HAPSO在权衡工作流(30~300任务数)完成时间与执行成本的多目标函数值上降低了40.9%~81.1%,HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外,HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果,验证了HAPSO的普适性。Aiming at the conflict between the makespan and execution cost of cloud workflows with deadlines,a Hybrid Adaptive Particle Swarm Optimization algorithm for workflow scheduling(HAPSO)was proposed.Firstly,a Directed Acyclic Graph(DAG)cloud workflow scheduling model was established based on deadlines.Secondly,through the combination of norm ideal points and adaptive weights,the DAG scheduling model was transformed into a multi-objective optimization problem that weighs DAG makespan and execution cost.Finally,based on Particle Swarm Optimization(PSO)algorithm,the adaptive inertia weight,the adaptive learning factors,the probability switching mechanism of flower pollination algorithm,Firefly Algorithm(FA)and the particle out-of-bound processing method were added to balance the global search ability and the local search ability of the particle swarm,and then to solve the objective optimization problem of DAG makespan and execution cost.The optimization results of PSO,Weight Particle Swarm Optimization(WPSO),Ant Colony Optimization(ACO)and HAPSO were compared and analyzed in the experiment.Experimental results show that HAPSO reduces the multi-objective function value by 40.9% to 81.1% that weighs the makespan and execution cost of workflow(30~300 tasks),and HAPSO effectively weighs the makespan and execution cost with the constraints of workflow deadlines.In addition,HAPSO also has a good effect on the single objective of reducing the makespan or execution cost,which verifies the universality of HAPSO.

关 键 词：云工作流 调度 截止期 自适应权重 粒子群优化算法 目标优化 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]