跨組織應(yīng)急業(yè)務(wù)過程挖掘

譚文安, 吳亞鋒

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,南京211106;2.上海第二工業(yè)大學(xué)計算機(jī)與信息工程學(xué)院,上海201209)

跨組織應(yīng)急業(yè)務(wù)過程挖掘

譚文安1,2, 吳亞鋒1

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,南京211106;2.上海第二工業(yè)大學(xué)計算機(jī)與信息工程學(xué)院,上海201209)

對跨組織應(yīng)急業(yè)務(wù)過程案例進(jìn)行分析,給出了跨組織應(yīng)急業(yè)務(wù)過程任務(wù)的形式化定義及其協(xié)作關(guān)系的定義,根據(jù)跨組織應(yīng)急業(yè)務(wù)過程任務(wù)間的協(xié)作關(guān)系定義不同組織間的協(xié)同模式;然后,基于擴(kuò)展消息庫所的Petri網(wǎng)模型來描述跨組織應(yīng)急業(yè)務(wù)過程模型;給出挖掘組織內(nèi)業(yè)務(wù)過程模型和組織間協(xié)同過程模型的挖掘算法,最后通過模型集成算法將不同組織的內(nèi)部業(yè)務(wù)過程模型和組織間協(xié)同過程模型進(jìn)行合并,得到跨組織全局應(yīng)急業(yè)務(wù)過程模型,使用PIPE對模型進(jìn)行正確性驗證。

跨組織;應(yīng)急;協(xié)同模式;Petri網(wǎng);業(yè)務(wù)過程

0 引言

涉及公共安全和公共衛(wèi)生的突發(fā)事件應(yīng)急救援需要多個組織部門共同完成,應(yīng)急預(yù)案是這些組織部門應(yīng)對突發(fā)事件的行動指南。然而,由于具體情況不同,應(yīng)急救援組織部門執(zhí)行的實際任務(wù)和應(yīng)急預(yù)案規(guī)定的執(zhí)行任務(wù)可能存在不同。通過挖掘跨組織應(yīng)急救援執(zhí)行過程,可發(fā)現(xiàn)應(yīng)急預(yù)案的不足,對應(yīng)急救援執(zhí)行過程進(jìn)行改進(jìn),從而提高應(yīng)急救援執(zhí)行效率,加強(qiáng)組織間協(xié)同合作,減少突發(fā)災(zāi)害事件造成的公共財產(chǎn)損失。

各類企業(yè)信息系統(tǒng)(IS)得到了廣泛應(yīng)用,大量信息以事件日志的形式保留在企業(yè)數(shù)據(jù)庫系統(tǒng)中[1]。過程挖掘技術(shù)能夠從IS產(chǎn)生的事件日志中抽取信息,為各類應(yīng)用的過程發(fā)現(xiàn)、監(jiān)測和改進(jìn)提供新的手段[2]。傳統(tǒng)上,過程挖掘應(yīng)用于單一的組織內(nèi)部。但是,隨著服務(wù)技術(shù)、供應(yīng)鏈技術(shù)和云計算技術(shù)的普及,會遇到很多包含多組織的事件日志挖掘場景。過程挖掘宣言[3]中指出一般存在2種跨組織的過程挖掘情形:① 不同組織共同工作,處理業(yè)務(wù)于過程協(xié)作環(huán)境;② 不同組織環(huán)境中執(zhí)行相同的過程,同時分享經(jīng)驗、知識或者一個共同的框架。前者,Claes等[4]提出一種根據(jù)不同組織之間的合作伙伴關(guān)系來合并不同組織的事件日志的方法,然后對不同組織的集成事件日志進(jìn)行集中挖掘,即可得到一個跨組織業(yè)務(wù)過程模型;Zeng等[5]提出一種分布式的跨組織業(yè)務(wù)過程挖掘方法,可以根據(jù)多源事件日志挖掘跨組織全局業(yè)務(wù)過程模型;劉聰[6]提出一種支持隱私保護(hù)的跨組織業(yè)務(wù)流程挖掘方法。后者,Buijs等[7-8]提出了一種挖掘不同組織從事同一類業(yè)務(wù)的過程模型的方法,借鑒處理經(jīng)驗,從而改進(jìn)自身業(yè)務(wù)過程。

1 跨組織應(yīng)急業(yè)務(wù)過程案例分析

結(jié)合南京市突發(fā)環(huán)境污染事件應(yīng)急方案中規(guī)定的事件處置過程給出跨組織任務(wù)的形式化定義,分析跨組織任務(wù)的構(gòu)成要素以及任務(wù)間的協(xié)作關(guān)系。

1.1 應(yīng)急案例分析

南京市突發(fā)環(huán)境污染事件應(yīng)急預(yù)案規(guī)定:當(dāng)發(fā)生環(huán)境污染突發(fā)事件后,各個應(yīng)急組織的具體應(yīng)急處理過程如下。

