Effective algorithm for deciding S-coverability of workflow nets

• Article •

Effective algorithm for deciding S-coverability of workflow nets

LU Fa-ming, ZENG Qing-tian, BAO Yun-xia

1. College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China;2. College of Science, Shangdong University of Science and Technology, Qingdao 266590, China

Online:2012-08-15 Published:2012-08-25

判定工作流网S-可覆盖性的有效算法

鲁法明,曾庆田,包云霞

1.山东科技大学信息科学与工程学院，山东青岛266590;2.山东科技大学理学院，山东青岛266590

Abstract

Abstract: To decide S-coverability of workflow net effectively, S-coverability decision was converted to linear programming problem. An effective algorithm was introduced to determine S-Coverability based on simplex method. Additionally, the simplex method was extended so that a set of minimal S-invariants supports could be generated with the proposed algorithm. When a given workflow net satisfied S-Coverability, the obtained set of minimal S-invariants supports would cover all the places. The proposed algorithm was verified in the circumstance of complaints handling business processes.

Key words: workflow nets, Petri nets, S-coverability, S-invariants

摘要： 为有效判定工作流网的S-可覆盖性，将工作流网的S-可覆盖性判定转化为线性规划问题，借助单纯形方法给出一个判定工作流网S-可覆盖性的有效算法。对单纯形算法进行扩展，在判定工作流网S-可覆盖性的同时可以求出一组S-不变量的极小支集。只要给定的工作流网满足S-可覆盖性，上述算法就可以求出一组覆盖所有库所的S-不变量的极小支集。结合投诉处理业务流程实例对算法进行了验证。

关键词: 工作流网, Petri网, S-可覆盖性

CLC Number:

TP301

LU Fa-ming, ZENG Qing-tian+, BAO Yun-xia. Effective algorithm for deciding S-coverability of workflow nets[J]. .

鲁法明,曾庆田+,包云霞. 判定工作流网S-可覆盖性的有效算法[J]. .

[1]	. Deadlock detection method based on Petri net mining of program trajectory [J]. , 2021, 27(9): 2611-2624.
[2]	. Dynamic decision-making of manufacturing resource based on digital twin [J]. , 2021, 27(2): 521-535.
[3]	. Modeling and simulation for enterprises' RFID adoption and internalization based on stochastic Petri nets [J]. , 2020, 26(第2): 470-480.
[4]	. Petri net-based hierarchical business process mining [J]. , 2020, 26(6): 1525-1537.
[5]	. Analyzing realizability of choreographies using Petri nets [J]. , 2020, 26(6): 1548-1556.
[6]	. Business alignments based on reachable graphs of Petri nets [J]. , 2020, 26(6): 1589-1606.
[7]	. Aligning event logs and process models based on Petri nets [J]. , 2019, 25(第4): 809-829.
[8]	. Conformance checking of business process based on artifact lifecycle mode [J]. , 2019, 25(第4): 856-863.
[9]	. Process mining approach of discovering behavior blocks based on successor relation [J]. , 2019, 25(第4): 901-908.
[10]	. Matching mechanism of physical and information processes in discrete series production system [J]. , 2019, 25(第11): 2923-2934.
[11]	. Failure response policy for revisiting dual-arm cluster tools based on Petri nets [J]. , 2019, 25(12): 3235-3246.
[12]	. Solving algorithm for scheduling problem with control-flow constraints [J]. , 2018, 24(第7): 1598-1607.
[13]	. Extending α-algorithm to mine simplest 2-Loops [J]. , 2018, 24(第3): 591-601.
[14]	. Multiple die and composite geometry machining process simulation technology for bending machine [J]. , 2018, 24(第1): 19-33.
[15]	. Business process modeling and analysis based on logical data Petri net [J]. , 2017, 23(第5期): 921-930.