沈美 于翔

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

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

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

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

1 基本概念

1.1 工作流網(wǎng)

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

1.2 隨機(jī)Petri網(wǎng)

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）接著要生成可達(dá)圖。首先可以先生成一個(gè)可達(dá)樹，再將可達(dá)樹轉(zhuǎn)換成一個(gè)可達(dá)圖。

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

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

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

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

3 實(shí)例分析

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

因?yàn)橐捎霉ぷ髁麟S機(jī)Petri網(wǎng)來分析工作流，首先要確保模型是合理的，通過分析驗(yàn)證方法[7]，可以得出結(jié)論，圖1模型是正確的、合理的。通過定理1，該網(wǎng)同構(gòu)于一個(gè)有限的馬爾可夫鏈，保證了計(jì)算的可行性。如前文所述，對(duì)工作流隨機(jī)Petri網(wǎng)的分析步驟如下：

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

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

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

一旦給出λ的具體值，就可以根據(jù)公式（1）得到穩(wěn)定概率P（Mi）的值。根據(jù)對(duì)實(shí)際問題的預(yù)測(cè)，該網(wǎng)中的變遷引入平均實(shí)施速率λi。給定隨機(jī)變量集合λ={λ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）的基礎(chǔ)上，就可以得出上文中提到的工作流網(wǎng)的其他性能指標(biāo)。

4 結(jié)語

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

[參考文獻(xiàn)]

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

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

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

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

[5]林闖.計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)的性能評(píng)價(jià)[M].清華大學(xué)出版社. 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]沈美.基于高級(jí)Petri網(wǎng)的工作流建模研究與仿真分析.計(jì)算機(jī)工程與應(yīng)用.2006，42（32）：200～203.