基于粒子群优化的多处理器任务调度算法

Task Scheduling Algorithm for Multiprocessor Based on Particle Swarm Optimization

对于NP(Non-Polynomial)完全问题,现有的算法主要是启发式算法,性能还有待提高。基于粒子群优化智能算法,提出一种新的任务调度算法,目标是在满足任务之间优先关系的条件下,使所有任务整体完成时间最小。算法将粒子位置和任务高度作为任务的优先级,通过表调度技术生成有效的调度方案,并将调度方案对应的调度长度作为粒子的适应值。首先随机产生一群粒子,然后通过使用全局模型的粒子状态更新策略不断迭代,获得可以接受的任务调度方案。仿真实验结果表明,与遗传算法相比,调度长度提高14.7%,运行时间缩短近一半,特别适合于求解规模较大的多处理器任务调度问题。

Efficient task scheduling technique is one of the key issues in exploring muhiprocessor systems＇ computing power. The existing methods for this NP （Non-Polynomial） completed problem are mainly heuristic algorithms, which still have room for improvement. A novel task scheduling algorithm is proposed based on particle swarm optimization, which is aiming to minimize the overall finish time of all tasks under their dependence relationships. The task priorities are based on both the particle position and the task height, and the scheduling schemes are formed with the list scheduling techniques, while the schedule length is used as particle＇s fitness value. It first initializes a swarm of particles, and then updates the particle through the global model strategy to reach the acceptable solution. Simulation results show that the schedule length of the proposed algorithm is on the average 14. 7% better than that of the genetic algorithms, but its execution time is almost half of the latter, thus it is especially suitable to the large scale task scheduling.