Heterogeneous multiprocessor task scheduling algorithm based on PSO
基于粒子群优化的异构多处理器任务调度算法

This paper proposed a task scheduling algorithm named FPSOTTS, which based on particle swarm optimization to improve the task scheduling execution efficiency of heterogeneous multi-processor and make the full use of the performance of parallel multi processors. FPSOTTS algorithm took the shortest task completion time as the goal. Firstly, the FPSOTTS algorithm realized the mapping from particle searching space to discrete space by building new coding method and particle update formula. And the mapping above made the continuous particle swarm optimization algorithm apply to the discrete heterogeneous multiprocessor task scheduling problem probably. At the same time, the FPSOTTS algorithm overcame the particle swarm algorithm premature convergence phenomenon and avoided the obtained solution trapping into the local optimum by introducing tabu search algorithm for local search. The experimental results show that the execution efficiency of FPSOTTS algorithm is superior to Min-min algorithm and genetic algorithm for reducing the task execution time effectively. FPSOTTS algorithm provides a better solution to the task scheduling problems of heterogeneous multi-processor. And it is suitable for large scale parallel task scheduling.