基于STN的業(yè)務(wù)流時間一致性消解方法

郁文樞 周 勇 燕雪峰

基于STN的業(yè)務(wù)流時間一致性消解方法

郁文樞 周 勇 燕雪峰

(南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院 江蘇 南京 210016)

目前對業(yè)務(wù)流約束驗證的研究著重于研究驗證單路徑的時間約束的滿足情況，沒有考慮多路徑的情況，對時間一致性沖突消解的研究也很少。為驗證業(yè)務(wù)流的時間一致性，從路徑分支問題和單任務(wù)動態(tài)時間滿足約束的情況出發(fā)，在原有約束一致性上提出路徑一致性和強一致性，以及基于STN(Simple Temporal Network)方法的不一致性消解算法并分析其收斂性等性質(zhì)。最后以醫(yī)療流程的業(yè)務(wù)流為例進行了分析驗證。

業(yè)務(wù)流 時間約束 STN 一致性檢驗 沖突消解

0 引 言

業(yè)務(wù)流建模方法被廣泛運用在各個領(lǐng)域，當(dāng)下對業(yè)務(wù)流模型的時間約束的驗證研究也很多，目前驗證的方法通常以對相關(guān)任務(wù)時間區(qū)間和約束時間進行數(shù)值計算或者使用模型檢測方法為主[1〗]。數(shù)值計算驗證通過對任務(wù)延遲和約束時間進行比較計算來判斷是否滿足約束，這種方法可以預(yù)先檢測時間是否可以滿足約束，但是只研究了業(yè)務(wù)流各時間區(qū)間是否可能滿足約束[2]，忽略了若干任務(wù)的執(zhí)行時間取值可能會導(dǎo)致后續(xù)約束的違反。模型檢測方法的思想基于窮舉法，通過設(shè)置狀態(tài)來記錄時間[3]，可以驗證任務(wù)時間約束，但是在結(jié)點比較多、時間粒度也比較小的情況下，時間效率無法保證[1]。文獻[4]以任一任務(wù)時間取值對選擇分支的影響出發(fā)定義了業(yè)務(wù)流的強弱一致性，但是驗證過程并不完整，并且缺少消解過程。文獻[5]通過構(gòu)建生成圖對業(yè)務(wù)流時序進行驗證和不一致消解，但是它不能確保消解不會影響其他約束?；谶@些問題本文提出路徑一致性和強一致性準(zhǔn)則，并提出了對應(yīng)的一致性判斷和消解方法。為此本文借助STN首先根據(jù)時間區(qū)間判斷業(yè)務(wù)流是否滿足路徑一致性，接著再判斷其是否滿足強一致性，最后針對消解問題提出了通過區(qū)間調(diào)節(jié)和路徑合并進行不一致消解的方法。

1 業(yè)務(wù)流與STN簡介

1.1 帶有時間約束信息的業(yè)務(wù)流

業(yè)務(wù)流是一個組織化業(yè)務(wù)流程，表現(xiàn)為一系列旨在業(yè)務(wù)目標(biāo)的完成的活動。它廣泛用于規(guī)范和業(yè)務(wù)過程可視化，其時間約束問題也被廣泛研究[6]。為了簡化問題本文只討論業(yè)務(wù)流的控制結(jié)構(gòu)，定義帶時間約束的業(yè)務(wù)流圖如下。

定義1 帶時序的業(yè)務(wù)流圖為一個多元組P=(N,F,C)，其中：

N=T∪G表示結(jié)點的集合，T?N是任務(wù)結(jié)點的集合。G?N代表分支結(jié)點的集合，F(xiàn)?N×N是結(jié)點間有向邊的集合。C是業(yè)務(wù)流中的時間約束的集合。

