一種可定制參考過程模型的自動構建方法

凌濟民 張 莉

(北京航空航天大學計算機學院 北京 100191) (lingjimin@buaa.edu.cn)

一種可定制參考過程模型的自動構建方法

凌濟民 張 莉

(北京航空航天大學計算機學院 北京 100191) (lingjimin@buaa.edu.cn)

過程模型在企事業單位中的應用日益普遍.由于企業為每個特定業務需求單獨開發過程模型是復雜并且高成本的工作,因此企業通常使用參考過程模型作為過程模型開發的基礎，以有效降低成本并提高開發效率和質量.由于參考模型需要領域專家大量的領域分析和抽象建模工作,如何基于領域內已有的過程模型變體自動創建出初步的參考模型以輔助領域專家的工作成為有意義的研究問題.現有的參考模型構建方法存在輸出模型復雜度較高或難以全面表達領域內多樣推薦實踐等問題.為了創建代表性和可讀性更強的參考模型,基于相似過程片段聚合技術,提出了一種支持層次化子過程結構的可定制參考過程模型的自動構建方法,全面支持可定制參考模型中基礎過程、變更可選項以及約束關系的自動構建.案例研究結果表明:該方法生成的參考模型具有良好的領域代表性和模型復雜度.

過程模型;過程變體;參考模型;可定制過程模型;過程片段

隨著企業對過程重視程度的不斷提高,過程模型在不同企事業單位中的使用變得日益普遍,企業通常通過建立過程模型分析和優化它們的業務流程[1].過程模型的開發包括活動及其關系的識別、選擇建模工具和建模語言以及描述其他過程相關元素等大量工作.由于企業為每個特定業務需求單獨開發過程模型是復雜并且高成本的工作,因此如何有效地裁剪和改編企業現有的過程模型以滿足業務需求的變化是當前企業組織所需的重要能力之一.參考模型是描述特定領域內推薦實踐的概念模型,因此在企業組織應對上述問題時被廣泛應用.通過使用參考過程模型(reference process model)作為過程模型開發的基礎可以有效降低成本并提高開發效率,模型的質量也因為最佳實踐的重用得以保證[2].

傳統的參考過程模型(以下簡稱為參考模型)通?；诮浀涞倪^程建模語言構建(例如由EPC語言描述的SAP R3參考模型),難以充分描述系統的可配置性和流程的可變性,領域內多樣的推薦實踐難以在單一的傳統過程模型中體現,并且無法提供相應的決策支持或約束來引導用戶對參考模型進行裁剪或修改.為了解決上述問題,現有研究通常引入配置[2-6]或定制[6-9]的概念擴展傳統過程建模方法來建立參考模型.由于創建此類參考模型需要領域專家大量的領域分析和抽象建模工作,因此如何基于領域內已有的過程變體(process model variants)自動創建出初步的參考模型以輔助領域專家的建模工作成為有意義的研究問題.

目前針對參考模型自動構建的研究主要采用過程模型合并[10-11]以及過程變體挖掘技術[12-14],在一組過程變體的基礎上歸納創建一個具有代表性的統一模型.過程模型合并技術通過將一組過程變體合并到一個可配置過程模型中,但是此類方法基于過程變體的兩兩合并,因此最終得到的過程模型的規模會隨著過程變體數量的增加而迅速增長,并且過程模型不支持層次化的子過程結構,因此參考模型的復雜度較高;過程變體挖掘技術能夠自動挖掘創建出一個與現有過程變體集合最接近的過程模型,但是此類方法僅支持構建傳統非可配置定制的過程參考模型,因此難以全面表達領域內多樣的推薦實踐,從而降低了參考模型的領域代表性.

為了解決現有研究中存在的上述問題,本文提出了一種支持層次化子過程結構的可定制參考過程模型的自動構建方法.通過檢測并聚合過程變體集合中相似的模型片段,將過程變體轉化為具有子過程的層次化過程模型,并提出可定制過程模型的自動構建方法,逐層細化實現參考模型中的每一個子過程,進而生成完整的分層可定制的參考模型,最后基于一系列來自工業界的實際過程模型對所提出的方法進行了評估和討論.

本文的貢獻有2個方面:1)提出了基于相似過程片段檢測和聚合的過程模型結構層次化方法,通過層次化結構提高復雜過程模型的可讀性;2)提出了基于過程變體(或相似過程片段)集合的可定制過程模型(或子過程片段)的自動構建方法,實驗評估表明該方法生成的參考模型能夠具有較低的復雜度和良好的領域代表性.

1 背景和研究基礎

1.1 過程變體的示例

由于建模目標和應用場景的不同,同一業務過程可能被描述為多個相似的業務過程模型,即過程變體.本節給出一組來自工業界的真實過程變體的示例，貫穿全文方法的闡述.這組過程變體來自于國內某專營機場貴賓服務與管理的企業(以下簡稱貴賓公司)的業務流程.該企業為不同類型的旅客提供不同但又相似的服務,例如政府貴賓、商務貴賓、商務嘉賓以及其他個人會員.此外,貴賓公司在全國各地擁有若干家成員子公司,它們的業務流程之間也具有一定的差異性.上述因素導致了過程變體廣泛共存的現象,因此有效地構建參考模型有助于提高企業未來業務流程的規范性、可重用性和可擴展性.

