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

Effective algorithm for deciding S-coverability of workflow nets

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

To decide S-coverability of workflow net effectively, S-coverability decision was converted to linear pro- grarnming 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-in- variants supports would cover all the places. The proposed algorithm was verified in the circumstance of complaints handling business processes.