市公安局:110接警后,在第一時間抽調(diào)警力趕赴事故現(xiàn)場,同時向市政府應(yīng)急辦報告突發(fā)環(huán)境污染事件的發(fā)生情況;組織開展現(xiàn)場治安、疏散人員、警戒及周邊道路交通管制,保障救援運輸暢通和城市公共交通;協(xié)調(diào)并做好事故現(xiàn)場記錄,視聽資料、證人證言收集等取證工作;參與對突發(fā)事件信息報道、善后處置、調(diào)查處理等工作。

市政府應(yīng)急辦:在接到突發(fā)環(huán)境污染事件爆發(fā)信息后,立即成立應(yīng)急小組,同時將接到信息報送上級部門,根據(jù)應(yīng)急響應(yīng)級別向省、市政府報告突發(fā)事件情況;組織有關(guān)部門和專家分析判定事故性質(zhì)和危害程度,同時制定事件處置方案;向市衛(wèi)生局、市環(huán)保局等有關(guān)部門發(fā)送啟動應(yīng)急處置方案的信息;匯集各部門的處置信息,組織相關(guān)部門召開突發(fā)事故通報會。

市消防局:119接警后,立刻組織消防人員趕赴現(xiàn)場,同時將事件上報,開展專業(yè)消防救援工作,組織調(diào)查突發(fā)事件中污染事故原因,并參與協(xié)調(diào)綜合力量投入救援行動。

市衛(wèi)生局:立即調(diào)配醫(yī)務(wù)人員、醫(yī)療器材、急救藥品等趕赴現(xiàn)場;組織有關(guān)醫(yī)療專家根據(jù)傷員情況制定救治方案;組織現(xiàn)場搶救及傷員轉(zhuǎn)運、分流等救治工作;組織突發(fā)事件中公共衛(wèi)生事件的調(diào)查、處理工作;負(fù)責(zé)統(tǒng)計上報接收到的傷亡人員信息。

市環(huán)保局:組織有關(guān)環(huán)保專家趕赴現(xiàn)場,開展突發(fā)環(huán)境事件現(xiàn)場調(diào)查,分析污染物種類、濃度、污染程度和范圍,提出對現(xiàn)場應(yīng)急處置和人員保護(hù)措施的建議,組織有關(guān)專家分析并評估事件發(fā)生的原因、發(fā)展趨勢以及污染影響程度等。

在跨組織應(yīng)急業(yè)務(wù)過程處置過程中,每個應(yīng)急組織部門都會有相應(yīng)的執(zhí)行任務(wù)集合,表1為某城市突發(fā)環(huán)境污染事件應(yīng)急處置任務(wù)集合。

表1中:M1表示某地發(fā)生突發(fā)環(huán)境污染事件,M2表示所執(zhí)行的突發(fā)環(huán)境污染事件應(yīng)急預(yù)案,M3表示事件中搶救的中毒人員,M4表示根據(jù)污染物給出的人員保護(hù)建議,M5表示中毒人員治療情況,M6表示后期環(huán)境污染情況,M7表示事故的發(fā)生原因。

分析上述城市突發(fā)環(huán)境污染事件應(yīng)急處置過程可以發(fā)現(xiàn):① 參與城市突發(fā)環(huán)境污染事件應(yīng)急救援的組織部門一共有5個,分別為市公安局、市政府應(yīng)急辦、市消防局、市衛(wèi)生局和市環(huán)保局;② 每個組織部門需要執(zhí)行各自的任務(wù)集合,每個任務(wù)具有一些固定的屬性,例如任務(wù)執(zhí)行的組織部門、任務(wù)執(zhí)行的開始和結(jié)束時間、任務(wù)執(zhí)行需要接收的消息集合以及發(fā)送的消息集合;③ 任務(wù)間可能存在消息傳遞關(guān)系,例如公安局執(zhí)行“上報事件”和應(yīng)急辦所執(zhí)行“成立應(yīng)急小組”之間存在消息傳遞關(guān)系;④ 任務(wù)間可能存在消息共享關(guān)系,例如衛(wèi)生局“趕赴現(xiàn)場”和環(huán)保局“趕赴現(xiàn)場”共享由應(yīng)急辦發(fā)送的消息“執(zhí)行突發(fā)環(huán)境污染事件應(yīng)急預(yù)案”;⑤ 任務(wù)“事件通報會”需要公安局、消防局、應(yīng)急辦、環(huán)保局和衛(wèi)生局等多個組織部門共同參與,則稱“事件通報會”為同步任務(wù)。

定義1 在跨組織應(yīng)急業(yè)務(wù)過程模型中,六元組Task= 〈Name,Organization,TimeStart,TimeEnd,MessReq,MessSent〉被稱為跨組織任務(wù)。

其中:Name表示任務(wù)的名稱,Organization表示任務(wù)所屬的執(zhí)行部門,TimeStart表示任務(wù)的開始執(zhí)行時間,TimeEnd表示任務(wù)的執(zhí)行完成時間,Mess-Req表示任務(wù)執(zhí)行時接收的消息集合,MessSent表示任務(wù)執(zhí)行完成后發(fā)送的消息集合。