本節涉及的過程模型示例描述了貴賓公司的服務預訂接入流程,圖1給出了其中3個經過簡化的由BPMN建模語言描述的過程模型變體.為了便于清晰地展示模型結構,模型中具體的活動命名未在圖中給出,示例模型包含的更多語義信息可以從在線鏈接①獲取.服務預訂請求可能來自于400服務電話、移動應用以及電話專線等.這些過程變體針對不同來源的預訂請求以及不同類型的旅客描述了相應的預訂接入流程.從圖1可以看出,這些過程變體表達的業務流程是相似的,但它們在所包含的活動、活動的命名以及模型的結構等方面存在一定的差異,如何基于這些描述當前業務現狀的過程變體自動地構建面向該領域的可定制參考過程模型并控制模型的復雜度是本文需要研究的關鍵問題.

Fig. 1 A running example of process model variants圖1 過程變體集的示例

1.2 過程模型和過程片段

目前在實踐中已有多種過程建模語言用于描述業務過程,包括BPMN,EPC,UML活動圖等.我們希望本文提出的方法能夠應用于不同建模語言,因此本文將使用過程圖(process graph)而非某種特定的建模語言來表示所有的過程模型(或過程片段),它由當前常見的過程建模語言的通用元素抽象而成.

定義1. 過程圖.一個過程圖是一個連通有向圖，通過四元組G=(N,E,T,L)表示,其中:

1)N表示模型中所有節點的集合;

2)E?N×N表示連接節點之間有向邊的集合;

3)T:N→t表示為節點分配的類型屬性,例如考慮BPMN建模語言中的基本流對象,t∈{event,activity,gateway};

4)L:N→label表示為節點分配的命名標簽,例如考慮BPMN建模語言中的基本元素,如果T(n)=event∨activity,則L(n)為該模型節點的名稱;如果T(n)=gateway,則L(n)∈{XOR,AND,OR}.

由于本文需要建立包含層次化子過程結構的參考模型,因此我們需要將過程模型中的過程片段抽取為子過程.由于在過程模型中子過程是基于調用返回機制實現的,因此我們規定抽取的子過程為單入口單出口過程模型片段(single-entry-single-exit process fragment)[15],以下簡稱為過程片段.簡單地說,過程片段就是過程圖中由單一入口開始并且由單一出口結束的任何區域,利用環路等價算法[16]對過程圖進行處理,可以在線性時間復雜度內將過程圖層次化分解為一系列過程片段.

定義2. 過程片段.在一個過程圖G=(N,E,T,L)中,一個過程片段F=(N′,E′,T′,L′)是G的一個非空子圖,即N′?N且E′=E∩(N′×N′),并且滿足:存在邊e,e′∈E，使得E∩((NN′)×N′)={e}以及E∩(N′×(NN′))={e′}.其中e和e′分別稱為過程片段F的入邊和出邊.

為了便于模型的展示,圖1中的虛線框僅僅標識出了過程模型所包含的少部分過程片段.根據定義2可以注意到,過程片段可以相互重疊或嵌套,例如F1和F2可以組成一個更大的過程片段,而活動D和F2同樣可以構成過程片段.因此在本文方法中,任何單入口單出口的區域都有可能被抽取為子過程活動.

1.3 可定制過程模型

為了描述過程模型的可變性,現有研究通常采用配置(configuration)[2-6]或定制(customization)[6-9]2種策略.可配置過程模型將所有已知的過程變體匯集到1個模型中描述,該模型包含了所有變體的行為,用戶通過裁剪與業務需求無關的配置項得到所需的過程模型;而可定制過程模型包含1個基礎過程(base process)和一系列變更可選項(change options),用戶通過定制變更可選項并將其作用于基礎過程上得到所需的過程模型.不難看出,可配置過程模型的建立需要預定義所有可能的過程變體,并且自身難以隨著過程變體的增加或修改而演化,其靈活性相比可定制過程模型較差[17].本文采用可定制過程模型作為生成的參考模型的表示形式,下面給出本文所構建出的可定制參考過程模型的詳細定義.

定義3. 可定制過程圖.一個可定制過程圖是一個四元組CG=(G,P,O,S),其中:

1)G表示基礎過程對應的過程圖G=(N,E,T,L);

2)P表示依附于基礎過程G上位于節點前后的可定制點構成的集合,即P?N×{pre,post};

3)O表示變更可選項構成的集合,1個變更可選項包括一系列變更操作,包括3種:

① 插入操作insert(F,p1,p2,opt).將過程片段F按照opt方式插入可定制點p1和p2之間,其中opt∈{SEQ,AND,XOR,OR},SEQ表示直接插入p1和p2之間,AND表示插入F并使之與p1和p2之間現有的過程片段構成并行結構,XOR和OR的含義與AND同理.

