郁文樞 周 勇 燕雪峰

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

郁文樞 周 勇 燕雪峰

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 距離圖矩陣

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

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

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

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

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

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

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

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

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

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

2.2 路徑一致性的檢測(cè)與消解

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

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

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

2.3 強(qiáng)一致性的驗(yàn)證與消解

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

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

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

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

設(shè)P={p1,p2,…,pn}為路徑集合，P中各個(gè)公共邊集合表示為R，強(qiáng)一致性消解與合并算法如下:

算法:強(qiáng)一致性消解與合并算法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’

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

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

3 案例分析

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

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

圖4 各個(gè)路徑流圖

檢查各個(gè)路徑的公共邊， P1P4和P2P3的A4、P1P3的A5、P2P4的A6存在不一致。P1P2P3P4的A4存在交集[2,2]，取[2,2]重新計(jì)算最短距離無變化；P1P3的A5存在交集[25,25]，重新計(jì)算最短距離無變化；P2P4的A6交集為空，擴(kuò)展P1、P2的A6前序邊[1,1]為[1,5]，可擴(kuò)展P2的A6為[30,45]，P4的A6為[25,30]，取交集得[30,30]，P4重新計(jì)算最短路徑將邊修正為[1,1]，與P2的[1,5]取交集得[1,1]，之后計(jì)算最短距離沒有發(fā)生變化，修改完成。合并P1P2P3P4可得圖5所示。

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

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

4 結(jié) 語

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

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

本文的驗(yàn)證與消解方法屬于靜態(tài)驗(yàn)證，動(dòng)態(tài)的驗(yàn)證方法是按序固定多個(gè)結(jié)點(diǎn)時(shí)間來對(duì)剩余的結(jié)點(diǎn)做驗(yàn)證，這將成為下步工作。

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

TP311

A

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