劉磊

(廣東工業(yè)大學(xué)，廣東廣州510006)

1.引言

作為宇宙間所有事物具有的一種屬性，時(shí)間貫穿著事物的發(fā)展過程。各式各樣與時(shí)間緊密相關(guān)的數(shù)據(jù)、信息及其聯(lián)系無(wú)不深深影響著人類社會(huì)生活的方方面面。在日常事務(wù)的處理過程中，人們不僅僅需要關(guān)注數(shù)據(jù)和信息本身，更要了解和研究它們?cè)谟绊懯聞?wù)處理的時(shí)序、有效性等時(shí)間問題。在工作流系統(tǒng)中，各種事務(wù)同樣有時(shí)間屬性[1]。有些事務(wù)在一個(gè)時(shí)間段內(nèi)是有效的，而超出這個(gè)時(shí)間段就是無(wú)效的。比如在采購(gòu)系統(tǒng)中，規(guī)定下訂單后的一周內(nèi)雙方必須簽合同，如果一周內(nèi)雙方?jīng)]有簽署，那么該訂單就是無(wú)效的；有的系統(tǒng)還會(huì)規(guī)定在每個(gè)季度的最后一個(gè)工作日提交統(tǒng)計(jì)報(bào)表。這些事務(wù)都是與時(shí)間有緊密關(guān)系的。

工作流系統(tǒng)中活動(dòng)的有效性可分為兩種：一種是由工作流邏輯結(jié)構(gòu)和活動(dòng)執(zhí)行延遲而產(chǎn)生的，如一個(gè)活動(dòng)必須在其所有前序活動(dòng)完成時(shí)才能啟動(dòng)；另一種是由過程設(shè)計(jì)者根據(jù)業(yè)務(wù)策略及法律法規(guī)來設(shè)定，如某個(gè)事件必須要在某個(gè)日期前完成，在某個(gè)月某個(gè)固定日期執(zhí)行某個(gè)動(dòng)作等。后一個(gè)有效性是與時(shí)間因素有關(guān)的，在本文中我們只研究后者，考慮如何有效地控制各事務(wù)的時(shí)間屬性，以保證工作流系統(tǒng)中各事務(wù)按時(shí)有序地完成。

2.CTL基本概念

本文中將采用的時(shí)序邏輯是計(jì)算樹邏輯(Computation Tree Logic，CTL)，CTL是一種分支時(shí)序邏輯[2]。它的時(shí)間模型是一個(gè)樹狀結(jié)構(gòu)，未來有不同的路徑，其中任何一個(gè)都可能是現(xiàn)實(shí)的實(shí)際路徑。由于行為的不確定性，它可以有多個(gè)可能的后繼狀態(tài)，每個(gè)這樣的狀態(tài)又可以有多個(gè)可能的后繼狀態(tài)，依此類推可以產(chǎn)生一顆狀態(tài)樹。

定義1 CTL有下列用Backus-Naur范式給出的語(yǔ)法：

其中p是取自某原子集的任意命題原子。

3.有效性約束的建模

[3]提出了工作流系統(tǒng)中時(shí)序約束的三種主要形式，根據(jù)這里對(duì)有效性的定義，以及在實(shí)際系統(tǒng)中碰到的有關(guān)時(shí)間有效性的問題，可以把時(shí)間有效性約束歸納分成以下三類：

(1)最長(zhǎng)時(shí)間距離約束：指活動(dòng)A和其后繼活動(dòng)B之間的時(shí)間距離最長(zhǎng)不能超過某一指定時(shí)間值。如本文剛開始提到的下訂單后的一周內(nèi)必須簽署合同，否則逾期訂單失效，就屬于此類約束。

(2)最短時(shí)間距離約束：指活動(dòng)A和其后繼活動(dòng)B之間的時(shí)間距離最短不能小于某一指定時(shí)間值。如在采購(gòu)系統(tǒng)中，中標(biāo)公告必須公示一段時(shí)間后，采購(gòu)雙方才能簽訂合同。

