（計算機軟件與理論專業(yè)論文）工作流挖掘與調(diào)度算法研究.pdf

摘要 論文題目： 專 業(yè)： 博士生： 指導教師： 工作流挖掘與調(diào)度算法研究 計算機軟件與理論 顧春琴 常會友教授 摘要 企業(yè)為了在日趨激烈的市場競爭中立于不敗之地，需要不斷優(yōu)化其生產(chǎn)、經(jīng) 營過程，因而對業(yè)務過程的高效組織和管理成為提高企業(yè)效益、增強企業(yè)競爭力 的重要手段。工作流建模作為一種業(yè)務過程的管理技術，為企業(yè)業(yè)務過程的高效 組織和管理提供了解決方案。 工作流挖掘作為一種重要的工作流建模方法，旨在從信息系統(tǒng)的事件日志中 發(fā)現(xiàn)關于業(yè)務流程的結(jié)構化過程，從而避免從空白開始進行既費時又容易出錯的 工作流模型的設計，其研究對于企業(yè)實現(xiàn)業(yè)務流程的建模和再造具有重要的意 義。目前國內(nèi)外，特別是國內(nèi)，對工作流建模的研究主要集中在模型設計方面， 而利用事件日志進行工作流挖掘的研究所見不多。此外工作流時間性能分析和調(diào) 度優(yōu)化也是工作流管理方面的研究熱點。 本論文從啟發(fā)式工作流挖掘算法、智能化工作流挖掘算法兩個方面對工作流 挖掘進行了深入地研究與分析；對工作流時間性能以及工作流調(diào)度優(yōu)化進行了深 入地研究與分析，具體的研究內(nèi)容和創(chuàng)新點如下： ( 1 ) 能解決多種復雜任務的工作流挖掘。為了有效挖掘含有多種復雜任務 的過程模型，對含有循環(huán)任務和重復任務的事件日志進行了研究，提出發(fā)現(xiàn)循環(huán)、 重復和同一任務的啟發(fā)式規(guī)則，并且給出證明；改進了a 算法的關聯(lián)關系定義， 在此基礎上提出了r 算法。實例驗證該算法是有效的，對循環(huán)、重復和同一任務 的判定是正確的。對挖掘出的模型進行仿真分析，仿真結(jié)果表明使用r 算法挖掘 出的模型所產(chǎn)生的日志和原始日志具有邏輯等價性。 ( 2 ) 基于混合自適應遺傳算法的工作流挖掘。為了解決目前工作流挖掘算 法大都采用局部策略因而無法保證最優(yōu)挖掘以及算法對噪聲敏感的問題，提出基 于混合自適應遺傳算法的工作流挖掘算法。該算法與啟發(fā)式算法相比具有更高的 i 中山大學博士學位論文 魯棒性和對噪聲的抗干擾性；與基本遺傳算法相比，該算法能顯著提高解的質(zhì)量 和收斂速度。 ( 3 ) 工作流時間性能分析。工作流性能分析是對工作流進行評價和優(yōu)化的 基礎，時間性能則是衡量工作流性能的一個重要指標。利用概率論中關于服從指 數(shù)分布的隨機變量的分布函數(shù)、密度函數(shù)及數(shù)學期望的基本性質(zhì)，詳細地分析了 組成s p n 模型的串行、并行、選擇和循環(huán)四種基本結(jié)構的平均延遲時間，設計 了通用的s p n 模型平均延遲時間公式。通過對復雜s p n 模型的等效化簡，實現(xiàn) 對工作流時間性能的分析。最后，通過實例驗證了該方法的可行性和有效性。 ( 4 ) 工作流調(diào)度優(yōu)化。為了解決工作流調(diào)度優(yōu)化問題，以q o s 為優(yōu)化目標， 提出了克隆選擇離散粒子群算法，運用該算法進行工作流調(diào)度優(yōu)化研究。該算法 增加了種群的多樣性，提高了算法精確度，加快了算法的收斂速度，克服了離散 粒子群算法早熟收斂和局部極值等問題，在工作流調(diào)度應用中具有良好的性能。 關鍵詞：工作流挖掘；工作流調(diào)度：時間性能；遺傳算法；離散粒子群算法 - i i - a b s t r a c t t i t l e ：r e s e a r c ho nw o r k f l o wm i n i n ga n ds c h e d u l i n ga l g o r i t h m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：c h u n q i ng u s u p e r v i s o r ：p r o f e s s o rh u i y o uc h a n g a b s t r a c t i no r d e rt ow i ni nt h ei n c r e a s i n g l ys e v e r em a r k e t i n gc o m p e t i t i o n , a l le n t e r p r i s e n e e d st oc o n s t a n t l yo p t i m i z et h ep r o d u c t i o na n db u s i n e s sp r o c e s s t h ee f f e c t i v eo r - g a n i z a t i o na n dm a n a g e m e n to fb u s i n e s sp r o c e s si sa ni m p o r t a n ta p p r o a c ht oi m p r o v - i n ge n t e r p r i s eb e n e f i ta n de n h a n c i n ge n t e r p r i s ec o m p e t i t i v e n e s s w o r k f l o wm o d e l i n g i sak i n do ft e c h n o l o g yw h i c hi sc l o s e l ya s s o c i a t e dw i t hb u s i n e s sp r o c e s s i tc a ns u p - p o r tt h ee f f e c t i v eo r g a n i z a t i o na n dm a n a g e m e n to fb u s i n e s sp r o c e s s w o r k _ f l o wm i n i n gi sa l li m p o r t a n tw o r k _ f l o wm o d e l i n gm e t h o d ，w h i c hi su s e dt o d i s c o v e rs t r u c t u r a lp r o c e s so fb u s i n e s sf r o me v e n tl o go fi n f o r m a t i o ns y s t e m w o r k - f l o wm i n i n gc a na v o i dd e s i g n i n gt h ew o r k f l o wm o d e lf r o ms c r a t c h , w h i c hi sac o m - p l i c a t e dt i m e - - c , o n s u m i n gp r o c e s s t h er e s e a r c ho nw o r k f l o wm i n i n gh a si m p o r t a n t s i g n i f i c a n c ef o rt h em o d e l i n ga n dr e e n g i n e e r i n go fb u s i n e s sp r o c e s s d e s p i t et h ei r a - p o r t a n c eo fw o r k f l o wm i n i n g ，t h e r ea r ef e wr e s e a r c hw o r kd o n ei nt h i sa r e a i na d d i - t i o n , w o r k f l o wt i m ep e r f o r m a n c ea n a l y s i sa n dw o r k f l o ws c h e d u l i n go p t i m i z a t i o na r e a l s ot h er e s e a r c hf o c u si nw o r k f l o wm a n a g e m e n t t h i sd i s s e r t a t i o ns t u d i e so nw o r k f l o wm i n i n g ，i n c l u d i n gh e u r i s t i cw o r k f l o w m i n i n ga l g o r i t h m , i n t e l l i g e n tw o r k f l o wm i n i n ga l g o r i t h m i na d d i t i o n , t h i sd i s s e r t a t i o n s t u d i e so nw o r k f l o wt i m ep e r f o r m a n c ea n a l y s i sa n dw o r k f l o ws c h e d u l i n go p t i m i z a t i o n t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r el i s t e da sf o l l o w s ： ( 1 ) i no r d e rt om i n ep r o c e s sf r o me v e n tl o gw i t hc y c l i ct a s k s ，d u p l i c a t et a s k s a n ds a m et a s k s ，a n dt oo p t i m i z ee n t e r p r i s em o d e l i n gm e t h o d ，a ni m p r o v e dm i n i n ga l g o r i t h mc a l l e df - a l g o r i t h mi sp r e s e n t e db a s e do ni m p r o v i n gt h ea - a l g o r i t h m t h e o r d e r i n gr e l a t i o n sb e t w e e nt a s k sa r er e d e f i n e d ；h e u r i s t i cr u l e sa r ep u tf o r w a r df o r i i i - 中山大學博士學位論文 i d e n t i f y i n gc y c l i ct a s k s ，d u p l i c a t et a s k sa n ds a m et a s k sa m o n ge v e n tl o g t h em i n e d w f - n e ti ss i i n u l a t e df o rg e n e r a t i n gr e v e r s e l ye v e n tl o g t h ee q u i v a l e n c eb e t w e e n s i m u l a t e dl o ga n dr a wl o gi sa n a l y z e d t h ev a l i d i t yo fr - a l g o r i t h mi sp r o v e d ( 2 ) c u r r e n tw o r k f l o wm i n i n ga l g o r i t h mu s i n gl o c a ls t r a t e g yc a n te n s u r et h a ta g l o b a l l yo p t i m a lp r o c e s sm o d e li sm i n e d t h ea l g o r i t h mi sa l s os e n s i t i v et on o i s e t o s o l v et h ep r o b l e m s ，ah y b r i da d a p t i v eg e n e t i ca l g o r i t h m ( h a g a ) i sp r o p o s e d t h e s i m u l a t i o nt e s t i n gr e s u l t sd e m o n s t r a t et h a tt h en e wa l g o r i t h mh a sn o i s ei m m u n i t ya n d i sm o g er o b u s tt h a naa l g o r i t h m , a n dt h a ti tc a nf i n db e t t e rs o l u t i o na n dc o n v e r g e f a s t e rt h a nt h es i m p l eg e n e t i ca l g o r i t h m ( s g a ) e m p l o y i n g g e n e r a lg e n e t i cs t r a t e g y ( 3 ) i no r d e rt oi m p r o v i n gt h ee f f i c i e n to r g a n i z a t i o na n dm a n a g e m e n t ，w o r k f l o w t i m ep e r f o r m a n c ea n a l y s i si sr e a l i z e db ym e a n so fe q u i v a l e n ts i m p l i f i c a t i o nt oc o m - p l e xs p nm o d e l s u s i n gt h eb a s i cp r o p e r t i e so fp r o b a b i l i t yt h e o r ya b o u td i s t r i b u t i o n f u n c t i o n , d e n s i t yf ：i l n c t i o na n dm a t h e m a t i c a le x p e c t a t i o no fr a n d o mv a r i a b l ea g r e e i n g w i t he x p o n e n t i a ld i s t r i b u t i o n , a v e r a g ed e l a yt i m ei sc a l c u l a t e dt oa n a l y z et h ea v e r a g e d e l a yt i m eo fs e r i a l ，p a r a l l e l , s e l e c t i v ea n dc y c l i cs t r u c t u r e ag e n e r a lm e t h o do fa l i a - l y z i n ga v e r a g ed e l a yt i m ei sp r o p o s e d w o r k f l o wt i m ep e r f o r m a n c ea n a l y s i si sr e a l - - i z e db ym e a n so fe q u i v a l e n ts i m p l i f i c a t i o nt oc o m p l e xs p nm o d e l s ( 4 ) i no r d e rt os o l v et h ep r o b l e mo fo o sc o n s t r a i n e dw o r k f l o ws c h e d u l i n go p t i - m i z a t i o n , t h ed i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mb a s e do nc l o n a ls e l e c t i o n i sg i v e n t h ea l g o r i t h mc a ni n c r e a s et h es w a r m sd i v e r s i t ya n dp r e c i s i o n , s p e e du p c o n v e r g e n c es p e e da n do v e r c o m ep r e m a t u r ec o n v e r g e n c ea n dl o c a lo p t i m u m t h e p e r f o r m a n c eo fo u ra l g o r i t h mi sv e r yp r o m i s i n gi nw o r k f l o ws c h e d u l i n ga p p l i c a t i o n k e y w o r d s ：w o r k f l o wm i n i n g ：w o r k f l o ws c h e d u l i n g ：t i m ep e r f o r m a n c e ；g e n e t i c a l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n 。 - - 論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下，獨 立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論 文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本文 的研究作出重要貢獻的個人和集體，均已在文中以明確方式標明。本 人完全意識到本聲明的法律結(jié)果由本人承擔。 學位論文作者簽名：附 日期：加c 1 年6 月g 日 學位論文使用授權聲明 本人完全了解中山大學有關保留、使用學位論文的規(guī)定，即：學 校有權保留學位論文并向國家主管部門或其指定機構送交論文的電 子版和紙質(zhì)版，有權將學位論文用于非贏利目的的少量復制并允許論 文進入學校圖書館、院系資料室被查閱，有權將學位論文的內(nèi)容編入 有關數(shù)據(jù)庫進行檢索，可以采用復印、縮印或其他方法保存學位論文。 學位論文作者繇槲新躲孝虧右 吼葉6 月g 日眺乞寸6 月g 日 第1 章緒論 第1 章緒論 1 1研究背景及意義 計算機支持的協(xié)同工作( c o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k ，c s c w ) 【1 】 是指地域分散的一個群體借助計算機及其網(wǎng)絡技術，共同協(xié)調(diào)與協(xié)作來完成一項 任務。通過建立協(xié)同工作流環(huán)境，可以改善人們的溝通方式，消除人們時間和空 間的距離，節(jié)省工作人員的時間和精力，提高群體工作質(zhì)量和效率。 工作流管理系統(tǒng)作為c s c w 系統(tǒng)的一個分支，是一項發(fā)展迅速的技術，已 成為各種管理信息系統(tǒng)以及辦公自動化系統(tǒng)的核心，在許多企業(yè)中得到了廣泛的 應用。d e l p h ig r o u p 的創(chuàng)始人和主席t h o m a sk o u l o p o u l o s 曾預言工作流管理系統(tǒng) 將最終成為覆蓋各類終端與網(wǎng)絡操作系統(tǒng)之上的業(yè)務操作系統(tǒng)( b u s i n e s so p e r a t i o ns y s t e m ，b o s ) ，將帶來操作系統(tǒng)、信息管理軟件的一次革命，乃至在將 來將應用從企業(yè)延伸到家庭中，成為新時代的家庭信息平臺( f a m i l yi n f o r m a t i o n p l a t f o r m ，f i p ) 2 1 。 工作流技術又是工作流管理系統(tǒng)的核心技術。工作流技術是實現(xiàn)企業(yè)業(yè)務過 程建模、業(yè)務過程仿真分析、業(yè)務過程優(yōu)化、業(yè)務過程管理與集成，從而最終實 現(xiàn)業(yè)務過程自動化的核心技術【3 】o 對企業(yè)利用工作流方法進行業(yè)務過程的建模和 深入分析不僅可以規(guī)范化企業(yè)的業(yè)務過程，發(fā)現(xiàn)業(yè)務流程中不合理的環(huán)節(jié)，進而 對企業(yè)的業(yè)務過程進行優(yōu)化重組，而且所建立的業(yè)務過程模型本身就是企業(yè)非常 重要的知識庫和規(guī)則庫，可以成為指導企業(yè)實施計算機管理信息系統(tǒng)的模型。 工作流建模作為一種業(yè)務過程的管理技術，為企業(yè)業(yè)務過程的高效組織和管 理提供了解決方案。工作流挖掘作為一種重要的工作流建模方法，旨在從信息系 統(tǒng)的事件日志中發(fā)現(xiàn)關于業(yè)務流程的結(jié)構化過程，從而避免了從空白開始進行既 費時又容易出錯的工作流模型的設計，其研究對于企業(yè)實現(xiàn)業(yè)務流程的建模和再 造具有重要的意義。目前國內(nèi)外，特別是國內(nèi)，對工作流建模的研究主要集中在 模型設計方面，而利用事件日志進行工作流挖掘的研究所見不多。 工作流模型的性能分析一般指通過仿真或嚴格的理論分析獲得系統(tǒng)性能的 量化指標，如業(yè)務平均處理時間1 4 1 ，在工作流管理系統(tǒng)中發(fā)揮著重要的作用，可 1 中山大學博士學位論文 定量評價工作流的時間性能。工作流時間性能分析是工作流管理方面的研究熱 點。 工作流調(diào)度優(yōu)化也是目前研究的熱點，合理地調(diào)度服務資源不但可以提高工 作流的運行效率，而且能降低資源的使用成本，提高系統(tǒng)的可靠性。 本論文從啟發(fā)式工作流挖掘算法、智能化工作流挖掘算法兩個方面對工作流 挖掘進行了深入地研究與分析；對工作流時間性能以及工作流調(diào)度優(yōu)化進行了深 入地研究與分析。將本論文研究的理論成果應用到企業(yè)中，有助于企業(yè)在更短時 間內(nèi)生產(chǎn)出成本低、質(zhì)量高的產(chǎn)品，或在更短的時間內(nèi)提供更好的服務，有助于 企業(yè)進行業(yè)務過程改進和優(yōu)化，以提高企業(yè)的市場競爭力，在全球市場競爭中立 于不敗之地。因此，本論文所做的研究具有一定的理論意義和重要的應用價值。 1 2主要研究工作 本論文從工作流挖掘、工作流時間性能分析和工作流調(diào)度三個方面對工作流 相關技術進行了深入地研究。 ( 1 ) 基于啟發(fā)式算法的工作流挖掘 研究與分析現(xiàn)有的工作流挖掘理論、技術和方法。了解到目前對于工作流挖 掘的研究不是很多，并且現(xiàn)有的研究都是只能解決簡單的挖掘問題。 在對工作流挖掘問題進行深入研究的基礎上，提出了新的工作流挖掘算法一 一r 算法。該算法解決了事件日志中含有循環(huán)任務、重復任務以及同一任務的工 作流挖掘問題。 ( 2 ) 基于進化算法的工作流挖掘 研究與分析了遺傳算法的基本理論以及應用現(xiàn)狀。了解到遺傳算法目前應用 的領域非常廣泛，包括工業(yè)、交通業(yè)、經(jīng)濟管理、圖像處理等。而在工作流挖掘 領域的應用，卻所見不多。雖有文獻使用了遺傳算法，但是由于基本遺傳算法具 有早熟或后期收斂緩慢等缺點，不能很好地解決活動多、復雜性高和有噪聲的問 題。 本文深入分析了工作流挖掘問題的模型表示，建立了工作流挖掘問題的數(shù)學 模型，提出使用關聯(lián)矩陣進行染色體編碼，并且根據(jù)挖掘模型與原有日志的符合 - 2 - 第1 章緒論 性定義了染色體的適應值評價函數(shù)。結(jié)合進化過程的分階段性，提出混合自適應 遺傳算法，有效地解決了活動規(guī)模大、含噪聲的工作流挖掘問題。 ( 3 ) 工作流時間性能分析 研究與分析了工作流時間性能分析方面的相關研究。了解到當前關于工作流 時間性能分析往往使用復雜難以理解的定理的形式給出，并且不具有可讀性。本 論文從另外一種角度出發(fā)，使用基本的數(shù)學期望的公式詳細定量分析了工作流四 種基本結(jié)構的時間性能。 ( 4 ) 工作流調(diào)度 研究并分析了工作流調(diào)度的相關文獻以及其它領域的調(diào)度問題，分析和總結(jié) 了目前工作流調(diào)度的主要問題和不足。在學習研究相關進化算法理論后，確定改 進適用于連續(xù)問題空間的粒子群算法，并運用改進后的算法進行工作流調(diào)度的研 究。將改進后的算法和經(jīng)典的二進制離散粒子群算法進行了實驗比較。實驗結(jié)果 表明新的算法收斂速度快，求解精度高、穩(wěn)定性好、能夠有效抑制早熟收斂，在 工作流調(diào)度應用中具有良好的性能。 1 3課題來源 本論文的研究是依托粵港關鍵重點突破項目“面向制造業(yè)信息化和電子政務 領域的軟件構件庫平臺 ( 編號：2 0 0 6 2 1 d 6 0 2 1 ) 、國家自然科學基金項目“基 于人工生命計算的計算協(xié)同關鍵問題研究 ( 編號：6 0 5 7 3 1 5 9 ) 和廣東省自然科 學基金項目“協(xié)同軟件關鍵技術及其應用研究”( 編號：0 5 2 0 0 3 0 2 ) 進行的。本 論文的研究內(nèi)容是這三個項目研究的重要組成部分。 1 4 論文組織 本論文共分為7 章，內(nèi)容安排如圖1 - 1 所示。 第1 章( 本章) 作為本論文的緒論部分，分析了工作流挖掘以及工作流調(diào)度 的重要地位，并闡述了本論文研究的背景和意義。另外，簡要介紹了本論文的主 要研究工作、課題來源和論文的組織結(jié)構。 第2 章主要介紹了本論文涉及的相關理論基礎及主要研究問題的現(xiàn)狀。首先 介紹了p e t d 網(wǎng)和工作流網(wǎng)的基本概念，然后介紹了遺傳算法和粒子群算法這兩 個和本論文相關的進化算法，最后從工作流挖掘、工作流時間性能分析和工作流 3 中山大學博士學位論文 調(diào)度三個方面綜述了目前國內(nèi)外的研究現(xiàn)狀。 第3 、4 、5 、6 章圍繞本論文的主題進行深入地討論與研究，是本論文的主 要內(nèi)容。 陳習 第2 章 相關理論及研究現(xiàn)狀 第3 章 可解決多種復雜任務 的工作流挖掘 第4 章 基于混合自適應遺傳算法 的工作流挖掘 第5 章 li第6 章 基于s p n 的工作流il 基于克隆選擇離散粒子 時間性能分析il 群算法的工作流調(diào)度 第7 章 總結(jié)與展望 圖1 - 1 論文組織結(jié)構 第3 章在分析前人工作的基礎上，針對目前工作流挖掘算法存在的不足，提 出了新的工作流挖掘算法一r 算法。首先提出啟發(fā)式判定規(guī)則，用來識別事件 日志中所包含的循環(huán)任務、重復任務和同一任務，然后運用z - 算法進行挖掘提取 出工作流網(wǎng)，并且通過c p n t o o l s 仿真工具對挖掘出的工作流模型進行仿真，并 分析仿真日志與原始日志的等價性，從而驗證r 算法的可行性和正確性。 第4 章運用混合自適應遺傳算法對工作流挖掘進行了深入地研究。針對目前 工作流挖掘算法采用局部策略因而無法保證最優(yōu)挖掘以及算法對噪聲敏感的情 況，提出基于混合自適應遺傳算法的工作流挖掘算法。首先定義了基本工作流網(wǎng) 以及變遷的使能和點火規(guī)則，給出了過程模型的定義；然后提出了過程模型轉(zhuǎn)換 成基本工作流網(wǎng)的算法，設計了衡量事件日志與過程模型符合性的適應值評價函 數(shù)：最后設計了根據(jù)進化階段以及個體相似度而混合自適應的交叉率和變異率。 仿真實驗結(jié)果表明，該算法與a 算法相比具有更高的魯棒性和對噪聲的抗干擾 性：與基本遺傳算法相比，該算法能顯著提高解的質(zhì)量和收斂速度。 第5 章基于s p n 對工作流時間性能進行了深入地分析。工作流性能分析是 對工作流進行評價和優(yōu)化的基礎，時間性能則是衡量工作流性能的一個重要指 - 4 - 第1 章緒論 標。利用概率論中關于服從指數(shù)分布的隨機變量的分布函數(shù)、密度函數(shù)及數(shù)學期 望的基本性質(zhì)，詳細地研究了組成s p n 模型的串行、并行、選擇和循環(huán)四種基 本結(jié)構的平均延遲時間，設計了通用的s p n 模型平均延遲時間公式。通過對復 雜s p n 模型的等效化簡，實現(xiàn)對工作流時間性能的分析。最后，通過實例驗證 了該方法的可行性和有效性。 第6 章研究了離散粒子群算法，以及其在工作流調(diào)度方面的應用。首先提出 旋轉(zhuǎn)擊發(fā)規(guī)則，并使用該規(guī)則對粒子的位置進行離散化處理，改進了傳統(tǒng)的適用 于連續(xù)優(yōu)化領域的粒子群算法，提出了克隆選擇離散粒子群算法。為了驗證本章 所提出的算法的優(yōu)越性，與二進制離散粒子群算法進行了實驗比較。實驗結(jié)果表 明，本章提出的克隆選擇離散粒子群算法收斂速度快，求解精度高、穩(wěn)定性好、 能夠有效抑制早熟收斂，在工作流調(diào)度應用中具有良好的性能。 第7 章是總結(jié)與展望。主要對本論文的研究工作做了進一步的歸納和總結(jié)， 并展望了下一步的研究工作。 5 ， 中山大學博士學位論文 第2 章相關理論及研究現(xiàn)狀 本章概述了工作流挖掘和調(diào)度涉及的p e t r i 網(wǎng)、工作流網(wǎng)的基本概念和基本 原理；應用于工作流挖掘和調(diào)度的相關進化算法，如遺傳算法、粒子群算法；工 作流挖掘、工作流時間性能分析和工作流調(diào)度的基本概念以及國內(nèi)外研究現(xiàn)狀。 2 1p e t r i 網(wǎng) p e t r i 網(wǎng)最早在1 9 6 2 年由德國的p e t r i 5 】提出。p e t r i 網(wǎng)的主要優(yōu)點是描述異步 并發(fā)能力和它的圖形表示。和其它系統(tǒng)模型一樣，p e t r i 網(wǎng)由兩類元素構成：表 示狀態(tài)的元素以及表示變化的元烈6 1 。p e t r i 網(wǎng)是一種可用圖形表示的組合模型， 同時又是嚴格定義的數(shù)學對象，既可用于靜態(tài)結(jié)構分析，又可用于動態(tài)行為分析。 有關p e t r i 網(wǎng)的更詳盡的闡述，可參見文獻【7 】。 定義2 - 1 ( 有向網(wǎng)，簡稱網(wǎng)舊) 三元組- 儼，t ，刃稱為有向網(wǎng)( 簡稱網(wǎng)) 的充分必要條件是： ( 1 ) p r i t - 矽； ( 2 ) p u t 一矽； ( 3 ) f p x tu z p ，其中“x 一表示笛卡爾乘積； ( 4 ) d o m ( f ) u c o d 但) 一p u t ，其中 d o m ( f ) 一缸1 3 y ： ，) ，) f c o d ( f ) - y i j z ：o ，y ) e f 它們分別是f 的定義域和值域，尸和r 分別稱為的庫所( p l a c e ) 集和變遷 ( t r a n s i t i o n ) 集。f 稱為流關系( f l o wr e l a t i o n ) 。 網(wǎng)由兩類節(jié)點組成：庫所和變遷。庫所用圓形“o 表示，變遷用方框“口 表示。節(jié)點間通過有向弧連接，同類節(jié)點不能直接相連，用從x 到y(tǒng) 的帶箭頭的 弧線表示流關系中的( z ，y ) 。 6 - 第2 章相關理論及研究現(xiàn)狀 定義2 2 ( 輸入庫所和輸出庫所) 如果存在一條有向弧線從庫所p 指向 交遷t ，則庫所p 稱為變遷t 的輸入庫所，變遷t 的輸入庫所集合記為f ；如果存 在一條有向弧線從變遷t 指向庫所p ，則庫所p 稱為變遷t 的輸出庫所，變遷f 的輸出庫所集合記為t 。 若網(wǎng)1 - - ( e , ，乃，f 1 ) ，p i = p 1 ，p 2 ，p 3 ，肼，d ，p 6 ) ，乃= f 1 ，t 2 ，t 3 ，t 4 ，t s ， f x - - ( p l ，f 1 ) ，( f l ，見) ，0 1 ，p 4 ) ，( p 2 ，t 2 ) ，( p 2 ，t 3 ) ，帆，“) ，純，p 3 ) ， ，p 3 ) ， m ，p 5 ) ，p 3 ，珞) ，慨，珞) ，( t 5 ，風) ，則l 網(wǎng)的圖形表示如圖2 - i 所示。 圖2 - i 有向網(wǎng)1 的圖形表示 有向網(wǎng)是系統(tǒng)的結(jié)構框架，在框架上的活動是系統(tǒng)中流動的資源。在有向網(wǎng) 的基礎上指明資源的初始分布，并規(guī)定框架上的活動規(guī)則( 即庫所的容量和變遷 與資源之間的數(shù)量關系) ，則稱為網(wǎng)系統(tǒng)。 記妒= o ，i ，2 ，礦= 1 ，2 ，3 ， ，甜表示無窮：= + 1 = 一1 = + 。 定義2 - 3 【6 】 ( 1 ) k - p 呻礦u c o 】稱為有向網(wǎng)i v - - ( p ，t ，d 的容量函數(shù)。 ( 2 ) 對給定的容量函數(shù)k ，m ：尸_ 妒稱為的一個標識的條件是： 坳p 膨( p ) s k 仞) 。 ( 3 ) 胍p 呻礦稱為上的權函數(shù)，對( z ，y ) f ，w ( x ，y ) 稱為 ，y ) 上的權。 權函數(shù)規(guī)定了每個變遷發(fā)生一次所引起的資源數(shù)量的變化。v ( x ，y ) e f ， 0 ，則t 在m 標識下是使能的，變遷點 火后得到新標識m ，對坳e p ， m 0 ) = m p ) 一形o ，f ) ，p e 4 - t m p ) + 形p ，f ) ，p f 。一。t m ( p ) - w ( s ，o + w ( t ，j ) ，p e t n ， m o ) ，p 譬f 標識由m 變?yōu)閙 的后繼m ，記作m p m 。 在網(wǎng)系統(tǒng)的圖形表示中，每個庫所p 都有一個對應的圓，標識m 的圖形表 示為：在p 對應的圓中畫上肘p ) 個黑點( 稱為托肯，t o k e n ) 。在腳) = n ，和w ( x ， y ) = 1 時均采用默認法，即不標明的容量均為無窮，不標明的權均為i 。 p c t r i 在文獻【5 】中使用的系統(tǒng)模型就是k 暑和形皇1 的網(wǎng)系統(tǒng)，這就是傳統(tǒng) 上稱為p c t r i 網(wǎng)的網(wǎng)系統(tǒng)，又稱為庫所變遷網(wǎng)( p h c e f r r a n s i t i o nn e t ，簡稱p 廠r 網(wǎng)) 。 定義2 - 7 ( 發(fā)生序列，變遷序列舊) s = m o t l m l 洲厶為的一個有 限出現(xiàn)序列的充分必要條件是：對所有的f ，i = 1 ，2 ，尬1 泓。稱f 爿1 t 2 厶為變遷序列。 2 2 工作流網(wǎng) i8 - 第2 章相關理論及研究現(xiàn)狀 a a l s t l 8 】等人把工作流的概念映射到p e t r i 網(wǎng)上，采用p e t r i 網(wǎng)對工作流的控制 流維度進行建模，并稱之為工作流網(wǎng)( w o r k f l o wn e t ，w f - n e t ) 。 定義2 - 8 ( w f n e t 嘲) p e t r i 網(wǎng)y = ( p ，t ，d 是w f - n e t ，當且僅當： ( 1 ) 2 有一個源庫所i e p ，且f = 矽； ( 2 ) 有一個匯庫所o e p ，且d - 矽； ( 3 ) 如果在中添加一個變遷t 且f = d ) ，t - - i ，則新的p e t r i 網(wǎng)i - 儼， r u t ，f u u ，i u d ，u ) ) 是強連通的。 文獻【8 】采用w f - n e t 描述了工作流過程模型中的順序、并行、選擇和循環(huán)這 四種基本控制結(jié)構。 ( 1 ) 順序路由 順序路由用來描述一個活動執(zhí)行完成后，另一個活動才能接著執(zhí)行的情況。 圖2 2 給出了一個順序路由的例子，活動a 完成后活動曰才能開始執(zhí)行；活動口 完成后，活動c 才能開始執(zhí)行。 ，plp 2 o ( 2 ) 并行路由 圖2 2 順序路由 并行路由用來描述多個活動可以同時執(zhí)行或以任意次序執(zhí)行的情況。為了建 ?；顒又g的并行路由關系，引入兩個控制任務a n d s p l i t 和a n d - j o i n 。圖2 - 3 給出了并行路由的例子，活動j 5 i 和活動c 的執(zhí)行順序有三種可能：b 、c 兩個活 動同時執(zhí)行；b 先執(zhí)行，c 后執(zhí)行；c 先執(zhí)行，丑后執(zhí)行。t 1 、t 2 分別表示a n d s p l i t 和a n d - j o i n 任務。 a n d c s p l i ta n p o i n 仍p4 圖2 - 3 并行路由 9 一 中山大學博士學位論文 - 目- - 目e | 自| l _ _ _ - - _ _ _ _ 目目_ _ _ _ _ _ r i i _ _ i l l _ _ _ _ _ _ ( 3 ) 選擇路由 選擇路由用來描述只能從多個活動中選擇其中一個活動來執(zhí)行的情況。為了 建?；顒又g的選擇路由關系，引入兩個控制任務o r - s p l i t 和o r - j o i n 。圖2 - 4 給出了選擇路由的例子，活動曰、c 中只能有一個活動被選擇執(zhí)行，可能是丑被 執(zhí)行，也可能是c 被執(zhí)行。p 1 、p 2 分別表示o r - s p l i t 和o r - j o i n 任務。 圖2 - 4 選擇路由 ( 4 ) 循環(huán)路由 循環(huán)路由用來描述某一個或多個活動需要反復執(zhí)行的情況。循環(huán)路由是一種 特殊的選擇路由，同樣引入了兩個控制任務o r s p l i t 和o r - j o i n 。圖2 - 5 給出了 循環(huán)路由的例子。活動曰可能被多次執(zhí)行。p 1 、p 2 分別表示o r - j o i n 和o r - s p l i t 任務。 2 3相關進化算法 2 3 1 遺傳算法 圖2 - 5 循環(huán)路由 求解最優(yōu)解或近似最優(yōu)解的傳統(tǒng)方法主要有枚舉法、啟發(fā)式方法和搜索算法 【9 】。隨著問題規(guī)模的擴大、約束條件的增多，這些傳統(tǒng)的方法在可以接受的時間 內(nèi)不能得到問題的最優(yōu)解或近似最優(yōu)解。 遺傳算法是近年來迅速發(fā)展起來的一種高度并行的隨機搜索與優(yōu)化方法，它 - 1 0 - 第2 章相關理論及研究現(xiàn)狀 為解決大規(guī)模優(yōu)化問題提供了種有效的途徑。遺傳算法( g e n e t i ca l g o r i t h m s ， g a ) 【1 0 】是美國m i c h i g a n 大學的j h o l a n d 于1 9 7 5 年受生物進化論的啟發(fā)提出的， 是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率 搜索算法。 ( 1 ) 基本遺傳算法 通過模仿自然界中生物遺傳與進化機制，許多學者設計了各種不同的遺傳算 子來模仿不同環(huán)境下的生物遺傳特性，構成了各種不同的遺傳算法。但這些遺傳 算法都有一個共同的特點，即在模仿生物遺傳與進化過程中都使用了選擇、交叉、 變異機制。g o l d b e r g l l l 】總結(jié)了一種統(tǒng)一的最基本的遺傳算法，稱為基本遺傳算法 ( s i m p l eg e n e t i ca l g o r i t h m , s g a ) 。 基本遺傳算法從一組隨機產(chǎn)生的初始解( 稱為初始種群) 開始進化過程。種 群中每個個體對應為問題空間的一個解，稱為染色體?；具z傳算法中以個體適 應度的大小來評價各個個體的優(yōu)良程度，從而決定其遺傳到下一代的機會大小。 評價個體適應度的函數(shù)稱為適應值函數(shù)?；具z傳算法主要通過選擇、變異、交 叉運算不斷迭代產(chǎn)生下一代種群。選擇運算把當前種群中適應值高的個體遺傳到 下一代種群中。交叉運算是遺傳算法中產(chǎn)生新個體的主要操作，它以某一概率( 稱 為交叉概率，p 艉) 將個體部分染色體相互交換產(chǎn)生兩個新個體( 稱為后代個體) ， 并用來替代原來的兩個“舊 個體( 稱為父個體) 。變異運算是對個體的某一個 或某一些基因座上的基因值按較小的概率( 稱為變異概率，只) 進行變異。種群 不斷地進行選擇、交叉和變異運算，經(jīng)過若干代，算法收斂于一個優(yōu)良個體，它 就是最優(yōu)解或次優(yōu)解?；具z傳算法的運算過程如圖2 - 6 所示。 該算法使用了上述三種遺傳算子( 選擇算子、交叉算子、變異算子) ，主要 運算步驟如下： ( 1 ) 初始化。設置進化代計數(shù)器f = 0 ；設置最大進化代死隨機生成規(guī)模為 的初始種群爿0 ) ； ( 2 ) 選擇運算。將選擇算子作用于種群； ( 3 ) 交叉運算。將交叉算子作用于種群，交叉概率般取【0 4 ，0 9 9 】： ( 4 ) 變異運算。將變異算子作用于種群，變異概率一般取【0 0 5 ，0 2 5 ，種 群尸( d 經(jīng)過選擇、交叉、變異運算后得到下一代種群心+ 1 ) ； 中山大學博士學位論文 ( 5 ) 判斷終止條件。若t w ) 、因果( 一w ) 、 并行( w ) 和不相關( 柵) 。由于a 算法采用集合來定義任務之間的關聯(lián)關系， 因此在判定重復任務時，算法將這些重復任務視為同一個任務，往往會導致挖掘 出錯誤的過程模型。文獻 8 2 1 提出了判定重復任務的啟發(fā)式規(guī)則，擴展了a 算法， 使其能發(fā)現(xiàn)不含有循環(huán)任務的日志中的重復任務，然而沒有考慮到在含有循環(huán)任 務的日志中循環(huán)任務和重復任務的發(fā)現(xiàn)。 當業(yè)務流程含有循環(huán)任務、重復任務時，產(chǎn)生的事件日志中會出現(xiàn)一個任務 多次出現(xiàn)的情況。為了判定多次出現(xiàn)的任務來自循環(huán)任務、重復任務還是同一任 務，本章改進了a 算法，提出了r 算法。首先通過啟發(fā)式規(guī)則判定出事件日志中 來自同一個軌跡的循環(huán)任務和重復任務以及來自不同軌跡的同一任務，然后運用 f 算法從事件日志中提取出w f - n e t 。該算法同樣適用于不含有循環(huán)任務的事件 日志。 3 2事件日志完備性及任務定義 3 2 1 工作流曰志和工作流軌跡 2 3 中山大學博士學位論文 工作流挖掘的目的是為了從事務日志抽取出工作流模型。在這些事務日志中 包含很多信息，文中為了工作流挖掘的需要，我們只關心工作流實例編號( i d ) 和任務名稱。表3 - 1 給出了一個事件日志的例子。 表3 2 中給出了從表3 - 1 的事件日志中整理出來的2 個工作流實例的任務 軌跡。定義3 - 1 給出了事件日志和任務軌跡的定義，其中事件日志的定義參考了 文獻【3 5 】。 定義3 - 1 ( 事件日志和任務軌跡) 設r 是任務集合，p 是由z 中0 個或 多個任務組成的所有序列的集合。形p 稱為工作流日志；s e t * 稱為任務軌跡。 表3 1 事件日志 實例l d任務名稱 表3 2 任務軌跡 軌跡m任務軌跡 s 1 s 2 a b c d 彳c b d 3 2 2 事件日志完備性 對于一個實際的業(yè)務流程，不完整的事件日志會導致挖掘出的過程模型有 誤，如循環(huán)結(jié)構的丟失等。文中所提及的事件日志若無特殊說明，都是指具有完 備性的事件日志。為此下面給出事件日志完備性的定義。 - 2 4 4 4 口 c c 丑 d d 第3 章可解決多種復雜任務的工作流挖掘 定義3 2 ( 事件日志完備性) 設矽是由任務集z 構成的業(yè)務流程產(chǎn)生的 事件日志，5 是業(yè)務流程一次執(zhí)行過程產(chǎn)生的任務軌跡，s 礬w 具有日志完 備性，當且僅當： ( 1 ) 對于由任務集z 構成的業(yè)務流程產(chǎn)生的任意事件日志礦，有形礬 ( 2 ) 對于任意f l 都存在s 形使得t e e s ； ( 3 ) 對于事件日志礦，若中有5 1 - x y ，s 2 - - x a y ，s 3 = ” x a a y ， 且a ，z ，y z ，則一定存在j l ，5 2 ，s 3 e w 且s l = ” x y ，s 2 x a y ，5 3 - x a a y ； ( 4 ) 對于事件日志礦，若中有5 1 - x a y ，5 2 -