摘要
为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法-PSOASA算法.PSOASA算法以求得任务最短完成时间为目标,首先采用整数矩阵对粒子进行编码,并定义交换操作更新粒子状态,实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题,同时引入模拟退火算法,克服粒子群算法的"早熟"收敛现象,避免求得的解陷入局部最优.实验结果表明,PSOASA算法的执行效率优于目前广泛采用的遗传算法,有效地降低任务执行时间,减少了迭代次数,适用于异构多处理器环境大规模任务调度.
A task scheduling method named PSOASA which based on particle swarm optimization algorithm was proposed to improve the execution efficiency of heterogeneous multiprocessor task scheduling and make full use of the performance of the processor parallel. PSOASA algorithm takes the shortest completion time as the goal. Firstly, the algorithm realizes the mapping from searching space to discrete space which makes the Particle swarm optimization algorithm applied to the discrete heterogeneous multiprocessor task scheduling problem. At the same time, the simulated annealing algorithm is introduced to overcome the particle swarm algorithm ＂premature＂ convergence phenomenon and avoid the solution trapping into the local optimum. The experimental results show that the execution efficiency of the PSOASA was superior to the Genetic Algorithm, and reduces much of the execution time of tasks. It is applicable to large-scale task scheduling in heterogeneous multiprocessor environment.
出处
《小型微型计算机系统》
CSCD
北大核心
2013年第5期1154-1157,共4页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61003036
60873138)资助
黑龙江省自然科学基金项目(F201124)资助
关键词
异构多处理器
任务调度
PSO算法
模拟退火
遗传算法
heterogeneous multi-processor
PSO
scheduling algorithm
simulated annealing
genetic algorithm
