摘要
在网格环境中 ,每个网格服务都面临着多种资源选择 ,网格作业中各服务间的关联在某种程度上可映射为资源之间的依赖关系 ,不同的资源配置将产生不同的服务满意度 ,由此提出服务资源分配问题SRA(ServiceResourceAssignment) ,通过构造资源关系图提出基于树分解的资源分配算法TDRA(Tree DecompositionbasedResourceAllocationalgorithm) ,利用该算法求出此问题的正确消元顺序 ,在多项式时间复杂度内获得该问题的最优解 ,给出实验结果并提出下一步的研究工作 .
As a component of a grid job, a grid service is required to select suitable resource from global wide providers so that the different resource assignments have distinctive impact on the utility of the job, which results in SRA (service resource assignment) problem. Addressing it a novel method TDRA (tree-decomposition based resource allocation algorithm), based on tree-decomposition of grid resource dependency graph, was chosen to form the correct vertex elimination order on which the variables were iteratively relaxed until the optimised result was reached. The method indicates the complexity of TDRA is polynomial instead of exponential, which proves available to solve SRA problem. As a conclusion the further work of this research was also discussed.
出处
《北京航空航天大学学报》
EI
CAS
CSCD
北大核心
2004年第11期1052-1056,共5页
Journal of Beijing University of Aeronautics and Astronautics
基金
国家自然科学基金资助项目 (90 412 0 12 )
关键词
网格服务
服务资源分配
资源关系图
树分解
Correlation methods
Optimization
Problem solving
Resource allocation
Trees (mathematics)
World Wide Web