基于改进蚁群算法的多处理器任务调度仿真  

Simulation of Multiprocessor System Task Scheduling Based on Improved Ant Colony Algorithm

作　　者：刘进[1] 刘春[2] 陈家佳[1] 

机构地区：[1]重庆邮电大学经济管理学院,重庆南岸400065 [2]四川建筑职业技术学院网络管理中心,四川德阳618000

出　　处：《计算机仿真》2014年第6期334-337,共4页Computer Simulation

基　　金：重庆市2013年高等学校教学改革研究重点项目(132004);重庆邮电大学自然科学基金项目(A2011-28)

摘　　要：研究多处理器系统任务调度优化问题。随着实时应用需求的不断提高,对多处理器任务调度系统提出了更高的性能要求。传统算法把调度准确性放在第一位考虑,实时性不能满足当前要求。在确保准确性的前提下,为了提高多处理器任务调度的实时性,提出一种基于改进蚁群算法的多处理器系统任务调度算法(GA-ACO)。首先建立多处理器系统任务调度数学模型,然后引入遗传算法快速找到多处理任务调度可行解,最后将遗传算法找到的可行解转换成蚁群优化算法初始信息素,并通过蚁群算法的局部寻优和正反馈机制找到多处理系统的任务调度最优解。仿真结果表明,改进算法不仅具有遗传算法全局寻优能力,同时兼有蚁群算法的局部寻优和正反馈能力,相对于单一寻优算法,可以更快找到任务的调度方案,满足实时性的要求,加快了任务执行速度,可以合理、有效的对多处理器任务分配和调度。This paper studied the optimization of muhiprocessor system task scheduling. With the constantly improving of real - time application requirements, the multiprocessor system task scheduling was required higher performance. The traditional algorithm put scheduling accuracy as the first consideration, but real - time performance cannot satisfy the current requirements. On the premise of ensuring accuracy, in order to improve the real - time performance of multiprocessor task scheduling, this paper presented an improved muhiproeessor system task scheduling algorithm （GA -the ACO） based on ant colony algorithm. A mathematical model of multiprocessor system task scheduling was established firstly. Then a genetic algorithm was introduced to find feasible solution of muhiprocessor task scheduling quickly. At last, the feasible solution found by genetic algorithm was converted to the initial phero- mone of ant colony optimization algorithm, and the optimal solution of muhiprocessor system task scheduling was found out through the local optimization and the positive feedback mechanism of ant colony algorithm. The results of simulation show that the improved algorithm has not only the ability of global optimization of genetic algorithm, but also the ability of local optimization and positive feedback of ant colony algorithm at the same time. Compared with single optimization algorithm, this algorithm can find the task scheduling scheme more quickly, meet the requirements of realtime, and speed up the task execution.

关 键 词：多处理器 任务调度 遗传算法 蚁群算法 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]