| 基于粒子群优化的多处理器任务调度算法 |
| |
| 引用本文： | 陈养平,王来雄,黄士坦. 基于粒子群优化的多处理器任务调度算法[J]. 吉林大学学报(信息科学版), 2007, 25(3): 277-285 |
| |
| 作者姓名： | 陈养平 王来雄 黄士坦 |
| |
| 作者单位： | 西安微电子技术研究所,西安,710075;西安微电子技术研究所,西安,710075;西安微电子技术研究所,西安,710075 |
| |
| 基金项目： | 国防预研基金资助项目(413160201) |
| |
| 摘 要： | 对于NP(Non-Polynomial)完全问题,现有的算法主要是启发式算法,性能还有待提高。基于粒子群优化智能算法,提出一种新的任务调度算法,目标是在满足任务之间优先关系的条件下,使所有任务整体完成时间最小。算法将粒子位置和任务高度作为任务的优先级,通过表调度技术生成有效的调度方案,并将调度方案对应的调度长度作为粒子的适应值。首先随机产生一群粒子,然后通过使用全局模型的粒子状态更新策略不断迭代,获得可以接受的任务调度方案。仿真实验结果表明,与遗传算法相比,调度长度提高14.7%,运行时间缩短近一半,特别适合于求解规模较大的多处理器任务调度问题。
|
| 关 键 词： | 粒子群优化算法 表启发式技术 多处理器系统 任务调度 |
| 文章编号： | 1671-5896（2007）03-0277439 |
| 收稿时间： | 2006-11-02 |
| 修稿时间： | 2006-11-02 |
Task Scheduling Algorithm for Multiprocessor Based on Particle Swarm Optimization |
| |
| CHEN Yang-ping,WANG Lai-xiong,HUANG Shi-tan. Task Scheduling Algorithm for Multiprocessor Based on Particle Swarm Optimization[J]. Journal of Jilin University:Information Sci Ed, 2007, 25(3): 277-285 |
| |
| Authors: | CHEN Yang-ping WANG Lai-xiong HUANG Shi-tan |
| |
| Affiliation: | Xi'an Microelectronic Technique Institute;Xi'an 710075;China |
| |
| Abstract: | Efficient task scheduling technique is one of the key issues in exploring multiprocessor 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 hei... |
| |
| Keywords: | particle swarm optimization list heuristic technique multiprocessor system task scheduling |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