1.2 任務(wù)關(guān)系

分析上述城市突發(fā)環(huán)境污染事件應(yīng)急處置過程,可以發(fā)現(xiàn)不同組織部門的跨組織任務(wù)間存在有消息傳遞、消息共享和任務(wù)同步等協(xié)同模式。

如果某個任務(wù)的執(zhí)行需要接收其他任務(wù)發(fā)送來的消息,則稱這2個任務(wù)間存在消息傳遞關(guān)系。

定義2 任意給定2個不同的跨組織任 務(wù) 〈t1,O1,TS1,TE1,MessReq1,MessSent1〉與〈t2,O2,TS2,TE2,MessReq2,MessSent2〉, 如 果 有條件O1/=O2,MessSent1∩MessRe q2/=?或MessSent2∩MessRe q1/= ?成立,則稱t1和t2間存在消息傳遞關(guān)系。

如果某2個任務(wù)的執(zhí)行需要接收其他任務(wù)發(fā)送的相同消息,則稱這2個任務(wù)間存在消息共享關(guān)系。

定義3 任意給定2個不同的跨組織任 務(wù) 〈t1,O1,TS1,TE1,MessReq1,MessSent1〉與〈t2,O2,TS2,TE2,MessReq2,MessSent2〉,如果 O1/=O2,MessReq1∩MessReq2/=?成立,則稱t1和t2間存在消息共享關(guān)系。

如果某個任務(wù)由不同組織部門共同合作完成,由此形成多個分屬各個組織部門內(nèi)部的任務(wù),它們具有相同的任務(wù)名稱、開始時間、完成時間、接收消息和發(fā)送消息等屬性,則稱此任務(wù)為同步任務(wù)。

定義4 任意給定2個不同的跨組織任 務(wù) 〈t1,O1,TS1,TE1,MessReq1,MessSent1〉與〈t2,O2,TS2,TE2,MessReq2,MessSent2〉,如果有條件t1=t2,O1/=O2,TS1=TS2,TE1=TE2,MessReq1=MessReq2MessSent1=MessSent2成立,則稱t1(或t2)為同步任務(wù)。

2 擴(kuò)展消息庫所的Petri網(wǎng)模型

2.1 基礎(chǔ)知識

介紹擴(kuò)展消息庫所的Petri網(wǎng)模型之前,先簡單介紹Petri網(wǎng)和工作流網(wǎng)等相關(guān)的基本概念。Petri網(wǎng)是一種用于描述離散的、分布式系統(tǒng)的數(shù)學(xué)建模工具[9]。它既能描述系統(tǒng)的結(jié)構(gòu),又能描述系統(tǒng)的運行。從形式上看,1個網(wǎng)就是1個沒有孤立節(jié)點的有向二分圖。

定義5 滿足下列條件的四元組(P,T;F,M)稱為Petri網(wǎng):

(1)P∪T/=?;

(2)P∩T=?;

(3)F?(P×T)∪(T×P);

(4)dom(F)∪cod(F)=P∪T;

(5)M ∶P → {0,1,2,···}。

其中:P是庫所的有限集合,T是變遷的有限集合,F是網(wǎng)的流關(guān)系集合,M是網(wǎng)的標(biāo)識映射。在建模過程中,一般使用庫所代表條件,變遷代表事件。一個變遷有一定數(shù)量的輸入和輸出庫所,分別代表可以使用的資源或者數(shù)據(jù)。

定義6 設(shè)四元組PN=(P,T;F,M)是一個Petri網(wǎng),對于任意給定的元素x∈P∪T,稱·x={y|y∈P∪T∧(y,x)∈F}是元素x的前集,稱x·={y|y∈P∪T∧(x,y)∈F}是x的后集。

在Petri網(wǎng)的基礎(chǔ)上,Aalst提出了工作流網(wǎng)的概念,工作流網(wǎng)是一種特殊的Petri網(wǎng),其定義如下:

定義7 Petri網(wǎng)PN=(P,T;F,M)被稱為工作流網(wǎng),當(dāng)且僅當(dāng)其滿足下面的條件:

(1)有2個特殊的庫所i和o。庫所i是起始庫所,即·i=?;庫所o是終止庫所,即o·=?。

(2)如果在PN 中加入1個新的變遷t?,使t?連接庫所 i和 o,即 ·t?={o},t?·={i},這時所得到的PN是強(qiáng)連通的。

2.2 擴(kuò)展消息庫所的Petri網(wǎng)

定義8 給定Petri網(wǎng)PN=(P,T;F,M),當(dāng)且僅當(dāng)其滿足條件:

(1)P=PL∪PM,其中PL為邏輯庫所集合,PM為消息庫所集合,且PL∩PM=?;

(2)T表示任務(wù)變遷集合;

(3)F=FL∪FM,稱FL=(PL×T)∪(T×PL)為邏輯庫所與任務(wù)變遷之間的邏輯關(guān)系,FM=(PM×T)∪(T×PM)為消息庫所與任務(wù)變遷之間的消息接收與發(fā)送關(guān)系;