② 刪除操作delete(p1,p2,opt).將可定制點p1和p2之間包含的過程片段按照opt方式刪除,其中opt∈{CON,DIS},CON表示刪除過程片段后添加從p1到p2的控制流連接,而DIS表示不添加該控制流連接.

③ 修改操作modify(n,label).將節點n的命名標簽修改為label.

4)S表示變更可選項之間約束關系構成的集合,包括蘊含(implies)和互斥(excludes)2種類型.變更可選項O1蘊含變更可選項O2表示,當選擇O1時,O2也必需被選中,記作O1→O2; 變更可選項O1與變更可選項O2互斥表示O1與O2不能被同時選擇,記作O1?O2.

定義4. 可定制參考過程模型.一個可定制參考過程模型是一個二元組CP=(CGC,M),其中:

1)CGC表示由各層次的可定制過程圖所組成的集合;

2)M表示各個可定制過程圖CG與子過程活動之間的映射關系.

為了便于理解上述定義,圖2給出了1個基礎過程及其相關的一組變更操作的示例,圖2(a)所示的基礎過程中包含了a,b,c,d,e共5個可定制點,圖2(b)～(f)給出了基礎過程經過插入、刪除和修改變更操作后得到的過程模型.

Fig. 2 Examples of change operations in customizable process graph圖2 可定制過程圖的變更操作示例

2 可定制參考過程模型的自動構建方法

為了使構建出的參考模型支持層次化子過程結構,我們首先通過識別并聚合過程變體集合中相似的過程片段,將過程變體轉化為支持子過程活動的過程模型.然后,提出可定制過程模型的自動構建算法,逐層細化實現參考模型中的每一個可定制過程圖,最終生成完整的分層可定制的參考模型.上述研究內容的詳細流程如圖3所示,本節將對圖中的各個步驟進行解釋說明.

Fig. 3 Working procedure overview of the method to automatically build reference process model圖3 參考模型的自動構建方法的工作流程概覽

2.1 相似過程片段的聚合

為了識別并聚合過程變體集合中相似的過程片段,首先需要定義過程片段之間的相似性度量方法.由于過程片段也是由過程圖表示,因此我們使用在過程模型相似性度量研究領域廣泛應用的圖編輯距離相似度[18]的方法度量過程片段之間的相似性.過程圖之間的編輯距離是從一個圖變換到另一個圖所需的最少編輯操作的數量.編輯操作包括3類:插入(或刪除)節點、插入(或刪除)邊以及替換節點.定義5給出了該度量的詳細定義.

Sim(G1,G2,M)=1-avg(fsubn,fskipn,fskipe),

fskipn=|skipn|(|N1|+|N2|),

fskipe=|skipe|(|E1|+|E2|),

其中,fskipn表示插刪節點占過程圖中所有節點的比例；fskipe表示插刪邊占過程圖中所有邊的比例；fsubn表示替換節點的平均操作開銷.

上述定義中的SimN(n1,n2)表示2個過程圖中的2個節點之間的相似度值,取值范圍為[0,1],使用文本相似度和上下文相似度相結合的方法進行度量,具體細節可以參考本文的前期工作[19].過程圖G1和G2之間的圖編輯距離相似度是所有節點對應關系M相應的Sim(G1,G2,M)中的最大值,記作SimG(G1,G2).由于尋找最佳映射關系M并計算SimG具有指數級復雜度,因此我們使用文獻[20]中給出的一種改進的貪心算法計算該相似度值.

由此可以得到由過程片段兩兩之間相似度值構成的相似度矩陣.需要說明的是,由于將單個活動抽象為子過程活動是沒有意義的,因此只包含單個節點的過程片段不出現在相似度矩陣中.此外,如果2個過程片段屬于同一個過程變體并且它們之間存在重疊的節點,它們之間的相似度值記為0,因為它們之間相互重疊導致無法同時被抽取為子過程活動.最后,為了便于存儲和數據處理,我們只需要在矩陣中記錄不低于給定閾值δ的相似度值,其他不相似的過程片段之間的相似度值在矩陣中也記為0.例如給定閾值δ=0.5,圖1示例過程變體中部分過程片段構成的相似度矩陣如表1所示:

Table 1 Similarity Matrix of Process Fragments

隨后需要基于相似度矩陣聚合相似的過程片段,我們認為一組過程片段能夠被聚合,當其中任意元素兩兩相似,即在相似度矩陣中的對應值不為0.為了實現該目標,我們使用經典的層次聚類算法(hierarchical agglomerate clustering, HAC)[21]實現.HAC算法的基本思路是:1)將集合中每一個對象都視為1個簇(cluster);2)在每一次迭代中合并距離最短的2個簇,直至所有對象都包含在同一個簇中為止.

