电子学报 ›› 2009, Vol. 37 ›› Issue (2): 329-333.

• 论文 • 上一篇    下一篇

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

易 侃1, 王汝传1,2   

  1. 1. 南京邮电大学计算机学院,江苏南京 210003;2.
  • 收稿日期:2008-03-06 修回日期:2008-07-06 出版日期:2009-02-25 发布日期:2009-02-25

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

YI Kan1, WANG Ru-chuan1,2   

  1. 1. College of Computer,Nanjing University of Posts and Telecommunications,Nanjing,Jiangsu 210003,China;2. State Key Laboratory for Novel Software Technology at Nanjing University,Nanjing,Jiangsu 210093,China
  • Received:2008-03-06 Revised:2008-07-06 Online:2009-02-25 Published:2009-02-25

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

关键词: 网格, 任务调度, Nash均衡, 粒子群算法, Repast

Abstract: 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.

Key words: grid, task scheduling, Nash equilibrium, PSO, repast

中图分类号: