蔣艷榮,李衛(wèi)華,楊勁濤

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 廣東 廣州 510006)

一種基于知識(shí)樹和約束的柔性活動(dòng)動(dòng)態(tài)細(xì)化方法

蔣艷榮,李衛(wèi)華,楊勁濤

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 廣東 廣州 510006)

柔性工作流在應(yīng)對(duì)業(yè)務(wù)建模過程中的動(dòng)態(tài)不確定因素、提高工作流系統(tǒng)的柔性具有巨大的優(yōu)勢(shì),然而,柔性活動(dòng)的動(dòng)態(tài)細(xì)化一直是柔性工作流建模和應(yīng)用的一個(gè)難點(diǎn)。因此,提出一種基于知識(shí)樹和約束的柔性活動(dòng)動(dòng)態(tài)細(xì)化方法。該方法以知識(shí)樹的包含和泛化關(guān)系作為啟發(fā)信息,以活動(dòng)選取約束和時(shí)序約束作為指導(dǎo)和校驗(yàn),實(shí)現(xiàn)柔性活動(dòng)的動(dòng)態(tài)細(xì)化。在介紹了知識(shí)樹及其蘊(yùn)含關(guān)系以及活動(dòng)選取約束和時(shí)序約束規(guī)則的基礎(chǔ)上,給出了柔性活動(dòng)的動(dòng)態(tài)細(xì)化算法,描述了活動(dòng)選取校驗(yàn)和時(shí)序約束校驗(yàn)算法。最后給出了算法的實(shí)現(xiàn)和實(shí)例分析,其結(jié)果表明了所提方法的有效性,能夠很好地解決柔性活動(dòng)的細(xì)化問題。

柔性工作流; 動(dòng)態(tài)細(xì)化; 時(shí)序約束; 工作流生成; 過程建模

近年來,隨著人工智能、自動(dòng)控制等技術(shù)的發(fā)展,工作流在很多領(lǐng)域獲得了廣泛的應(yīng)用。然而,傳統(tǒng)工作流建模和實(shí)施的剛硬性限制了工作流應(yīng)用的成功,其靜態(tài)、無柔性的流程描述無法適應(yīng)動(dòng)態(tài)、復(fù)雜的業(yè)務(wù)過程。隨著工作流應(yīng)用領(lǐng)域的不斷拓寬,這種復(fù)雜性不斷加大,表現(xiàn)在業(yè)務(wù)過程中存在大量的不確定、模糊和不完整的流程信息,但是在工作流的建模階段,卻無法涵蓋所有的不確定因素。這對(duì)工作流的建模和應(yīng)用帶來巨大的困難。因此,如何針對(duì)業(yè)務(wù)過程具有的動(dòng)態(tài)性和模糊性,提高工作流的柔性,成為工作流研究領(lǐng)域的一個(gè)熱點(diǎn)問題[1-2]。

動(dòng)態(tài)細(xì)化是提高工作流柔性、應(yīng)對(duì)不確定性的一種有效方法[1]。其基本思想是: 在流程實(shí)例運(yùn)行之前,先對(duì)業(yè)務(wù)流程的已知部分進(jìn)行建模,建立流程模型的整體框架,而不需要精確、完整地定義流程模型的每一個(gè)細(xì)節(jié)。對(duì)不清楚的局部細(xì)節(jié)可以用“黑箱”活動(dòng)來描述[3-5],然后隨著業(yè)務(wù)工作的展開和對(duì)具體問題認(rèn)識(shí)的不斷深入,在過程運(yùn)行中動(dòng)態(tài)細(xì)化流程模型,以提高流程模型的柔性。因此,動(dòng)態(tài)細(xì)化成為提高業(yè)務(wù)過程柔性的關(guān)鍵,其本質(zhì)是將過程中不確定的、模糊的區(qū)域進(jìn)行逐步細(xì)化,用一種更明確、更細(xì)尺度的活動(dòng)或子流程去進(jìn)行代替。該不確定的區(qū)域在很多文獻(xiàn)中被封裝為柔性活動(dòng)或占位符等。例如,S. Sadiq(2001)等[3]采用柔性區(qū)(pocket of flexiblity)來提高工作流的柔性,并為柔性區(qū)提供實(shí)例模版,支持多種控制結(jié)構(gòu)。鄧水光等[6]將過程中的不確定因素用“flexible activity”表示,用ECA規(guī)則表示活動(dòng)之間的邏輯關(guān)系。