如何定義2個簇之間的距離是HAC算法的關鍵問題之一,通常有單鏈、全鏈和組平均3種策略.單鏈將距離定義為不同2個簇的2個最近點之間的距離;反之,全鏈則考慮最遠點之間的距離;組平均則將距離定義為取自2個不同簇的所有點對鄰近度的平均值.考慮到1個簇內任意過程片段兩兩相似的要求,本文選取全鏈策略以保證該目標的實現,即2個片段簇之間的相似度為取自不同簇的2個片段的相似度最小值.因此,本文將HAC算法實施如下:1)將每個過程片段都各自視作1個簇,然后合并2個相似度最高的簇形成1個新簇,在相似度矩陣中刪除這2個簇,并按照全鏈策略計算新簇與其他簇的相似度,插入到相似度矩陣中;2)重復上述合并步驟直到相似度矩陣中不存在大于0的值結束,如算法1所示.在示例模型中,表1所示的相似度矩陣執行HAC算法后能夠最終得到3個過程片段簇,即{F5,F10,F14},{F3,F8},{F4}.

算法1. 相似過程片段聚合算法.

輸入:過程片段集合FragSet、片段相似度矩陣FragMx;

輸出:過程片段簇集合ClusterSet.

① for eachFragSet中的過程片段Fido

② 添加過程片段Fi到片段簇Clusteri中;

③ 添加片段簇Clusteri到ClusterSet中;

④ end for

⑤ 初始化簇相似度矩陣ClusterMx;

⑥ while |ClusterSet|>1并且矩陣ClusterMx中的值不都為0 do

⑦ 從ClusterSet中選擇相似度值最高的2個簇C1和C2;

⑧ 合并C1和C2至1個新簇CM;

⑨ 添加CM至ClusterSet,并從ClusterSet中刪除C1和C2;

⑩ 計算CM與ClusterSet中其他簇的相似度，并更新ClusterMx;

2.2 可定制參考過程模型的構建

將過程變體中的相似過程片段聚合之后,為了逐層細化構建可定制參考模型,需要在每一層過程圖中選擇需要抽象為子過程的過程片段簇.由于過程片段簇之間可能存在相互重疊或嵌套(例如簇{F3,F8,F12}與簇{F4,F9,F11,F13}之間存在共有節點),為了將過程片段抽象為子過程活動,需要在該層過程圖包含的過程片段簇中選擇互不相交的簇,將它們加入未處理集合中供后續迭代,從而實現模型的逐層細化.為了使每個層次的過程圖的可讀性更高,我們盡可能地優先選擇過程片段平均規模更大的簇.例如,考慮初始迭代的情況,即當前需要處理的是圖1中的3個頂層過程圖,最終選擇的過程片段簇為:{F1,F6},{F2,F7},{F3,F8,F12},{F5,F10,F14},使用4個子過程活動分別替換上述4個簇包含的過程片段,然后將這4組片段的過程圖加入到未處理集中,并進入頂層可定制過程圖的構建流程,重復上述步驟直至不存在未處理的過程片段簇,從而得到最終的參考模型.

基于一組相似的過程圖構建相應的可定制過程圖主要包括3項工作:創建基礎過程圖、識別可定制點和變更可選項以及創建變更可選項之間的約束關系,下面我們對這3項工作進行詳細說明.

2.2.1 創建基礎過程圖

為了使可定制過程圖中的基礎過程盡可能地具有代表性,可以采取4個策略[7]進行設計:領域專家定義標準過程、選擇最頻繁執行的變體、使用與各個變體平均距離最短的模型、采用所有過程變體的交集或并集.前2種策略需要人工建?；蛄鞒虉绦械臄祿?而取并集或交集的方法可能導致基礎過程過于復雜或簡單,從而降低基礎過程的可讀性或代表性,因此本文使用最短平均距離的策略自動地創建基礎過程.

創建基礎過程的步驟如下:

1) 首先在輸入過程圖集合中選擇中心元素(與其他過程圖之間的平均相似度最高者)作為初始的基礎過程;

2) 搜索基礎過程的近鄰過程圖(對基礎過程圖進行1次變更操作后得到),若存在比基礎過程圖更優(即與輸入過程圖的平均相似度更高)的鄰近過程圖,選擇其中最優的1個替換當前的基礎過程;

3) 重復步驟2)直至不能找到比當前基礎過程更優的近鄰過程圖結束.

變更操作包括插入活動、刪除活動以及重命名活動3類.任何在輸入過程圖中出現但不存在于當前基礎過程中的活動允許被插入,活動可以被修改為其他輸入過程圖中與之匹配的相似命名,基礎過程中的任何活動都允許被刪除.

Fig. 4 Examples of change operations to F14圖4 對過程片段F14的變更操作示例

2.2.2 創建可定制點和變更可選項

為了創建可定制點和變更可選項,需要識別基礎過程G到各個過程圖Gi之間的轉換操作,如算法2所示,基礎過程G到每一個過程圖Gi的轉換操作序列可以初始地視為1個變更可選項Optioni,具體的規則如下:

1) 若Gi中不存在與G中的活動Act匹配的活動,則向Points中添加可定制點Actpre和Actpost,并根據Act的上下文節點在Gi中的連通性判斷刪除Act后是否需要添加Actpre到Actpost的控制流連接,然后向變更可選項Optioni中添加刪除操作delete(Actpre,Actpost,opt);

