基于隨機Petri網(wǎng)工作流模型的時間性能分析方法

沈美 于翔

摘 要：工作流Petri網(wǎng)的時間性能分析方法有多種，本文采用加入時間因素的擴展馬爾可夫鏈，建立與隨機Petri網(wǎng)同構的有窮馬爾可夫鏈，再根據(jù)此過程的穩(wěn)定概率求解系統(tǒng)的性能參數(shù)。

關鍵詞：工作流；Petri網(wǎng)；時間性能分析；馬爾可夫鏈

工作流模型的時間性能分析是工作流研究的重要內容之一，也是分析資源利用率、成本等指標的基礎。目前，大多數(shù)實用的工作流應用系統(tǒng)，在業(yè)務流程的性能分析上，幾乎未給出適合各種工作流模型的有效方法。工作流除了正確性之外，還要關心它的性能分析，而這一點又往往被人們所忽視。工作流性能分析主要反映工作流定量方面的特性，比如過程的完成時間，資源利用率等等。定量分析模型之前須確認模型的正確性，即保證模型在業(yè)務流程和邏輯結構上沒有錯誤且是合理的。傳統(tǒng)的基于馬爾可夫鏈的性能分析方法[1]具有指數(shù)時間復雜性，影響了其實用性。對給定的工作流，可以生成一個馬爾可夫鏈，利用它可以分析工作流的某些方面，而且馬爾可夫鏈的分析[2]非常耗時（即使是對本來不難處理的問題）。但是，根據(jù)實際應用可以通過成本或時間的引入來擴展馬爾可夫鏈，就能獲取一系列性能指標。

本文討論加入時間因素的擴展馬爾可夫鏈，根據(jù)被評價的隨機Petri網(wǎng)工作流模型構造出連續(xù)時間的馬爾可夫鏈，即隨機模型[3]，對其進行時間性能分析。

1 基本概念

1.1 工作流網(wǎng)

對工作流的控制流建模的Petri網(wǎng)被稱作工作流網(wǎng)（WF-net），是Aalst在Petri網(wǎng)的基礎上提出的概念。

1.2 隨機Petri網(wǎng)

隨機Petri網(wǎng)（SPN）：一個連續(xù)時間SPN是一個六元組SPN=（P，D，F(xiàn)，W，M0，λ），在Petri網(wǎng)基礎上，λ={λ1，λ2，…，λm}，是變遷平均實施速率集合。

在連續(xù)時間SPN中，一個變遷t從變成可實施的時刻到它實施時刻之間的延時被看成一個連續(xù)隨機變量，服從以λ為參數(shù)的指數(shù)分布。λ是變遷t的平均實施速率，表示在可實施的情況下單位時間內平均實施的次數(shù)，單位是次數(shù)/單位時間。平均實施速率的倒數(shù)1/λ稱為變遷ti的平均實施延時或平均服務時間。

1.3 工作流-隨機Petri網(wǎng)的定義

工作流-隨機Petri網(wǎng)（WF-SPN）是在隨機Petri網(wǎng)（SPN）和工作流網(wǎng)（WF-net）的基礎上提出的，目的是將隨機觸發(fā)時間引入工作流網(wǎng)，使模型具有分析時間性能的能力。

WF-SPN是SPN的真子集，可遞歸定義為：由一個基本結構組成的SPN是WF-SPN。WF-SPN滿足如下性質：（1）有一個初始庫所i∈P，·i=φ；（2）有一個終止庫所0∈P，o·=φ；（3）每個節(jié)點x∈P∪T都在從I到o的一條路徑上。

2 工作流-隨機Petri 網(wǎng)時間性能分析

基本Petri網(wǎng)模型不能用于系統(tǒng)的性能評價，必須對其擴展?？梢栽诿總€變遷的可實施和實施之間聯(lián)系一個隨機的時間延遲。應用隨機Petri網(wǎng)對系統(tǒng)評價時分三步：1）構造系統(tǒng)對應的隨機Petri網(wǎng)模型。2）構造出該Petri網(wǎng)所同構的馬爾可夫過程。3）基于馬爾可夫過程的穩(wěn)定概率求解系統(tǒng)的性能參數(shù)。