現(xiàn)有的研究工作在動(dòng)態(tài)細(xì)化方面取得了較多的進(jìn)展。文獻(xiàn)[7]采用柔性活動(dòng)對(duì)不確定因素進(jìn)行封裝,然后對(duì)柔性活動(dòng)進(jìn)行縱向分解,生成不同抽象水平的活動(dòng),從而提出一種支持柔性活動(dòng)樹狀分解和增量細(xì)化的柔性工作流建模方法。Joonsoo Bae[8]提出了一種樹形的過程模型的表示,采用ECA規(guī)則表示活動(dòng)關(guān)系,并用存儲(chǔ)過程實(shí)現(xiàn)了ECA規(guī)則。其缺點(diǎn)是,為每個(gè)ECA規(guī)則創(chuàng)建一個(gè)對(duì)應(yīng)的存儲(chǔ)過程并管理活動(dòng)的狀態(tài),是一個(gè)耗時(shí)和成本高昂的事情。Y. Gil[9]采用工作流來實(shí)現(xiàn)計(jì)算實(shí)驗(yàn)的設(shè)計(jì)過程,將其功能實(shí)現(xiàn)逐步細(xì)化為組件選擇、數(shù)據(jù)集選擇和參數(shù)選擇3個(gè)步驟,其缺點(diǎn)在于其建模過程的柔性不夠,其建模和細(xì)化方法難以借鑒到其他應(yīng)用領(lǐng)域,同時(shí)需要提供完備的組件庫(kù)。S.A.Chun等[10]在實(shí)現(xiàn)跨組織的工作流子流程自動(dòng)生成的過程中,采用政府組織的本體樹來幫助生成子流程,其缺點(diǎn)是生成的子流程控制結(jié)構(gòu)比較簡(jiǎn)單,難以適應(yīng)復(fù)雜流程結(jié)構(gòu)的生成。同時(shí)適應(yīng)面較窄,本體的建立和合理利用也比較困難。Shepelev[11]針對(duì)計(jì)算機(jī)輔助VLSI的設(shè)計(jì)領(lǐng)域,提出一種基于任務(wù)計(jì)劃的圖形邏輯表達(dá)的工作流自動(dòng)生成方法。

上述研究工作,雖然在提高工作流建模的柔性和柔性活動(dòng)細(xì)化上取得了較多的進(jìn)展,但是存在如下不足:1) 在工作流建模和細(xì)化時(shí),未能充分考慮到工作流的應(yīng)用背景,如動(dòng)態(tài)因素和不確定因素多,需要滿足一定的約束條件等特點(diǎn),而這對(duì)于柔性建模和活動(dòng)細(xì)化非常重要;2) 一些工作側(cè)重于某個(gè)特定領(lǐng)域的工作流自動(dòng)生成,在通用性方面存在不足;或者過于強(qiáng)調(diào)靈活性,試圖從頭開始創(chuàng)建工作流,這非常依賴于模型設(shè)計(jì)者的技能和特殊知識(shí),而沒有充分利用領(lǐng)域知識(shí)來指導(dǎo)實(shí)現(xiàn)動(dòng)態(tài)細(xì)化;3)現(xiàn)有的柔性活動(dòng)細(xì)化的研究還不夠,特別是考慮到約束條件等因素影響的細(xì)化研究還比較缺乏。

因此,本文提出一種基于知識(shí)樹和約束的柔性活動(dòng)細(xì)化方法,知識(shí)樹可以為柔性活動(dòng)的細(xì)化過程提供指導(dǎo),而相關(guān)的約束規(guī)則可以為細(xì)化過程提供活動(dòng)選擇、活動(dòng)時(shí)序關(guān)系的校驗(yàn)。

1 柔性工作流的建模

定義1 柔性活動(dòng)是一種特殊的活動(dòng)類型,在建模階段由于存在模糊和不確定的因素,而無法事先給出完整和明確的活動(dòng)定義,需要獲取更多和更完全的信息以將柔性元素逐步明確化。柔性活動(dòng)可用一個(gè)多元組表示:FA=(Id, name, Ctx, FAP, FAR, FAC, Role, Rdata, Attr),其中Id為柔性活動(dòng)的唯一標(biāo)識(shí);name為柔性活動(dòng)的名稱;Ctx為柔性活動(dòng)的應(yīng)用上下文,包括該柔性活動(dòng)需要達(dá)成的目標(biāo)和完成的功能,以及應(yīng)用場(chǎng)景等; FAP=Aatom∪Acomp∪Aflex為柔性活動(dòng)的活動(dòng)池,分別由原子活動(dòng)集、復(fù)合活動(dòng)集合柔性活動(dòng)集組成。也就是說,柔性活動(dòng)可以由原子活動(dòng)、復(fù)合活動(dòng)和其他柔性活動(dòng)構(gòu)成。Role是活動(dòng)執(zhí)行者對(duì)應(yīng)的角色; Rdata是與此活動(dòng)相關(guān)的工作流相關(guān)數(shù)據(jù),包括輸入數(shù)據(jù)和輸出數(shù)據(jù)。Attr為活動(dòng)具有的屬性集。

FAR=FR∪CR為描述活動(dòng)池中活動(dòng)關(guān)系的規(guī)則集,可以為空。其中FR為柔性規(guī)則集,CR為普通規(guī)則集,采用ECA規(guī)則形式表示。FAC=C∪M為柔性活動(dòng)的約束規(guī)則集,其目的是用于柔性活動(dòng)細(xì)化過程中的活動(dòng)選擇、活動(dòng)時(shí)序關(guān)系的校驗(yàn)和生成子流圖的正確性驗(yàn)證,以保證細(xì)化結(jié)果的正確。采用一元或二元謂詞、預(yù)設(shè)的操作集和規(guī)則進(jìn)行表達(dá),在柔性活動(dòng)的細(xì)化過程中,生成的子流程必須滿足該約束條件的規(guī)定。其中,C為約束規(guī)則集,用于約束活動(dòng)的選取、活動(dòng)的組合、活動(dòng)之間的時(shí)序關(guān)系、活動(dòng)的屬性等;M為修正規(guī)則集,用于對(duì)生成的流程進(jìn)行修改。

