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

沈美 于翔

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

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

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

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

1 基本概念

1.1 工作流網

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

1.2 隨機Petri網

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

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

1.3 工作流-隨機Petri網的定義

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

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

2 工作流-隨機Petri 網時間性能分析

基本Petri網模型不能用于系統的性能評價，必須對其擴展。可以在每個變遷的可實施和實施之間聯系一個隨機的時間延遲。應用隨機Petri網對系統評價時分三步：1）構造系統對應的隨機Petri網模型。2）構造出該Petri網所同構的馬爾可夫過程。3）基于馬爾可夫過程的穩定概率求解系統的性能參數。

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

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

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

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

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

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

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

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

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

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

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

3 實例分析

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

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

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

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

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

一旦給出λ的具體值，就可以根據公式（1）得到穩定概率P（Mi）的值。根據對實際問題的預測，該網中的變遷引入平均實施速率λ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}。在求得穩定概率P（Mi）的基礎上，就可以得出上文中提到的工作流網的其他性能指標。

4 結語

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

[參考文獻]

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

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

[3]衛剛.基于Petri網的工作流建模工具的研究與實現.南京航空航天大學學位論文.南京航空航天大學.2005.

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

[5]林闖.計算機網絡和計算機系統的性能評價[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，February 1989.

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