摘要
结合工作流的思想,提出了一种网格资源调度的统一模型,统一了对异构资源的描述,使网格资源不仅包括技术资源如计算资源、存储资源、网络资源,也包括人力资源、代理资源等;统一了从存储结点获取数据和从前驱任务获取数据的不同的数据获取方式.阐述了多任务的资源调度问题的形式化定义、复杂性和可近似性难度分析,证明了该问题是NP完全的且是强NP完全的,不存在任何常数近似比的多项式时间近似算法.
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.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2006年第3期35-38,共4页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(70471077)
高等学校博士学科点专项基金资助项目(20020487046)
关键词
资源匹配
任务调度
网格
工作流
resource matchmaking
task scheduling
grid
workflow
