基于STN的业务流时间一致性消解方法

郁文枢 周 勇 燕雪峰

基于STN的业务流时间一致性消解方法

郁文枢 周 勇 燕雪峰

(南京航空航天大学计算机科学与技术学院 江苏 南京 210016)

目前对业务流约束验证的研究着重于研究验证单路径的时间约束的满足情况，没有考虑多路径的情况，对时间一致性冲突消解的研究也很少。为验证业务流的时间一致性，从路径分支问题和单任务动态时间满足约束的情况出发，在原有约束一致性上提出路径一致性和强一致性，以及基于STN(Simple Temporal Network)方法的不一致性消解算法并分析其收敛性等性质。最后以医疗流程的业务流为例进行了分析验证。

业务流 时间约束 STN 一致性检验 冲突消解

0 引 言

业务流建模方法被广泛运用在各个领域，当下对业务流模型的时间约束的验证研究也很多，目前验证的方法通常以对相关任务时间区间和约束时间进行数值计算或者使用模型检测方法为主[1〗]。数值计算验证通过对任务延迟和约束时间进行比较计算来判断是否满足约束，这种方法可以预先检测时间是否可以满足约束，但是只研究了业务流各时间区间是否可能满足约束[2]，忽略了若干任务的执行时间取值可能会导致后续约束的违反。模型检测方法的思想基于穷举法，通过设置状态来记录时间[3]，可以验证任务时间约束，但是在结点比较多、时间粒度也比较小的情况下，时间效率无法保证[1]。文献[4]以任一任务时间取值对选择分支的影响出发定义了业务流的强弱一致性，但是验证过程并不完整，并且缺少消解过程。文献[5]通过构建生成图对业务流时序进行验证和不一致消解，但是它不能确保消解不会影响其他约束。基于这些问题本文提出路径一致性和强一致性准则，并提出了对应的一致性判断和消解方法。为此本文借助STN首先根据时间区间判断业务流是否满足路径一致性，接着再判断其是否满足强一致性，最后针对消解问题提出了通过区间调节和路径合并进行不一致消解的方法。

1 业务流与STN简介

1.1 带有时间约束信息的业务流

业务流是一个组织化业务流程，表现为一系列旨在业务目标的完成的活动。它广泛用于规范和业务过程可视化，其时间约束问题也被广泛研究[6]。为了简化问题本文只讨论业务流的控制结构，定义带时间约束的业务流图如下。

定义1 带时序的业务流图为一个多元组P=(N,F,C)，其中：

N=T∪G表示结点的集合，T⊆N是任务结点的集合。G⊆N代表分支结点的集合，F⊆N×N是结点间有向边的集合。C是业务流中的时间约束的集合。

T表示原子任务集合。任务的持续时间通常不是确定的值而是一个范围。以S(t)表示任务t∈T的开始时间，E(t)表示结束时间[7]，任务t持续时间为[MinT,MaxT],且满足MinT≤E(t)-S(t)≤MaxT。G是业务流中的分支节点的集合，分支节点G包含了选择分支和并行分支。选择分支表示后继边中只选择一条执行，并行分支表示所有边都要并行执行。F⊆N×N是连接T或者G的有向边的集合，表示结点间的顺序关系。结点间的时间区间[MinT,MaxT]表示结点间的延迟范围。C是业务流中的时间约束集合。它表现形式类似边，约束了结点间的执行时间。

例：图1是一个业务流P。A是P中一个任务结点，标示[2,6]表示该了该任务的持续时间。A与其他节点以实边相连。虚线表示约束，AB之间的虚线[2,3]代表A到B的时间必须在区间[2,3]以内。

图1 一个业务流P

1.2 带时间业务流转换为STN

STN模型于1991年由Dechter等人提出，随后以其简洁的表达方式以及可有效验证时间约束而得到广泛应用。STN定义为图G=(V,E,I)，结点集合V表示时间点，边集合E表示时间点间的间隔，每一条边上都有一个约束范围[Ii,Ij],来表示两个时间点Ti和Tj之间需要满足约束Ii

