基于层次时间Petri网的工作流模型可达性分析方法

• 论文 •

基于层次时间Petri网的工作流模型可达性分析方法

唐达，刘丹妮

1.大连理工大学计算机科学与工程系，辽宁大连 116023；2.东北大学东软信息学院计算机系，辽宁大连 116023

收稿日期:2005-01-21 修回日期:2005-07-21 出版日期:2006-04-15 发布日期:2006-04-25

ethod of reachability analysis in HTPN based workflow model

TANG Da，LIU Dan-ni

1.Dep. of Computer Sci. & Eng., Dalian Univ. of Tech., Dalian 116023, China; 2.Neusoft Inst. of Info., Northeastern Univ., Dalian 116023, China

Received:2005-01-21 Revised:2005-07-21 Online:2006-04-15 Published:2006-04-25

摘要/Abstract

摘要： 为了有效管理工作流，需要对工作流模型进行合理性分析与验证。为此，提出了一种基于层次时间Petri网的工作流模型，给出了从时间Petri网工作流模型转化成基于层次时间Petri网工作流模型的规则及算法。证明了任何一个能够转化成基于层次时间Petri网的时间Petri网工作流模型在物理上都是可达的。在时间方面，提出了基于层次时间Petri网工作流模型的层次时间树算法，并给出了时间可达性的静态和动态分析与验证方法。通过实例验证了该方法在工作流模型的物理、时间静态和时间动态可达性分析中的有效性。

关键词: 工作流, 时间Petri网, 层次时间Petri网, 层次时间树

Abstract: The rationality analysis and verification of workflow are crucial to the effective management and execution of it. A new temporal workflow model based on Hierarchically Timed Petri Net (HTPN) was proposed to implement the analysis and verification of Timed Petri Net (TPN) workflow model. The rules and algorithm of transforming TPN model into HTPN model were given. And it was proved that a workflow model based on TPN would be physically reachable if the model was able to be transformed into a HTPN model. A new algorithm, HTPN based Hierarchically Timed Tree (HTT), was presented to implement the analysis and verification of static and dynamic availability. Finally, a case study was used to illustrate the effectiveness of above-mentioned method in the analysis and verification of static and dynamic availability in a workflow model.

Key words: workflow, timed Petri net, hierarchically timed Petri net, hierarchically timed tree

中图分类号:

TP311

唐达，刘丹妮. 基于层次时间Petri网的工作流模型可达性分析方法[J]. .

TANG Da，LIU Dan-ni. ethod of reachability analysis in HTPN based workflow model[J]. .

参考文献

［1］ LI Jianqiang, FAN Yushun. Timing boundedness verification and analysis of workflow model［J］. Computer Integrated Manufacturing Systems, 2002,8(8):770-775(in Chinese).［李建强, 范玉顺.工作流模型时间有界性验证与分析研究［J］. 计算机集成制造系统,2002,8(8)：770-775.］

[2] WERNER M, LOUCHKA P Z,RICHLING J. Non-reachability in priority duration Petri nets［A］. Proceedings of CS&P［C］.Czarma,Poland:Warsaw University,2003.134-149.

[3] DIANXIANG X, XUDONG H, YI D. Compositional schedulability analysis of real-time systems using time Petri nets［J］.IEEE Transactions on Software Engineering,2002,28(10):984-996.

[4] JEFFREY T, STEVE Y. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications［J］.IEEE Transactions on Software Engineering，1995, 21(1): 32-49.

[5] TANG Da, LIU Danni. Method for dynamic verification of activity deadlines in timed workflow［J］. Computer Integrated Manufacturing Systems, 2004,10(9):1154-1159(in Chinese).［唐达, 刘丹妮. 一种工作流时间截止期限的动态验证方法［J］. 计算机集成制造系统,2004,10(9):1154-1159.］

[6] BOTHA A, ELOFF J. Designing role hierarchies for access control in workflow systems［A］.Computer Software and Applicationg Confereme［C］.Chicago,IL,USA:IEEE Computer Society Press,2001.117-122.

[7] JUN H, SUH H. The hierarchical frame of enterprise activity modeling(HF-EAM)［J］.IEEE Transactions on Engineering Management, 2002, 49(4): 459-478.

