摘要
用有向无环图表示的网格工作流调度问题是一种典型的NP-完全问题,因而,有效的调度算法是必不可少的。为解决这一问题,提出了一种改进型的遗传算法。运用适应度差的染色体与最优个体进行二级优先杂交和变异,不仅保障了种群的多样性,也提高了种群的收敛速度。采用Gridsim工具进行模拟后,证实该算法较标准的遗传算法更适用、更有效。
Grid workflow scheduling represented by directed acyclic graph(DAG) is a typical NP-complete problem,and thus a scheduling algorithm of high efficiency is required.So an improved genetic algorithm was proposed to solve this problem.In the algorithm,chromosomes of poor fitness made secondary preferential hybridization and mutation with the overall best individual.It not only guarantees the population diversity but increases the convergence rate of population.Simulation results based on Gridsim show that the improved algorithm is available and better than standard genetic algorithm
出处
《河南科技大学学报（自然科学版）》
CAS
北大核心
2012年第3期32-35,111,共4页
Journal of Henan University of Science And Technology:Natural Science
基金
重庆市自然科学基金项目(2008BB2296)
关键词
网格工作流
调度问题
改进型遗传算法
二级优先杂交和变异
Grid workflow
Scheduling problem
Improved genetic algorithm
Secondary preferential hybridization and mutation