定義2 柔性工作流。柔性工作流是一個(gè)四元組,FWF = (ID,D,A,E),其中ID為柔性工作流的唯一標(biāo)識(shí)符,D為柔性工作流的一般描述信息,如工作流的版本號(hào),流程的創(chuàng)建日期等,D=(Version, Date, Desciption, …);A為流程中的活動(dòng)集合,A=Aatom∪Acomp∪Aflex;E表示工作流中規(guī)則的集合,用ECA規(guī)則表示,用來描述活動(dòng)之間的時(shí)序關(guān)系。

該模型采用柔性活動(dòng)封裝流程中的不確定的、模糊的因素,采用原子活動(dòng)和復(fù)合活動(dòng)描述具有不同抽象度的流程元素,可以快速建立流程模型,并隨著領(lǐng)域知識(shí)的后續(xù)獲取和分析的逐步深入,對(duì)柔性活動(dòng)進(jìn)行明確化和細(xì)化,以減低復(fù)雜領(lǐng)域的工作流建模難度,提高模型的穩(wěn)健性和易用性。

2 細(xì)化算法

2.1 知識(shí)樹及與流程模板的影射

在領(lǐng)域知識(shí)表示中,可以用不同粒度大小的知識(shí)點(diǎn)來表示不同的知識(shí)單元。而知識(shí)點(diǎn)不是孤立存在的,它們之間存在著各種關(guān)系,考察這些關(guān)系對(duì)于工作流的生成具有促進(jìn)作用。

定義3 知識(shí)點(diǎn)。知識(shí)點(diǎn)可以表示為一個(gè)多元組:K=(ID, name, des, KWS), 其中ID為知識(shí)點(diǎn)的唯一編號(hào),name為知識(shí)點(diǎn)的名稱,des為知識(shí)點(diǎn)的描述,包括該知識(shí)點(diǎn)的定義、闡述等,來源于領(lǐng)域知識(shí);KWS為知識(shí)的關(guān)鍵詞集,是對(duì)該知識(shí)點(diǎn)的高度概括。

定義4 包含關(guān)系。表示知識(shí)點(diǎn)Kj與Ki之間存在整體與部分的關(guān)系,記為a(Ki,Kj),表示Kj包含Ki。知識(shí)點(diǎn)可以被分解為幾個(gè)滿足包含關(guān)系的知識(shí)點(diǎn),依次類推,一直到不能分解為此。

定義5 泛化關(guān)系。泛化關(guān)系可以定義為一般與特殊的關(guān)系,記為g(Ki,Kj), 表示知識(shí)點(diǎn)Ki是Kj的特殊情況,Kj與Ki滿足一般與特殊的關(guān)系。例如,面向?qū)ο笤O(shè)計(jì)、基于結(jié)構(gòu)化的設(shè)計(jì)和面向過程的設(shè)計(jì)等是軟件設(shè)計(jì)的特殊情況,是軟件設(shè)計(jì)在面對(duì)不同領(lǐng)域的具體應(yīng)用。

定義6 父子關(guān)系。若對(duì)任意的兩個(gè)知識(shí)點(diǎn)x,y,滿足a(x,y)或g(x,y)成立,則稱知識(shí)點(diǎn)y和x滿足父子關(guān)系,x為y的子知識(shí)點(diǎn),記為s(x,y)。 顯然,這種關(guān)系具有單反性、傳遞性。

定義7 知識(shí)樹。對(duì)一個(gè)知識(shí)點(diǎn)A自頂向下地進(jìn)行逐步分解,則最終可得到一棵根節(jié)點(diǎn)為A的樹,我們稱其為知識(shí)樹,記為T(A)。樹中的孩子節(jié)點(diǎn)是雙親節(jié)點(diǎn)的子知識(shí)點(diǎn),滿足包含或泛化關(guān)系。當(dāng)樹中所有的知識(shí)點(diǎn)都不能分解時(shí),則分解過程結(jié)束。

顯然,可以用知識(shí)樹表示不同的領(lǐng)域知識(shí)。這種知識(shí)表達(dá)具有直觀、易于理解和易于建立的特點(diǎn),可以由領(lǐng)域?qū)＜疫M(jìn)行構(gòu)建,而不需要建模和開發(fā)的專業(yè)知識(shí)。圖1為一棵關(guān)于軟件開發(fā)過程的知識(shí)樹,其中包含了包含關(guān)系和泛化關(guān)系。

圖1 軟件開發(fā)的知識(shí)樹Fig.1 Knowledge tree for software development

針對(duì)某一個(gè)領(lǐng)域的知識(shí)樹數(shù)目比較多,則構(gòu)成了一個(gè)知識(shí)樹森林。那么在建立了領(lǐng)域知識(shí)的知識(shí)樹之后,為了用于指導(dǎo)流程建模和柔性工作流細(xì)化,需要將流程模板與知識(shí)樹的知識(shí)點(diǎn)之間進(jìn)行關(guān)聯(lián),即為流程模板與知識(shí)樹的映射。流程模板庫(kù)的建立需要全體設(shè)計(jì)人員在設(shè)計(jì)過程中共同構(gòu)建。需要注意的是,流程模板可以全部由定義完全的子活動(dòng)或復(fù)合活動(dòng)構(gòu)成,也可以在流程中包含子柔性活動(dòng)。

映射的步驟可描述為:1)根據(jù)知識(shí)點(diǎn)的名稱,在流程模板庫(kù)中進(jìn)行搜索,得到屬性相同的流程模板集合;2) 考察集合中的每個(gè)流程模板的適用條件,得到各模板的適用性并進(jìn)行排序;3) 若集合只有一個(gè)流程模板,則返回該模板,否則返回適用性最高的流程模板。

2.2 約束規(guī)則

柔性工作流的細(xì)化過程,其實(shí)質(zhì)為柔性活動(dòng)逐步細(xì)化和確定化的過程。在此過程中,需要將一些模糊的、抽象的需求進(jìn)行具體化,將粗粒度的元素轉(zhuǎn)換為細(xì)粒度的元素。顯然,該細(xì)化過程需要遵循某些特定的約束和規(guī)則,滿足該活動(dòng)定義的初始意圖。例如,在工作流的設(shè)計(jì)階段,用Ctx參數(shù)規(guī)定了柔性活動(dòng)需要達(dá)成的目標(biāo)和完成的功能,以及應(yīng)用的條件等。那么在確定化該柔性活動(dòng)時(shí),需要滿足所設(shè)目標(biāo)或功能的約束要求。在細(xì)節(jié)上,需要根據(jù)選取規(guī)則從系統(tǒng)提供的活動(dòng)庫(kù)中選取合適的活動(dòng),并用時(shí)序規(guī)則約束活動(dòng)之間的時(shí)序關(guān)系。具體討論如下。

1) 活動(dòng)選取規(guī)則

用于約束活動(dòng)的選取。用謂詞select()表示活動(dòng)的選取, 可以用邏輯運(yùn)算符進(jìn)行連接,分如下情況: 1)select(a)表示選取活動(dòng)a; 2)NOT select(a)表示不能選取活動(dòng)a; 3) select(a) AND select(b) AND…表示同時(shí)選取活動(dòng)a,b,…; 4) select(a) OR select(b) OR…表示選擇活動(dòng)a,b,…中的任意活動(dòng)。在這里,邏輯運(yùn)算符的優(yōu)先性滿足:NOT>AND>OR。

用產(chǎn)生式規(guī)則對(duì)活動(dòng)選取的邏輯約束進(jìn)行規(guī)定,形式如下:

IF〈context(1)〉A(chǔ)ND〈context(2)〉 …

AND〈context(n)〉THEN〈selections〉

(1)

式中：context為與工作流相關(guān)的上下文環(huán)境,可以是當(dāng)前的上下文事實(shí),如“the calculus type is staghorn”,也可以是對(duì)某個(gè)活動(dòng)的選取或未選取情況。selections為一個(gè)或多個(gè)活動(dòng)的選取邏輯,如select(a) AND NOT select(b)。以上表達(dá)可以簡(jiǎn)寫為C1∧C2∧…Cn→S, whereCimeans 〈context(i)〉 andSmeans selections。 規(guī)則的前題和結(jié)論可以為多個(gè)item的合取范式。對(duì)于多個(gè)context組成的析取范式,如(C11∧C12∧…)∨(C21∧C22∧…)∨…則拆分為由簡(jiǎn)單的合取范式前提組成的多個(gè)規(guī)則如下:

(2)

2) 活動(dòng)的時(shí)序約束規(guī)則

用于約束活動(dòng)之間的時(shí)序關(guān)系。① 用Previous(x,y)表示活動(dòng)x在活動(dòng)y之前執(zhí)行(中間可以插入其他活動(dòng)); ② ImtPrevious(x,y)表示活動(dòng)x在y之前執(zhí)行,且x是y的直接前驅(qū)(中間沒有其他活動(dòng));③ AndSyn (x,y)表示活動(dòng)x與y為并行執(zhí)行關(guān)系(AND-split/AND-join),必須要在x與y兩者執(zhí)行完之后才能執(zhí)行下一活動(dòng);④ OrSyn(x,y) 表示活動(dòng)x與y為選擇執(zhí)行關(guān)系(OR-split/OR-join),在執(zhí)行時(shí),根據(jù)上下文在x與y兩者選擇其一執(zhí)行,x與y任意一個(gè)執(zhí)行完可以觸發(fā)后續(xù)活動(dòng)的運(yùn)行; ⑤ NotLimit(x,y) 表示活動(dòng)x與y的執(zhí)行次序隨意,活動(dòng)x可以在y之前執(zhí)行,也可以在y之后執(zhí)行。