T表示原子任務(wù)集合。任務(wù)的持續(xù)時間通常不是確定的值而是一個范圍。以S(t)表示任務(wù)t∈T的開始時間，E(t)表示結(jié)束時間[7]，任務(wù)t持續(xù)時間為[MinT,MaxT],且滿足MinT≤E(t)-S(t)≤MaxT。G是業(yè)務(wù)流中的分支節(jié)點的集合，分支節(jié)點G包含了選擇分支和并行分支。選擇分支表示后繼邊中只選擇一條執(zhí)行，并行分支表示所有邊都要并行執(zhí)行。F?N×N是連接T或者G的有向邊的集合，表示結(jié)點間的順序關(guān)系。結(jié)點間的時間區(qū)間[MinT,MaxT]表示結(jié)點間的延遲范圍。C是業(yè)務(wù)流中的時間約束集合。它表現(xiàn)形式類似邊，約束了結(jié)點間的執(zhí)行時間。

例：圖1是一個業(yè)務(wù)流P。A是P中一個任務(wù)結(jié)點，標(biāo)示[2,6]表示該了該任務(wù)的持續(xù)時間。A與其他節(jié)點以實邊相連。虛線表示約束，AB之間的虛線[2,3]代表A到B的時間必須在區(qū)間[2,3]以內(nèi)。

圖1 一個業(yè)務(wù)流P

1.2 帶時間業(yè)務(wù)流轉(zhuǎn)換為STN

STN模型于1991年由Dechter等人提出，隨后以其簡潔的表達方式以及可有效驗證時間約束而得到廣泛應(yīng)用。STN定義為圖G=(V,E,I)，結(jié)點集合V表示時間點，邊集合E表示時間點間的間隔，每一條邊上都有一個約束范圍[Ii,Ij],來表示兩個時間點Ti和Tj之間需要滿足約束Ii

業(yè)務(wù)流中存在選擇分支，根據(jù)條件選擇某一后續(xù)結(jié)點繼續(xù)執(zhí)行。業(yè)務(wù)流在一次執(zhí)行中所執(zhí)行的結(jié)點的集合為一條路徑p=(N,F)，N和F分別為該路徑的結(jié)點和邊的集合。

一條路徑可以轉(zhuǎn)換為一個STN[4]，路徑到STN的轉(zhuǎn)換規(guī)則如下：

結(jié)點時序轉(zhuǎn)換規(guī)則：設(shè)有一個結(jié)點n,開始結(jié)束時間為S(n)和E(n)，若其對應(yīng)時間為[a,b]，則其表示為a≤E(n)-S(n) ≤b。

有向邊轉(zhuǎn)換規(guī)則：設(shè)有邊e連接結(jié)點n1、n2，e對應(yīng)的時間為[a,b]，則其約束關(guān)系可以表示為a≤E(n2)-S(n1) ≤b。

約束轉(zhuǎn)換規(guī)則:兩個結(jié)點A和B間約束[a,b]可以表示為a≤E(B)-S(A)≤b。

圖2 距離圖矩陣

利用規(guī)則可以將一個業(yè)務(wù)流圖轉(zhuǎn)換成一個或者多個STN。再將STN轉(zhuǎn)換為距離圖矩陣，就可方便地對其進行驗證與修正工作。例如圖1中P的路徑ABDE轉(zhuǎn)換為距離圖矩陣如圖2所示。

距離圖矩陣有自己特點，它的對角線一定為0，下三角除了Inf不存在正值，且下三角絕對值一定小于等于上三角對應(yīng)的正值。下文將距離圖中一條有向邊的權(quán)值稱為弧值。

2 業(yè)務(wù)流時間約束沖突檢測消解

2.1 業(yè)務(wù)流的路徑一致性與強一致性

定義2 (路徑一致性) 若對業(yè)務(wù)流的任意路徑p，路徑上所有節(jié)點n與邊f(xié)至少存在一組時間[t1,t2,…,tn]滿足該路徑上的所有約束，則稱該業(yè)務(wù)流是路徑一致的。

圖1業(yè)務(wù)流P中存在ABD和ACD兩條路徑，ACD存在一組執(zhí)行時間滿足約束[4,9]，但是ABD沒有執(zhí)行時間能滿足AB約束[2,3]。這樣ABD就無法執(zhí)行，業(yè)務(wù)流是路徑不一致的。反之如果能在ABD找到執(zhí)行時間滿足約束，就是路徑一致的。

路徑一致性保證了該業(yè)務(wù)流的每條路徑都是可執(zhí)行的。然而在業(yè)務(wù)流執(zhí)行期間，部分任務(wù)存在過大或者過小的執(zhí)行時間，會導(dǎo)致后續(xù)部分路徑約束無法滿足。為了檢測這類情況，需要擴展一致性，由此引出如下一致性定義。

定義3 (強一致性) 如果對業(yè)務(wù)流任意結(jié)點在其區(qū)間內(nèi)取任一執(zhí)行時間ti，任意路徑均是路徑一致的，則業(yè)務(wù)流滿足強一致性。

圖1的P中的A點的執(zhí)行時間允許取到6，一旦取到6無論AB之間[2,3]的時間約束和AD的[4,9]約束均無法滿足，所以P是強不一致的。反之就是強一致的。

滿足強一致性的情況下，可以保證任一任務(wù)時間的選擇和后續(xù)路徑是否可被執(zhí)行完全無關(guān)，使業(yè)務(wù)流的時間更有效、更具有參考價值。下面討論各一致性的檢測方法，以及對應(yīng)一致不滿足的化解。

2.2 路徑一致性的檢測與消解

業(yè)務(wù)流滿足路徑一致性是其滿足強一致性的基本條件。在STN中若各時間和約束的上下界構(gòu)成的環(huán)為負(fù)，約束就不被滿足[9]。將業(yè)務(wù)流路徑都轉(zhuǎn)換為STN，則路徑一致性的檢測就轉(zhuǎn)化為對距離圖負(fù)環(huán)的檢測，將負(fù)環(huán)消解就消解了路徑不一致性。Floyd算法是經(jīng)典最短路徑算法，在計算結(jié)束后得到全源最短路徑圖和全源最短距離圖[10]。如果出現(xiàn)負(fù)環(huán)(距離圖矩陣對角線出現(xiàn)負(fù)值)，則將負(fù)環(huán)權(quán)值改為正就修正了不一致。有時約束本身相互沖突，無法同時滿足所有約束的要求。在檢測前對距離矩陣圖進行一次檢測，若負(fù)環(huán)包含多個約束，說明約束存在沖突，需要重新確認(rèn)。

算法產(chǎn)生最短路徑矩陣為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

修正弧值需要同時保持距離圖的性質(zhì)[11]。為此為每條邊設(shè)置一個優(yōu)先度P。約束邊的p設(shè)為0表示優(yōu)先度最低，其他弧設(shè)一個初始值，每次修改優(yōu)先度減少1，以此達到修改要求。

算法中floyd操作根據(jù)Floyd思想尋找負(fù)環(huán)，一旦找出一個負(fù)環(huán)，以其負(fù)環(huán)路徑L計算其負(fù)值rem。之后遍歷L，找到一個優(yōu)先度最高的邊，對其進行修正；若滿足正值，則繼續(xù)尋找下一負(fù)環(huán)，否則再尋找其他邊，直到rem為正為止。在最壞情況下算法將每條邊都處理為0，則時間復(fù)雜度為O(n3m)，其中n3為Floyd算法復(fù)雜度，m為邊數(shù)。算法一次處理一條邊，最壞情況是將所有邊都進行處理后退出，所以不存在無法終止的情況。

2.3 強一致性的驗證與消解

定理1 對于業(yè)務(wù)流P=(N,E,C)中任意結(jié)點n∈N的執(zhí)行時間區(qū)間t，若t取其最大值和最小值時業(yè)務(wù)流仍能保持路徑一致性，則P滿足強一致性。

當(dāng)取最小值時仍能保持一致，則說明當(dāng)取最小值時距離圖對應(yīng)正向環(huán)的累加值仍為正，則取其余值時對應(yīng)環(huán)的值仍為正；取最大值時分析類似。所以強一致性驗證可以通過多個路徑一致性檢驗來驗證。

最短距離矩陣表示了路徑各結(jié)點所能滿足約束的時間區(qū)間。在STN中，一個環(huán)由一個約束和多個時間組成。設(shè)環(huán)中結(jié)點A和B，AB之間的距離表示了時間上界。結(jié)點AB除了A到B邊還存在一條由約束上界和多個時間下界構(gòu)成的路徑，他們約束了AB時間上界，如果被超過說明取AB上界時環(huán)中其他時間都取下界仍會超過約束上界，無法滿足約束。為了滿足強一致性，路徑中的時間上下界需要取最短距離圖的。這樣會縮短原結(jié)點區(qū)間上下界，但不會產(chǎn)生新的負(fù)環(huán)，因為修正后最短距離矩陣本身的對角線一定等于0，保證了沒有負(fù)環(huán)。這樣保證各個路徑都滿足強一致性。

