摘要
文章研究了考虑负载平衡、有优先约束的n个任务在m个同等处理机上处理,使总完成时间最小的分布式任务调度问题。对两个以上处理机的这类问题便是NP难题,因此以往都是用启发式算法来求解。文章首次提出了使用遗传算法来解决该类问题,设计了相应的编码方法和适应值评估方法,并用一个一维向量来表示任务间的优先关系。仿真结果证实了算法的有效性。
In this paper,a kind of distributed task scheduling problems is studied,in which load balance and prece-dence constraint are taken account of.This kind of problems is NP-hard problem and has only heuristic algorithm solu-tions.Genetic algorithm is first applied to this kind of problems in this paper.The authors not only design corresponding encoding and fitness -evaluating methods,but also denote the precedence constraint with a one-dimension vector.The simulation result shows the algorithm's efficiency.
出处
《计算机工程与应用》
CSCD
北大核心
2003年第12期86-88,共3页
Computer Engineering and Applications
基金
国家自然科学基金项目(编号:60075018)
关键词
遗传算法
分布式调度
优先约束
负载平衡
Genetic Algorithm,Distributed Task Scheduling,Precedence Constraint ,Load Balance