(4)?p∈ P,如果 p ∈ PL∧·p= ?,則有M0(p)=1,否則 M0(p)=0。

則稱PN為擴(kuò)展消息庫所的Petri網(wǎng),記為MWF net。MWF net模型是在普通Petri網(wǎng)基礎(chǔ)上增加了消息庫所元素,有關(guān)其變遷引發(fā)規(guī)則、可達(dá)性和有界性等可根據(jù)普通Petri網(wǎng)的相關(guān)知識給出。

2.3 組織間協(xié)同模式

在1個跨組織應(yīng)急業(yè)務(wù)過程中,如果2個不同組織的任務(wù)之間存在消息傳遞或消息共享關(guān)系,則說這2個組織之間存在消息交互模式。

定義9設(shè)MWF Net1=(P1,T1;F1,M01)和MWF Net2=(P2,T2;F2,M02)分別是兩個不同組織部門O1和O2的業(yè)務(wù)過程模型,其中Pi=PLi∪PMi(i=1,2),如果 ① PM1∩PM2/= ?;②PL1∩PL2=?;③ T1∩T2=?成立,則稱O1和O2之間存在消息交互模式。

在1個跨組織應(yīng)急業(yè)務(wù)過程中,如果2個不同組織之間存在同步任務(wù),則說這2個組織之間存在任務(wù)同步模式。

定義10設(shè)M WF Net1=(P1,T1;F1,M01)和M WF Net2=(P2,T2;F2,M02)分別是2個不同組織部門O1和O2的業(yè)務(wù)過程模型,如果①P1∩P2=?;② T1∩T2/=?成立,則稱O1和O2之間存在任務(wù)同步模式。

3 跨組織應(yīng)急業(yè)務(wù)過程挖掘

本節(jié)首先介紹運行日志、任務(wù)集合和直接后繼任務(wù)集合等相關(guān)概念,然后給出組織內(nèi)業(yè)務(wù)過程挖掘算法和組織間協(xié)同模式挖掘算法,最后給出模型集成算法以得到全局跨組織業(yè)務(wù)過程模型。

定義11 跨組織應(yīng)急業(yè)務(wù)過程產(chǎn)生的案例是一系列跨組織任務(wù)的集合,即案例Case={Task|其中Task是一個跨組織任務(wù)}。

定義12 跨組織應(yīng)急業(yè)務(wù)過程產(chǎn)生的運行日志(RunningLogs)是一系列案例的集合,即運行日志RLogs={Case|Case是一個案例}。

定義13 設(shè)RLogs是一個跨組織應(yīng)急業(yè)務(wù)過程產(chǎn)生的運行日志,對于?Casei∈RLogs,則稱集合 TaskSet(Casei)={Tk|?Task ∈ Casei,其中任務(wù) Task= 〈Tk,O,TS,TE,MessReq,MessSent〉,1≤k≤|Case|}為案例任務(wù)集合,則稱集合TaskSet(RLogs)=TaskSet(Casei)為運行日志任務(wù)集合。

定義14 設(shè)RLogs是一個跨組織應(yīng)急業(yè)務(wù)過程產(chǎn)生的運行日志,對于運行日志RLogs中的任意兩個任務(wù)Ti與Tj,滿足條件Ti·TE ≤Tj·TS,則稱Tj是Ti的一個后繼任務(wù)(稱Ti是Tj的一個前驅(qū)任務(wù)),記為Ti?Tj;如果Ti?Tj,且不存在任務(wù)Tk,使得Ti? Tk與Tk? Tj成立,則稱Tj是Ti的一個直接后繼任務(wù)(稱Ti是Tj的一個直接前驅(qū)任務(wù)),記為Ti? Tj。

定義15 集合Ti·PostSet={Tj|Ti? Tj}稱為任務(wù)Ti的直接后繼任務(wù)集合。

3.1 組織內(nèi)部業(yè)務(wù)過程挖掘

使用擴(kuò)展消息庫所的Petri網(wǎng)模型表示組織內(nèi)部的業(yè)務(wù)過程模型,現(xiàn)有過程挖掘方法[10-14]不能直接應(yīng)用于組織內(nèi)部的業(yè)務(wù)過程模型挖掘,需要根據(jù)MWF Net模型擴(kuò)展消息庫所這一特性,給出新的挖掘方法來挖掘組織內(nèi)部的業(yè)務(wù)過程模型。在挖掘組織內(nèi)部的MWF Net模型之前,本文首先給出計算案例(Case)中的任務(wù)T的直接后繼任務(wù)集合的方法。

算法1 計算案例(Case)中的任務(wù)T的直接后繼任務(wù)集合T·PostSet。

輸入:〈Ti,Ti·TS,Ti·TE〉(1 ≤ i≤ |Case|)

輸出:Ti·PostSet

Step 1 For i=1 to|Case|do

Ti·PostSet← ?

For j=1 to|Case|do

If Ti·TE ≤ Tj·TS do

Ti·PostSet← Ti·PostSet∪ {Tj}

End if

End for

End for

Step 2 For each Tj∈ Ti·PostSet do

For each Tk∈Tj·PostSet do

Ti·PostSet← Ti·PostSet? {Tk}

End for

End for

Step 3 Return Ti·PostSet

其中,步驟1負(fù)責(zé)計算案例(Case)中的每個任務(wù)Ti的后繼任務(wù),首先令Ti·PostSet為空,依次遍歷案例(Case)中的每個任務(wù)Tj,如果Ti·TE ≤ Tj·TS,則將任務(wù) Tj加入到 Ti·PostSet;步驟 2,對于?Tj∈Ti·PostSet,將Tj的后繼任務(wù)集合中的所有任務(wù)從Ti·PostSet中刪除,此時所得集合即為Ti的直接后繼任務(wù)集合;步驟3,返回Ti·PostSet。

算法1的時間復(fù)雜度主要在于步驟1,由分析知步驟1的復(fù)雜度為O(|Case|2),因此算法1的時間復(fù)雜度為O(|Case|2)。

以表1中公安局的任務(wù)集合為例,使用算法1可以得到如表2所示的直接后繼任務(wù)集合。

表2 公安局任務(wù)的直接后繼任務(wù)集合Tab.2 Direct successor task set of public security bureau

通過算法1得到運行日志中的每個案例任務(wù)的直接后繼任務(wù)集合后,就可以利用算法2挖掘組織內(nèi)部的MWF Net模型,具體挖掘過程如下:

算法2 挖掘組織內(nèi)部的MWF Net模型。

輸入:(Ti,Ti·PostSet,Ti·MessReq,Ti·Sent)

輸出:MWF Net=(P,T;F,M0)

Step 1 PL← ?,PM← ?T← T∪{Ti},(1≤i≤|Case|),F←?,M0←?;

Step 2 For each Ti∈T do

If Ti·MessSent/= ? do

PM←PM∪Ti·MessSent

F←F∪{(Ti,P)|P∈Ti·MessSent}

End if

If Ti·MessReq/= ? do

PM←PM∪Ti·MessReq

F←F∪{(P,Ti)|P∈Ti·MessReq}

End if

End for

Step 3 For any two tasks Ti,Tj∈T do

If Tj∈ Ti·PostSet do

PL←PL∪{Pij}

F←F∪{(Ti,Pij),(Pij,Tj)}

End if

End for

Step 4 For each place p∈P do

If p=psdo

M0(p)←1

Else

M0(p)←0

End if

End for

Step 5 Return MWF Net=(P,T;F,M0)

其中,步驟1負(fù)責(zé)初始化組織內(nèi)MWF Net模型;步驟2,若MessSent/= ? 或MessReq/= ?,則將PM加入Ti的消息集合,并增加Ti與消息庫所間的流關(guān)系;步驟3,對于?Ti,Tj∈T,如果Tj∈ Ti·PostSet,則將Pij加入集合PL,并增加流關(guān)系(Ti,Pij),(Pij,Tj);步驟4,對于?p∈P,如果p是開始庫所,則置M0(p)為1,否則置M0(p)為0;步驟5,返回單個組織內(nèi)部的MWF Net模型。

算法2的時間復(fù)雜度主要在于步驟3,經(jīng)分析知步驟3的時間復(fù)雜度為O(|T|2),因此算法2的時間復(fù)雜度為O(|T|2)。

將表2中公安局的任務(wù)及其直接后繼任務(wù)集合作為算法2的輸入,即可得到圖1所示的公安局內(nèi)的應(yīng)急業(yè)務(wù)過程模型,其中使用同心圓表示消息庫所。

圖1 公安局應(yīng)急業(yè)務(wù)過程模型Fig.1 Emergency business process model of public security bureau

3.2 組織間協(xié)同模型挖掘

為了得到組織間的協(xié)同模型,需要過濾處理每個組織的運行日志。設(shè)RLogi和RLogj分別是組織Oi和Oj的運行日志,任意給定2個任務(wù)Ti∈RLogi和Tj∈RLogj,如果滿足下列條件之一:

(1)Ti·MessReq∩Tj·MessSent/= ?;

(2)Ti·MessSent∩Tj·MessReq/= ?;

(3)Ti·MessReq∩Tj·MessReq/= ?;

(4)Ti·TS=Tj·TS ∧Ti·TE=Tj·TE。

則將任務(wù)Ti和Tj保留在各自的運行日志中,否則將它們從運行日志中刪除。

算法3 組織間協(xié)同模型挖掘。

輸入:2個組織過濾處理后的運行日志RLog1和RLog2

輸出:2個組織間的協(xié)同模型MWF Net12

Step 1 PL← ?,PM← ?,T← ?,F← ?,M0←?

Step 2 For i=1 to|Case1|do

For j=1 to|Case2|do

If Ti·TS=Tj·TS and

Ti·TE=Tj·TE do

Ti←Tj

T←T∪Ti