工作流-隨機Petri網(wǎng)和一般工作流網(wǎng)的區(qū)別：在變遷中引入平均實施速率λi，每個λi值是從對所模擬系統(tǒng)的實際測量中獲得或根據(jù)某種要求的預測值，它們具有實際意義。

定理1[4]任何具有有窮個庫所、有窮個變遷的連續(xù)時間的隨機Petri網(wǎng)同構于一個一維連續(xù)時間的馬爾可夫鏈。K-有界的隨機Petri網(wǎng)同構于有窮馬爾可夫鏈。

假定一個工作流隨機網(wǎng)同構于一個馬爾可夫鏈，那么工作流隨機網(wǎng)的每一個標識可以達到一個動態(tài)平衡狀態(tài)，即每一個標記有一個確定的值，稱為標記Mi的穩(wěn)定概率，記為P（Mi）， （i=1，2，...，k）。根據(jù)馬爾可夫鏈平穩(wěn)分布的有關理論，得出如下的公式[5]：

其中Q為變遷速率矩陣，其非對角線上的元素qi，j（i≠j）是這樣確定的：如果在馬爾可夫鏈中從Mi到Mj有一條有向弧連接時，qi，j為弧上的速率值；如果沒有弧，則qi，j（i=j）是從Mi發(fā)出的各條弧速率之和的相反數(shù)。將工作流隨機網(wǎng)同構為馬爾可夫鏈之后，利用公式（1），可以解出P（Mi）的值。由此可以得出工作流模型的一些系統(tǒng)特性和運行特性。

生成一個工作流網(wǎng)的可達圖是實現(xiàn)從工作流網(wǎng)到馬爾可夫鏈轉換的關鍵，但要確保工作流網(wǎng)模型是合理的。工作流網(wǎng)是合理的，那么工作流隨機網(wǎng)必定有界，該網(wǎng)就可以同構于一個有限的馬爾可夫鏈，保證了計算的可行性。具體的分析步驟如下：

（1）從工作流隨機網(wǎng)的定義可以看出，它是工作流網(wǎng)的一個特例。由于任何一個合理的工作流網(wǎng)必將結束于標識（0，0，...，0，1），也就是在馬爾可夫鏈中該結束標識的穩(wěn)定概率為1，其他標識的穩(wěn)定概率均為0。這樣就不能用來分析其性能，原因是工作流網(wǎng)僅執(zhí)行一次。因此要將一個工作流網(wǎng)執(zhí)行多次，然后得出每個標識的穩(wěn)定概率。現(xiàn)有的工作流網(wǎng)模型不能反映這一特性，在文獻[6]中提出在庫所o和庫所i間增加一個瞬間變遷t*，并連接庫所o和變遷t*，連接變遷t*和庫所i，由于變遷t*是不需要時間的，實際上標識（0，0，...，0，1）是不存在的。因此，可以考慮將庫所o映射為庫所i，也就是將庫所o和庫所i合并，這樣在不額外增加變遷的基礎上，也能反映工作流網(wǎng)可任意次執(zhí)行的特性，得出的標識穩(wěn)定概率可用于分析工作流的性能。因此這一步要完成的任務就是將庫所i和庫所o合并。

（2）接著要生成可達圖。首先可以先生成一個可達樹，再將可達樹轉換成一個可達圖。

（3）計算Q矩陣的值。在馬爾可夫鏈中，當從狀態(tài)Mi到狀態(tài)Mj有一條弧相連時，則弧上標注的值即是qi，j的值；如果從狀態(tài)Mi到狀態(tài)Mj沒有弧相連時，則qi，j=0。對角線上的元素qi，j（i=j）是從Mi發(fā)出的各條弧速率之和的相反數(shù)。

根據(jù)公式1得到穩(wěn)定概率P（Mi）的值；在求得穩(wěn)定概率的基礎上，可進一步分析系統(tǒng)的以下性能指標，如變遷的標記流速，子系統(tǒng)的平均延時時間等，具體可參考文獻[5]。