可以用規(guī)則描述活動(dòng)之間復(fù)雜的時(shí)序約束,規(guī)則的形式如下: IF selectOp(x1) AND selectOp(x2) AND selectOp(xi) AND …。AND selectOp(xn) THEN temporalCons1 AND temporalCons2AND…temporalConsn。 這里,selectOp 表示select() 或NOT select(), temporalCons 表示這5個(gè)時(shí)序約束。

以下為一個(gè)時(shí)序約束的規(guī)則實(shí)例:

IF select(a) AND select(b) THEN Previous(a,b), 如果選擇了活動(dòng)a和b,則活動(dòng)a必須要在b之前執(zhí)行。

一般情況下,規(guī)則的前件都是對(duì)涉及到的活動(dòng)的選取情況進(jìn)行判斷,即很少有NOT的情況,此時(shí)前件可以忽略,則規(guī)則可以轉(zhuǎn)換為時(shí)序約束集:{Previous(a,b), AndSyn(c,d), …}。

3)屬性約束規(guī)則

包括時(shí)間約束規(guī)則、地點(diǎn)約束規(guī)則等,用于對(duì)活動(dòng)屬性的約束。如對(duì)活動(dòng)的時(shí)間屬性進(jìn)行約束:“活動(dòng)a的持續(xù)時(shí)間不能大于3天”、“活動(dòng)b在活動(dòng)a結(jié)束后的3 hour內(nèi)必須開始”等。

顯然,邏輯運(yùn)算符的引入可以實(shí)現(xiàn)復(fù)雜的約束邏輯,以適應(yīng)復(fù)雜多變的建模需求。那么通過對(duì)模糊信息的封裝,在較大粒度的層面快速建立起流程模型之后,通過對(duì)柔性活動(dòng)約束條件的設(shè)定,可以作為啟發(fā)信息用于柔性活動(dòng)的細(xì)化和確保創(chuàng)建的工作流的正確性。

2.3 柔性活動(dòng)的動(dòng)態(tài)細(xì)化算法

柔性活動(dòng)的細(xì)化算法FlexActRefining()如圖2所示。

圖2 柔性活動(dòng)細(xì)化算法FlexActRefiningFig.2 Refinement algorithm for flexible activity

在細(xì)化過程中,利用知識(shí)樹中知識(shí)點(diǎn)之間的關(guān)系作為啟發(fā)信息用于輔助生成子流圖,用柔性活動(dòng)的約束規(guī)則(包括活動(dòng)選取約束、時(shí)序關(guān)系約束等)對(duì)細(xì)化后的子流程進(jìn)行驗(yàn)證,其主要步驟如下:

1) 根據(jù)柔性活動(dòng)的目標(biāo),在知識(shí)樹中查找匹配的節(jié)點(diǎn)。對(duì)該節(jié)點(diǎn)映射的流程模板進(jìn)行分析:若存在完善的流程模板,則選擇匹配最佳的流程模板返回;否則轉(zhuǎn)2)。

2)分析該節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系。若不存在子節(jié)點(diǎn),則如果存在對(duì)應(yīng)的約束關(guān)系,用約束關(guān)系生成流程并返回,否則出錯(cuò)返回。如果存在子節(jié)點(diǎn),則根據(jù)如下規(guī)則將父節(jié)點(diǎn)的實(shí)現(xiàn)轉(zhuǎn)換為子節(jié)點(diǎn)的實(shí)現(xiàn),生成細(xì)化的子流圖。①若存在明確的時(shí)序關(guān)系規(guī)定,則按照時(shí)序關(guān)系的要求去生成細(xì)化的子流圖;② 若該節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系為包含關(guān)系,則按照AND或順序結(jié)構(gòu)生成子流圖;③ 若該節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系為泛化關(guān)系,則按照OR結(jié)構(gòu)生成子流圖;④ 其他情況則按照順序結(jié)構(gòu)生成子流圖。

3)依據(jù)約束規(guī)則,對(duì)生成的子流圖進(jìn)行校驗(yàn)。分別調(diào)用函數(shù)ActSelValid()對(duì)活動(dòng)選取進(jìn)行校驗(yàn),調(diào)用TemporalCons( )對(duì)活動(dòng)的時(shí)序約束進(jìn)行校驗(yàn)。若沒有通過校驗(yàn),則出錯(cuò)返回。

4) 檢查生成的子流圖是否存在子柔性活動(dòng)。若不存在,則返回生成的子流圖,算法結(jié)束。否則,對(duì)每一個(gè)子柔性活動(dòng),轉(zhuǎn)算法的步驟1)。

3 校驗(yàn)算法

對(duì)生成的子流程通常存在著合法性檢驗(yàn)問題。一個(gè)子流圖只有符合柔性活動(dòng)的設(shè)計(jì)目標(biāo)和功能,滿足其預(yù)先定義的約束條件,才能被認(rèn)為是合法的和有效的。另外,子流圖在流程結(jié)構(gòu)上必須要定義良好,例如不存在孤立不可到達(dá)的活動(dòng)、不存在死循環(huán)等,對(duì)此可以采用拓?fù)渑判蜻M(jìn)行檢查。下面從以上幾個(gè)方面對(duì)柔性活動(dòng)細(xì)化后生成的子流圖的合法性進(jìn)行檢驗(yàn),其中, ActSelValid ()是活動(dòng)選取規(guī)則檢驗(yàn)算法, TemporalCons( )是活動(dòng)時(shí)序約束檢驗(yàn)算法。

