蔣國(guó)銀,劉行軍

(湖北經(jīng)濟(jì)學(xué)院 信息管理學(xué)院,湖北 武漢 430205)

●模型研究

協(xié)同工作流過程模型的時(shí)間機(jī)制研究

蔣國(guó)銀,劉行軍

(湖北經(jīng)濟(jì)學(xué)院 信息管理學(xué)院,湖北 武漢 430205)

時(shí)間機(jī)制是工作流過程模型的一個(gè)關(guān)鍵部分,開展時(shí)間機(jī)制研究,對(duì)于增強(qiáng)工作流過程模型的柔性和提高企業(yè)競(jìng)爭(zhēng)力具有重要意義。文章通過總結(jié)當(dāng)前關(guān)于工作流過程模型的時(shí)間約束機(jī)制研究工作的不足,基于時(shí)間約束的過程模型,探討了自動(dòng)和手動(dòng)觸發(fā)實(shí)例的時(shí)間約束變量設(shè)定方法,簡(jiǎn)單討論了不同時(shí)區(qū)下時(shí)間映射方法,并輔以算例解釋,為分布式環(huán)境下企業(yè)工作流過程模型應(yīng)用提供了方法指導(dǎo)。

工作流過程模型;時(shí)間約束機(jī)制;時(shí)區(qū)

一、引 言

隨著網(wǎng)絡(luò)和信息技術(shù)的發(fā)展,企業(yè)之間的競(jìng)爭(zhēng)日益激烈,提升核心競(jìng)爭(zhēng)力和敏捷性成為企業(yè)當(dāng)前的迫切任務(wù)。作為提高核心競(jìng)爭(zhēng)力的主要手段,并行工程、經(jīng)營(yíng)過程重組以及敏捷制造工程等管理思想對(duì)企業(yè)發(fā)展起著重要的作用,而這些管理方法的核心思想在于對(duì)流程的管理或改造,需要工作流管理系統(tǒng)的支持。

工作流過程模型是工作流管理系統(tǒng)的核心?，F(xiàn)代組織的信息環(huán)境的動(dòng)態(tài)性、分布性、異構(gòu)性和自治性的特征日益明顯,傳統(tǒng)的工作流模型缺乏對(duì)動(dòng)態(tài)變化所必須的柔性支持[1],時(shí)間成為影響流程運(yùn)行和資源分配的關(guān)鍵因素,具有時(shí)間約束描述功能的時(shí)間工作流過程模型成為當(dāng)前研究的重點(diǎn)。當(dāng)前對(duì)時(shí)間約束研究工作主要有:

(1)關(guān)鍵路徑約束[2-3]:通過相關(guān)算法找出工作流程的關(guān)鍵路徑,對(duì)關(guān)鍵路徑最大完成時(shí)間進(jìn)行估算,并以此時(shí)間控制其他路徑任務(wù)執(zhí)行時(shí)間;

(2)時(shí)間區(qū)間約束[4,5]:為每個(gè)活動(dòng)設(shè)置最早和持續(xù)約束時(shí)間,活動(dòng)的執(zhí)行應(yīng)在約束時(shí)間內(nèi),否則為異常,若活動(dòng)時(shí)間約束為不確定變量,可對(duì)開始時(shí)間和結(jié)束時(shí)間分別用時(shí)間區(qū)間描述[6],也可能用模糊量進(jìn)行描述[7];

(3)時(shí)間段約束[8]:對(duì)工作流程中任意兩個(gè)活動(dòng)之間分配一時(shí)間段或時(shí)間常量,而活動(dòng)正常執(zhí)行期間應(yīng)在該時(shí)間段或時(shí)間常量?jī)?nèi);

(4)超級(jí)時(shí)間約束[9]:在前面兩類約束基礎(chǔ)上,將流程中時(shí)間約束分為建立和執(zhí)行時(shí)兩類,為分布于不同時(shí)區(qū)業(yè)務(wù)過程建立在不同的時(shí)間軸,其中一個(gè)作為參考軸,當(dāng)涉及與時(shí)間有關(guān)的業(yè)務(wù)過程時(shí),將其他軸的時(shí)間映射至參考坐標(biāo)軸;

(5)擴(kuò)展時(shí)間約束:超級(jí)時(shí)間約束考慮了時(shí)區(qū)約束問題,但只是基于同一流程的時(shí)間約束研究,沒有考慮并行流程時(shí)間約束和同一流程的多個(gè)實(shí)例的時(shí)間約束問題。文獻(xiàn)[10]定義了一類規(guī)則,用于描述同一流程的時(shí)間約束和不同流程時(shí)間約束問題,但該類規(guī)則應(yīng)用前提為流程已知,流程實(shí)例間的時(shí)間約束在運(yùn)行前預(yù)先靜態(tài)設(shè)定,而這些設(shè)定值并非通過一定的計(jì)算機(jī)制動(dòng)態(tài)求得,通?？咳藶榈慕?jīng)驗(yàn)估計(jì),當(dāng)流程發(fā)生改變,所有的流程的時(shí)間約束參數(shù)得重新手工變動(dòng),針對(duì)動(dòng)態(tài)的流程運(yùn)行環(huán)境,這種靜態(tài)設(shè)定方法顯得尤為不便和不科學(xué),所以動(dòng)態(tài)靈活地設(shè)定約束時(shí)間具有重要意義。

在業(yè)務(wù)過程的實(shí)例中,不同的實(shí)例,其優(yōu)先級(jí)別不同,在系統(tǒng)中逗留的時(shí)間也各異,正是這種差異,使得業(yè)務(wù)過程的邏輯及實(shí)例的資源分配變得愈為復(fù)雜,尤其是在這種環(huán)境下的資源分配問題,沒有得到很好的解決。當(dāng)前的研究工作均考慮了過程的時(shí)間屬性,都從靜態(tài)的角度出發(fā)考慮了時(shí)間的影響,設(shè)定了變遷的靜態(tài)觸發(fā)時(shí)間,即設(shè)定了觸發(fā)時(shí)間的上下限,但沒有探討上下限如何設(shè)置;討論了先進(jìn)先出的排隊(duì)機(jī)制,即靜態(tài)的考慮了不同流程按先進(jìn)先出 (FIFO)的規(guī)則進(jìn)行資源分配,事實(shí)上,由于同一流程的不同實(shí)例和不同的流程,其優(yōu)先級(jí)別不盡相同,對(duì)于高優(yōu)先級(jí)別的流程,有可能終止當(dāng)前流程的服務(wù)或插隊(duì)服務(wù),所以,對(duì)過程的動(dòng)態(tài)特性還需考慮。

本文以擴(kuò)展的 Petri網(wǎng)為例,探討過程模型的時(shí)間約束機(jī)制。先設(shè)計(jì)過程模型的時(shí)間機(jī)制,然后詳述相關(guān)時(shí)間參數(shù)的設(shè)定方法和分布環(huán)境下的時(shí)間調(diào)準(zhǔn)方法,并輔以算例進(jìn)行說明。

二、基于時(shí)間約束機(jī)制的工作流過程模型

工作流過程建模方法有很多,相關(guān)的研究工作也很多,以擴(kuò)展的 Petri網(wǎng)為例,探討過程模型的時(shí)間約束機(jī)制。

定義:擴(kuò)展對(duì)象網(wǎng)XOPN=(OPS,R,C,FT,I,O,M0),其中:

(1)OPS為一系列對(duì)象庫(kù)所組成的對(duì)象網(wǎng)系統(tǒng);R活動(dòng)變遷集合;C為顏色托肯集合;I是連接從對(duì)象到擁有顏色托肯變遷之間的弧的轉(zhuǎn)移函數(shù);O是連接從擁有顏色托肯變遷到對(duì)象之間的弧的轉(zhuǎn)移函數(shù);M0為模型的初始標(biāo)志。對(duì)于 OPS、R、C、I和 O的詳細(xì)定義參閱文[11]。

(2)FT=FI∪FD∪FE,其中:

Q+為正實(shí)數(shù), INT為變遷的靜態(tài)觸發(fā)時(shí)間,即變遷的服務(wù)時(shí)間,通常用期望服務(wù)時(shí)間來表示;DWT為變遷的觸發(fā)等待時(shí)間,即變遷準(zhǔn)備觸發(fā)到變遷觸發(fā)的時(shí)間,其值為相對(duì)值,即相對(duì)于變遷準(zhǔn)備觸發(fā)時(shí)間點(diǎn);EWT為變遷的期望等待時(shí)間,由排隊(duì)理論計(jì)算得到。

三、時(shí)間約束參數(shù)的設(shè)定與調(diào)準(zhǔn)

(一)時(shí)間參數(shù)設(shè)定

對(duì)于工作流過程建模,其流程的運(yùn)轉(zhuǎn)有兩種方式,即系統(tǒng)自動(dòng)觸發(fā)運(yùn)作,如產(chǎn)品信息處理流程中的產(chǎn)品信息管理類[11],由系統(tǒng)自動(dòng)觸發(fā)處理;還有一種是手工觸發(fā)處理,如總工程師審批類。對(duì)于不同的觸發(fā)方式,其時(shí)間參數(shù)的設(shè)定方法將不同。下文將對(duì)這兩種觸發(fā)方式的流程實(shí)例進(jìn)行參數(shù)設(shè)定進(jìn)行分別探討。

1.自動(dòng)處理實(shí)例時(shí)間參數(shù)設(shè)定

由于面向?qū)ο蟮奶攸c(diǎn),自動(dòng)處理機(jī)制可以產(chǎn)生多個(gè)實(shí)例,即相當(dāng)于由多個(gè)人工去執(zhí)行或處理該實(shí)例,當(dāng)有多個(gè)實(shí)例同時(shí)到達(dá)某一流程節(jié)點(diǎn)處,系統(tǒng)將產(chǎn)生多個(gè)處理機(jī)制分別處理各個(gè)實(shí)例,不存在等待現(xiàn)象,這種服務(wù)方式相當(dāng)于排隊(duì)理論中無窮多個(gè)服務(wù)臺(tái)情況 (M/M/∞)[12],令流程實(shí)例的到達(dá)率為λ,而系統(tǒng)的服務(wù)率為μ,由于是 0等待,則流程實(shí)例的 EWT為 0,每個(gè)實(shí)例的服務(wù)時(shí)間 INT即為在系統(tǒng)中的平均逗留時(shí)間,即:

其平穩(wěn)分布函數(shù):

故系統(tǒng)擁擠概率小于某一確定值α?xí)r (α為常數(shù)),其系統(tǒng)自動(dòng)處理機(jī)制的個(gè)數(shù) n應(yīng)滿足下式 (n為變量,待求值):

假設(shè)流程的實(shí)例到達(dá)該處理機(jī)制的過程為 Poisson過程,其到達(dá)率為模擬求得 n,對(duì)系統(tǒng)自動(dòng)處理類進(jìn)行優(yōu)化設(shè)計(jì),以保證流程實(shí)例的正常運(yùn)行,尤其可以對(duì)WebService服務(wù)數(shù)進(jìn)行控制。

2.手工處理實(shí)例時(shí)間參數(shù)設(shè)定

一般情況,該實(shí)例由一個(gè)人或一個(gè)單位去處理,故其服務(wù)模式為單服務(wù)機(jī)制,又由于不同實(shí)例和不同的流程可能具有不同的優(yōu)先級(jí)別,在使用資源時(shí)的時(shí)間順序也可能不相同,因此依據(jù)具有優(yōu)先級(jí)別的強(qiáng)制服務(wù)排隊(duì)理論對(duì)流程的時(shí)間參數(shù)進(jìn)行設(shè)定,該方法也包括先來先服務(wù) (FIFO)的服務(wù)思想 (所有流程實(shí)例的優(yōu)先級(jí)別相同,則按先來先服務(wù)的思想執(zhí)行)。

λ,λi為具有優(yōu)先級(jí)別 i的流程實(shí)例的到達(dá)速率,該流程被執(zhí)行或被服務(wù)時(shí)間均服從負(fù)指數(shù)分布,其服務(wù)率為μ,記Wqi,Wsi分別為第 i級(jí)流程實(shí)例在系統(tǒng)中平均等待時(shí)間和平均逗留時(shí)間,Ws,1-k為 1,2…k級(jí)優(yōu)先權(quán)流程實(shí)例在系統(tǒng)中每一個(gè)流程實(shí)例的平均逗留時(shí)間。

根據(jù)排隊(duì)理論[11],i級(jí)流程實(shí)例的平均服務(wù)時(shí)間即為NT,則:

故 i級(jí)流程實(shí)例的 EWT=Wqi。

不論是自動(dòng)觸發(fā)過程實(shí)例還是手工觸發(fā)實(shí)例,其 DWT為動(dòng)態(tài)等待時(shí)間,即為系統(tǒng)實(shí)際的等待時(shí)間,其值應(yīng)該小于等于期望時(shí)間,即 DWT≤EWT,否則出現(xiàn)異常。

