基于遗传算法的网格任务调度研究及实现

随着科学的日新月异,网络技术的发展正向着网格迈进。网格是地理上分布的异构的动态的各种高性能计算资源,它将高速互联网、计算机、大型数据库、传感器、远程设备等融为一体,为人们提供更多的资源、功能和服务。网格的最终目的就是给用户提供一种与地理位置无关、与具体计算设施无关的透明的计算能力。网格是要将合适的资源分配给用户使用,基于该问题的求解称为网格计算,它是近年兴起的一种重要的并行分布式计算技术,在统一的框架下把广域分布的资源互连、解决日益增长的计算需求以及飞速发展的互联网通讯技术。但是由于网格计算具有扩展性、异构性、不可预测性,使得其资源管理及任务调度策略面临了很大的挑战。 本文介绍了网格的基本概念,着重讨论了网格环境下计算任务在地理分布的各种资源之间的动态调度。这类问题可描述为将n个相互独立的任务分配到m个异构可用资源上以获取最小的完成时间和最大的资源利用率[13],这是一个NP完全问题[3]。本文采用启发式遗传算法[6]来解决该问题,通过设计染色体编码、解码方式获得初始种群,依据有向无环图(DAG)图定义任务执行的逻辑关系,选取适应值函数计算每一代的适应值,制定复制、交叉、变异算子的取得方式,并根据网格调度必须解决异构计算系统以及多处理器之间的通信延迟