基于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