,1286. 北京科技大学学报 第29卷 International Symposium on High Performance Distributed Com- 性能分析.计算机研究与发展，2005,42(8)：1397 puting.Los Alamitos:IEEE Computer Society Press,1998:140 [10]殷剑宏，吴开亚.图论及其算法.安微：中国科学技术大学出 [5]Foster I.Kesselman C,Nick J.et al.Grid services for distribut- 版社，2003：192 ed system integration.IEEE Comput.2002.35(6):37 [11]Tierney B.Johnstone W,Crowley B.et al.The NetLogger [6们郝卫东，杨扬，王先梅，等。网络环境下的电子商务与电子政 methodology for high performance distributed systems perfor- 务建设.北京：清华大学出版社，2006：112 mance analysis/7th IEEE International Symposium on High [7]Foster I.Jennings N.Kesselman C.Brain meets brawn:Why Performance Distributed Computing.Los Alamitos:IEEE Com- grid and agents need each other3th Internatinal Joint Confer puter Society Press.1998:28 ence on Autonomous Agents and Multiagent Systems.New [12]The Open Group.C807 Systems Management:Application Re- York,2004:8 sponse Measurement (ARM)API.Berkshire:The Open Group [8]单志广，戴琼海，林闯，等.W山请求分配和选择的综合方案 Publishers Inc,1998:1 与性能分析.软件学报，2001,12(3)：355 [13]杨扬，离散事件系统理论与柔性制造系统，北京：冶金工业 [9]曲绍刚，杨广文，林闯，等，基于完成时间的任务分配方案与 出版社，1994：219 Optimized solution to the grid services matchmaking problem based on running time weight matrix HAO Weidong,YANG Yang,LIU Honglan,LIA NG Quan Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT In order to solve the resource scheduling problem in service grid environment to guarantee the need of user jobs complete time,an independent matchmaker was introduced into the three-element service grid model.The service grid model was formally illustrated based on the graph theory,and the necessary and suffi- cient conditions of complete match of user jobs and grid service resources were also proved.A grid services matchmaking system was const ructed on the base of sensor feedback.The optimal matchmaking problem of the system was formally illustrated based on the running time weight matrix,and the optimal solution arithmetic was proposed based on the discrete event dynamic system theory.Simulation analysis shows that the arithmetic can improve the QoS (quality of services)performance parameter of the grid services matchmaking system,pro- vide the user jobs completed time guarantee and meet the load balance need of grid service resources. KEY WORDS service grid;matchmaker;complete match;weight matrix;discrete event dynamic system the- ory;graph theoryInternational Symposium on High Performance Distributed Com￾puting．Los Alamitos：IEEE Computer Society Press‚1998：140 ［5］ Foster I‚Kesselman C‚Nick J‚et al．Grid services for distribut￾ed system integration．IEEE Comput‚2002‚35（6）：37 ［6］ 郝卫东‚杨扬‚王先梅‚等．网络环境下的电子商务与电子政 务建设．北京：清华大学出版社‚2006：112 ［7］ Foster I‚Jennings N‚Kesselman C．Brain meets brawn：Why grid and agents need each other∥3th Internatinal Joint Confer￾ence on Autonomous Agents and Mult-i agent Systems． New York‚2004：8 ［8］ 单志广‚戴琼海‚林闯‚等．Web 请求分配和选择的综合方案 与性能分析．软件学报‚2001‚12（3）：355 ［9］ 曲绍刚‚杨广文‚林闯‚等．基于完成时间的任务分配方案与 性能分析．计算机研究与发展‚2005‚42（8）：1397 ［10］ 殷剑宏‚吴开亚．图论及其算法．安徽：中国科学技术大学出 版社‚2003：192 ［11］ Tierney B‚Johnstone W‚Crowley B‚et al．The NetLogger methodology for high performance distributed systems perfor￾mance analysis ∥7th IEEE International Symposium on High Performance Distributed Computing．Los Alamitos：IEEE Com￾puter Society Press‚1998：28 ［12］ The Open Group．C807Systems Management：Application Re￾sponse Measurement （ARM） API．Berkshire：The Open Group Publishers Inc‚1998：1 ［13］ 杨扬．离散事件系统理论与柔性制造系统．北京：冶金工业 出版社‚1994：219 Optimized solution to the grid services matchmaking problem based on running time weight matrix HAO Weidong‚Y A NG Y ang‚LIU Honglan‚LIA NG Quan Information Engineering School‚University of Science and Technology Beijing‚Beijing100083‚China ABSTRACT In order to solve the resource scheduling problem in service grid environment to guarantee the need of user jobs complete time‚an independent matchmaker was introduced into the three-element service grid model．The service grid model was formally illustrated based on the graph theory‚and the necessary and suffi￾cient conditions of complete match of user jobs and grid service resources were also proved．A grid services matchmaking system was constructed on the base of sensor feedback．The optimal matchmaking problem of the system was formally illustrated based on the running time weight matrix‚and the optimal solution arithmetic was proposed based on the discrete event dynamic system theory．Simulation analysis shows that the arithmetic can improve the QoS （quality of services） performance parameter of the grid services matchmaking system‚pro￾vide the user jobs completed time guarantee and meet the load balance need of grid service resources． KEY WORDS service grid；matchmaker；complete match；weight matrix；discrete event dynamic system the￾ory；graph theory ·1286· 北 京 科 技 大 学 学 报 第29卷