End if

If Ti·MessReq∩Tj·MessSent/= ? do

PM← PM∪(Ti·MessReq∩

Tj·MessSent)T ←T∪Ti∪Tj

F←F∪{(Tj,p),(p,Ti)|

p∈ Ti·MessReq∩Tj·MessSent}

End if

If Ti·MessSent∩Tj·MessReq/= ? do

PM←PM∪(Ti·MessSent∩Tj·

MessReq)

T←T∪Ti∪Tj

F←F∪{(Ti,p),(p,Tj)|

p ∈ Ti·MessSent∩Tj·MessReq}

End if

If Ti·MessReq∩Tj·MessReq/= ? do

PM← PM∪(Ti·MessReq∩

Tj·MessReq)

T←T∪Ti∪Tj

F←F∪{(p,Ti),(p,Tj)|

p∈ Ti·MessReq∩Tj·MessReq}

End if

End for

End for

Step 3 For each place p∈P do

If p=psdo

M0(p)←1

Else

M0(p)←0

End if

End for

Step 5 Return MWF Net12

其中,步驟1負(fù)責(zé)初始化不同組織間的協(xié)同模型;步驟2依次遍歷RLog1中的任務(wù)Ti,?Tj∈RLog2,如果 Ti·TS=Tj·TS 且 Ti·TE=Tj·TE,則Ti和Tj為同步任務(wù),合并Ti和Tj,將Ti加入集合T中;如果Ti·MessReq∩Tj·MessSent/= ?,則將它們的交集加入集合P中,并增加流關(guān)系(Tj,p),(p,Ti);如果Ti·MessSent∩Tj·MessReq/= ?,則將它們的交集加入集合P中,并增加流關(guān)系(Ti,p),(p,Tj);如果 Ti·MessReq∩Tj·MessReq/= ?,則將它們的交集加入集合P中,并增加流關(guān)系(p,Ti),(p,Tj);步驟3對于?p∈P,如果p是開始庫所,則置M0(p)為1,否則置M0(p)為0;步驟4返回組織間協(xié)同模型MWF Net12。

算法3的時間復(fù)雜度主要在于步驟2,經(jīng)分析知步驟2的復(fù)雜度為O(|Case1|·|Case2|),因此算法3的時間復(fù)雜度為O(|Case1|·|Case2|)。

過濾公安局與應(yīng)急辦的運行日志,作為算法3的輸入,可得圖2所示的協(xié)同過程模型。

圖2 公安局與應(yīng)急辦的協(xié)同模型Fig.2 Cooperative model of public security bureau and emergency office

3.3 跨組織應(yīng)急業(yè)務(wù)過程模型挖掘

組織的內(nèi)部業(yè)務(wù)過程模型描述了組織內(nèi)部任務(wù)的執(zhí)行情況,組織間的協(xié)同過程模型描述了不同組織之間相互協(xié)作情況,但是組織內(nèi)部業(yè)務(wù)過程模型和組織間協(xié)同過程模型都不能直觀的反映跨組織業(yè)務(wù)過程的全局執(zhí)行情況,因此需要將組織內(nèi)業(yè)務(wù)過程模型和組織間協(xié)同過程模型進(jìn)行集成,以得到全局跨組織應(yīng)急業(yè)務(wù)過程模型。

算法4 業(yè)務(wù)過程模型集。

輸入:n個組織內(nèi)的業(yè)務(wù)過程模型MWF Neti(1≤i≤n),兩兩組織間的協(xié)同模型

MWF Netij(1≤i,j≤n)

輸出:跨組織應(yīng)急業(yè)務(wù)過程模型MWF Net

Step 1 P←?,T←?,F←?,M0←?;

Step 2 For i=1 to n do

For j=1 to n do

If i/=j do

Pi←Pi∪Pj∪Pij

Ti←Ti∪Tj∪Tij

Fi←Fi∪Fj∪Fij

M0i←M0i∪M0j∪M0ij

End if

End for

P←P∪Pi

T←T∪Ti

F←F∪Fi

M0←M0∪M0i

End for

Step 3 For i=1 to n do

M0i(psi)←1

End for

Step 4 Return MWF Net

其中,步驟1負(fù)責(zé)初始化跨組織應(yīng)急業(yè)務(wù)過程模型;步驟2對于?MWF Neti,MWF Netj,合并MWF Neti,MWF Netj與MWF Netij,即可得到2個組織的跨組織應(yīng)急業(yè)務(wù)過程模型,依次對只包含2個組織的跨組織應(yīng)急業(yè)務(wù)過程模型合并,即可得到全局跨組織應(yīng)急業(yè)務(wù)過程模型;步驟3對于每個組織內(nèi)的開始庫所Psi和結(jié)束庫所Pei,將每個組織內(nèi)的開始庫所標(biāo)識設(shè)置為1;步驟4返回跨組織全局應(yīng)急業(yè)務(wù)過程模型MWF Net。