(二)時(shí)間參數(shù)調(diào)準(zhǔn)

為了支持全球的業(yè)務(wù)過程應(yīng)用,工作流過程模型應(yīng)用于全球范圍,每個(gè)活動(dòng)可能分布于不同的地理位置,也就是分布于不同時(shí)區(qū)[9]。傳統(tǒng)的過程模型忽視了流相關(guān)時(shí)間因素,邏輯序列和時(shí)間序列關(guān)系,為便于統(tǒng)一時(shí)區(qū)管理,可進(jìn)行時(shí)區(qū)映射。

1.確定時(shí)間參數(shù)映射

文獻(xiàn) [9]給出時(shí)區(qū)映射方法,參照該文獻(xiàn)方法,引入時(shí)間調(diào)準(zhǔn)準(zhǔn)則,將所有的過程活動(dòng)的時(shí)間約束映射至同一時(shí)區(qū)上。

記 axisk(k∈[1,n])為時(shí)區(qū)坐標(biāo)軸,axisk(i)為活動(dòng) Ai的時(shí)間軸,時(shí)區(qū)差異函數(shù) TD(axisi,axisj)為時(shí)間軸 axisi和時(shí)間軸 axisj的時(shí)間差,時(shí)區(qū)映射函數(shù) T M(,axisj)為將屬于時(shí)區(qū)軸 axisi的時(shí)間 timei映射到時(shí)間軸 axisj的時(shí)間值。

在過程模型中,每一個(gè)活動(dòng)的所有關(guān)于時(shí)間約束值都屬于一個(gè)具體的時(shí)區(qū),選定一個(gè)時(shí)區(qū)參考軸 axisi,利用時(shí)區(qū)映射函數(shù)將每個(gè)時(shí)間值映射至參考時(shí)區(qū)軸,圖 1中,活動(dòng) B在活動(dòng)A之后執(zhí)行,axisi為參考時(shí)間軸,活動(dòng)A為處于時(shí)間軸axisi上,則不需調(diào)準(zhǔn),而活動(dòng) B的一個(gè)時(shí)間參數(shù) timej(1)在時(shí)間軸 axisj上,則需調(diào)準(zhǔn),將其調(diào)準(zhǔn)至參考軸上的 timei(2)處,則有:

timei(2)=T M(,axisi)

圖1 確定時(shí)間映射

2.模糊時(shí)間參數(shù)映射

若活動(dòng)在時(shí)間軸上的映射為不確定時(shí)間,此時(shí)活動(dòng)的開始和結(jié)束時(shí)間不確定,可用模糊或者定性方法對(duì)時(shí)間進(jìn)行描述,本文探討模糊時(shí)間。如圖 2所示,活動(dòng) B在活動(dòng) A之后執(zhí)行,將非參考時(shí)間軸上活動(dòng)B的時(shí)間關(guān)系映射至?xí)r間參考軸上,此時(shí),可能出現(xiàn) 3種情形:(1)時(shí)間點(diǎn) d’在時(shí)間點(diǎn)a之前。此時(shí),系統(tǒng)活動(dòng) A和 B之間的邏輯關(guān)系有誤,應(yīng)提示錯(cuò)誤;(2)時(shí)間點(diǎn) c’在時(shí)間點(diǎn) a和 b中間。在圖 c’be區(qū)域,若活動(dòng)A的結(jié)束晚于活動(dòng)A的開始,系統(tǒng)出現(xiàn)邏輯錯(cuò)誤,否則,系統(tǒng)正常工作,可用該三角區(qū)的面積代表出錯(cuò)可能性,面積越大,出現(xiàn)邏輯錯(cuò)誤概率越大,反之,越小;(3)時(shí)間點(diǎn) c’在時(shí)間點(diǎn) b之后。這種情形下系統(tǒng)能正常工作。

圖2 模糊時(shí)間映射

四、結(jié)束語

