同构计算环境中DAG任务图的调度算法

摘要：

在并行多处理机系统中,任务调度算法是保证整个系统性能的关键.通常用有向无环图(DAG)表示任务间的依赖关系.将粒子群算法应用于组合优化领域,构造了求解任务调度问题的离散粒子群算法.算法采用基于分组的思想对粒子进行直接编码,借鉴遗传算法的思想,将粒子个体最优及全局最优解分别采用交又操作作用到当前粒子位置上,使粒子不断向最优位置逼近;同时在每次迭代过程中引入变异操作以提高粒子群体多样性.实验结果表明,算法在不同规模的任务调度问题中均取得了良好的效果.

关键词：任务调度、粒子群算法、多处理机系统、同构环境、组合优化

所属期刊栏目：30

分类号：TP301(计算技术、计算机技术)

资助基金：山东省自然科学基金项目2004ZX14;聊城大学自然科学基金项目X051033

在线出版日期：2009-04-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：668-670