設(shè)選取的活動(dòng)組成的集合為A,A={a1,a2, …,an}, 選擇約束sc可以分解為左部Lpart和右部Rpart, Lpart由上下文事實(shí)和活動(dòng)選擇的操作組成,Rpart為操作的邏輯表達(dá)式。如Lpart=con1AND con2OR…AND conn, coni=ctxi| opi, ctx為上下文事實(shí),如“calculus。diameter≤20 mm”,op = select() | NOT select()。 在算法ActSelValid()中,Ei代表true or false。 算法 1 ActSelValid ( )

輸入 activity setA, activity selection constraintsSC.

輸出 return true if valid, false if not valid

{

for each selection constraintsciinSC{

decomposesciinto Lpart and Rpart;

for each coniin Lpart {

if coniis “NOT select(a)”

ifaAthen coni= false;

else coni= true;

if coniis “select(a)”

ifaAthen coni= true;

else coni= false;

if coniisctx

check if there exist factfaciand coni=faci

coni= true;

else coni= false;

}

while Lpart is not a single “true” or “false”{

if there exist “E1 AND…AND En” in Lpart{

if there exist a “false” in sub-expression

replace sub-expression with “false”;

else replace it with “true”;

}

if there exist “E1 OR…OR En” in Lpart{

if there exist a “true” in sub-expression

replace the sub-expression with “true”;

else replace it with “false”;

}

} // end while

if Lpart is true then{// rulesciis triggered.

for each opiin Rpart {

if opiis “NOT select(a)”

ifaAthen opi= false;

else opi= true;

if opiis “select(a)”

ifaAthen opi= true;

else opi= false;

}//end for

while Rpart is not a single “true” or “false”{

if there exist “E1AND…En” in Rpart{

if there exist a “false” in sub-expression

replace sub-expression with “false”;

else replace it with “true”;

}

if there exist “E1OR…En” in Rpart{

if there exist a “true” in sub-expression

replace sub-expression with “true”;

else replace it with “false”;

}

} // end while

if Rpart is “false” then{

report the information of error to user;

return false; //quit

}

} // end of the deal of Rpart

}// end of the deal ofsci

return true;

TemporalCons( )是活動(dòng)時(shí)序約束檢驗(yàn)算法,其中A為活動(dòng)集,TC為時(shí)序約束集。算法首先檢查時(shí)序約束tc涉及的活動(dòng)是否存在于活動(dòng)集A中,如果不存在,則返回false. 時(shí)序約束規(guī)則tc可以分解出由時(shí)序約束組成的操作集Rpart,然后對(duì)其中每個(gè)約束進(jìn)行檢查,對(duì)不滿足約束的情況進(jìn)行出錯(cuò)報(bào)告,并返回false.

算法二 TemporalCons( )

輸入 activity setA, activity temporal constraints TC.

輸出 return true if valid, false if not valid

{

for each temporal constraint tciin TC {

decompose tciinto Lpart and Rpart;

if activities referred by Lpart are all in setA{

for each opiin Rpart{

if opiis “Previous(a,b)”{

if there is no path fromatob{

mark the error place;

return false;

}

}

if opiis “ImtPrevious (a,b)”{

if there is not any edge 〈a,b〉 then{

mark the error place;

return false;

}

}

if opiis “AndSyn (a,b)”{

if there exists a common predecessorAs

and successorAeforaandbthen{

if satisfy Previous(As,a) and

Previous(As,b) and Previous(a,Ae)

and Previous(b,Ae) and there exist no

path fromatoborbtoathen{

return true;

}

}

return false;

}

if opiis “OrSyn(a,b)”{

if there exists a common predecessorAs

and successorAeforaandbthen{

if satisfy either (Previous(As,a) and

Previous(a,Ae)) or (Previous(As,b)

andPrevious(b,Ae)) andaandb

can not run at the same time then{

return true;

}

}

return false;

}

if opiis NotLimit (a,b){

if there is no path fromatobor frombtoa{

mark the error place;

return false;

}

} //end of the deal for each opi

} //end if

} //end of the deal of each tci

return true;

4 實(shí)現(xiàn)及實(shí)例分析

為了驗(yàn)證所提方法的有效性,我們?cè)谝慌_(tái)高性能PC機(jī)上實(shí)現(xiàn)以上算法.開發(fā)的硬件環(huán)境:Intel E5200 CPU, 2G DDR, 250G HD,開發(fā)平臺(tái):JDK1.7+MyEclipse2014, 工作流引擎采用Activiti 5.18.0,數(shù)據(jù)庫(kù)采用MySQL 5.1.37。采用Hibernate實(shí)現(xiàn)領(lǐng)域知識(shí)樹的知識(shí)查詢與管理。

下面我們以圖1所示的知識(shí)樹為例,來驗(yàn)證本文所提方法的有效性和正確性。某軟件開發(fā)過程的主流程如圖3所示,其中的“需求分析”和“測(cè)試”為未定義的柔性活動(dòng),用Activiti的call activity類型的活動(dòng)來表示。當(dāng)工作流執(zhí)行到活動(dòng)“項(xiàng)目人員確定”時(shí),由于后續(xù)的柔性活動(dòng)“需求分析”未定義,因此柔性活動(dòng)細(xì)化算法FlexActRefining()被激活。該算法首先在領(lǐng)域知識(shí)樹中進(jìn)行查找,通過對(duì)活動(dòng)目標(biāo)的匹配,找到對(duì)應(yīng)的知識(shí)點(diǎn)“需求分析”,獲取其3個(gè)滿足泛化關(guān)系的子知識(shí)點(diǎn),即“面向?qū)ο笮枨蠓治觥?、“結(jié)構(gòu)化需求分析”和“模塊化需求分析”,并生成一個(gè)OR結(jié)構(gòu)。根據(jù)上下文及約束條件,“面向?qū)ο笮枨蠓治觥狈种П贿x擇執(zhí)行。因此,其對(duì)應(yīng)的流程模板被實(shí)例化后通過Activiti工作流引擎部署到其流程定義數(shù)據(jù)表和部署表中,并開始執(zhí)行該流程。當(dāng)工作流執(zhí)行完之后,返回主流程執(zhí)行剩下的活動(dòng)。