算法4的時間復(fù)雜度主要在于步驟2,經(jīng)分析知步驟2的復(fù)雜度為O(n2),因此算法4的時間復(fù)雜度為O(n2),其中n表示組織數(shù)。

綜合集成執(zhí)行突發(fā)環(huán)境污染事件應(yīng)急救援的5個組織內(nèi)部業(yè)務(wù)過程模型和他們之間的協(xié)同過程模型,即可得到如圖3所示的跨組織全局應(yīng)急業(yè)務(wù)過程模型。

4 模型正確性驗證

這里將給出跨組織應(yīng)急業(yè)務(wù)過程模型的正確性定義,并使用Petri網(wǎng)編輯器[15]驗證所挖掘的跨組織應(yīng)急業(yè)務(wù)過程模型滿足正確性定義。在文獻(xiàn)[16]中,Aalst等給出了工作流網(wǎng)的正確性引理:

圖3 跨組織應(yīng)急業(yè)務(wù)過程模型Fig.3 Cross-organizational emergency businessprocessmodel

引理1任意給定工作流網(wǎng)WF =(P,T,F,M0),其中庫所i∈P為開始庫所,o∈P為結(jié)束庫所,WF是正確的,當(dāng)且僅當(dāng)下列條件成立:① 對于庫所i中的任意托肯,在庫所o中都將有對應(yīng)的托肯,當(dāng)WF運行結(jié)束時;② 如果庫所o中僅有一個托肯,則其他庫所中無托肯;③ 在WF中無死變遷。

根據(jù)引理1,可以給出跨組織應(yīng)急業(yè)務(wù)過程模型的正確性定義:

定義16設(shè)MWF Netk={MWF Neti=(Pi,Ti,Fi,M0i)|MWF Neti是第i個組織的應(yīng)急過程模型},MWF Net=(P,T,F,M0)是集成的跨組織應(yīng)急業(yè)務(wù)過程模型,當(dāng)條件① 當(dāng)MWF Net運行完成時,在消息庫所中無托肯;② 對于每一個MWF Neti運行完成時,其結(jié)束庫所中的托肯數(shù)等于開始庫所中的初始托肯數(shù);③ MWF Net中無死變遷,成立時,則MWF Net是正確的。

模擬運行圖3所示的跨組織應(yīng)急業(yè)務(wù)過程模型,可得到圖4所示的結(jié)果,其運行完成的狀態(tài)滿足定義16中的3個條件,故本文所挖掘的跨組織應(yīng)急業(yè)務(wù)過程模型是正確的。

圖4 運行完成的跨組織應(yīng)急業(yè)務(wù)過程模型Fig.4 The fi nished cross-organizational emergency business process model

5 結(jié)語

應(yīng)急預(yù)案設(shè)計的合理有利于減少突發(fā)事件造成的公共財產(chǎn)損失,挖掘分析跨組織應(yīng)急救援過程,可發(fā)現(xiàn)應(yīng)急預(yù)案存在的不足,從而改進(jìn)應(yīng)急救援過程,通過組織間協(xié)同合作,提高應(yīng)急救援執(zhí)行效率。本文對跨組織應(yīng)急業(yè)務(wù)過程案例進(jìn)行分析,提出了一種跨組織應(yīng)急業(yè)務(wù)過程挖掘方法。通過定義跨組織任務(wù)的協(xié)作關(guān)系,確定跨組織間協(xié)同運作模式和策略;擴(kuò)展消息庫所的Petri網(wǎng)模型來描述跨組織應(yīng)急業(yè)務(wù)過程模型,在任務(wù)同步和消息交換的基礎(chǔ)上,挖掘跨組織協(xié)同業(yè)務(wù)過程模型,本文的創(chuàng)新貢獻(xiàn)是設(shè)計組織內(nèi)業(yè)務(wù)過程模型挖掘和組織間協(xié)同過程模型挖掘算法,采用模型集成得到全局跨組織應(yīng)急業(yè)務(wù)過程模型。

下一步的工作將對跨組織任務(wù)間的協(xié)作關(guān)系進(jìn)行擴(kuò)展,如對挖掘任務(wù)的并行、互斥和資源共享等模式進(jìn)行研究,以及驗證挖掘的模型是否為最優(yōu)模型。

[1]AALST W M PV D,SCHONENBERG M H,SONG M.Time prediction based on process mining[J].Information Systems,2011,36(2):450-475.

[2] AALST W M PV D.Process mining:Discovery,conformanceand enhancement of businessprocesses[M].Berlin,Heidelberg:Springer-Verlag,2011.

[3]AALST W V D,ADRIANSYAH A,MEDEIROS A,et al.Process mining manifesto[C]//International Conference on Business Process Management.Berlin,Heidelberg:Springer-Verlag,2011:169-194.

[4] CLAESJ,POELSG.Merging event logs for processmining:A rule based merging method and rule suggestion algorithm[J].Expert Systems with Applications,2014,41(16):7291-7306.

[5] ZENGQ,SUN SX,DUAN H,et al.Cross-organizational collaborativeworkfl ow mining from amulti-sourcelog[J].Decision Support Systems,2013,54(3):1280-1301.