[8] TANG Da, YANG Yuansheng. Research on workflow participant mechanism and dynamic characteristic based on hierarchically refined Petri nets［J］. Journal of Computer Research and Development, 2004,41(9): 1545-1553(in Chinese).［唐达,杨元生.基于层次细化Petri网的工作流参与者机制遇动态特性研究［J］.计算机研究与发展,2004,41(9):1545-1553.］

[9] BENATALLAH B,PIOTR C W, HAMADI H, et al. HiWorD:a Petri net-based hierarchical workflow designer［A］.Third International Conference on Application of Concurrency to System Design(ACSD′03)［C］.Washington，D.C.,USA:IEEE Computer Society Press,2003.235-236.

[10] Workflow Management Coalition. Interface 1:proterchange,process model［EB/OL］.http://www.wfmc.org/standards/docs/TC-1016-P_V11_IF1_Process_definition_Interchange.pdf,2005-01-21.

[11] WANG J, XU G, DENG Y. Reachability analysis of real time systems based on time Petri nets［J］. IEEE Transactions on System, Man and Cybernetics, 2000, 5(30): 725-736.

[1]	唐玄昭,余阳,吴荆璞,潘茂林. 基于区块链的业务流程互操作服务框架[J]. 计算机集成制造系统, 2021, 27(9): 2508-2516.
[2]	文一凭,王志斌,刘建勋,许小龙,康国胜. 云际协作环境下能耗与成本感知的工作流调度方法[J]. 计算机集成制造系统, 2021, 27(9): 2583-2591.
[3]	袁友伟,黄锡恺,俞东进,李忠金. 移动边缘计算环境下服务工作流容错调度算法[J]. 计算机集成制造系统, 2021, 27(6): 1693-1702.
[4]	李万清,刘辉,李忠金,袁友伟. 移动边缘计算环境下面向安全和能耗感知的服务工作流调度方法[J]. 计算机集成制造系统, 2020, 26(7): 1831-1842.
[5]	林国丹,黄钦开,余阳,潘茂林. Activiti引擎的无状态云工作流调度算法[J]. 计算机集成制造系统, 2020, 26(6): 1456-1464.
[6]	文一凭,王志斌,刘建勋,许小龙,陈爱民,曹步清. 混合云环境下成本与隐私感知的工作流调度方法[J]. 计算机集成制造系统, 2020, 26(6): 1582-1588.
[7]	齐平,王福成,徐佳,李学俊. 移动边缘计算环境下基于信任模型的可靠多重计算卸载策略[J]. 计算机集成制造系统, 2020, 26(6): 1616-1627.
[8]	姚艳,曹健. 一种成本有效的面向超参数优化的工作流执行优化方法[J]. 计算机集成制造系统, 2020, 26(6): 1628-1635.
[9]	孙晋永,闻立杰,匡增雄,李涛,张展. 基于数据生成—消耗依赖的语义工作流并行化重构方法[J]. 计算机集成制造系统, 2020, 26(6): 1636-1650.
[10]	袁友伟,刘恒初,俞东进,李忠金. 面向边缘侧卸载优化的工作流动态关键路径调度算法[J]. 计算机集成制造系统, 2019, 25(第4): 798-808.
[11]	魏懿,曹健. 基于机器学习的流程异常预测方法[J]. 计算机集成制造系统, 2019, 25(第4): 864-872.
[12]	文一凭,刘建勋,窦万春,陈爱民,周昱昊. 云工作流环境下隐私感知的多租户访问控制模型[J]. 计算机集成制造系统, 2019, 25(第4): 894-900.
[13]	林兵,项滔,陈国龙,陈星. 混合云环境下面向时延优化的科学工作流数据布局策略[J]. 计算机集成制造系统, 2019, 25(第4): 909-919.
[14]	徐佳,李学俊,丁瑞苗,刘晓. 移动边缘计算中能耗优化的多重资源计算卸载策略[J]. 计算机集成制造系统, 2019, 25(第4): 954-961.
[15]	陈文冲,刘洪伟,齐二石,刘伟. 离散串联生产系统物理与信息过程匹配机理[J]. 计算机集成制造系统, 2019, 25(第11): 2923-2934.