D0I:10.13374/.issn1001-053x.2012.10.016 第34卷第10期 北京科技大学学报 Vol.34 No.10 2012年10月 Journal of University of Science and Technology Beijing 0ct.2012 基于模板的服务工作流的优化组合方法 颉 斌四 杨扬宋京王磊 北京科技大学计算机与通信工程学院，北京100083 ☒通信作者，E-mail:xiebin@usth.ed.cn 摘要研究了网络环境下基于模板的服务工作流的优化组合算法.该算法将服务优化组合问题转化为服务工作流模板的 优化组合问题，既极大程度地复用历史服务工作流模板以减少组建新工作流的工作量，又通过优化使得服务工作流结构更为 合理，缩短了服务工作流的执行时间.通过使用Ptmi网对网络流媒体课件制作服务工作流进行建模，并对比优化前后服务工 作流模型的SPNP性能分析结果，证明了优化算法的有效性 关键词网络服务：工作流软件：模板匹配：算法：Petri网 分类号TP393 Service workflow optimization and composition method based on templates XIE Bin,YANG Yang,SONG Jing,WANG Lei School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China XCorresponding author,E-mail:xiebin@ustb.edu.cn ABSTRACT An optimization and composition algorithm based service workflow templates in network environment was proposed in this paper.The algorithm turns the problem of service optimization and composition into a problem of service workflow templates,thus it can largely reuse history workflow templates and decrease the buildup work of new workflow templates.In the algorithm,optimization makes the structure of the service workflow more reasonable and the execution time shortened.A network stream media courseware- making service workflow as an example was modeled with a Petri net.The comparison of SPNP performance analysis results of the service workflow between pre-optimization and post-optimization proves the algorithm's effectiveness. KEY WORDS web services;workflow management software:template matching:algorithms;Petri nets 近年来，对工作流的研究成为计算机科学领域 将服务作为优化组合对象，没有考虑重用己有的服 的一个研究热点，工作流技术已被广泛地应用于办 务工作流模板，所以组建工作流的工作量很大.文 公自动化、业务流程重组和业务流程管理等领域. 献B]研究了基于模板的Wb服务组合模型，能够 服务工作流将工作流中的任务以服务的形式实现， 较准确地得到服务组合需要的Wb服务及工作流 是Wb服务与工作流相结合的产物，其抽象业务逻 模板，这样通过复用历史模板减小组建工作流的工 辑模型由多个服务节点组成，是一种半自动的服务 作量；然而组建的工作流规模庞大，结构复杂，执行 组合方式四.随着网络的不断发展，网络提供的服 时间过长.文献4]提出了一个基于抽象模板的语 务种类越来越多，服务组合方式千差万别，这就会导 义Wb服务组合框架，当不存在一个满足用户请求 致网络环境下的服务工作流出现组建工作量大、结 的模板时，可以实现对模板的自动修改；它虽然实现 构复杂和规模庞大等问题. 了对模板自动修改的功能，减少了工作量，但是只考 目前关于服务工作流优化组合方法研究己经有 虑匹配一个模板，灵活性不高.文献5]提出了基于 大量研究成果.文献2]基于排队论的知识提出了 Petri网的过程优化算法：虽然它在一定程度上化简 一种服务工作流的优化算法，该算法将费用、响应时 了工作流模型，但是考虑的组合对象是服务，组建工 间和排队顾客数作为限制条件，通过对可选服务的 作流的工作量大 选择使得工作流的服务利用率得到优化；但该算法 目前大多数关于工作流模板查找与匹配的研究 收稿日期：201108-30 基金项目：国家自然科学基金资助项目(61070182：60873192：61170209)第 34 卷 第 10 期 2012 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 10 Oct． 2012 基于模板的服务工作流的优化组合方法 颉 斌! 杨 扬 宋 京 王 磊 北京科技大学计算机与通信工程学院，北京 100083 !通信作者，E-mail: xiebin@ ustb． edu． cn 摘 要 研究了网络环境下基于模板的服务工作流的优化组合算法． 该算法将服务优化组合问题转化为服务工作流模板的 优化组合问题，既极大程度地复用历史服务工作流模板以减少组建新工作流的工作量，又通过优化使得服务工作流结构更为 合理，缩短了服务工作流的执行时间． 通过使用 Petri 网对网络流媒体课件制作服务工作流进行建模，并对比优化前后服务工 作流模型的 SPNP 性能分析结果，证明了优化算法的有效性． 关键词 网络服务; 工作流软件; 模板匹配; 算法; Petri 网 分类号 TP393 Service workflow optimization and composition method based on templates XIE Bin!，YANG Yang，SONG Jing，WANG Lei School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China !Corresponding author，E-mail: xiebin@ ustb． edu． cn ABSTRACT An optimization and composition algorithm based service workflow templates in network environment was proposed in this paper． The algorithm turns the problem of service optimization and composition into a problem of service workflow templates，thus it can largely reuse history workflow templates and decrease the buildup work of new workflow templates． In the algorithm，optimization makes the structure of the service workflow more reasonable and the execution time shortened． A network stream media courseware￾making service workflow as an example was modeled with a Petri net． The comparison of SPNP performance analysis results of the service workflow between pre-optimization and post-optimization proves the algorithm's effectiveness． KEY WORDS web services; workflow management software; template matching; algorithms; Petri nets 收稿日期: 2011--08--30 基金项目: 国家自然科学基金资助项目( 61070182; 60873192; 61170209) 近年来，对工作流的研究成为计算机科学领域 的一个研究热点，工作流技术已被广泛地应用于办 公自动化、业务流程重组和业务流程管理等领域． 服务工作流将工作流中的任务以服务的形式实现， 是 Web 服务与工作流相结合的产物，其抽象业务逻 辑模型由多个服务节点组成，是一种半自动的服务 组合方式［1］． 随着网络的不断发展，网络提供的服 务种类越来越多，服务组合方式千差万别，这就会导 致网络环境下的服务工作流出现组建工作量大、结 构复杂和规模庞大等问题． 目前关于服务工作流优化组合方法研究已经有 大量研究成果． 文献［2］基于排队论的知识提出了 一种服务工作流的优化算法，该算法将费用、响应时 间和排队顾客数作为限制条件，通过对可选服务的 选择使得工作流的服务利用率得到优化; 但该算法 将服务作为优化组合对象，没有考虑重用已有的服 务工作流模板，所以组建工作流的工作量很大． 文 献［3］研究了基于模板的 Web 服务组合模型，能够 较准确地得到服务组合需要的 Web 服务及工作流 模板，这样通过复用历史模板减小组建工作流的工 作量; 然而组建的工作流规模庞大，结构复杂，执行 时间过长． 文献［4］提出了一个基于抽象模板的语 义 Web 服务组合框架，当不存在一个满足用户请求 的模板时，可以实现对模板的自动修改; 它虽然实现 了对模板自动修改的功能，减少了工作量，但是只考 虑匹配一个模板，灵活性不高． 文献［5］提出了基于 Petri 网的过程优化算法; 虽然它在一定程度上化简 了工作流模型，但是考虑的组合对象是服务，组建工 作流的工作量大． 目前大多数关于工作流模板查找与匹配的研究 DOI:10.13374/j.issn1001-053x.2012.10.016