(3)固定時(shí)間約束：在固定的日期執(zhí)行某些活動(dòng)。如每月的第一個(gè)周一系統(tǒng)自動(dòng)發(fā)布職位空缺公告。

為了對(duì)時(shí)間有效性約束建模，在一階邏輯系統(tǒng)中定義常量Start，End，I，J，K，…分別表示工作流的開始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)以及工作流模型中的各項(xiàng)活動(dòng)，系統(tǒng)中變量的定義如下：

(1)向量s[k]，k=0，1，…，n+1，其中，n是工作流模型中除去開始和結(jié)束節(jié)點(diǎn)外的實(shí)際活動(dòng)數(shù)量，s[k]取1或0，分別表示活動(dòng)處于執(zhí)行或非執(zhí)行狀態(tài)。

(2)全局時(shí)鐘變量c，c的取值為整數(shù)，值域?yàn)閇-1，N]，N為一個(gè)大于工作流模型執(zhí)行總時(shí)間的整數(shù)，c的變化表示系統(tǒng)時(shí)鐘的運(yùn)行。實(shí)際系統(tǒng)中在不考慮時(shí)間約束和活動(dòng)執(zhí)行延遲的情況下可令，其中n為工作流活動(dòng)的總數(shù)量，dk是活動(dòng)k的執(zhí)行時(shí)間。

(3)局部時(shí)鐘向量lc[k]，k=0，1，…，n+1。lc[k]的值域與變量c的值域相同，lc[k]的變化表示和活動(dòng)k相關(guān)的局部時(shí)鐘運(yùn)行。

下面用該邏輯系統(tǒng)來為三類時(shí)間有效性約束分別建模。

(1)最長(zhǎng)時(shí)間距離約束的CTL公式描述：

上式表示對(duì)于任意路徑，活動(dòng)k和活動(dòng)j之間的時(shí)間距離都不大于指定時(shí)間，其中活動(dòng)j是活動(dòng)k的后繼，dk是活動(dòng)k的執(zhí)行時(shí)間，lc[j]和lc[k]分別是活動(dòng)j和k局部時(shí)鐘。

(2)最短時(shí)間距離約束的CTL公式描述：

上式表示對(duì)于任意路徑，活動(dòng)k和活動(dòng)j之間的時(shí)間距離不小于指定時(shí)間，其中活動(dòng)j是活動(dòng)k的后繼，dk是活動(dòng)k的執(zhí)行時(shí)間，lc[j]和lc[k]分別是活動(dòng)j和k局部時(shí)鐘。

(3)固定時(shí)間約束的CTL公式描述：

上式表示對(duì)于任意路徑，活動(dòng)k都在指定時(shí)間開始執(zhí)行，其中c為全局時(shí)鐘。如果在指定時(shí)間有多個(gè)活動(dòng)，如j、k、i并行執(zhí)行，可用如下公式表示：

上述時(shí)序邏輯公式只是在時(shí)間層面上對(duì)有效性約束進(jìn)行描述，沒有涉及到活動(dòng)的邏輯結(jié)構(gòu)。在本文中，有效性約束模型可以在一個(gè)一階邏輯系統(tǒng)描述的Kripke結(jié)構(gòu)上進(jìn)行語(yǔ)義解釋。

國(guó)網(wǎng)電力調(diào)控自動(dòng)化機(jī)房中的布線工作是較為復(fù)雜的工作，并且有很多的線路都是在地下或者是建筑物頂端位置，所以，布線的工作難度也是相對(duì)較大的。在實(shí)際施工過程中，還會(huì)有很多的突發(fā)事情，比如線路長(zhǎng)度的差異，機(jī)房中線路布置出來的美觀性等諸多方面的問題，都會(huì)影響到布線的實(shí)際施工。目前，我國(guó)有很多供電企業(yè)在機(jī)房布線方面都是存在很大問題的。因此，在實(shí)際國(guó)網(wǎng)電力自動(dòng)化機(jī)房布線工作當(dāng)中，必須要在前期的設(shè)計(jì)階段，設(shè)計(jì)出科學(xué)合理具有實(shí)用性的布線線路，還需要保證線路的使用效率，以及后期的線路維護(hù)、管理等問題，只有這樣才能在一定程度上提高國(guó)網(wǎng)電力自動(dòng)化機(jī)房的安全性和效率性，從而去實(shí)現(xiàn)機(jī)房所帶來的經(jīng)濟(jì)價(jià)值。