圖3 軟件開發(fā)過程的主流程Fig.3 Main flowchart of a software development process

同樣的,在工作流執(zhí)行到“編碼”活動(dòng)時(shí),算法FlexActRefining()被激活以細(xì)化后續(xù)的柔性活動(dòng)“測(cè)試”。查詢知識(shí)樹可得知,其存在對(duì)應(yīng)的流程測(cè)試模板,并根據(jù)“測(cè)試”活動(dòng)的3個(gè)滿足包含關(guān)系的子知識(shí)“單元測(cè)試”、“綜合測(cè)試”和“系統(tǒng)測(cè)試”,細(xì)化生成流程模板中的“各類型測(cè)試”活動(dòng)。依據(jù)其約束關(guān)系,采用順序結(jié)構(gòu)生成其時(shí)序關(guān)系,得到子流程: “單元測(cè)試”→“綜合測(cè)試”→“系統(tǒng)測(cè)試”,并部署到工作流引擎進(jìn)行執(zhí)行。整個(gè)過程可以用圖4表示,細(xì)化之后的流程圖見圖5所示。

圖4 軟件開發(fā)過程的動(dòng)態(tài)細(xì)化方法示意圖Fig.4 Illustration of dynamic refinement for a software development process

圖5 細(xì)化之后的流程圖Fig.5 Process model after refinement

5 結(jié)束語

柔性活動(dòng)的動(dòng)態(tài)細(xì)化一直是柔性工作流建模的一個(gè)關(guān)鍵問題和難點(diǎn)。其細(xì)化過程需要遵循縱向的知識(shí)關(guān)聯(lián)關(guān)系和活動(dòng)選取、時(shí)序關(guān)系的約束。因此,本文提出一種基于知識(shí)樹和約束的柔性活動(dòng)動(dòng)態(tài)細(xì)化方法,給出了知識(shí)樹和約束規(guī)則的定義,詳細(xì)討論了柔性活動(dòng)細(xì)化的步驟,描述了活動(dòng)選取校驗(yàn)的算法,以及根據(jù)時(shí)序約束對(duì)生成的子流圖進(jìn)行校驗(yàn)的算法細(xì)節(jié)。

由于Activiti支持對(duì)流程模型的動(dòng)態(tài)生成和修改,因此在Activiti工作流環(huán)境中對(duì)以上算法進(jìn)行了實(shí)現(xiàn)和實(shí)例分析。其結(jié)果表明,該方法能夠根據(jù)知識(shí)樹和約束動(dòng)態(tài)地生成對(duì)應(yīng)的子流程,并部署到Activiti的工作流數(shù)據(jù)庫(kù)中進(jìn)行執(zhí)行。所生成的bpmn流程文件可以作為該柔性活動(dòng)的細(xì)化結(jié)果,在主流程模型中對(duì)其進(jìn)行替換。實(shí)驗(yàn)驗(yàn)證了本文方法的有效性。下一步工作將考慮結(jié)合上下文計(jì)算提高工作流的柔性和過程感知性,進(jìn)一步完善柔性活動(dòng)的細(xì)化方法。

[1]李競(jìng)杰, 王維平, 楊峰. 柔性工作流理論方法綜述[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2010, 16(8): 1569-1577. LI Jingjie, WANG Weiping, YANG Feng. Review on approaches of flexible workflow[J]. Computer integrated manufacturing systems, 2010, 16(8): 1569-1577.

[2]周建濤, 史美林, 葉新銘. 柔性工作流技術(shù)研究的現(xiàn)狀與趨勢(shì)[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005, 11(11): 1501-1510. ZHOU Jiantao, SHI Meilin, YE Xinming. State of arts & trends on flexible workflow technology[J]. Computer integrated manufacturing systems, 2005, 11(11): 1501-1510.

[3]SADIQ S, SADIQ W, ORLOWSKA M. Pockets of flexibility in workflow specification[C]//Proceedings of the 20th International Conference on Conceptual Modeling. Berlin, Germany: Springer, 2001: 513-526.

[4]VAN ELST L, ASCHOFF F R, BERNARDI A, et al. Weakly-structured workflows for knowledge-intensive tasks: an experimental evaluation[C]//Proceedings of the Twelfth International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises. Linz, Austria: IEEE, 2003: 340-345.

[5]ADAMS M, TER HOFSTEDE A H M, EDMOND D, et al. Worklets: a service-oriented implementation of dynamic flexibility in workflows[M]//MEERSMAN R, TARI Z. On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE. Berlin Heidelberg: Springer, 2006: 291-308.

[6]鄧水光, 吳朝暉, 俞鎮(zhèn). 支持動(dòng)態(tài)建模的工作流管理系統(tǒng)的研究與設(shè)計(jì)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(5): 712-718. DENG Shuiguang, WU Chaohui, YU Zhen. Flexible workflow model based on ECA joined with activity[J]. Journal of computer-aided design & computer graphics, 2004, 16(5): 712-718.

[7]JIANG Yanrong, LI Weihua, YANG Jingtao. An incremental approach to modeling flexible workflows using activity decomposition and gradual refinement[J]. Journal of software, 2014, 9(10): 2628-2637.

[8]BAE J, BAE H, KANG S H, et al. Automatic control of workflow processes using ECA rules[J]. IEEE transactions on knowledge and data engineering, 2004, 16(8): 1010-1023.

[9]GIL Y, RATNAKAR V, KIM J, et al. Wings: intelligent workflow-based design of computational experiments[J]. IEEE intelligent systems, 2011, 26(1): 62-72.

[10]CHUN S A, ATLURI V, ADAM N R. Domain knowledge-based automatic workflow generation[C]//Proceedings of the 13th International Conference on Database and Expert Systems Applications. Berlin, Germany: Springer-Verlag, 2002: 81-93.

[11]SHEPELEV V A, DIRECTOR S W. Automatic workflow generation[C]//Proceedings of the EURO-DAC '96, European Design Automation Conference. Geneva, Switzerland: IEEE, 1996: 104-109.

蔣艷榮,男,1976年生,講師,博士,主要研究方向?yàn)闄C(jī)器智能、上下文感知計(jì)算、智能交互。發(fā)表學(xué)術(shù)論文20余篇,其中被SCI檢索8篇、EI/ISTP檢索10余篇。

李衛(wèi)華,女,1957年生,教授,博士,主要研究方向?yàn)橹悄苘浖?、網(wǎng)絡(luò)信息系統(tǒng)、面向Agent計(jì)算。發(fā)表學(xué)術(shù)論文40余篇,出版著作多部。

楊勁濤,男,1971年生,博士,主要研究方向?yàn)閃eb服務(wù)計(jì)算、模式識(shí)別、醫(yī)學(xué)圖像處理技術(shù),發(fā)表學(xué)術(shù)論文20余篇。

A dynamic refinement approach for flexible activitybased on knowledge tree and constraints

JIANG Yanrong, LI Weihua, YANG Jintao

(School of Computer, Guangdong University of Technology, Guangzhou 510006, China)

Flexible workflow systems offer huge advantages in addressing dynamic uncertain factors during the modeling period; however, the dynamic refinement of flexible activities remains a challenge in the modeling and application of flexible workflows. Therefore, we propose a dynamic refinement approach of flexible activities based on a knowledge tree and various constraints. More specifically, we used the inclusion and generalization relationships of knowledge trees as heuristic information; further, we used activity selection constraints and temporal constraints to guide our verification processes. Given the introduction of a knowledge tree and its containing relationships, as well as activity selection constraint and temporal constraint rules, we provide a dynamic refinement algorithm and an algorithm for activity selection checkout and temporal constraint checkup. Finally, we provide a realization of our algorithms and offer case analyses. Our results show that our proposed algorithms are effective and can solve the problem of dynamic refinement of flexible activities quite well.

flexible workflow; dynamic refinement; temporal constraints; workflow generation; process modeling

2016-03-06.

日期：2017-02-20.

國(guó)家自然科學(xué)基金項(xiàng)目(61142012); 廣東省科技計(jì)劃項(xiàng)目(2015B010128005, 2013B021800115).

蔣艷榮. E-mail：yrjiang@gdut.edu.cn.

10.11992/tis.201603009

http://www.cnki.net/kcms/detail/23.1538.tp.20170220.1009.006.html

TP391

A

1673-4785(2017)02-0158-08

蔣艷榮,李衛(wèi)華,楊勁濤. 一種基于知識(shí)樹和約束的柔性活動(dòng)動(dòng)態(tài)細(xì)化方法[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(2): 158-165.

英文引用格式：JIANG Yanrong, LI Weihua, YANG Jintao. A dynamic refinement approach for flexible activity based on knowledge tree and constraints[J]. CAAI transactions on intelligent systems, 2017, 12(2): 158-165.