任务分配与调度中的遗传算法:知识表示与遗传算子研究  

Representation and Genetic Operators in Tasks Matching & Scheduling by Genetic Algorithms

作　　者：钟求喜[1] 谢涛[1] 陈火旺[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《计算机科学》2000年第6期46-49,共4页Computer Science

基　　金：国家自然科学基金(No:69903010)

摘　　要：1 引言分布与并行系统中的任务分配与调度,对发挥系统的并行性能和保持负载平衡有重大意义,也是被公认的NP问题。Richard F.Freund等通过对一个假设的具有多层并发度计算需求的计算实例的计算分析表明,对于普通串型机需要100个时间单位,对于向量机需要50个时间单位。Task matching and scheduling play an important role in parallel and distributed systems. In order to use genetic algorithms(GAs) for tasks matching and scheduling,not only appropriate representations of solutions but also genetic operators' efficiency and generality are very important. In this paper, analysis between problem space and representation space is given at the first. Then based on the representation of permutation, two general efficient genetic operators are proposed, order crossover (OCX)and migration. OCX generates new schedules with heuristic due to the problem space with constraints among tasks. Migration transfers a task from one processor to another within a schedule. The simulation results of algorithms and conclusions are given at last.

关 键 词：任务分配 调度 遗传算法 知识表示 遗传算子 

分 类 号：O224[理学—运筹学与控制论] O242.23[理学—数学]