第4章_网格调度技术.ppt

第4章 网格调度技术华南理工大学电子与信息学院网格调度技术概况 u网格的目的实现资源共享和协调工作。u网格调度技术解决如何调用各个资源，如何实现协调工作问题。u网格调度技术是一个组合优化问题。u网格调度技术常用一些数学模型解决。网格调度技术简介1.快速贪婪算法(Fast-Greedy)u从任务集中依次选择一个任务，计算该任务的期望执行时间。u将具有最小期望完成时间的机器分配给该任务。u重复进行，直到全部任务分配完毕。网格调度技术常用算法1.快速贪婪算法(Fast-Greedy)u依次选择一个任务u计算期望执行时间u最小期望完成时间网格调度技术常用算法时间时间任务任务1任务任务2任务任务3任务任务42.最小-最小算法(Min-Min)u目的是将任务分配给不仅完成时间最早，而且执行最快的机器。u计算各个任务在各个机器上的期望完成时间，获得各个任务的最早完成时间和机器。u将具有最小期望完成时间且完成时间最早的机器分配给该任务。u重复进行，直到全部任务分配完毕。网格调度技术常用算法2.最小-最小算法(Min-Min)u完成时间最早u最小期望完成时间网格调度技术常用算法时间时间任务任务1任务任务2任务任务3任务任务43.最大-最小算法(Max-Min)u目的是优先考虑长任务。u计算各个任务在各个机器上的期望完成时间，获得各个任务的最早完成时间和机器。u将具有最大期望完成时间且完成时间最早的机器分配给该任务。u重复进行，直到全部任务分配完毕。网格调度技术常用算法3.最大-最小算法(Max-Min)u完成时间最早u最大期望完成时间网格调度技术常用算法时间时间任务任务1任务任务2任务任务3任务任务44.最大时间跨度算法(Max-Int)u利用了Min-Min和Max-Min的优点。u基本思想是使全部任务的完成时间最小。u计算每个任务的最小完成时间和次小完成时间。u计算每个任务的最小完成时间和次小完成时间的差值，即时间跨度。u找出时间跨度最大的任务，并分配最小且最小完成时间的机器给该任务。u重复进行，直到全部任务分配完毕。网格调度技术常用算法4.最大时间跨度算法(Max-Int)u最小完成时间u次小完成时间u时间跨度最大u最小且最早完成时间网格调度技术常用算法时间时间任务任务1任务任务2任务任务3任务任务45.遗传算法(GA)u模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。u在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体。u利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群。u重复此过程，直到满足某种收敛指标为止。网格调度技术常用算法6.粒子群算法(PSO)u模拟鸟集群飞行觅食的行为，鸟之间通过集体协作使群体达到最优，是一种群智能优化方法。u基于群体叠代，粒子在解空间追随最优的粒子进行搜索。u在每一次叠代中，粒子通过跟踪两个极值来更新自己。u第一个极值是粒子本身所找到的最优解，另一个极值是整个种群目前找到的最优解。网格调度技术常用算法