业务流中存在选择分支，根据条件选择某一后续结点继续执行。业务流在一次执行中所执行的结点的集合为一条路径p=(N,F)，N和F分别为该路径的结点和边的集合。

一条路径可以转换为一个STN[4]，路径到STN的转换规则如下：

结点时序转换规则：设有一个结点n,开始结束时间为S(n)和E(n)，若其对应时间为[a,b]，则其表示为a≤E(n)-S(n) ≤b。

有向边转换规则：设有边e连接结点n1、n2，e对应的时间为[a,b]，则其约束关系可以表示为a≤E(n2)-S(n1) ≤b。

约束转换规则:两个结点A和B间约束[a,b]可以表示为a≤E(B)-S(A)≤b。

图2 距离图矩阵

利用规则可以将一个业务流图转换成一个或者多个STN。再将STN转换为距离图矩阵，就可方便地对其进行验证与修正工作。例如图1中P的路径ABDE转换为距离图矩阵如图2所示。

距离图矩阵有自己特点，它的对角线一定为0，下三角除了Inf不存在正值，且下三角绝对值一定小于等于上三角对应的正值。下文将距离图中一条有向边的权值称为弧值。

2 业务流时间约束冲突检测消解

2.1 业务流的路径一致性与强一致性

定义2 (路径一致性) 若对业务流的任意路径p，路径上所有节点n与边f至少存在一组时间[t1,t2,…,tn]满足该路径上的所有约束，则称该业务流是路径一致的。

图1业务流P中存在ABD和ACD两条路径，ACD存在一组执行时间满足约束[4,9]，但是ABD没有执行时间能满足AB约束[2,3]。这样ABD就无法执行，业务流是路径不一致的。反之如果能在ABD找到执行时间满足约束，就是路径一致的。

路径一致性保证了该业务流的每条路径都是可执行的。然而在业务流执行期间，部分任务存在过大或者过小的执行时间，会导致后续部分路径约束无法满足。为了检测这类情况，需要扩展一致性，由此引出如下一致性定义。

定义3 (强一致性) 如果对业务流任意结点在其区间内取任一执行时间ti，任意路径均是路径一致的，则业务流满足强一致性。

图1的P中的A点的执行时间允许取到6，一旦取到6无论AB之间[2,3]的时间约束和AD的[4,9]约束均无法满足，所以P是强不一致的。反之就是强一致的。

满足强一致性的情况下，可以保证任一任务时间的选择和后续路径是否可被执行完全无关，使业务流的时间更有效、更具有参考价值。下面讨论各一致性的检测方法，以及对应一致不满足的化解。

2.2 路径一致性的检测与消解

业务流满足路径一致性是其满足强一致性的基本条件。在STN中若各时间和约束的上下界构成的环为负，约束就不被满足[9]。将业务流路径都转换为STN，则路径一致性的检测就转化为对距离图负环的检测，将负环消解就消解了路径不一致性。Floyd算法是经典最短路径算法，在计算结束后得到全源最短路径图和全源最短距离图[10]。如果出现负环(距离图矩阵对角线出现负值)，则将负环权值改为正就修正了不一致。有时约束本身相互冲突，无法同时满足所有约束的要求。在检测前对距离矩阵图进行一次检测，若负环包含多个约束，说明约束存在冲突，需要重新确认。

算法产生最短路径矩阵为R，最短距离矩阵为D，基于Floyd算法的路径一致性消解算法如下:

