求解独立任务调度问题的改进粒子群算法

Improved Particle Swarm Optimization Algorithms for Independent Task Scheduling

独立任务调度问题是分布式系统中的一个NP难题.提出了基于实数编码和基于机器编码的两种改进粒子群算法.前者利用协同子群进化的方式进行问题寻优,后者通过重新定义粒子的位置更新方法,使粒子群算法更好地应用于组合优化问题.仿真结果表明,与遗传算法和基本粒子群算法相比,改进算法具有更快的收敛特性和更好的求解质量.

The independent task scheduling problem is known to be NP-complete in the field of distributed processing. Two particle swarm optimization （PSO） algorithms are presented, which are PSO with real number-based representation and PSO with machine-based representation. The former algorithm finds global optimization through co-evolution of subswarms, while the latter one can be used in combinatorial optimization finds better by redefining the updating formula of particle positions. The experimental results compared with genetic algorithm and basic PSO algorithm manifest that the improved algorithms improve not only the speed of convergence, but also the quality of solutions.