2) 若Gi中存在活動Act′與G中的活動Act匹配但命名存在差異,則向Optioni中添加修改操作modify(Act,Act′);

3) 若G中不存在與Gi中的活動Act匹配的活動,首先根據Act在Gi中的上下文節點確定其在G中的插入位置和操作方式,例如需要將Act按照opt方式插入到活動B和C之間,則向Points中添加可定制點Bpost和Cpre,并向Optioni中添加插入操作insert(Act,Bpost,Cpre,opt).

算法2. 可定制點和變更可選項構建算法.

輸入:基礎過程圖G、過程圖集合Variants;

輸出:可定制點集Points、變更可選項集Options.

① 初始化集合Points和Options;

② for eachGi∈Variantsdo

③ 在Options中新增變更可選項Optioni;

④ for each活動Act∈Gdo

⑤ ifAct?Gi并且Gi中不存在與Act相似匹配的活動then

⑥ 向Points中添加Actpre和Actpost;

⑦ 根據Act的上下文節點在Gi中的連通性判斷刪除操作方式opt;

⑧ 向Optioni中添加刪除操作delete(Actpre,Actpost,opt);

⑨ else ifAct?Gi并且Gi中存在與Act相似匹配的活動Act′ then

⑩ 向Optioni中添加修改操作modify(Act,Act′);

最后,我們針對創建出的可定制點和變更可選項進行一些優化.1)如果2個插入或刪除操作對象可以組合成為1個過程片段,則將這2個操作合并為針對過程片段的操作,并刪除過程片段內部相應的可定制點;2)由于1個相同的變更操作可能在多個變更可選項中出現,例如過程圖G1和G2都可能包括從基礎過程中刪除活動Act的操作,因此我們針對變更可選項與變更操作之間的組合進行優化,將同時出現在完全相同的變更可選項中的變更操作組合到1個新的變更可選項中.圖5給出了變更可選項優化的示例,可以看出,經過優化后的變更可選項能夠去除重復出現的變更操作.

InitialChangeOptionsOption1：modify(Q1，Q)delete(Rpre，Rpost，DIS)modify(W，W1)Option2：insert(Y，Rpost，g2pre，SEQ)Option3：modify(W，W1)insert(Y，Rpost，g2pre，SEQ)NumChange→Options：3NumChangeOperations：6 OptimizedChangeOptionsOption1：modify(Q1，Q)delete(Rpre，Rpost，DIS)Option2：insert(Y，Rpost，g2pre，SEQ)Option3：modify(W，W1)Constraints：Option1→Option3Option1 Option2NumChange→Options：3NumChangeOperations：4

Fig. 5 Optimization to change options
圖5 變更可選項優化

2.2.3 創建變更可選項之間的約束關系

在自動構建出基礎過程以及可定制點和變更可選項之后，需要創建變更可選項之間存在的約束關系.約束關系包括蘊含和互斥2類,O1蘊含O2表示選擇了變更可選項O1后也需要選擇O2,而互斥關系則表示2個變更可選項不能同時選擇.我們提出3條規則,通過兩兩比較變更可選項,檢查它們對于每條規則的符合性來創建約束關系:

1) 為了避免操作沖突,若2個變更可選項包含針對同一個活動(或過程片段)的變更操作,則為這2個變更可選項之間建立互斥約束;

2) 若某變更可選項包含作用于可定制點p1和p2之間的變更操作,而p1或p2所依附的節點在另一變更可選項中被刪除,則為這2個變更可選項之間建立互斥約束,例如圖5中的Option1?Option2;

3) 在所有的初始變更可選項中,若當變更可選項O1中的變更操作出現時,變更可選項O2中的變更操作也會同時出現,則添加O1蘊含O2約束,例如圖5中的Option1→Option3.將創建的基礎過程圖、可定制點、變更可選項以及約束關系組合起來即可得到最終的可定制過程圖,例如圖6給出了由示例模型中的過程片段簇{F5,F10,F14}創建的可定制過程圖,其中包含了1個基礎過程、5個可定制點、3個變更可選項以及2條互斥約束關系.

Fig. 6 Customizable process graph built from process fragment cluster {F5,F10,F14}圖6 由過程片段簇{F5,F10,F14}創建的可定制過程圖

3 評估與討論

3.1 實驗評估設置

本節重點評估并討論本文方法構建出的可定制參考模型的復雜度和領域代表性以及本文方法的性能.我們選取來自貴賓公司的4組描述不同業務的過程變體作為評估的模型來源,這些模型是我們在與貴賓公司的前期合作中梳理并創建的,描述的業務包括預訂接入控制、服務預訂、現場服務以及財務結算,更多的模型詳細信息如表2所示.

為了評估參考模型的復雜度,我們從模型規模以及配置選項數量2個角度,將使用本文方法構建出的可定制參考模型與現有方法進行對比,涵蓋了過程模型合并以及過程變體挖掘等2類典型方法,具體地,評估中考慮的參考模型構建方法包括4種:

