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

Heterogeneous multiprocessor task scheduling algorithm based on PSO

作　　者：李静梅[1] 张博 王雪[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机应用研究》2012年第10期3621-3624,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61003036;60873138);黑龙江省自然科学基金资助项目(F201124)

摘　　要：为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题;同时通过引入禁忌算法进行局部搜索,克服粒子群算法的早熟收敛现象,避免陷入局部最优。实验结果表明,FPSOTTS算法的执行效率优于Min-min算法和遗传算法,有效地降低任务的执行时间。FP-SOTTS算法很好地解决了异构多处理器任务调度问题,并且适合于大规模并行任务调度。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.

关 键 词：异构多处理器 任务调度 粒子群优化算法 禁忌搜索 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]