算法:路径一致性消解算法input:G=(V,A)output:G=(V,A’)while (found,L)=floyd(G) if(found) rem=length(L); while(rem<0) selectarconLwithParc; if(noarcfind) returnerror; if(w(arc)<0)then if(rem

修正弧值需要同时保持距离图的性质[11]。为此为每条边设置一个优先度P。约束边的p设为0表示优先度最低，其他弧设一个初始值，每次修改优先度减少1，以此达到修改要求。

算法中floyd操作根据Floyd思想寻找负环，一旦找出一个负环，以其负环路径L计算其负值rem。之后遍历L，找到一个优先度最高的边，对其进行修正；若满足正值，则继续寻找下一负环，否则再寻找其他边，直到rem为正为止。在最坏情况下算法将每条边都处理为0，则时间复杂度为O(n3m)，其中n3为Floyd算法复杂度，m为边数。算法一次处理一条边，最坏情况是将所有边都进行处理后退出，所以不存在无法终止的情况。

2.3 强一致性的验证与消解

定理1 对于业务流P=(N,E,C)中任意结点n∈N的执行时间区间t，若t取其最大值和最小值时业务流仍能保持路径一致性，则P满足强一致性。

当取最小值时仍能保持一致，则说明当取最小值时距离图对应正向环的累加值仍为正，则取其余值时对应环的值仍为正；取最大值时分析类似。所以强一致性验证可以通过多个路径一致性检验来验证。

最短距离矩阵表示了路径各结点所能满足约束的时间区间。在STN中，一个环由一个约束和多个时间组成。设环中结点A和B，AB之间的距离表示了时间上界。结点AB除了A到B边还存在一条由约束上界和多个时间下界构成的路径，他们约束了AB时间上界，如果被超过说明取AB上界时环中其他时间都取下界仍会超过约束上界，无法满足约束。为了满足强一致性，路径中的时间上下界需要取最短距离图的。这样会缩短原结点区间上下界，但不会产生新的负环，因为修正后最短距离矩阵本身的对角线一定等于0，保证了没有负环。这样保证各个路径都满足强一致性。

若上述操作修改了路径之间公共结点区间上下界，可能会出现不一致的情况导致路径无法合并。为此需要检查对应路径之间的交集，若不为空，则路径的上下界都取交集。这样做缩短了时间上下界，可能导致路径不一致，所以需要重新计算他们的最短距离，若有不同重新替换。

设P={p1,p2,…,pn}为路径集合，P中各个公共边集合表示为R，强一致性消解与合并算法如下:

算法:强一致性消解与合并算法input:P={p1……pn}output:P’={p1’……pn’}while for(rin(pn(pm)) if(rm(rn=Ø)//rmrn是r在pnpm的边 balance(pn,pm) else rm=rn=(rm∩rn); refresh(pn,pm); endforuntil(norchange)returnP’

算法每次对比两个路径的公共结点r∈R，如果存在交集则两条路径均取交集并重新计算最短距离，若不存在交集则修改两个路径产生交集再重新处理。算法中设置refresh操作和balance操作。refresh操作重新计算距离矩阵的最短距离矩阵并更新对应数值使其满足强一致性；balance操作在一个环上对一条弧上的区间的一边进行收缩或扩张的同时在同样约束下的对应另一边进行相反操作，使得没有交集的公共边产生交集，方便进行合并。由于两条边都在一个约束下，他们不会对约束产生影响。例如有[1,2]和[3,4]两条边，取值范围是[4,6]，[3,4]边的一边扩展为[3,5]，将[1,2]缩小为[1,1]，取值范围仍是[4,6]。若两条边都在同一约束下，操作不会对一致性产生影响。

算法可能会对同一条边反复修改，每次修改都是缩短区间操作。最坏情况下，当所有区间上下界相同时算法停止。

3 案例分析

图3 流程业务流图

文献[4]的一个实例业务流如图3表示了某医疗诊断的流程。文献中只对其一致性进行了分析，没有对其冲突进行消解。这个业务流有2个选择分支，可以分解成4个路径A1A2A4A5A7、A1A3A4A6A7、A1A3A4A5A7和A1A2A4A6A7，以下简称路径P1P2P3P4。将他们分别转化为距离图矩阵后，首先对每条路径分别进行一致性检测，结果发现路径P4存在负环。根据优先级修改所属路径最少的A6的时间下界为30，消解了负环同时得到全源最短距离图。在以最短距离图进行上下界缩减后得出修正路径如图4所示。

图4 各个路径流图

检查各个路径的公共边， P1P4和P2P3的A4、P1P3的A5、P2P4的A6存在不一致。P1P2P3P4的A4存在交集[2,2]，取[2,2]重新计算最短距离无变化；P1P3的A5存在交集[25,25]，重新计算最短距离无变化；P2P4的A6交集为空，扩展P1、P2的A6前序边[1,1]为[1,5]，可扩展P2的A6为[30,45]，P4的A6为[25,30]，取交集得[30,30]，P4重新计算最短路径将边修正为[1,1]，与P2的[1,5]取交集得[1,1]，之后计算最短距离没有发生变化，修改完成。合并P1P2P3P4可得图5所示。

图5 修改完毕的业务流图

至此业务流中不再有冲突，完成了冲突消解。

4 结 语

目前对业务流约束验证的研究着重于研究验证单路径的时

间约束的满足情况，没有考虑多路径的情况，对时间一致性冲突消解的研究也很少。本文提出了路径一致性和强一致性，讨论了对应的一致性判断准则和不一致情况下的消解方法。以流程图的案例为例完成了冲突消解，验证方法的可行性。

本文的验证与消解方法属于静态验证，动态的验证方法是按序固定多个结点时间来对剩余的结点做验证，这将成为下步工作。

[1] 李慧芳,范玉顺.工作流系统时间管理[J].软件学报,2002,13(8):1552-1558.

[2] Chen J,Yang Y.Temporal dependency-based checkpoint selection for dynamic verification of temporal constraints in scientific workflow systems[J].ACM Transactions on Software Engineering and Methodology (TOSEM),2011,20(3):9.

[3] Cheikhrouhou S,Kallel S,Guermouche N,et al.Toward a Time-centric modeling of Business Processes in BPMN 2.0[C]//Proceedings of International Conference on Information Integration and Web-based Applications & Services.ACM,2013:154.

[4] Combi C,Gozzi M,Posenato R,et al.Conceptual modeling of flexible temporal workflows[J].ACM Transactions on Autonomous and Adaptive Systems (TAAS),2012,7(2):19.

[5] Du Y H,Xiong P C,Fan Y S,et al.Dynamic Checking and Solution to Temporal Violations in Concurrent Workflow Processes[J].IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS-PART A:SYSTEMS AND HUMANS,2011,41(6):1166-1181.

[6] Chinosi M,Trombetta A.BPMN:An introduction to the standard[J].Computer Standards & Interfaces,2012,34(1):124-134.

[7] Eder J,Panagos E,Rabinovich M.Workflow Time Management Revisited[M]//Seminal Contributions to Information Systems Engineering.Springer Berlin Heidelberg,2013:207-213

[8] Dechter R,Meiri I,Pearl J.Temporal constraint networks[J].Artificial intelligence,1991,49(1):61-95.

[9] Oei L I.Resolving Disruptions in Simple Temporal Problems[D].delft university of technology.Master’s Thesis in Computer Science.2009.

[10] Haouari M,Maculan N,Mrad M.Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles[J].Computers & Operations Research,2013,40(10):2485-2492.

[11] Rizzi R,Posenato R.Optimal Design of Consistent Simple Temporal Networks[C]//Temporal Representation and Reasoning (TIME),2013 20th International Symposium on.IEEE,2013:19-25.

TIME CONSISTENCY RESOLUTION FOR BUSINESS FLOW BASED ON STN

Yu Wenshu Zhou Yong Yan Xuefeng

(CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,Jiangsu,China)

Current study on validation of business flow constraint focuses on the situation of time constraint satisfaction in single-path but ignores the cases of multi-path,and the study on time consistency conflict resolution is also rare.In order to verify the time consistency in business flow,proceeding from path branch problem and the situation of dynamic time of single-task satisfying the constraint,in this paper we propose the path consistency and strong consistency based on original constraint consistency,and the STN method-based inconsistency resolution algorithm,as well as analyse its property of convergence,etc.In end of the paper,we take the business flow of medical process as an example to conduct the analysis and verification.

Business flow Time consistency Simple temporal network (STN) Consistency check Conflict resolution

2014-10-21。国防科工局十二五重大基础科研项目(c0420110005)。郁文枢，硕士生，主研领域：软件形式化与自动化。周勇，副教授。燕雪峰，副教授。

TP311

A

10.3969/j.issn.1000-386x.2016.04.056