若上述操作修改了路徑之間公共結(jié)點區(qū)間上下界，可能會出現(xiàn)不一致的情況導(dǎo)致路徑無法合并。為此需要檢查對應(yīng)路徑之間的交集，若不為空，則路徑的上下界都取交集。這樣做縮短了時間上下界，可能導(dǎo)致路徑不一致，所以需要重新計算他們的最短距離，若有不同重新替換。

設(shè)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’

算法每次對比兩個路徑的公共結(jié)點r∈R，如果存在交集則兩條路徑均取交集并重新計算最短距離，若不存在交集則修改兩個路徑產(chǎn)生交集再重新處理。算法中設(shè)置refresh操作和balance操作。refresh操作重新計算距離矩陣的最短距離矩陣并更新對應(yīng)數(shù)值使其滿足強一致性；balance操作在一個環(huán)上對一條弧上的區(qū)間的一邊進行收縮或擴張的同時在同樣約束下的對應(yīng)另一邊進行相反操作，使得沒有交集的公共邊產(chǎn)生交集，方便進行合并。由于兩條邊都在一個約束下，他們不會對約束產(chǎn)生影響。例如有[1,2]和[3,4]兩條邊，取值范圍是[4,6]，[3,4]邊的一邊擴展為[3,5]，將[1,2]縮小為[1,1]，取值范圍仍是[4,6]。若兩條邊都在同一約束下，操作不會對一致性產(chǎn)生影響。

算法可能會對同一條邊反復(fù)修改，每次修改都是縮短區(qū)間操作。最壞情況下，當(dāng)所有區(qū)間上下界相同時算法停止。

3 案例分析

圖3 流程業(yè)務(wù)流圖

文獻[4]的一個實例業(yè)務(wù)流如圖3表示了某醫(yī)療診斷的流程。文獻中只對其一致性進行了分析，沒有對其沖突進行消解。這個業(yè)務(wù)流有2個選擇分支，可以分解成4個路徑A1A2A4A5A7、A1A3A4A6A7、A1A3A4A5A7和A1A2A4A6A7，以下簡稱路徑P1P2P3P4。將他們分別轉(zhuǎn)化為距離圖矩陣后，首先對每條路徑分別進行一致性檢測，結(jié)果發(fā)現(xiàn)路徑P4存在負(fù)環(huán)。根據(jù)優(yōu)先級修改所屬路徑最少的A6的時間下界為30，消解了負(fù)環(huán)同時得到全源最短距離圖。在以最短距離圖進行上下界縮減后得出修正路徑如圖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]，之后計算最短距離沒有發(fā)生變化，修改完成。合并P1P2P3P4可得圖5所示。

圖5 修改完畢的業(yè)務(wù)流圖

至此業(yè)務(wù)流中不再有沖突，完成了沖突消解。

4 結(jié) 語

目前對業(yè)務(wù)流約束驗證的研究著重于研究驗證單路徑的時

間約束的滿足情況，沒有考慮多路徑的情況，對時間一致性沖突消解的研究也很少。本文提出了路徑一致性和強一致性，討論了對應(yīng)的一致性判斷準(zhǔn)則和不一致情況下的消解方法。以流程圖的案例為例完成了沖突消解，驗證方法的可行性。

本文的驗證與消解方法屬于靜態(tài)驗證，動態(tài)的驗證方法是按序固定多個結(jié)點時間來對剩余的結(jié)點做驗證，這將成為下步工作。

[1] 李慧芳,范玉順.工作流系統(tǒng)時間管理[J].軟件學(xué)報,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。國防科工局十二五重大基礎(chǔ)科研項目(c0420110005)。郁文樞，碩士生，主研領(lǐng)域：軟件形式化與自動化。周勇，副教授。燕雪峰，副教授。

TP311

A

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