基于改进遗传算法的网格任务调度算法  

GRID TASK SCHEDULING ALGORITHM BASED ON IMPROVED GENETIC ALGORITHM

作　　者：吴德鹏[1] 张建[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机应用与软件》2009年第3期126-127,222,共3页Computer Applications and Software

基　　金：上海市教委发展基金项目(2006AZ049)

摘　　要：网格任务调度是一个NP完全问题,它关注大规模的资源和任务调度,要求采用的调度算法能够具有高效性。遗传算法被证明是解决这类小规模问题的有效算法,随着任务数和资源数的增加,遗传算法表现出慢速收敛的缺点。为了克服其缺点,提出将Min-min算法与遗传算法相结合的改进遗传算法,从而设计出很好的选择和交叉算子,提高了算法搜索能力和收敛速度。仿真结果表明该算法能更有效解决网格任务调度问题。Grid task scheduling is a NP-complete problem which concerns the scheduling of tasks and resources in a large scale, and thus a scheduling algorithm of high efficiency is required. Genetic algorithm has been proven to be an effective method to solve this problem in small scale ,but it has a drawback of slow convergence as the number of tasks and resources increases. In order to overcome this drawback, in this paper it provides a method of an improved genetic algorithm which integrates genetic algorithm with Min-min algorithm, and then designs good selection operator and cross operator, all these improvements can help to enhance the searching ability and convergence speed. The simulation results show that this algorithm can solve the problem of grid task scheduling more effectively.

关 键 词：网格计算 任务调度 遗传算法 MIN-MIN算法 时间跨度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]