在基于時(shí)間機(jī)制的工作流過程模型基礎(chǔ)上,探討了時(shí)間參數(shù)的約束問題。針對(duì)依靠設(shè)備和程序自動(dòng)觸發(fā)實(shí)例,探討了實(shí)例排隊(duì)機(jī)理,得到系統(tǒng)平均逗留時(shí)間和服務(wù)臺(tái)數(shù),而對(duì)手工觸發(fā)實(shí)例,也探討其各實(shí)例平均等待時(shí)間。為解決不同時(shí)區(qū)時(shí)間映射問題,初步分析時(shí)間軸映射方法,但略顯粗糙,尤其是當(dāng)實(shí)例出現(xiàn)異常時(shí)的時(shí)間同步、不同時(shí)區(qū)活動(dòng)交互作用時(shí)的時(shí)間同步等問題還需深入探討。

文中提出的工作流過程模型的時(shí)間約束機(jī)制,有助于并行流程和同一流程的不同實(shí)例之間的時(shí)間管理,有效的解決了流程實(shí)例的資源分配和資源競(jìng)爭(zhēng)問題,通過時(shí)間調(diào)準(zhǔn)機(jī)制,使過程模型能很好的應(yīng)用到分布式企業(yè)的應(yīng)用環(huán)境中,具有現(xiàn)實(shí)意義。

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

[2]Jim Hyun Son,Jung Sun Kim,Myoung Ho K im.Extracting the workflow critical path for m the extended well-formed workflow schema[J].Journal of Computer and System Sciences,2005,70:86-106.

[3]Jin Hyun Son,Myoung Ho Kim. Improving the performance of t ime-constrained workflow processing[J]. The Journal of Systems and Software,2001,58:211-219.

[4]李煒,曾廣周,王曉琳.一種基于時(shí)間 Petri網(wǎng)的工作流模型 [J].軟件學(xué)報(bào),2002,13(8):1666-1671.

[5]HuaiqingWang,Qingtian Zeng.Modeling and Analysis for Workflow Constrainedby Resources and Nondetermined T ime:An Approach Based on PetriNets[J].IEEE Transactions on Systems,Man,and Cybernetics—Part A:Systems and Humans,2008,38(4):802-817。

[6]鄧水光,吳朝暉,李瑩,等.一種網(wǎng)格工作流的時(shí)間管理方法 [J].計(jì)算機(jī)集成制造系統(tǒng),2008,14(2):357-365.

[7]PAN Yan,TANG Yong,TANG Na,et al.A Workflow ModelBased on Fuzzy-timing Petri Nets[C].The 9th International Conference on Computer Supported Cooperative Work in Design Proceedings,2005:541-545.

[8]Marjanovic O,Orlowsk M E.On Modeling and verification of temporal constraints in production workflows[J].Knowledge and Information Systems,1999,1(2):157-192.

[9]Hai Zhuge,To-yat Cheung,Hung-keng Pung.A timed workflow process model[J]. The Journal of Systems and Software,2001,55(3):231-243.

[10]杜栓柱,譚建榮,陸國(guó)棟.一個(gè)基于 T WF-net的擴(kuò)展時(shí)間工作流模型及其應(yīng)用 [J].計(jì)算機(jī)研究與發(fā)展2003,40(4):521-530.

[11]蔣國(guó)銀,何躍.基于高級(jí)對(duì)象 Petri網(wǎng)的工作流過程建模研究 [J].系統(tǒng)工程理論與實(shí)踐,2005,25(3):86-97.

[12]陸傳賚.排隊(duì)論 [M].北京:北京郵電學(xué)院出版社,1994.

Research on T imeM echan ism of CollaborativeW orkflow ProcessM odel

J IANG Guo-yin,L IU Xing-jun
(School of Infor m ation M anagem ent,Hubei University of Econom ics,W uhan430205,China)

Time mechanism is a key part ofworkflow processmodel.Doing related researches for time mechanis m can enhance the flexibility ofworkflow process model and make enterprise more competitive.By concluding the current state of research in time constraint mechanism ofworkflow processmodeling,the workflow processmodel based on timing constraint is put forward,and then,examples are given to explain how to set up variables of timing constrains for manual and automatic workflow instance.Finally,we explore the t ime mappingmethod among different time zone.

workflow processmodel;time constraintmechanism;time zone

F270.7

A

1007—5097(2011)01—0150—03

10.3969/j.issn.1007-5097.2011.01.036

2009—09—20

蔣國(guó)銀 (1976—),男,湖北天門人,講師,博士,研究方向:管理信息系統(tǒng),管理系統(tǒng)模擬;劉行軍 (1974—),男,湖北仙桃人,講師,博士,研究方向:信息管理。

[責(zé)任編輯:張 青 ]