[6] 劉聰.跨組織業(yè)務(wù)流程挖掘及其隱私保護(hù)方法研究[D].山東:山東科技大學(xué),2015.

[7]BUIJS J C A M,DONGEN B F V,AALST W M P V D.Towards cross-organizational process mining in collections of process models and their executions[J].Business Process Management Workshops-bpm International Workshops,2015,100:2-13.

[8]BUIJS J C A M,DONGEN B F V,AALST W M P V D.Mining confi gurable process models from collections of event logs[M].Berlin,Heidelberg:Springer-Verlag,2013.

[9] 吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2006.

[10]WEN L J,AALSTWM PV D,WANGJM,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.

[11]WEIJTERA JM M,AALST W M PV D.Process mining with theheuristics miner-algorithm[R].Eindhoven:Eindhoven University of Technology,2006.

[12]BRATOSIN C,SIDOROVA N,AALST W V D.Discovering process models with genetic algorithms using sampling[C]//BERLIN S-V.KES’10 Proceedings of the 14th International Conferenceon Knowledge-based and Intelligent Information and Engineering Systems.Cardiff,UK:Cardiff,2010:41-50.

[13]BERGENTHUM R,DESEL J,LORENZ R,et al.Processmining based on regionsof languages[C]//ALONSO G,ZURICH E.BPM’07 Proceedings of the 5th International Conference on Business Process Management.Berlin,Heidelberg:Springer-Verlag,2007:375-383.

[14]SONG M,GUNTHER C W,AALST W M PV D.Trace clustering in process mining[M].Berlin,Heidelberg:Politecnico di Milano,2008.

[15]DINGLE N J,KNOTTENBELT W J,SUTO T.Pipe2:A tool for theperformanceevaluation of generalised stochastic Petri Nets[J].Acm Sigmetrics Performance Evaluation Review,2009,36(4):34-39.

[16]AALST W M P V D.The application of Petri nets to workfl ow management[J].Journal of Circuits Systemsand Computers,1998,8(1):21-66.

Abstract:Thecaseof cross-organizationalemergency businessprocesswasfirstly analyzed,and theformal defi nitionof cross-organizational task was given.At the same time,the cooperative relationship between cross-organizational taskswas defi ned.The cooperative modelbetween different organizations based on the cooperative relationship among inter-organizational tasks was defined.Then,the crossorganizational emergency business process model was described by using the extended Petri net model.The mining algorithms of the intra-business process model and the inter-organizational collaborative process model were given.Finally,the internal business process model and the inter-organizational collaborative process model of different organizations are merged through the model integration algorithm to obtain the global cross-organizational emergency business process model.The platform independent petri net editor(PIPE)wasapplied to support thesoundnessof thecross-organizational emergency businessprocessmodel.

Keywords:cross-organization;emergency;collaborativemodel;petrinet;businessprocess

簡 訊

應(yīng)用藝術(shù)設(shè)計學(xué)院教師獲2016年度“晨光計劃”(藝術(shù)學(xué)專項)資助

近日,上海市教育委員會、上海市教育發(fā)展基金會組織舉辦了2016年度“晨光計劃”項目資助儀式,全市70項A類項目、29項B類項目以及9項藝術(shù)學(xué)專項項目獲得立項資助。上海第二工業(yè)大學(xué)應(yīng)用藝術(shù)設(shè)計學(xué)院黎春輝老師的“古代玉器造型在當(dāng)代陶藝創(chuàng)作中的應(yīng)用研究”成功立項。

“晨光計劃”是為推進(jìn)本市高校教師隊伍建設(shè),促進(jìn)優(yōu)秀人才的成長,培養(yǎng)造就一批青年骨干教師,由上海市教育發(fā)展基金會倡議并出資設(shè)立的上海高校青年科研骨干培養(yǎng)計劃,由上海市教育委員會與上海市教育發(fā)展基金會共同管理實施。

Cross-organizational Emergency Business Process Mining

TAN Wenan1,2,WU Yafeng1
(1.School of Computer Science and Technology,Nanjing University of Aeronauticsand Astronautics,Nanjing 210016,China;2.School of Computer and Information Engineering,Shanghai Polytechnic University,Shanghai201209,China)

TP 391

A

1001-4543(2017)03-0217-10

10.19570/j.cnki.jsspu.2017.03.010

2017-05-29

譚文安(1965–),男,湖北荊州人,博士,教授,主要研究方向為協(xié)同計算與系統(tǒng)進(jìn)化、協(xié)同學(xué)習(xí)與知識管理。E-mail:watan@sspu.edu.cn。

國家自然科學(xué)基金項目(61672022),南京航空航天大學(xué)研究生創(chuàng)新基地(實驗室)開放基金項目(kfjj20161608),上海第二工業(yè)大學(xué)校重點學(xué)科(XXKZD1604),上海第二工業(yè)大學(xué)研究生創(chuàng)新基金(No.A01GY17F022)資助