值得說明的是，在工作流系統(tǒng)中CTL能描述的有效性約束不僅僅只是上面三種，很多復(fù)雜的約束都可以用CTL來描述。

4.有效性約束的驗(yàn)證

上述用CTL描述的有效性約束可用模型檢查的方法來進(jìn)行驗(yàn)證。模型檢查的研究始于八十年代初，經(jīng)過二十多年的發(fā)展，現(xiàn)已廣泛應(yīng)用于計(jì)算機(jī)硬件、通信協(xié)議、控制系統(tǒng)、安全認(rèn)證協(xié)議等方面的分析與驗(yàn)證，而且已發(fā)展出了很多優(yōu)秀的模型檢查工具，如SMV、SPIN、CWB等[4]。模型檢查的主要思想是檢測(cè)用狀態(tài)遷移系統(tǒng)描述的有窮狀態(tài)系統(tǒng)的行為是否滿足用時(shí)序邏輯描述的系統(tǒng)的性質(zhì)。

我們采用SMV模型檢查工具，SMV基本原理如圖1所示：

利用SMV進(jìn)行模型檢查的基本步驟為[5]：

(1)用SMV自帶的系統(tǒng)描述語(yǔ)言，給出系統(tǒng)的形式化模型，包括系統(tǒng)狀態(tài)和狀態(tài)間的遷移關(guān)系；

(2)用CTL給出待驗(yàn)證的屬性描述；

(3)將系統(tǒng)的SMV描述和待驗(yàn)證屬性的CTL描述輸入檢測(cè)系統(tǒng)；

(4)若結(jié)果為TRUE，則系統(tǒng)滿足該性質(zhì)，否則不滿足，系統(tǒng)給出反例。

如果用SMV來驗(yàn)證工作流系統(tǒng)的有效性約束，需要用SMV自帶的描述語(yǔ)言來對(duì)工作流系統(tǒng)建模，SMV模型檢查工具是基于Kripke結(jié)構(gòu)的，而實(shí)際工作流系統(tǒng)大多是用工作流過程定義語(yǔ)言(Workflow Process Definition Language，WPDL)來描述的[6]，所以我們需要將工作流過程模型轉(zhuǎn)換為Kripke遷移系統(tǒng)模型。具體的轉(zhuǎn)換方法請(qǐng)參考文獻(xiàn)[7]。

5.實(shí)例研究

本文研究的工作流系統(tǒng)是一個(gè)采購(gòu)系統(tǒng)，其業(yè)務(wù)流程如圖2所示。在這個(gè)采購(gòu)系統(tǒng)中，采購(gòu)單位先制作訂單，然后提交部門內(nèi)部負(fù)責(zé)人審核，若審核通過后，可以選擇供應(yīng)商，也就是向供應(yīng)商下單。待商家確認(rèn)訂單后，即可簽署合同。在業(yè)務(wù)流程圖中，每個(gè)節(jié)點(diǎn)由三部分組成：一部分為活動(dòng)標(biāo)識(shí)，另一部分為活動(dòng)的名字，最后一部分為活動(dòng)執(zhí)行的時(shí)間。

根據(jù)上面給出的驗(yàn)證方法，首先將WPDL描述的工作流模型轉(zhuǎn)換成SMV語(yǔ)言描述的系統(tǒng)，限于篇幅，這里不再給出該采購(gòu)系統(tǒng)的WPDL描述。下面我們給出其對(duì)應(yīng)的狀態(tài)遷移圖，如圖3所示，遷移弧上有兩部分內(nèi)容：一個(gè)標(biāo)識(shí)遷移動(dòng)作，另一個(gè)標(biāo)識(shí)該動(dòng)作持續(xù)的時(shí)間。

