ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (9): 1990-1999.doi: 10.7544/issn1000-1239.2016.20151175

• 人工智能 • 上一篇    下一篇

任务调度算法中新的自适应惯性权重计算方法

李学俊,徐佳,朱二周,张以文   

  1. (安徽大学计算机科学与技术学院 合肥 230601) (xjli@ahu.edu.cn)
  • 出版日期: 2016-09-01
  • 基金资助: 
    国家自然科学基金项目(61300169);安徽省教育厅自然科学研究重点项目(KJ2016A024)

A Novel Computation Method for Adaptive Inertia Weight of Task Scheduling Algorithm

Li Xuejun, Xu Jia, Zhu Erzhou, Zhang Yiwen   

  1. (School of Computer Science and Technology, Anhui University, Hefei 230601)
  • Online: 2016-09-01

摘要: 粒子群算法(particle swarm optimization, PSO)是解决云计算环境中工作流系统的任务调度优化问题的主流智能算法.然而基于传统自适应惯性权重的粒子群任务调度算法易陷入局部最优,导致调度方案的执行时间与费用较高.因此,通过改进单个粒子的成功值计算方法,提出了一种新的自适应惯性权重计算方法NAIWPSO(new adaptive inertia weight based particle swarm optimization).该方法通过比较每个粒子的适应度与全局最优值,可以更加精确描述粒子状态,进而提高了权重的自适应性.在新惯性权重基础上,提出了一种解决云工作流系统中任务调度优化问题的改进粒子群算法.新权重可以更准确的调整粒子速度,使算法更好地平衡粒子全局与局部搜索,避免陷入局部最优,获得执行费用更优的调度方案.实验表明,与5种已有惯性权重算法比较,新算法收敛稳定、适应度最低、执行费用平均减少18%.

关键词: 云计算, 工作流, 任务调度, 粒子群算法, 惯性权重

Abstract: Particle swarm optimization (PSO) is a primary intelligence algorithm to solve task scheduling problem for workflow systems in cloud computing. The inertia weight is one of the most important parameters to achieve a balance between the global and local search in PSO algorithm. However, traditional adaptive inertia weight-based PSO task scheduling algorithms usually get local optimal and cause longer execution time and higher cost for scheduling plan. The traditional adaptive inertia weight does not comprehensively represent the information of particle position, and then cannot make a suitable balance between global and local search. Hence, a novel computation method for adaptive inertia weight is proposed to improve the computation method of success value of each particle. This method shows the position state of each particle more accurately and then improves the adaptability of inertia weight by comparing the fitness of each particle with the global best particle. Then a new inertia weight-based PSO algorithm is presented to solve task scheduling problem for cloud workflow systems. The novel weight can adjust the particle velocity more correctly so that the algorithm avoids premature convergence by a proper balance between local and global search. Comparing our new adaptive inertia weight with other five traditional inertia weights (viz. constant, index decreasing, linear decreasing, random, and adaptive inertia weight), the results show that our new adaptive inertia weight-based scheduling algorithm can always achieve stable convergence speed, the optimal fitness and execution cost of the scheduling plan (i.e. roughly 18% reduction of execution cost).

Key words: cloud computing, workflow, task scheduling, particle swarm optimization (PSO), inertia weight

中图分类号: