网格环境下资源调度问题的统一建模与分析

结合工作流的思想,提出了一种网格资源调度的统一模型,统一了对异构资源的描述,使网格资源不仅包括技术资源如计算资源、存储资源、网络资源,也包括人力资源、代理资源等;统一了从存储结点获取数据和从前驱任务获取数据的不同的数据获取方式.阐述了多任务的资源调度问题的形式化定义、复杂性和可近似性难度分析,证明了该问题是NP完全的且是强NP完全的,不存在任何常数近似比的多项式时间近似算法.

Modeling and analyzing resource schedules in grid environments

According to workflow concept,a unified model for grid resource schedule problem was built.All kinds of resource,including computing resource,storage one and network one,human one and agent one,and the ways of getting data set from storage sites and predecessor tasks were integrated.A formalized definition of multi-tasks resource schedules was proposed,and its complexity and approximate difficulty were analyzed.It was concluded that the problem is strong NP complete without any approximate algorithms that had constant polynomial time approximate ratio.