基于遗传算法的考虑优先约束和负载平衡的多任务调度

Multi-task Sheduling with Precedence Constraint and Load Balance Based on Genetic Algorithm

文章研究了考虑负载平衡、有优先约束的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.