要驗(yàn)證的有效性約束為：訂單通過審核后，在一周內(nèi)必須要簽署合同，否則訂單失效。其對(duì)應(yīng)的時(shí)序邏輯描述如下：

將SMV語(yǔ)言描述的采購(gòu)系統(tǒng)模型和有效性約束輸入SMV后的系統(tǒng)主界面如圖4所示。在該界面中已經(jīng)打開了模型文件，點(diǎn)擊主界面Prop菜單中的Verify all來驗(yàn)證有效性約束，驗(yàn)證結(jié)果如圖5所示。由圖5可知，驗(yàn)證結(jié)果為false，即該模型未滿足此有效性約束。從狀態(tài)跟蹤結(jié)果來看，工作流系統(tǒng)可能處于這樣一種狀態(tài)：當(dāng)系統(tǒng)時(shí)鐘運(yùn)行到5個(gè)時(shí)間單位時(shí)，訂單審核完畢，此時(shí)lc[2]為3個(gè)時(shí)鐘單位；當(dāng)系統(tǒng)時(shí)鐘運(yùn)行到13個(gè)時(shí)鐘單位時(shí)，lc[5]為0，即開始執(zhí)行簽署合同，而此時(shí)lc[2]為11個(gè)時(shí)間單位，lc[2]-3〉7，故有效性約束不滿足。

6.結(jié)束語(yǔ)

隨著工作流系統(tǒng)的應(yīng)用越來越廣泛，工作流系統(tǒng)中事務(wù)的時(shí)間有效性的問題越來越突出。在工作流系統(tǒng)中，如何保證恰當(dāng)?shù)娜嗽谇‘?dāng)?shù)臅r(shí)間完成恰當(dāng)?shù)娜蝿?wù)已成為限制工作流系統(tǒng)應(yīng)用推廣的關(guān)鍵問題。本文探討了如何利用時(shí)序邏輯來控制工作流系統(tǒng)中信息的有效性。在實(shí)際系統(tǒng)中，可以采用時(shí)序邏輯來控制時(shí)間有效性。此外，本文還利用模型檢測(cè)給出了有效性的驗(yàn)證方法，探討了模型檢測(cè)在工作流系統(tǒng)中的應(yīng)用，實(shí)驗(yàn)證明該方法是有效的。

參考文獻(xiàn)：

[1]李慧芳，范玉順.工作流系統(tǒng)時(shí)間管理[J].軟件學(xué)報(bào)，2002，13(4)：1-8.

[2]Edmund M，Clarke J，Orna G，Doron AP.Model Checking.Cambridge：MIT Press，2001.

[3]Eder J.，Panagos E.，Rabinovich M..Time Constraints in WorkflowSystems[C].In：Proc.11thConferenceonAdvanced Information Systems Engineering，Heidelberg，Germany，1999，1-14.

[4]林惠民，張文輝.模型檢測(cè)：理論、方法和應(yīng)用[J].軟件學(xué)報(bào)，2002，30(12)：1907-1912.

[5]McMillan KL.The SMV language.2001.http：//www.cs.cmu.edu/～modelcheck/smv.html.

[6]范玉順.工作流管理技術(shù)基礎(chǔ)[M].北京：清華大學(xué)出版社，2001.

[7]閆志華，李成，鄭艷萍.工作流模型檢測(cè)研究[J].計(jì)算機(jī)應(yīng)用，2007，27(6)：1448-1451.

[8]王遠(yuǎn)，范玉順.工作流時(shí)序約束模型分析與驗(yàn)證方法[J].軟件學(xué)報(bào)，2007，18(9)：2153-2161.

[9]Eder J.，Panagos E.，Pozewaunig H.，Rabinovich M..Time Management in Workflow Systems.In：Abramowicz W，Orlowska M E，BIS’993rdInternational Conference on Business Information Systems，Heidelberg：Springer Verlag London Berlin，1999：265-280.