多目标服务工作流混合粒子群调度算法

Hybrid particle swarm optimization algorithm for multi-objective scheduling in service-workflows

针对NP难的服务工作流时间-费用优化问题,提出多目标混合粒子群算法(HMOPSO)来优化工作流调度问题.HMOPSO算法包括:初始种群生成、适应值分配、种群多样性保持、外部种群和极值选择.通过分析服务工作流的特征,构建有效的粒子结构使之离散化;通过设定单目标最优初始解,优化初始种群;通过引入外部种群和基于小生境技术的网格方法,获得分布均匀的Pareto最优解集.实验结果表明,HMOPSO具有更快的收敛速度和更好的寻优能力,并且在不同特征的问题实例上获得了数量众多、分布均匀、有较高质量的Pareto最优解集.

A multi-objective hybrid PSO（particle swarm optimization） method is proposed for the time-cost optimization problem in service-workflows,a NP-Hard problem.Characteristics of service-workflows are analyzed.Discrete particles are constructed.HMOPSO is included： initial population generation,fitness distribution,population diversity maintainance,outside population and extreme choice.The initial population is generated by setting optimal solutions to single-objective problems.To obtain an evenly distributed Pareto set,an outside population and a meshing method based on the niche technique are introduced.Experimental results show that the proposed algorithm is efficient and effective for the considered problem.Many evenly distributed Pareto sets with high quality are obtained for various characteristic instances.