基于Nash均衡的网格多调度节点的任务调度算法

Nash Equilibrium Based Task Scheduling Algorithm of Multi-schedulers in Grid Computing

目前网格任务调度算法主要是针对1×n型即单调度节点多资源的网格环境,而针对m×n型的网格环境研究较少.论文用M/M/1排队系统对m×n型网格环境建模,然后以每个调度节点调度任务的平均完成时间为优化目标,提出了m×n型网格环境任务调度的Nash均衡问题,并利用粒子群算法求得该Nash均衡解.通过仿真验证了该算法在单位时间内平均完成的任务数,网络平均负载,以及系统的平均负载上均优于基于均匀调度策略的调度算法.

At present,grid task scheduling Algorithms focus on 1×n type grid,namely one scheduler and n resources but neglect m×n type grid.We built a Grid model of m×n type grid using M/M/1 queue system,and promoted the concept of task scheduling Nash equilibrium among multi-schedulers.The optimal objective of each scheduler is mean complete time per task.The Nash equilibrium took advantage of PSO to be solved.By simulations,we conclude that the new algorithm is better than the algorithm based on the mean scheduling strategies in mean finished task numbers per time,mean load of network and mean load of Grid resources.