協同工作流過程模型的時間機制研究

蔣國銀,劉行軍

(湖北經濟學院 信息管理學院,湖北 武漢 430205)

●模型研究

協同工作流過程模型的時間機制研究

蔣國銀,劉行軍

(湖北經濟學院 信息管理學院,湖北 武漢 430205)

時間機制是工作流過程模型的一個關鍵部分,開展時間機制研究,對于增強工作流過程模型的柔性和提高企業競爭力具有重要意義。文章通過總結當前關于工作流過程模型的時間約束機制研究工作的不足,基于時間約束的過程模型,探討了自動和手動觸發實例的時間約束變量設定方法,簡單討論了不同時區下時間映射方法,并輔以算例解釋,為分布式環境下企業工作流過程模型應用提供了方法指導。

工作流過程模型;時間約束機制;時區

一、引 言

隨著網絡和信息技術的發展,企業之間的競爭日益激烈,提升核心競爭力和敏捷性成為企業當前的迫切任務。作為提高核心競爭力的主要手段,并行工程、經營過程重組以及敏捷制造工程等管理思想對企業發展起著重要的作用,而這些管理方法的核心思想在于對流程的管理或改造,需要工作流管理系統的支持。

工作流過程模型是工作流管理系統的核心。現代組織的信息環境的動態性、分布性、異構性和自治性的特征日益明顯,傳統的工作流模型缺乏對動態變化所必須的柔性支持[1],時間成為影響流程運行和資源分配的關鍵因素,具有時間約束描述功能的時間工作流過程模型成為當前研究的重點。當前對時間約束研究工作主要有:

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

(2)時間區間約束[4,5]:為每個活動設置最早和持續約束時間,活動的執行應在約束時間內,否則為異常,若活動時間約束為不確定變量,可對開始時間和結束時間分別用時間區間描述[6],也可能用模糊量進行描述[7];

(3)時間段約束[8]:對工作流程中任意兩個活動之間分配一時間段或時間常量,而活動正常執行期間應在該時間段或時間常量內;

(4)超級時間約束[9]:在前面兩類約束基礎上,將流程中時間約束分為建立和執行時兩類,為分布于不同時區業務過程建立在不同的時間軸,其中一個作為參考軸,當涉及與時間有關的業務過程時,將其他軸的時間映射至參考坐標軸;

(5)擴展時間約束:超級時間約束考慮了時區約束問題,但只是基于同一流程的時間約束研究,沒有考慮并行流程時間約束和同一流程的多個實例的時間約束問題。文獻[10]定義了一類規則,用于描述同一流程的時間約束和不同流程時間約束問題,但該類規則應用前提為流程已知,流程實例間的時間約束在運行前預先靜態設定,而這些設定值并非通過一定的計算機制動態求得,通常靠人為的經驗估計,當流程發生改變,所有的流程的時間約束參數得重新手工變動,針對動態的流程運行環境,這種靜態設定方法顯得尤為不便和不科學,所以動態靈活地設定約束時間具有重要意義。

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

本文以擴展的 Petri網為例,探討過程模型的時間約束機制。先設計過程模型的時間機制,然后詳述相關時間參數的設定方法和分布環境下的時間調準方法,并輔以算例進行說明。

二、基于時間約束機制的工作流過程模型

工作流過程建模方法有很多,相關的研究工作也很多,以擴展的 Petri網為例,探討過程模型的時間約束機制。

定義:擴展對象網XOPN=(OPS,R,C,FT,I,O,M0),其中:

(1)OPS為一系列對象庫所組成的對象網系統;R活動變遷集合;C為顏色托肯集合;I是連接從對象到擁有顏色托肯變遷之間的弧的轉移函數;O是連接從擁有顏色托肯變遷到對象之間的弧的轉移函數;M0為模型的初始標志。對于 OPS、R、C、I和 O的詳細定義參閱文[11]。

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

Q+為正實數, INT為變遷的靜態觸發時間,即變遷的服務時間,通常用期望服務時間來表示;DWT為變遷的觸發等待時間,即變遷準備觸發到變遷觸發的時間,其值為相對值,即相對于變遷準備觸發時間點;EWT為變遷的期望等待時間,由排隊理論計算得到。

三、時間約束參數的設定與調準

(一)時間參數設定

對于工作流過程建模,其流程的運轉有兩種方式,即系統自動觸發運作,如產品信息處理流程中的產品信息管理類[11],由系統自動觸發處理;還有一種是手工觸發處理,如總工程師審批類。對于不同的觸發方式,其時間參數的設定方法將不同。下文將對這兩種觸發方式的流程實例進行參數設定進行分別探討。

1.自動處理實例時間參數設定

由于面向對象的特點,自動處理機制可以產生多個實例,即相當于由多個人工去執行或處理該實例,當有多個實例同時到達某一流程節點處,系統將產生多個處理機制分別處理各個實例,不存在等待現象,這種服務方式相當于排隊理論中無窮多個服務臺情況 (M/M/∞)[12],令流程實例的到達率為λ,而系統的服務率為μ,由于是 0等待,則流程實例的 EWT為 0,每個實例的服務時間 INT即為在系統中的平均逗留時間,即:

其平穩分布函數:

故系統擁擠概率小于某一確定值α時 (α為常數),其系統自動處理機制的個數 n應滿足下式 (n為變量,待求值):

假設流程的實例到達該處理機制的過程為 Poisson過程,其到達率為模擬求得 n,對系統自動處理類進行優化設計,以保證流程實例的正常運行,尤其可以對WebService服務數進行控制。

2.手工處理實例時間參數設定

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

λ,λi為具有優先級別 i的流程實例的到達速率,該流程被執行或被服務時間均服從負指數分布,其服務率為μ,記Wqi,Wsi分別為第 i級流程實例在系統中平均等待時間和平均逗留時間,Ws,1-k為 1,2…k級優先權流程實例在系統中每一個流程實例的平均逗留時間。

根據排隊理論[11],i級流程實例的平均服務時間即為NT,則:

故 i級流程實例的 EWT=Wqi。

不論是自動觸發過程實例還是手工觸發實例,其 DWT為動態等待時間,即為系統實際的等待時間,其值應該小于等于期望時間,即 DWT≤EWT,否則出現異常。

(二)時間參數調準

為了支持全球的業務過程應用,工作流過程模型應用于全球范圍,每個活動可能分布于不同的地理位置,也就是分布于不同時區[9]。傳統的過程模型忽視了流相關時間因素,邏輯序列和時間序列關系,為便于統一時區管理,可進行時區映射。

1.確定時間參數映射

文獻 [9]給出時區映射方法,參照該文獻方法,引入時間調準準則,將所有的過程活動的時間約束映射至同一時區上。

記 axisk(k∈[1,n])為時區坐標軸,axisk(i)為活動 Ai的時間軸,時區差異函數 TD(axisi,axisj)為時間軸 axisi和時間軸 axisj的時間差,時區映射函數 T M(,axisj)為將屬于時區軸 axisi的時間 timei映射到時間軸 axisj的時間值。

在過程模型中,每一個活動的所有關于時間約束值都屬于一個具體的時區,選定一個時區參考軸 axisi,利用時區映射函數將每個時間值映射至參考時區軸,圖 1中,活動 B在活動A之后執行,axisi為參考時間軸,活動A為處于時間軸axisi上,則不需調準,而活動 B的一個時間參數 timej(1)在時間軸 axisj上,則需調準,將其調準至參考軸上的 timei(2)處,則有:

timei(2)=T M(,axisi)

圖1 確定時間映射

2.模糊時間參數映射

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

圖2 模糊時間映射

四、結束語

在基于時間機制的工作流過程模型基礎上,探討了時間參數的約束問題。針對依靠設備和程序自動觸發實例,探討了實例排隊機理,得到系統平均逗留時間和服務臺數,而對手工觸發實例,也探討其各實例平均等待時間。為解決不同時區時間映射問題,初步分析時間軸映射方法,但略顯粗糙,尤其是當實例出現異常時的時間同步、不同時區活動交互作用時的時間同步等問題還需深入探討。

文中提出的工作流過程模型的時間約束機制,有助于并行流程和同一流程的不同實例之間的時間管理,有效的解決了流程實例的資源分配和資源競爭問題,通過時間調準機制,使過程模型能很好的應用到分布式企業的應用環境中,具有現實意義。

[1]李慧芳,范玉順.工作流系統時間管理 [J].軟件學報,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]李煒,曾廣周,王曉琳.一種基于時間 Petri網的工作流模型 [J].軟件學報,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]鄧水光,吳朝暉,李瑩,等.一種網格工作流的時間管理方法 [J].計算機集成制造系統,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]杜栓柱,譚建榮,陸國棟.一個基于 T WF-net的擴展時間工作流模型及其應用 [J].計算機研究與發展2003,40(4):521-530.

[11]蔣國銀,何躍.基于高級對象 Petri網的工作流過程建模研究 [J].系統工程理論與實踐,2005,25(3):86-97.

[12]陸傳賚.排隊論 [M].北京:北京郵電學院出版社,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

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

[責任編輯:張 青 ]