Table 2 Sets of Process Variants for Evaluation

1) 層次化的可定制過程模型(方法1).由本文方法構建出的可定制參考模型.

2) 非層次化的可定制過程模型(方法2).去除相似過程片段聚合與子過程逐層構建的迭代步驟,僅使用2.2節方法基于頂層過程變體集合構建出的單層的可定制參考模型.

3) 可配置過程模型(方法3).利用文獻[10]中過程模型合并技術構建出的可配置參考模型.

本文所有實驗程序使用Java實現,軟件環境為Windows7 SP1,JDK 1.7,硬件環境為Inter Core i5-4590處理器,8 GB內存.

3.2 評估結果

分別使用上述4種方法針對選取的4組過程變體構建相應的參考模型,并統計了參考模型的規模(包含的節點總數或每層過程圖包含節點的平均數量)和配置選項(可定制過程模型的變更可選項或可配置過程模型的可配置節點)的數量.各方法構建出的參考模型包含節點的總數量對比情況如圖7所示.可以看出:方法3因為將配置選項以可配置節點的形式集成在單個過程圖,因此它構建出的參考模型在4種對比方法中規模最大,影響了參考模型的可讀性.方法1由于子過程結構的引入,增加了相應的子過程活動和子過程中的開始和結束節點,因此相比方法2和方法4的節點總數量較大,但分層的子過程結構能夠提高復雜模型的可讀性.

Fig. 7 Total number of nodes in reference models圖7 參考模型節點總數量對比

方法1構建的參考模型中每層過程圖包含的節點數量的統計信息如表3所示.可以看出,該方法構建出的參考模型每層過程圖的規模較小,模型節點在各層過程圖中分布相對平均,因此參考模型具有較好的層次化結構.

方法4構建出的參考模型與方法2構建出的參考模型的基礎過程相似,但它不具有配置選項,只能表達單一的推薦流程實踐,因此在參考模型的領域代表性方面不如方法1～3構建出的模型.方法1～3構建的參考模型的配置選項數量如圖8所示.可以看出:方法2構建出的參考模型相比方法1和方法3具有較少的配置選項,即變更可選項,但由于此類模型不具有層次化子過程結構,基礎過程的規模較大,并且變更操作集中在少量的變更可選項中,不利于未來參考模型的維護和演化.方法1將變更操作和變更可選項分散至各層過程圖中,雖然變更可選項的總數量較多,但變更可選項包含變更操作的平均數量相比方法2明顯降低,如表4所示.

Table 3 Number of Nodes in Reference Models by Method 1

Fig. 8 Number of configuration options in reference models圖8 參考模型的配置選項數量對比

DataSetMethod1Method2AvgNumofOptionsperCGAvgOperationsperOptionAvgOperationsperOptionSet13．51．714．67Set24．141．935．08Set33．51．644．29Set43．21．694．71

上述4種參考模型構建方法的性能對比情況如圖9所示.可以看出,方法1和方法2的時間開銷明顯高于方法3和方法4,這是因為本文方法相比現有方法增加了層次化子過程的構建,變更可選項及其約束的生成等步驟,在性能上相比現有方法存在一定的劣勢.盡管如此,本文方法能夠在可接受的較短時間內構建層次化可定制參考模型,能夠應用到參考模型輔助建模的實際工業場景中.

Fig. 9 Time efficiency of building reference models圖9 各方法構建參考模型運行時間對比

3.3 討 論

通過分析構建出的參考模型我們發現本文方法尚存在一定的局限性:

1) 本文構建的參考模型中的變更可選項不包含相應的條件說明,即指導用戶應該在何種需求條件下選取該變更可選項,并且構建的約束關系存在于同層次過程的變更可選項之間,因此構建得到的初步模型仍需要領域專家進行調整或補足工作;

2) 在每次迭代選擇需要抽象為子過程活動的過程片段簇時,本文使用的策略是優先選擇過程片段平均規模更大的簇,這在一些特殊情況下可能導致參考模型的層次過多反而影響了模型的可讀性,在未來需要考慮如何優化選擇策略以權衡參考模型的層次數量和每層過程圖的規模;

3) 目前抽取出的子過程活動采用數字ID的形式命名,未添加具體語義信息,可以研究針對過程片段的自動命名技術對構建的參考模型做進一步的改進;最后,本文方法在變更可選項的構建步驟中時間開銷較大,在未來需要對可定制點和變更可選項構建算法的性能作進一步改進.

4 相關工作

本文研究的參考模型的自動構建技術與過程模型合并[10-11]以及過程變體挖掘技術[12-14]密切相關.Rosa等人[10]提出了一種滿足行為保留、追蹤性和可逆性3項需求的過程模型合并方法,能夠在輸出的可配置過程模型[2]中表達所有輸入模型的行為,并且輸出模型也能夠派生出所有輸入的過程變體.Gottschalk等人[11]提出了一種將2個EPC模型合并的方法,將輸入模型轉換為一種描述EPC活躍行為(active behavior)的中間形式實現模型的合并.上述方法簡單地將多個輸入模型到1個輸出模型中,雖然能夠表達領域內流程的變化性,但輸出模型不支持層次化的子過程結構,復雜度會隨著輸入模型的增多而迅速上升,從而影響模型的可讀性.

