（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）工作流系統(tǒng)中時間建模及其一致性驗證研究.pdf

江蘇人學(xué)碩士學(xué)位論文摘要 摘要 時間管理是工作流管理系統(tǒng)的重要組成部分。企業(yè)應(yīng)用越復(fù)雜，對工作流時 間管理技術(shù)的要求越高。由于時間概念表示、分析的復(fù)雜性，以及缺乏統(tǒng)一的時 間建模規(guī)范與標(biāo)準(zhǔn)，對工作流中的時間信息的有效建模成為當(dāng)前的研究熱點。開 展工作流時間建模及時間管理研究對于豐富工作流建模理論、確保工作流計劃的 高效執(zhí)行和有效實施企業(yè)復(fù)雜應(yīng)用具有重要意義。 工作流模式理論形成之后并沒有進(jìn)一步地突破，只有很少幾種建模方法有意 識地運用了工作流模式來作為重要的設(shè)計準(zhǔn)則。y a w l ( y e ta n o t h e rw o r k f l o w l a n g u a g e ) 工作流語言雖然可以全面地直接支持工作流模式并且具有圖形化、形 式化的優(yōu)點，但是在工作流時間管理方面比較薄弱。另外，傳統(tǒng)的工作流系統(tǒng)因 為缺少適應(yīng)性而備受質(zhì)疑。 本論文針對以上問題，展丌以下方面的研究： 首先，在分析時間約束的基礎(chǔ)上，深入研究工作流模式及其包含的時間信息， 結(jié)合區(qū)間時間表達(dá)方法和點時間表達(dá)方法提出一種工作流模式的時間建模方法， 并將它用于經(jīng)典工作流模式的時間約束建模過程中。 其次，在工作流時間約束網(wǎng)絡(luò)的建立和時間約束一致性驗證兩個方面進(jìn)行了 較為深入的研究。結(jié)合工作流時間約束的表示及其轉(zhuǎn)換給出工作流時問約束網(wǎng)絡(luò) w t c n ( w o r k f l o wt e m p o r a lc o n s t r a i n tn e t w o r k s ) 的定義及其相關(guān)運算。在此基 礎(chǔ)上，基于工作流模式的時間約束分析給出一種w t c n 的建立方案，進(jìn)而使用 時問約束一致性驗證算法完成過程沖突檢測任務(wù)。之后以簽證辦理過程為實例， 給出了具體實現(xiàn)過程和實際運行效果。 最后，針對在過程建模階段無法完全預(yù)定義的業(yè)務(wù)過程，在時間約束概念的 基礎(chǔ)上建立了一種動態(tài)可適應(yīng)的過程建?？蚣?，用以解決動態(tài)修改過程定義時涉 及到的工作流時間約束j 下確性和一致性問題。在這個框架中，執(zhí)行過程可以根據(jù) 特殊需求在流程運行時由直觀的圖形語言定制，而過程時問約束的正確性和一致 性分析則通過時間約束網(wǎng)絡(luò)推理來證明。 關(guān)鍵詞：工作流模式；時間約束建模；y a w l ；時間約束一致性驗證；動態(tài)過程 建模 i 江蘇人學(xué)碩士學(xué)位論文 a b s t r a c t t i m em a n a g e m e n ti sa ni m p o r t a n tp a r to fw o r k f l o wm a n a g e m e n ts y s t e m t h e m o r ec o m p l i c a t e dt h ee n t e r p r i s e a p p l i c a t i o ni s ，t h em o r ep o w e r f u lt h e t i m e m a n a g e m e n tt e c h n o l o g ys h o u l db e e f f e c t i v em o d e l i n go ft i m ei n f o r m a t i o n i n w o r k f l o ws y s t e m si so n eo ft h ec u r r e n tr e s e a r c hh o t s p o t sd u et ot h ec o m p l e x i t yo f e x p r e s s i n ga n da n a l y z i n gt i m en o t i o na n dt h el a c ko fu n i f o r ms p e c i f i c a t i o na n d s t a n d a r do ft i m em o d e l i n g t h er e s e a r c ho nt i m em o d e l i n ga n dt i m em a n a g e m e n ti s s i g n i f i c a n tt oe n r i c ht h et h e o r yo fw o r k f l o wm o d e l i n g ，t oe n s u r et h ee f f i c i e n t e x e c u t i o no fw o r k _ f l o wp l a n sa n dt oa c t u a l i z et h ec o m p l i c a t e de n t e r p r i s ea p p l i c a t i o n e f f e c t i v e l y w o r k f l o wp a t t e mt h e o r yd o e s n tm a k em u c h p r o g r e s sa f t e ri t sf o u n d a t i o n af e w m o d e l i n gm e t h o d su s ew o r 姐o wp a t t e ma sa ni m p o r t a n td e s i g np r i n c i p l ec o n s c i o u s l y y a w lw o r k f l o wl a n g u a g ew h o l l ys u p p o r t sc l a s s i c a lw o r k f l o wp a t t e r n sb u ti t sw e a k i nw o r k f l o wt i m em a n a g e m e n t i na d d i t i o n ，t r a d i t i o n a lw o r k f l o ws y s t e m sa r ed o u b t f u l d u et ot h el a c ko ff l e x i b i l i t y r e s e a r c hb a s e do nt h ep r o b l e m sd e s c r i b e da b o v ea r ea sf o l l o w s f i r s t l y , w o r k f l o wp a t t e r n sa n dt h et i m ei n f o r m a t i o nc o n t a i n e di nt h e mh a v eb e e n d e e p l yr e s e a r c h e db a s e do nt h ea n a l y s i so ft i m ec o n s t r a i n t sa n do n ek i n do ft i m e m o d e l i n gm e t h o dc o m b i n i n gi n t e r v a lt i m ee x p r e s s i o na n dp o i n tt i m ee x p r e s s i o nh a s b e e np r o p o s e dw h i c hh a v et h e nb e e ne m p l o y e di nt h ep r o c e s so f t i m em o d e l i n go ft h e c l a s s i c a lw o r k f l o wp a t t e r n s s e c o n d l y , t h es e t t i n gu po fw o r k f l o wt e m p o r a lc o n s t r a i n tn e t w o r k sa n di t s c o n s i s t e n c yv e r i f i c a t i o nh a v e b e e nd e e p l yr e s e a r c h e di nt h i sp a p e r f i r s t ，t h ed e f i n i t i o n o fw t c n ( w o r k f l o wt e m p o r a lc o n s t r a i n tn e t w o r k s ) a n di t sr e l a t e dc a l c u l a t i o n sa r e g i v e nc o n s i d e r i n g t h e e x p r e s s i o n o fw o r k f l o w t e m p o r a l c o n s t r a i n t sa n di t s t r a n s f o r m a t i o n s e c o n d ，o n ek i n do fw t c ns e t t i n gu pp r o j e c th a sb e e ng i v e nb a s e d o na n a l y z i n gt h et e m p o r a lc o n s t r a i n t so fw o r k f l o wp a t t e r n st od e t e c tt h ec o n f l i c t i o ni n p r o c e s sb yu s i n gt h ea l g o r i t h mo fv e r i f y i n gt h ec o n s i s t e n c yo fw o r l d a o wt e m p o r a l c o n s t r a i n t s t h i r d ，t h ep r o j e c ta b o v eh a sb e e ne m p l o y e dt oy a w lw o r k f i o w m a n a g e m e n ts y s t e ma n dt h ei m p l e m e n tp r o c e s sa n dr u n n i n ge f f e c ta r es h o w na f t e r m a t i nt h ee n d ，o n ek i n do fd y n a m i ca n da d a p t i v ep r o c e s sm o d e l i n gf r a m e w o r kh a s 江蘇大學(xué)預(yù)1 學(xué)位論文 b e e nb r o u g h tu po nt h en o t i o no ft e m p o r a lc o n s t r a i n t st od e a lw i t ht h ep r o c e s s e st h a t c a n tb ep r e d e f i n e dt o t a l l yi nt h ep h a s eo fp r o c e s sm o d e l i n ga n dr e l a t e dv a l i d i t ya n d c o n s i s t e n c yp r o b l e m so fw o r k f l o wt e m p o r a lc o n s t r a i n t si nt h ec o u r s eo fr e v i s i n gt h e p r o c e s sd e f i n i t i o n i nt h i sf r a m e w o r k , i n s t a n c ec u s t o m i z a t i o ni so f f e r e di na ni n t u i t i v e g r a p h i c a ll a n g u a g et om e e ts p e c i f i cr e q u i r e m e n t s ，w h e r ea sa n a l y s i so nt h ec o r r e c t n e s s a n dc o n s i s t e n c yo ft e m p o r a lc o n s t r a i n t so ft h ei n s t a n c et e m p l a t ei sp r o v i d e dt h r o u g h w o r k f l o wt e m p o r a lc o n s t r a i n t sn e t w o r k sr e a s o n i n g k e yw o r d s ：w o r k f l o wp a t t e r n s ，t e m p o r a lc o n s t r a i n t sm o d e l i n g ，y a w l , c o n s i s t e n c y v e r i f i c a t i o no ft e m p o r a lc o n s t r a i n t s ，d y n a m i cp r o c e s sm o d e l i n g 1 1 1 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定， 同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版， 允許論文被查閱和借閱。本人授權(quán)江蘇大學(xué)可以將本學(xué)位論文的全部 內(nèi)容或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃 描等復(fù)制手段保存和匯編本學(xué)位論文。 本學(xué)位論文屬于 保密口，在年解密后適用本授權(quán)書。 不保密酉 學(xué)位論文作者簽名：蘚娟 2 0 0 9 年6 月6 日 指導(dǎo)教師簽 2 0 0 9 年舌月艫日 獨創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨 立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容以外，本 論文不包含任何其他個人或集體己經(jīng)發(fā)表或撰寫過的作品成果。對本 文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。 本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名：薛娟 曰期：2 0 0 9 年石月6 日 江蘇大學(xué)碩士學(xué)位論文第一章緒論 1 1 研究背景及意義 第一章緒論弟一早珀下匕 工作流技術(shù)是實現(xiàn)企業(yè)業(yè)務(wù)流程建模、業(yè)務(wù)流程仿真分析、業(yè)務(wù)流程優(yōu)化、 業(yè)務(wù)流程管理與集成，從而最終實現(xiàn)業(yè)務(wù)流程自動化的核心技術(shù)。至今，雖然已 經(jīng)有不少研究人員從不同的角度開展了工作流管理及其相關(guān)技術(shù)的研究，但是有 關(guān)工作流管理技術(shù)研究和應(yīng)用中的許多關(guān)鍵技術(shù)問題還處于探索階段。 首先，9 0 年代術(shù)期，在軟件領(lǐng)域丌始興起了對模式( p a t t e r n ) 的研究熱潮， 誕生了許多至今還難以超越的著作( e r i cg a m m a 等人合著的設(shè)計模式等) 。 在這股熱潮的影響下，a a l s t 等人率先開始研究工作流領(lǐng)域的模式，并在2 0 0 2 年 初步形成了完整的“工作流模式( w o r k f l o wp a t t e r n s ) 理論【1 】1 2 11 3 】【4 】。此后，對 工作流領(lǐng)域的模式研究不斷地拓展到控制流以外的新的問題域，比如“工作流資 源模式 ( w o r k f l o wr e s o u r c ep a t t e r n s ) 、“工作流數(shù)據(jù)模式 ( w o r k f l o wd a t a p a t t e r n s ) 、“工作流異常模式( w o r k _ f l o we x c e p t i o np a t t e r n s ) 等【5 】 6 1 【7 】1 8 】。但是 工作流模式( 控制流模式) 本身的研究并沒有進(jìn)一步地突破，而是作為一種“成 熟 手段被廣泛地運用。而且國內(nèi)目前很少有工作流模式的相關(guān)中文資料。 其次，所有的業(yè)務(wù)流程都存在于一個時間環(huán)境中，且?guī)в袝r問約束，一個業(yè) 務(wù)流程是否能成功執(zhí)行往往依賴于其所含活動的執(zhí)行是否符合約定的同步關(guān)系。 在某些業(yè)務(wù)流程中，任何時間約束方面的背離將導(dǎo)致額外的支出、危險，甚至是 違法的。例如法律程序、航班調(diào)度和危險品處理。為了適應(yīng)這個重要特征，工作 流系統(tǒng)必須具備業(yè)務(wù)流程時間管理的能力。然而，目前的工作流管理產(chǎn)品還遠(yuǎn)遠(yuǎn) 不能滿足業(yè)務(wù)流程時間管理的需求，缺乏對時間管理的支持是當(dāng)今工作流管理系 統(tǒng)的一個重要不足，也是工作流技術(shù)實施復(fù)雜企業(yè)應(yīng)用的嚴(yán)重局限。工作流系統(tǒng) 中的時間管理仍是一個有待深入研究的開放性問題。 另外，面對動態(tài)的業(yè)務(wù)環(huán)境和不斷變化的需求和目標(biāo)，工作流技術(shù)不斷經(jīng)受 考驗。目前，雖然已經(jīng)提出了不少有意義的工作流模型，并在此基礎(chǔ)上設(shè)計了許 多商品化的工作流管理系統(tǒng)。但從其功能上看，多數(shù)工作流模型基本上是基于“靜 態(tài)”過程定義的，這使得用戶在某些情況下不得不越過工作流管理系統(tǒng)而用其它 江蘇人學(xué)碩上學(xué)位論文 第一章緒論 方法來完成有關(guān)的工作。這一點主要是由于目前已有系統(tǒng)中建立時過程定義與運 行時過程執(zhí)行脫節(jié)，而致使預(yù)定義的過程模型不能很好地反映實際的業(yè)務(wù)流程， 工作流管理系統(tǒng)在應(yīng)用的許多關(guān)鍵特性上無法得到保證。建立動態(tài)、可適應(yīng)的工 作流管理系統(tǒng)是國內(nèi)、國際工作流相關(guān)領(lǐng)域研究的熱點問題【9 1 。但是，這種適應(yīng) 性不能以犧牲過程控制為代價，因為過程控制仍然是過程執(zhí)行技術(shù)的必備條件。 1 2 工作流時間約束的研究現(xiàn)狀及不足 1 2 1 研究現(xiàn)狀 一般來說，工作流模型的研究可分為三個層次：語義層、表示層和分析層。 語義層在概念級上給出了與工作流相關(guān)的定義等；表示層是對工作流的抽象描 述，也即對業(yè)務(wù)流程的抽象描述；分析層又可分為兩個方面，一是邏輯分析，二 是性能分析。其中邏輯分析是驗證模型中活動之間的結(jié)構(gòu)關(guān)系，是否存在邏輯上 的死鎖、不可達(dá)，而性能分析則一般通過對表示層模型仿真或嚴(yán)格的理論分析獲 得與系統(tǒng)性能相關(guān)的量化指標(biāo)，來評估建立的表示層模型是否滿足目標(biāo)需求。 對工作流模型時間約束的研究也可以從上述三個層次展開。下面我們就從這 三個層次介紹工作流模型的時間約束的國內(nèi)外研究現(xiàn)狀。 1 、語義層 工作流的時間約束語義層定義了與業(yè)務(wù)行為相關(guān)的顯式時間約束概念。 e d e r l l o l1 1 1 】基于觸發(fā)活動執(zhí)行的事件，定義了活動的時問下界、時間上界， 另外給出了固定日期對象概念。m a r j a n o v i c l l 2 】定義了有限延遲約束、截止期限約 束和時間距離約束，并引入延遲空間和實例空間，分別對流程的靜態(tài)和動態(tài)時間 約束信息描述。z h u g e 1 3 】顯式定義了與時區(qū)相關(guān)的時問約束，為分布于不同時區(qū) 的活動建立不同的時間軸，其中一個作為參考軸，通過時間映射函數(shù)將其它軸的 時間映射至參考坐標(biāo)軸。王海洋1 1 4 1 定義了擴(kuò)展工作流模型g = ( v ，w ，a ，f ， r ) 中活動的延遲上界、開啟時間、最后完成期限及運行時間概念，以描述g 中 活動之間的關(guān)鍵路徑和模型的關(guān)鍵路徑。 上述研究工作，分別從與業(yè)務(wù)流程相關(guān)的時間間隔、時間延遲、時間期限及 時區(qū)等方面給出了時間工作流中具體定義，以適應(yīng)觸發(fā)活動變遷的事件、活動執(zhí) 2 江蘇大學(xué)碩士學(xué)位論文第一章緒論 行控制及活動執(zhí)行多時區(qū)分布的時間約束描述。 2 、表示層 工作流的時間約束表示層是在考慮時間約束條件下，業(yè)務(wù)流程的抽象表示。 由于工作流必須首先描述一個經(jīng)營過程是怎樣進(jìn)行的，因此一般工作流都從流程 定義入手描述，如流程圖、狀態(tài)圖等，這一類基于有向圖模型的優(yōu)點是直觀、容 易理解。許多研究者同樣基于有向圖方法給出了工作流時間的表示層描述。 e d e r 1 0 】在基本工作流圖中的活動節(jié)點引入時間約束信息，構(gòu)造了賦時工作流 圖。時間p e r t i 網(wǎng)也被用來描述時間工作流。l i n g t l s l x f fw f n e t 1 6 】進(jìn)行擴(kuò)充，加入 時間語義，提出t 、肺一n e t 模型( t i m ew f n e t ) ，對每項活動分配一相對時i 日j 段， 分別表示活動的靜念設(shè)定最早執(zhí)行和最晚執(zhí)行相對時間，任務(wù)實際執(zhí)行期間應(yīng)在 該時間段內(nèi)。當(dāng)流程中活動的服務(wù)請求為泊松( p o i s s n o ) 過程、活動延遲時間 服從指數(shù)分布時，排隊網(wǎng)絡(luò)【1 7 】【1 8 】被用于描述業(yè)務(wù)流程，其網(wǎng)絡(luò)中每一活動節(jié)點 可看作獨立的m m 1 排隊系統(tǒng)。e c a ( e v e n t c o n d i t i o n - a c t i o n ) 規(guī)則描述了觸發(fā) 活動的事件和內(nèi)部條件，因此廣泛用于描述活動的執(zhí)行依賴關(guān)系。胡錦敏【1 9 1 建 立了一種基于e c a 規(guī)則和活動分解的工作流模型。通過重寫方法把e c a 模型變 為觸發(fā)器形式的t a ( t r i g g e r - a c t i o n ) 模型，把事件重寫為事件發(fā)生時間，重寫 后事件表達(dá)式不僅可表達(dá)事件之間的邏輯關(guān)系，而且可表達(dá)與事件相關(guān)的時間約 束。 上述研究工作，分別從流程圖、排隊網(wǎng)絡(luò)、p e r t i 網(wǎng)及e c a 規(guī)則等方面建立 了工作流模型的描述方式，表達(dá)了活動及活動之間的時間約束。由于流程圖不便 于建立數(shù)學(xué)分析模型，排隊網(wǎng)絡(luò)只能適應(yīng)于特定的時間約束，而時間p e r t i 網(wǎng)表 達(dá)具有不完善性【刎，因此，需要研究一種通用的、具有良好數(shù)學(xué)表達(dá)的時間約 束表示方式。 3 、分析層 工作流模型的時間邏輯分析層指時間相關(guān)的計算及時序一致性驗證；性能分 析層主要分析模型的可靠性、任務(wù)處理能力和效率。 ( 1 ) 時間計算 時間計算包括求解流程的靜態(tài)期限及活動間的動態(tài)傳輸延遲、相對時i 、丑j 和絕 對時間轉(zhuǎn)換等。不同的時間表示層所考慮的時間約束不同，因此對應(yīng)著不同的時 3 江蘇人學(xué)碩ij 學(xué)位論文第一章緒論 間計算。e d e r l l o 】將時間計算分為3 個階段：在流程建立階段，將固定同期約束轉(zhuǎn) 化為下界時間距離約束，求得活動的最早最晚完成時間；在流程實例化階段， 將相對時間值轉(zhuǎn)化為絕對時間點；在實例執(zhí)行階段，監(jiān)控前序活動的結(jié)束時間， 重新計算后續(xù)活動的完成時間，以盡早發(fā)現(xiàn)時問錯誤。邢n e t 1 5 】的時間延遲通 過將其結(jié)構(gòu)分解為順序、并行及時問選擇等子結(jié)構(gòu)，根據(jù)線性推理規(guī)則，即可在 線性時間復(fù)雜度內(nèi)求得【2 1 】【2 2 1 。j i n 1 8 】基于排隊網(wǎng)絡(luò)流程實例中活動的平均延遲時 間、平均等待時間，在流程結(jié)構(gòu)( a n d 、o r 及l(fā) o o p ) 的基礎(chǔ)上，給出了用來 計算流程從開始到結(jié)束的平均執(zhí)行時間的算法。胡錦敏【1 9 】引入時間操作函數(shù) t i m p o i n t ( 艫) ，計算時間點矽與相對時間點的差值，差值的單位取決于時間單元。 ( 2 ) 時序一致性驗證 時序一致性驗證是為了實現(xiàn)時問約束工作流的可靠執(zhí)行，驗證流程、活動的 時序一致性，即驗證靜態(tài)設(shè)定時間約束與工作流模型的一致性，以及工作流實例 執(zhí)行中的時問約束滿足性。時序一致性的驗證分為以下3 個方面： 1 ) 相對時間約束一致性驗證：這是一種模型建立階段的靜態(tài)驗證方法?；?于所建立的工作流模型結(jié)構(gòu)，檢查流程模型與時間約束的可能沖突，修改或松弛 不一致的時間約束，為工作流設(shè)計者進(jìn)行時間約束的合理設(shè)定與有效建模提供幫 助。e d e r 1 0 】在模型建立時確定不一致的時間約束，并反復(fù)修改賦時工作流圖，以 確保時間約束的靜態(tài)一致。z h u g e l 2 3 】通過計算活動之間的最長最短時間間隔，給 出了有限延遲時間距離和截止期限約束的一致性驗證規(guī)則。 2 ) 絕對時間約束一致性驗證：這是在模型實例動態(tài)執(zhí)行過程中，基于實例 當(dāng)前狀態(tài)的絕對時間與關(guān)鍵路徑，通過計算關(guān)鍵路徑的執(zhí)行延遲，估算尚未調(diào)度 活動的預(yù)期執(zhí)行時間，從而判斷時序一致性。隨著實例執(zhí)行進(jìn)程的推進(jìn)，即便一 致的期限約束也無法保證它在將來的工作流執(zhí)行中仍然滿足。為此，需要對時間 約束進(jìn)行動態(tài)或多次驗證。e d e r 1 0 1 利用流程定義所描述的時間信息，適時調(diào)度活 動，以尋找最優(yōu)的工作流執(zhí)行資源。z h u g e 2 3 l 引入活動和活動之間流程傳輸?shù)臋z 測點集合c ，通過c 中元素時間點的計算，動態(tài)檢測當(dāng)前及預(yù)測潛在的時問約束 一致性。 3 ) 模型一致性驗證：這是驗汪集成時間約束工作流模型的合理性，模型中 是否存在由于時間約束而導(dǎo)致的死鎖及不可達(dá)。合理的工作流要求它的每一次執(zhí) 4 江蘇大學(xué)碩士學(xué)位論文 第一章緒論 行，都是以整個工作流的一個初始事件為開始，以整個工作流的一個結(jié)束事件為 終止。在這個初始事件發(fā)生前，任何其他事件都不允許發(fā)生，即所有的活動任務(wù) 或者操作都處于未執(zhí)行狀態(tài)；在這個結(jié)束事件發(fā)生后，任何事件都不可能發(fā)生， 即不存在正處于進(jìn)行中的活動任務(wù)或者操作，它為工作流的安全可靠執(zhí)行奠定理 論基礎(chǔ)。l i n g 1 5 】將活動執(zhí)行對時間約束的影響分為兩類，給出了相應(yīng)的修改或擴(kuò) 展規(guī)則，同時，通過分析活動中時間約束接觸情形( c o n t a c ts i t u a t i o n ) ，定義了活 動的時間安全性( t i m e s a f e ) ，并給出了形式化方法以檢測模型錯誤及資源沖突。 羅海濱f 冽從事件平衡的角度推導(dǎo)了合理工作流所具備的必要條件，提出工作流 執(zhí)行歷史的事件平衡定理，并把事件平衡的計算引入工作流模型，用以分析模型 中是否存在可能破壞工作流合理性的結(jié)構(gòu)。 ( 3 ) 性能分析 工作流模型的性能指標(biāo)包括兩個方面：一方面是它的可靠性，即通過分析模 型中不同路徑分支流程的時間耗費及發(fā)生概率，得到模型可正常工作的概率；另 一方面是其處理能力或效率，這可分為3 類指標(biāo)：一類指標(biāo)是各種吞吐率，如模 型在單位時間內(nèi)可以處理的任務(wù)數(shù)；另一類指標(biāo)是各種利用率，即在給定的時問 區(qū)間內(nèi)，各種資源的工作時間與資源的占用時間之比；再一類指標(biāo)是流程執(zhí)行時 間，即流程從開始到結(jié)束之間的時間；對時間工作流來說，由于流程執(zhí)行時間在 模型的分析層即己得到，因此其性能分析只基于前兩類指標(biāo)進(jìn)行。 可靠性評價的關(guān)鍵在于流程對資源的耗費應(yīng)當(dāng)有恰當(dāng)?shù)臄?shù)學(xué)度量。為此， j i n 1 8 】從工作流排隊網(wǎng)的最大關(guān)鍵路徑出發(fā)，基于m m c 分布函數(shù)和密度函數(shù)， 給出了在滿足流程執(zhí)行時間期限條件下，流程中活動的資源占用最少算法 m n s ，由此可計算模型的可靠性；林暉【2 5 1 建立了工作流結(jié)構(gòu)的數(shù)學(xué)模型，提供 了計算系統(tǒng)資源耗費及流程不確定的方法，對包含環(huán)結(jié)構(gòu)的系統(tǒng)，可以實現(xiàn) 對環(huán)的提取，同時給出了模型不可靠概率公式：r ( q ) = b z ) ，其中t 為流程時限，a 為超過時限的流程i 發(fā)生概率。 性能分析方法傳統(tǒng)上采用排隊淪數(shù)學(xué)理論來解決系統(tǒng)單個描述問題。 l ( i m 【御【2 7 1 立足于工作流模型的可伸縮性，建立了l q m ( l a y e r e dq u e u i n gm o d e l ) 性能分析模型，并給出了基于m o l ( m e t h o do f l a y e r s ) 的吞吐率x ：、資源占用 5 江蘇人學(xué)碩士學(xué)位論文第一章緒論 時間艫y 等性能計算公式：林闖 2 8 1 通過分析隨機(jī)p e r t i 網(wǎng)的工作流模型的j 順序、 并行、選擇、循環(huán)4 種基本模型，給出了這4 種基本模型的性能等價公式，通過 這些等價公式，不僅可以對復(fù)雜的系統(tǒng)進(jìn)行性能等價化簡，而且還可以得到性能 參數(shù)的乘積解，最終求出整個模型的性能參數(shù)，如吞吐率、系統(tǒng)中平均任務(wù)數(shù)等。 1 2 2 研究的不足 到目前為止，研究者雖然提出了不少有意義、有見解的時問工作流模型，但 從模型的能力上看，還有一些不足之處： ( 1 ) 語義層缺乏完備的時問約束規(guī)范與標(biāo)準(zhǔn) 工作流管理聯(lián)盟旨在語義層建立工作流術(shù)語使用與規(guī)范之間的一致性，但由 于時間建模是一個新的研究領(lǐng)域，工作流管理聯(lián)盟尚未制定時間約束的規(guī)范與標(biāo) 準(zhǔn)；當(dāng)前的各種時i 、日j 工作流模型中，不同模型的語義層時間約束具有很大的不同 性、局限性，不能完全反映實際業(yè)務(wù)流程中對時間約束的要求。因此，為了支持 表示層中時間約束的描述及其形式化驗證，應(yīng)首先定義完備的、可描述業(yè)務(wù)流程 時間特點的時問約束語義，并且各時間約束語義概念不重疊，每一個都有特定的 含義。 ( 2 ) 表示層缺乏支持各種時間約束、流程演進(jìn)的形式化數(shù)學(xué)模型 時間工作流表示層的核心是流程定義，包括組成流程的基本活動、活動之間 隱式時序關(guān)系、活動及活動之間顯式時問約束和活動的同步協(xié)同約束。目前的各 種工作流模型大多從直觀的感覺出發(fā)，以圖形方式定義工作流程。這種圖形定義 方式實際是面向用戶層，具有直觀、容易理解的優(yōu)點，對用戶而言是比較理想的 方式，但不便于對流程的本質(zhì)特征進(jìn)行形式化描述，從而無法對模型進(jìn)行較深入 的分析和評價。p e t d 網(wǎng)作為一種圖形化和數(shù)學(xué)化建模工具，既具有流程圖和網(wǎng) 絡(luò)圖的可視化描述功能，又具有嚴(yán)格的數(shù)學(xué)描述，被應(yīng)用于時問工作流模型中。 然而，這種應(yīng)用只是局部的，并不能完備地反映業(yè)務(wù)流程中的各種時間特性，使 得p e t r i 網(wǎng)在應(yīng)用于具體業(yè)務(wù)流程時存在限制。 ( 3 ) 分析層缺乏統(tǒng)一的時間約束分析方法 由于工作流建模與分析的復(fù)雜性，現(xiàn)有工作流模型中的時問計算和時序一致 性驗證分析都是針對某一類模型，如流程圖或活動網(wǎng)絡(luò)圖等，而缺乏對基于p e r t i 6 江蘇人學(xué)碩士學(xué)位論文 第一章緒論 網(wǎng)的時間工作流模型分析。另外，目前的時間分析中，要么側(cè)重于時間計算，要 么側(cè)重于時序一致性驗證，缺乏統(tǒng)一的集成分析體系。性能層次的分析，由于一 般采用排隊論數(shù)學(xué)理論來解決系統(tǒng)描述問題，數(shù)學(xué)求解基礎(chǔ)則是m a r k o v 隨機(jī)過 程，它要求每個活動的執(zhí)行延遲時間服從負(fù)指數(shù)分布，不適于一般的活動執(zhí)行時 間延遲分布。 目前存在的上述不足，導(dǎo)致工作流時間約束在語義層、表示層和分析層都不 能完全反映業(yè)務(wù)流程的時間約束。 1 3 論文的研究目標(biāo)及工作內(nèi)容 1 3 1 研究目標(biāo) 針對以上研究背景及研究現(xiàn)狀和不足，提出本文的研究目標(biāo)： 首先，在研究工作流模式及其包含的時間約束的基礎(chǔ)上，提出一種基于區(qū)間 時間表達(dá)方法和點時間表達(dá)方法的工作流模式時間建模方法，并將其用于2 0 種 經(jīng)典的工作流模式的時間約束建模過程中。從工作流時間約束角度進(jìn)一步豐富工 作流模式內(nèi)容，同時為工作流時間約束網(wǎng)絡(luò)的建立打下堅實的基礎(chǔ)。 然后，對工作流時間約束網(wǎng)的建立和工作流時間約束一致性驗證兩個部分進(jìn) 行深入研究，旨在建立一種比較理想的、具有良好數(shù)學(xué)表達(dá)的時間約束表示方式， 在此基礎(chǔ)上給出一種工作流時間約束網(wǎng)絡(luò)的建立方案，并將它應(yīng)用到y(tǒng) a w l 0 0 l 工作流管理系統(tǒng)中，從而彌補y a w l 在時間約束表示和時間約束一致性驗證方 面的缺乏和不足。 最后在工作流時間約束概念上，建立一種動態(tài)可適應(yīng)的過程建模框架，以此 來解決動態(tài)修改過程定義時涉及到的工作流時間約束正確性和一致性問題。 1 3 2 工作內(nèi)容 基于上述研究目標(biāo)，本文的主要工作內(nèi)容包括： l 、通過閱讀大量文獻(xiàn)，對與本文相關(guān)的工作流技術(shù)進(jìn)行了較為深入的研究 和分析，主要包括工作流模式，工作流的時間約束建模和工作流時間管理技術(shù)。 針對這些領(lǐng)域的研究現(xiàn)狀和不足，提出了本文的研究目標(biāo)。 7 江蘇大學(xué)碩士學(xué)位論文第一章緒論 2 、在對工作流模式理論進(jìn)行深入研究的基礎(chǔ)上，回顧了文獻(xiàn)1 1 中提出的2 0 種經(jīng)典的工作流模式，給出了每個工作流模式的解釋和圖例，并對每個工作流模 式進(jìn)行時間語義分析，闡述了工作流模式中包含的工作流時問約束。在此基礎(chǔ)上， 提出一種基于區(qū)間時間表達(dá)方法和點時間表達(dá)方法的工作流模式時間建模方法， 并對2 0 種經(jīng)典的工作流模式進(jìn)行時問約束建模，給出建模實例。 3 、從工作流時問約束網(wǎng)絡(luò)的建立和工作流時間約束一致性驗證兩個方面對 工作流中的時間管理進(jìn)行深入研究。 ( 1 ) 綜合應(yīng)用區(qū)問時間表達(dá)方法和點時間表達(dá)方法，給出一種具有較強表 達(dá)能力的時間約束表示方法。這種方法將時間變量分為點時間變量和區(qū)間時間變 量，將工作流時間約束分為定性時間約束和定量時間約束，這樣就可以全面描述 過程建模中遇到的所有時問對象及時間對象之間的所有時間關(guān)系。然后根據(jù)定量 時問表達(dá)方法，將所有的定性時間約束做定量化處理，最后所有的約束都轉(zhuǎn)化成 點時間二元定量時間約束，便于時間約束的一致性處理。 ( 2 ) 結(jié)合以上時問約束表示方法，給出了工作流時間約束網(wǎng)絡(luò)w t c n 的定 義及其相關(guān)定義和運算。在工作流模式分析的基礎(chǔ)上，給出了一種w t c n 的建 立方案。該方案將工作流時間約束分為結(jié)構(gòu)時間約束和非結(jié)構(gòu)時間約束。首先， 分解出工作流控制結(jié)構(gòu)中包含的工作流模式結(jié)構(gòu)，作為工作流模型的基本結(jié)構(gòu)。 根據(jù)每個基本結(jié)構(gòu)的執(zhí)行路徑，得到工作流模型的所有執(zhí)行路徑。根據(jù)基本結(jié)構(gòu) 的執(zhí)行路徑包含的時l 、日j 約束，得到工作流模型的所有執(zhí)行路徑中的結(jié)構(gòu)時間約 束。然后，在結(jié)構(gòu)時間約束的基礎(chǔ)上，加入工作流模型中的非結(jié)構(gòu)時間約束，包 括定性時間約束和定量時間約束。最后，將所有的時間約束轉(zhuǎn)化為僅包含點時間 變量的二元定量時間約束，從而得到工作流模型的w t c n 。 ( 3 ) 針對y a w l 在工作流時間約束的表示和時間約束一致性驗證方面研究 的不足，將以上方案用于y a w l 的w t c n 的建立和時間約束一致性驗證過程中， 并給出了方案的具體實現(xiàn)以及它在y a w l 系統(tǒng)中的運行效果。 4 、針對在過程建模階段無法完全預(yù)定義的業(yè)務(wù)過程，在時間約束概念的基 礎(chǔ)上建立了一種動態(tài)可適應(yīng)的過程建?？蚣埽⒔Y(jié)合實例描述了這個框架的功能 和執(zhí)行步驟。首先在過程建模階段，根據(jù)業(yè)務(wù)過程的時間約束要求建立業(yè)務(wù)過程 的時f 日j 約束網(wǎng)絡(luò)，并且驗證是否存在結(jié)構(gòu)錯誤。在過程實例運行階段，驗證運行 8 江蘇大學(xué)碩+ 學(xué)位論文第一章緒論 時建立的實例模板中的時間約束與過程建模階段建立的時間約束網(wǎng)絡(luò)是否一致。 應(yīng)用該框架來解決動態(tài)修改過程定義時涉及到的工作流時間約束正確性和一致 性問題。 1 4 論文的組織結(jié)構(gòu) 本文共分六章，各章節(jié)具體安排如下： 第一章緒論 介紹了本文的研究背景以及研究意義，較為全面地介紹了國內(nèi)外的研究現(xiàn) 狀，簡要地介紹了論文的研究內(nèi)容及主要工作和論文的組織結(jié)構(gòu)。 第二章論文相關(guān)技術(shù) 本章首先給出了工作流技術(shù)中的基本知識。在此基礎(chǔ)上著重介紹了工作流模 式理論和y a w l 工作流管理系統(tǒng)相關(guān)知識。 第三章工作流中的時間管理 本章從工作流系統(tǒng)中時間約束的建模、時間約束的執(zhí)行和運行后的數(shù)據(jù)分析 三方面全面概述工作流系統(tǒng)中時間管理的內(nèi)容。 第四章工作流模式的時間建模研究 本章提出一種工作流模式的時間建模方法，并對2 0 種經(jīng)典的工作流模式進(jìn) 行時問約束建模，為第五章時間工作流時i 、日j 約束網(wǎng)絡(luò)的建立打下了堅實的基礎(chǔ)。 第五章工作流時間約束網(wǎng)絡(luò)的建立及其一致性驗證 本章給出一種基于工作流模式分析的工作流時間約束網(wǎng)的建立方案，并將其 應(yīng)用到y(tǒng) a w l 過程模型的時間約束網(wǎng)絡(luò)的建立和一致性驗證過程中。最后給出了 具體實現(xiàn)和運行效果。 第六章基于時間約束的動態(tài)過程建模框架研究 本章針對在過程建模階段無法完全預(yù)定義的業(yè)務(wù)過程，在時間約束概念的基 礎(chǔ)上建立了一種動態(tài)可適應(yīng)的過程建模框架，并通過實例描述了這個框架的功能 和執(zhí)行步驟，并給出了框架性能分析。 第七章總結(jié)與展望 總結(jié)本文的研究工作，根據(jù)自己的研究和體會，指出現(xiàn)有研究工作的局限性 和有待提高和改進(jìn)的方面，確定下一步研究工作的重點及方法。 9 江蘇人學(xué)顧i j 學(xué)位論文第一二章論文相關(guān)技術(shù) 2 1 工作流技術(shù)簡介 第二章相關(guān)技術(shù) 工作流技術(shù)的概念起源于辦公自動化和企業(yè)生產(chǎn)過程領(lǐng)域。它是針對r 常工 作中具有固定程序的活動而提出的一個概念。目的是通過將工作分解成定義良好 的任務(wù)、角色，按照一定的規(guī)則和流程來執(zhí)行這些任務(wù)并對它們進(jìn)行監(jiān)控，達(dá)到 提高辦事效率、降低生產(chǎn)成本、提高企業(yè)生產(chǎn)經(jīng)營管理水平和企業(yè)競爭力的目標(biāo) 3 x l o 工作流技術(shù)是實現(xiàn)企業(yè)業(yè)務(wù)過程建模、業(yè)務(wù)過程仿真分析、業(yè)務(wù)過程優(yōu)化、 業(yè)務(wù)過程管理與集成，從而最終實現(xiàn)業(yè)務(wù)過程的自動化的核心技術(shù) 2 3 1 。對企業(yè) 利用工作流方法進(jìn)行業(yè)務(wù)過程的建模和深入分析不僅可以規(guī)范化企業(yè)的業(yè)務(wù)過 程，發(fā)現(xiàn)業(yè)務(wù)過程中不合理的環(huán)節(jié)，進(jìn)而對企業(yè)的業(yè)務(wù)過程進(jìn)行優(yōu)化重組，而且 所建立的業(yè)務(wù)過程模型本身就是企業(yè)非常重要的知識庫和規(guī)則庫，可以成為指導(dǎo) 企業(yè)實施計算機(jī)管理信息系統(tǒng)的模型。在深入分析企業(yè)需求基礎(chǔ)上建立的企業(yè)業(yè) 務(wù)模型可以在最大程度上提高企業(yè)實施e r p 或者其他管理信息系統(tǒng)的成功率。 所以，大力發(fā)展并推廣工作流技術(shù)對于促進(jìn)我國企業(yè)管理規(guī)范化和信息化有重要 的現(xiàn)實意義【3 2 1 。 2 1 1 工作流的定義和相關(guān)概念 工作流的概念源于生產(chǎn)組織和辦公自動化領(lǐng)域，是針對日常工作中具有固定 程序的活動提出的一個概念，目的是通過將工作分解成定義良好的任務(wù)、角色， 并按照一定的規(guī)則和流程執(zhí)行和監(jiān)控這些任務(wù)，達(dá)到提高辦事效率、降低生產(chǎn)成 本、提高企業(yè)生產(chǎn)經(jīng)營管理水平和企業(yè)競爭力的目的。 1 9 9 3 年，國際工作流管理聯(lián)盟( w o r k f l o wm a n a g e m e n tc o a l i t i o n ，w f m c ) 的成立標(biāo)志著工作流技術(shù)開始進(jìn)入相對成熟的階段。w f m c 給出的工作流定義 是：工作流是一類能夠完全或者部分自動執(zhí)行的經(jīng)營過程，它根據(jù)一系列過程規(guī) 則，使文檔、信息或任務(wù)能夠在不同的執(zhí)行者之問進(jìn)行傳遞與執(zhí)行【3 3 】。 還有許多關(guān)于工作流的不同定義【3 1 1 1 3 4 1 ，這些工作流的定義都是使用非形式 1 0 江蘇人學(xué)碩士學(xué)位論文 第_ 二章論文相關(guān)技術(shù) 化的語言對工作流所進(jìn)行的描述，雖然表達(dá)方式不同，但是基本上都說明了這樣 一個問題，即工作流是經(jīng)營過程的一個計算機(jī)實現(xiàn)，而工作流管理系統(tǒng)則是這一 實現(xiàn)的軟件環(huán)境，并且這些工作流的定義分別反映了經(jīng)營過程如下幾個方面的問 題，即做什么w h a t ( 由哪些活動、任務(wù)組成，也就是結(jié)構(gòu)上的定義) 、怎么做 h o w ( 活動問的執(zhí)行條件、規(guī)則以及所交互的信息，也就是控制流與信息流的定 義l 、什么時間做w h e n ( 工作流的啟動時間、時間約束) 、誰來做m o ( 人或者 計算機(jī)應(yīng)用程序，也就是組織角色的定義) 。 業(yè)務(wù)過程( b u s i n e s sp r o c e s s ) ：為了實現(xiàn)特定業(yè)務(wù)目標(biāo)和策略的一組相互連 接的過程和活動集合。 工作流模型( w o r k f l o wm o d e l ) ：工作流模型是對工作流的抽象表示，也就 是對企業(yè)業(yè)務(wù)過程的抽象表示。工作流模型包括流程的開始和完成條件、構(gòu)成流 程的活動以及進(jìn)行活動間導(dǎo)航的規(guī)則、用戶所需要完成的任務(wù)、可能被調(diào)用的應(yīng) 用、工作流的引用關(guān)系，以及所有與工作流相關(guān)數(shù)據(jù)的定義。工作流模型由4 部分組成：( 1 ) 過程模型：用來定義工作流的過程邏輯。包括組成工作流的所有 活動及活動問的依賴關(guān)系。它是整個工作流模型的基礎(chǔ)與核心。( 2 ) 組織模型： 用來定義企業(yè)人員的組織結(jié)構(gòu)，為過程模型提供“人”的支持。( 3 ) 資源模型： 用來定義企業(yè)資源的組織結(jié)構(gòu)，為企業(yè)人員執(zhí)行工作流提供“物 的支持。( 4 ) 時間模型：主要是用來對業(yè)務(wù)過程的時間約束建模，以對工作流執(zhí)行中時間約束 進(jìn)行監(jiān)控和調(diào)整，以在規(guī)定的時間內(nèi)完成工作流實例或提高工作流的執(zhí)行效率。 活動( a c t i v i t y ) ：工作流中的一個邏輯執(zhí)行步驟。包含的信息有：開始和結(jié) 束條件、可參與的用戶、完成此活動所需的應(yīng)用程序或數(shù)據(jù)以及一些限制條件如 時間上的限制等。 流程定義( p r o c e s sd e f i n i t i o n ) ：業(yè)務(wù)過程的計算機(jī)形式表示，用來支持系統(tǒng) 建模和運行過程的自動化，它定義的是流程運行中涉及到的各種參數(shù)，如業(yè)務(wù)過 程的開始和終止條件、各個工作環(huán)節(jié)及相互之間的控制流動與數(shù)據(jù)流動關(guān)系等。 不同的工作流管理系統(tǒng)( w o r k f l o wm a n a g e m e n ts y s t e m ，w f m s ) 所實現(xiàn)的工作流 模型是各不相同的。在早期的具有工作流管理功能的系統(tǒng)中，這種表示是通過“硬 編碼”的方式完成的，因此導(dǎo)致修改工作流程上的困難。在后來的w f m s 中逐 漸出現(xiàn)了使用有向圖、條件化有向圖p e t r i n e t 、活動模型、語言動作( l a n g u a g e 江蘇人學(xué)碩上學(xué)位論文 第一二章論文相關(guān)技術(shù) a c t s ) 理論、基于約束條件的形式語言文法表示以及基于目標(biāo)的知識表示等。這 些系統(tǒng)一般都提供有一個可視化的業(yè)務(wù)過程建模工具，以使用戶能夠以比較直觀 的方式對實際的業(yè)務(wù)過程模型進(jìn)行建模，并得到相應(yīng)的形式化表示。不同的流程 模型各有其不同的特點，一個好的模型應(yīng)該有比較強的描述能力、易于使用、易 于修改以便能夠適應(yīng)不斷變化的工作環(huán)境的要求。 流程活動實例( p r o c e s s a c t i v i t yi n s t a n c e s ) ：指的足某個工作流流程的一次執(zhí) 行。在實例的執(zhí)行過程中，w f m s 將解釋相應(yīng)的過程定義，生成有關(guān)的活動并根 據(jù)過程定義中的控制規(guī)則協(xié)調(diào)這些活動實例之間的順序關(guān)系，同時根據(jù)數(shù)據(jù)流動 關(guān)系的定義完成活動實例之間的數(shù)據(jù)傳送。一般情況下每一個活動實例都將表現(xiàn) 為一個工作項( w o r k i t e m ) ，它將由某個或某組用戶負(fù)責(zé)完成。因此從用戶的角 度來說實例的執(zhí)行實際上是由用戶調(diào)用相應(yīng)的應(yīng)用程序?qū)λ婕暗哪莻€環(huán)節(jié) 有關(guān)的數(shù)據(jù)進(jìn)行處理，處理完之后由w f m s 根據(jù)相應(yīng)的結(jié)果決定激活后續(xù)的那 個環(huán)節(jié)并生成相應(yīng)的工作項，同時通知與此有關(guān)的那些用戶對之進(jìn)行處理。由此 依次反復(fù)進(jìn)行，直至整個過程的完成。某個用戶所負(fù)責(zé)的所有工作項將構(gòu)成其工 作項列表( w o r kl i s t ) 。那些被稱作是工作流應(yīng)用數(shù)據(jù)的，其中有一部分將同工 作流過程定義一道用于控制工作流的執(zhí)行。這部分?jǐn)?shù)據(jù)一般被稱作是工作流相關(guān) 數(shù)據(jù)。 代理( a g e n t ) ：工作流系統(tǒng)中，一個獨立的處理實體被定義為代理，它由所 包含的個體、團(tuán)隊成員、工具及他們相應(yīng)的職責(zé)所構(gòu)成。在組織模型中代理包括 以下兩種實體：( 1 ) 參與者( a c t o r ) 。一個參與者是個體處理單元，它可以是員 工和自動工具。與參與者相關(guān)的有工作時間表、身體狀況或故障等因素，這些因 素可以綜合確定一個參與者的當(dāng)前狀態(tài)。( 2 ) 組( g r o u p ) 。一個組是參與者的集 合組成，其具有所有參與者的公共特征。 角色