①在每個狀態(tài)M中的駐留時間：在每個可達標識M∈[M0>的駐留時間是以-γi，i為參數(shù)的一個指數(shù)分布的隨機變量，平均為： 。

②標記概率密度函數(shù)：在穩(wěn)定狀態(tài)下，每個庫所中所包含標記數(shù)量的概率。對 ， ，令P{M（S）=i}表示庫所s中包含i個標記的概率，則可從標識的穩(wěn)定概率求得庫所s的標記概率密度函數(shù)： ，其中Mj∈[M0>且Mj（s）=i。

3 實例分析

本文以ASP平臺進銷存系統(tǒng)為例對其過程模型進行時間性能分析。此系統(tǒng)的簡化過程模型見圖1所示，庫所集合P=（p1，p2，…，p6），變遷集合T=（t1，t2，…，t5）。其中變遷標識和含義：標識t1代表客戶下訂單，即當收到客戶的訂貨信息就觸發(fā)變遷t1，實施創(chuàng)建銷售訂單的任務；t2表示檢查庫存，若當前庫存能滿足訂單需求，則實施p2分支，否則實施p3分支；t3代表采購；t4表示出銷售單；t5代表出貨。標識i是庫所開始，o表示庫所結束。

因為要采用工作流隨機Petri網(wǎng)來分析工作流，首先要確保模型是合理的，通過分析驗證方法[7]，可以得出結論，圖1模型是正確的、合理的。通過定理1，該網(wǎng)同構于一個有限的馬爾可夫鏈，保證了計算的可行性。如前文所述，對工作流隨機Petri網(wǎng)的分析步驟如下：

⑴在庫所o和庫所i之間增加一個瞬間變遷t*，將庫所o和庫所i合并，形成圖2所示的改進模型。反映工作流網(wǎng)可任意次執(zhí)行的特性，得出的標識穩(wěn)定概率可用于分析工作流的性能。

⑵生成可達圖，得出圖2所示的工作流網(wǎng)的可達狀態(tài)標識，可用表1來表示。將圖2所示的工作流Petri網(wǎng)轉換成與其等價的馬爾可夫鏈，見下圖3。

⑶Q為變遷速率矩陣，根據(jù)前文計算規(guī)則，得出圖3馬爾可夫鏈對應Q矩陣的值見表2

一旦給出λ的具體值，就可以根據(jù)公式（1）得到穩(wěn)定概率P（Mi）的值。根據(jù)對實際問題的預測，該網(wǎng)中的變遷引入平均實施速率λi。給定隨機變量集合λ={λ1，λ2，λ3，λ4，λ5，λ*}={2，5，20，3，15，0}。得到P（Mi）={0.2498，0.2145，0.2237，0.187，0.1250，0}。在求得穩(wěn)定概率P（Mi）的基礎上，就可以得出上文中提到的工作流網(wǎng)的其他性能指標。

4 結語

本文采用加入時間因素的擴展馬爾可夫鏈對被評價的隨機Petri網(wǎng)工作流模型，首先構造出相應的連續(xù)時間的馬爾可夫鏈，再根據(jù)此過程的穩(wěn)定概率對其進行時間性能分析。通過實例分析得出：此方法是有效、可行的，對同類問題的分析和評價具有一定的參考價值。

[參考文獻]

[1]王建民，聞立杰，等，譯.工作流管理—模型、方法和系統(tǒng)[M].北京：清華大學出版社.2004.

[2]曲揚.基于Petri網(wǎng)的工作流建模和分析方法研究.清華大學學位論文.清華大學，2004.

[3]衛(wèi)剛.基于Petri網(wǎng)的工作流建模工具的研究與實現(xiàn).南京航空航天大學學位論文.南京航空航天大學.2005.

[4]林闖.隨機Petri網(wǎng)和系統(tǒng)性能評價[M].北京：清華大學出版社.2000.

[5]林闖.計算機網(wǎng)絡和計算機系統(tǒng)的性能評價[M].清華大學出版社. 2002，1：3～202.

[6]Lin C，Marinescu D C，Reachability trees for high level Petri nets with marking variables，Computer Sciences Department， Purdue University，CSD-TR-857，F(xiàn)ebruary 1989.

[7]沈美.基于高級Petri網(wǎng)的工作流建模研究與仿真分析.計算機工程與應用.2006，42（32）：200～203.