Li等人[12]以及Ardalani等人[13]提出了過程變體挖掘技術從給定的過程變體集合中發現最佳的參考模型.這些方法基于最短平均距離的機制重新創建參考模型或者改進現有的參考模型.不同于上述以過程變體集合作為輸入的方法,Buijs等人[14]提出一種基于事件日志挖掘的參考模型改進方法提高參考模型包含的行為的質量.上述方法以構建“更接近”現有過程變體或事件日志的參考模型為目標,無需滿足行為保留和可逆性等需求,因此輸出模型的復雜度優于過程模型合并的方法,但是它們的輸出模型僅支持傳統建模語言描述,不支持配置定制機制描述參考模型的可變性,并且同樣不支持層次化的子過程結構.

本文涉及的相似過程片段聚合的工作與過程匹配[19,22]、模型克隆檢測[23-25]以及子圖發現[26-27]等技術密切相關.本文的前期工作[19]以及Branco等人[22]重點考慮了過程片段的匹配問題.與本文采用的片段相似度算法不同的是,它們考慮了其他更多表征片段相似性的因素,例如過程片段中節點匹配關系的覆蓋率、過程片段的上下文相似度等,但這些方法僅僅研究過程片段之間的兩兩匹配關系的建立而不是聚合相似的過程片段.在模型克隆檢測方面,Dumas等人[23]提出一種名為RPSDAG的索引結構快速檢測過程模型集合中的精確克隆,而Ekanayake等人[24]的方法能夠支持過程模型庫中近似克隆的檢測,并利用該方法從事件日志中挖掘出一組具有子過程活動的相似過程模型變體[25],從而降低過程模型集合的冗余程度.此外,頻繁子圖挖掘[26]和子圖同構[27]等技術與本文工作具有一定關聯,但是它們的研究目標是發現圖集合中多次出現的任意聯通的子圖而不是過程片段,因此不能滿足本文層次化子過程抽取的需求.

5 結束語

為了創建領域代表性和可讀性更強的參考模型,本文基于相似過程片段聚合技術,提出了一種支持層次化子過程結構的可定制參考過程模型的自動構建方法,并且案例評估表明該方法生成的參考模型具有良好的領域代表性和模型復雜度.未來的工作中,我們考慮引入更多新出現的相似性度量技術提高過程片段聚合準確性,并嘗試擴展本文的方法以支持過程模型的數據和資源視角.此外,我們考慮將把本文方法應用于來自工業界更大規模的過程模型集合并通過用戶實驗等其他方式來進一步驗證其有效性和效率.

[1]Dijkman R M, Rosa M, Reijers H A. Managing large collections of business process models: Current techniques and challenges[J]. Computers in Industry, 2012, 63(2): 91-97

[2]Rosemann M, Aalst W. A configurable reference modelling language[J]. Information Systems, 2007, 32(1): 1-23

[3]Rosa M, Dumas M, Hofstede A H M, et al. Configurable multi-perspective business process models[J]. Information Systems, 2011, 36(2): 313-340

[4]Huang Yiwang, He Keqing, Feng Zaiwen, et al. A colored C-net model based on RGPS and its application[J]. Journal of Computer Research and Development, 2014, 51(9): 2030-2045 (in Chinese)(黃貽望, 何克清, 馮在文, 等. 一種基于RGPS著色的C-net模型及其應用[J]. 計算機研究與發展, 2014, 51(9): 2030-2045)

[5]Murguzur A, Carlos X, Trujillo S, et al. Context-aware staged configuration of process variants@Runtime[G]LNCS 8484: Proc of the 26th Int Conf on Advanced Information Systems Engineering. Basel, Switzerland: Springer International Publishing, 2014: 241-255

[6]D?hring M, Reijers H A, Smirnov S. Configuration vs. adaptation for business process variant maintenance: An empirical study[J]. Information Systems, 2014, 39(1): 108-133

[7]Hallerbach A, Bauer T, Reichert M. Capturing variability in business process models: The Provop approach[J]. Journal of Software Maintenance and Evolution: Research and Practice, 2010, 22(67): 519-546

[8]Reinhartz I, Soffer P, Sturm A. Extending the adaptability of reference models[J]. IEEE Trans on Systems, Man and Cybernetics, Part A: Systems and Humans, 2010, 40(5): 1045-1056

[9]Kumar A, Yao W. Design and management of flexible process variants using templates and rules[J]. Computers in Industry, 2012, 63(2): 112-130

[10]Rosa M, Dumas M, Uba R. Business process model merging: An approach to business process consolidation[J]. ACM Trans on Software Engineering & Methodology, 2013, 22(2): Article No.11

[11]Gottschalk F, Aalst W, Jansen M H. Merging event-driven process chains[G]LNCS 5331: Proc of the 16th Int Conf on Cooperative Information Systems. Berlin: Springer, 2008: 418-426

