第10期 颉斌等：基于模板的服务工作流的优化组合方法 ·1217· 6.0 组合优化问题转化为历史服务工作流模板组合优化 5.8 墨优化前 5.6 ☑优化后 问题，提出了基于模板的服务工作流的优化组合算 法.为了证明优化算法的有效性，以网络流媒体课 5.2 5.0 件制作服务工作流为实例，使用Petri网对其进行建 4.8 模，通过对比优化前后服务工作流模型的SPNP性 46 4 能分析结果，发现优化后服务工作流的吞吐量变化 请求到达速率（个·） 不大，但是响应时间较优化前可大幅降低，从而证明 图8优化前后服务工作流吞吐量对比图 了优化算法的有效性. Fig.8 Service workflow throughput comparison between pre-optimi- zation and postoptimization 参考文献 27 [1]Hu C H.Wu M,Liu G P,et al.Approach to constructing web 25 圆优化前 service workflow based on business spanning graph.J Softcare, 三2B ☑优化后 2007,18(8):1870 21 (胡春华，吴敏，刘国平，等.一种基于业务生成图的W山服 19 务工作流构造方法.软件学报，2007,18(8)：1870) 17 Eckert J,Schulte S,Repp N,et al.Queuing-based capacity plan- 4 5 ning approach for Web service workflows using optimization algo- 请求到达速率（个·） rithms /2008 Second IEEE International Conference on Digital 图9优化前后服务工作流响应时间对比图 Ecosystems and Technologies.Phitsanulok,2008:313 Fig.9 Service workflow responding time comparison between preop- [3] Ling H Y.Realization of Web Services Composition System Based on timization and post-optimization Workflow Template [Dissertation].Wuhan:Wuhan University of Science and Technology,2009 幅降低，从而证明了优化算法的有效性 (凌海洋.基于工作流模板的Wb服务组合系统实现[学位论 为验证所提算法较其他同类算法的有效性，本 文].武汉：武汉科技大学，2009) 文设计了与传统Petri网网格工作流在服务组合执 [4] Hu J,Feng Z Y.Semantic web service composition framework 行效率上的对比实验.同样，当服务工作流请求到 based on abstract template.Comput Appl,00929(11):3150 达速率在1~6个·s-时，通过SPNP仿真，得出服务 (胡佳，冯志勇.一种基于抽象模板的语义W山服务组合框 架.计算机应用，2009,29(11)：3150) 组合执行时间如图10所示 [5] Zhou J B,Ling H,Xu Z C.Petri net-based workflow optimization 40 analysis.Chin J Manage Sci,2005,13(3):50 图传统Pelri (周江波，凌鸿，胥正川.基于Ptr网的工作流优化分析.中 ☑本文算法 30 国管理科学，2005,13(13)：50) [6]Chen F.Dynamic Semantic Web Serrice Composition Model and 20 Achierement Based on Workflow [Dissertation].Wuhan:Hua- zhong University of Science and Technology,2007 (陈飞.基于工作流的语义W山服务动态组合模型及实现 [学位论文].武汉：华中科技大学，2007) 请求到达速率从个·s少 ] Lin C.Stochastic Petri Nets and Performance Evaluation of Sys- 图10服务组合执行效率对比 tems.2nd Ed.Beijing:Tsinghua University Press,2005 Fig.10 Comparison of execution efficiency of service composition (林闯.随机Ptr网和系统性能评价.2版.北京：清华大学 出版社，2005) 依据图10可以看出，本文提出的基于模板的服 四 Schimm G.Mining exact models of concurrent workflows.Comput 务组合优化算法在执行时间上大大优于传统的Peti 1md,2004,53(3):265 网网格工作流服务组合，尤其是在服务请求增多时， 9] Hu Z G,Zhao R F,Chen R,et al.Research on grid service work- 其执行效率对比优势更为明显. flow model based on dynamic colored Petri net.J Chin Comput Ss,2007,28(7):1205 4结论 (胡志刚，赵瑞芳，谌任，等.基于动态有色P如网的网格服务工 作流模型的研究.小型微型计算机系统，2007,28(7)：1205) 本文结合网络环境下服务的特点，研究了服务 [10]Reibman A,Smith R,Trivedi K.Markov and Markov reward 工作流模板模型及服务工作流模板间的关系.为了 model transient analysis:an overview of numerical approaches. 极大程度地复用己有历史服务工作流模板，将服务 Eur J Oper Res,1989,40(2):257第 10 期 颉 斌等: 基于模板的服务工作流的优化组合方法 图 8 优化前后服务工作流吞吐量对比图 Fig． 8 Service workflow throughput comparison between pre-optimi￾zation and post-optimization 图 9 优化前后服务工作流响应时间对比图 Fig． 9 Service workflow responding time comparison between pre-op￾timization and post-optimization 幅降低，从而证明了优化算法的有效性． 为验证所提算法较其他同类算法的有效性，本 文设计了与传统 Petri 网网格工作流在服务组合执 行效率上的对比实验． 同样，当服务工作流请求到 达速率在 1 ～ 6 个·s － 1 时，通过 SPNP 仿真，得出服务 组合执行时间如图 10 所示． 图 10 服务组合执行效率对比 Fig． 10 Comparison of execution efficiency of service composition 依据图 10 可以看出，本文提出的基于模板的服 务组合优化算法在执行时间上大大优于传统的Petri 网网格工作流服务组合，尤其是在服务请求增多时， 其执行效率对比优势更为明显． 4 结论 本文结合网络环境下服务的特点，研究了服务 工作流模板模型及服务工作流模板间的关系． 为了 极大程度地复用已有历史服务工作流模板，将服务 组合优化问题转化为历史服务工作流模板组合优化 问题，提出了基于模板的服务工作流的优化组合算 法． 为了证明优化算法的有效性，以网络流媒体课 件制作服务工作流为实例，使用 Petri 网对其进行建 模，通过对比优化前后服务工作流模型的 SPNP 性 能分析结果，发现优化后服务工作流的吞吐量变化 不大，但是响应时间较优化前可大幅降低，从而证明 了优化算法的有效性． 参 考 文 献 ［1］ Hu C H，Wu M，Liu G P，et al． Approach to constructing web service workflow based on business spanning graph． J Software， 2007，18( 8) : 1870 ( 胡春华，吴敏，刘国平，等． 一种基于业务生成图的 Web 服 务工作流构造方法． 软件学报，2007，18( 8) : 1870) ［2］ Eckert J，Schulte S，Repp N，et al． Queuing-based capacity plan￾ning approach for Web service workflows using optimization algo￾rithms / / 2008 Second IEEE International Conference on Digital Ecosystems and Technologies． Phitsanulok，2008: 313 ［3］ Ling H Y． Realization of Web Services Composition System Based on Workflow Template ［Dissertation］． Wuhan: Wuhan University of Science and Technology，2009 ( 凌海洋． 基于工作流模板的 Web 服务组合系统实现［学位论 文］． 武汉: 武汉科技大学，2009) ［4］ Hu J，Feng Z Y． Semantic web service composition framework based on abstract template． J Comput Appl，2009，29( 11) : 3150 ( 胡佳，冯志勇． 一种基于抽象模板的语义 Web 服务组合框 架． 计算机应用，2009，29( 11) : 3150) ［5］ Zhou J B，Ling H，Xu Z C． Petri net-based workflow optimization analysis． Chin J Manage Sci，2005，13( 3) : 50 ( 周江波，凌鸿，胥正川． 基于 Petri 网的工作流优化分析． 中 国管理科学，2005，13( 13) : 50) ［6］ Chen F． Dynamic Semantic Web Service Composition Model and Achievement Based on Workflow ［Dissertation］． Wuhan: Hua￾zhong University of Science and Technology，2007 ( 陈飞． 基于工作流的语义 Web 服务动态组合模型及实现 ［学位论文］． 武汉: 华中科技大学，2007) ［7］ Lin C． Stochastic Petri Nets and Performance Evaluation of Sys￾tems． 2nd Ed． Beijing: Tsinghua University Press，2005 ( 林闯． 随机 Petri 网和系统性能评价． 2 版． 北京: 清华大学 出版社，2005) ［8］ Schimm G． Mining exact models of concurrent workflows． Comput Ind，2004，53( 3) : 265 ［9］ Hu Z G，Zhao R F，Chen R，et al． Research on grid service work￾flow model based on dynamic colored Petri net． J Chin Comput Syst，2007，28( 7) : 1205 ( 胡志刚，赵瑞芳，谌任，等． 基于动态有色 Petri 网的网格服务工 作流模型的研究． 小型微型计算机系统，2007，28( 7) : 1205) ［10］ Reibman A，Smith R，Trivedi K． Markov and Markov reward model transient analysis: an overview of numerical approaches． Eur J Oper Res，1989，40( 2) : 257 ·1217·