[12]Li C, Reichert M, Wombacher A. Mining business process variants: Challenges, scenarios, algorithms[J]. Data & Knowledge Engineering, 2011, 70(5): 409-434

[13]Ardalani P, Houy C, Fettke P, et al. Towards a minimal cost of change approach for inductive reference model development [C]Proc of the 21st Euro Conf on Information Systems. Atlanta: AIS, 2013: No.127

[14]Buijs M, Rosa M, Reijers H A, et al. Improving business process models using observed behavior[G]LNBIP 162: Proc of the 2nd Int Symp on Process Discovery and Analysis. Berlin: Springer, 2013: 44-59

[15]Vanhatalo J, Volzer H, Leymann F. Faster and more focused control-flow analysis for business process models through SESE decomposition[G]LNCS 4749: Proc of the 5th Int Conf on Service-Oriented Computing. Berlin: Springer, 2007: 43-55

[16]Johnson R, Pearson D, Pingali K. The program structure tree: Computing control regions in linear time [C]Proc of the ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 1994: 171-185

[17]Qian L. Managing business process variability: Business brocess configuration vs. business process customization [D]. Eindhoven, Netherlands: Eindhoven University of Technology, 2013

[18]Dijkman R, Dumas M, Dongen B V, et al. Similarity of business process models: Metrics and evaluation[J]. Information Systems, 2011, 36(2): 498-516

[19]Ling Jimin, Zhang Li. Matching process model variants based on process structure tree[J]. Journal of Software, 2015, 26(3): 460-474 (in Chinese)(凌濟民, 張莉. 基于過程結構樹的過程模型變體匹配技術[J]. 軟件學報, 2015, 26(3): 460-474)

[20]Yan Z, Dijkman R, Grefen P. Fast business process similarity search[J]. Distributed and Parallel Databases, 2012, 30(2): 105-144

[21]Aalst W. Process Mining: Discovery, Conformance and Enhancement of Business Processes[M]. Berlin: Springer, 2011

[22]Branco M, Troya J, Czarnecki K, et al. Matching business process workflows across abstraction levels[G]LNCS 7590: Proc of the 15th Int Conf on Model Driven Engineering Languages and Systems. Berlin: Springer, 2012: 626-641

[23]Dumas M, García-Bauelos L, Rosa M, et al. Fast detection of exact clones in business process model repositories[J]. Information Systems, 2013, 38(4): 619-633

[24]Ekanayake C, Dumas M, García-Bauelos L, et al. Approximate clone detection in repositories of business process models[G]LNCS 7481: Proc of the 10th Int Conf on Business Process Management. Berlin: Springer, 2012: 302-318

[25]Ekanayake C, Dumas M, García-Bauelos L, et al. Slice, mine and dice: Complexity-aware automated discovery of business process models[G]LNCS 8094: Proc of the 11th Int Conf on Business Process Management. Berlin: Springer, 2013: 49-64

[26]Jiang C, Coenen F, Zito M. A survey of frequent subgraph mining algorithms[J]. The Knowledge Engineering Review, 2013, 28(1): 75-105

[27]Skouradaki M, Goerlach K, Hahn M, et al. Application of sub-graph isomorphism to extract reoccurring structures from BPMN 2.0 process models [C]Proc of the 9th IEEE Symp on Service-Oriented System Engineering. Piscataway, NJ: IEEE, 2015: 11-20

Ling Jimin, born in 1989. PhD candidate at Beihang University. His main research interests include business process manage-ment, process modeling and analysis, and reference models.

Zhang Li, born in 1968. Professor and PhD supervisor at Beihang University. Senior member of CCF. Her main research interests include software architecture, software product line and business process modeling.

An Approach to Automatically Build Customizable Reference Process Models

Ling Jimin and Zhang Li

(SchoolofComputerScienceandEngineering,BeihangUniversity,Beijing100191)

Process models are becoming more and more widespread in contemporary organizations. It is a complex and high-cost work to develop individual process models for specific business requirements. The modeling procedure can be accelerated and cost-decreased by using reference process models as a basis for individual process models development, so reference process models are widely adopted by organizations. Because building reference process models requires a mass of modeling and analyzing work by domain experts, a major challenge has emerged that how to automatically build a preliminary reference model inductively based on the existing process variants to provide assistance to domain experts. The existing methods of building reference process models have some shortcomings, such as output reference models of most methods have high model complexity and reference models described by traditional process modeling language could not entirely represent various recommended practice in a specific domain. To build reference process models with high representativeness and understandability, this paper proposes an approach to automatically build customizable reference models which support hierarchical sub-process based on fragments clustering. The base model, change options and constraints in customized process models are fully supported to build automatically by our method. The evaluation results show that the generated reference models could achieve fine domain representativeness and model complexity.

process model; process variant; reference model; customizable process model; process fragments

2015-12-09；

2016-04-28

國家自然科學基金項目(61370058) This work was supported by the National Natural Science Foundation of China (61370058).

張莉(lily@buaa.edu.cn)

TP311.5