劉　磊，余汾芬

（1.浙江理工大學先進制造技術研究所，浙江　杭州　310033；2.安慶職業(yè)技術學院　機電工程系，安徽　安慶　246003；

3.安慶醫(yī)藥高等專科學校，安徽　安慶　246052）

支持過程改進的工作流仿真及優(yōu)化技術研究

劉磊1，2，余汾芬3

（1.浙江理工大學先進制造技術研究所，浙江杭州310033；2.安慶職業(yè)技術學院機電工程系，安徽安慶246003；

3.安慶醫(yī)藥高等?？茖W校，安徽安慶246052）

業(yè)務流程重組（BPR）是增強企業(yè)競爭能力的關鍵，而工作流技術是支持過程改進的有效技術.至今為止，工作流仿真和優(yōu)化還是一個薄弱環(huán)節(jié).本文提出了一種基于petri網的工作流仿真方法和工作流優(yōu)化的關鍵路徑方法（CPM），從而為支持企業(yè)業(yè)務過程改進找到了一個可行的思路.最后，給出工作流仿真系統(tǒng)JXWorkflow具體實例分析.

過程改進；工作流仿真；工作流優(yōu)化；Petri網；關鍵路徑

自上世紀九十年代初，企業(yè)的核心競爭力由之前的時間、成本逐步轉移到對整個業(yè)務流程的控制，業(yè)務流程重組（BusinessProcessReengineering，BPR）的概念應運而生，它的主要標志是以企業(yè)過程為中心，并通過ISO9001質量標準檢測和CMM過程成熟度評估.而工作流技術則是實現企業(yè)業(yè)務過程自動執(zhí)行和各部分信息交互的有效方法，它起源于業(yè)務過程的自動化，通過企業(yè)過程的計算機模型表示，從而實現文檔、信息和任務的自動執(zhí)行，繼而實現企業(yè)業(yè)務過程的自動化處理.但是工作流模型在建模階段不可能完全考慮到所有的情況，業(yè)務過程中深層的語義規(guī)則也不可能完全挖掘出來，因此，工作流仿真和優(yōu)化便成為支持企業(yè)業(yè)務過程改進的關鍵技術[1].

1　Petri網仿真

工作流仿真是對模型評估、分析業(yè)務過程、發(fā)現瓶頸問題并對業(yè)務模型進行優(yōu)化的有效方法.它可以在系統(tǒng)運行之前對模型進行跟蹤，配置，設置仿真環(huán)境，利用離散事件驅動的方式使得流程向下流轉，自動推進工作流實例，通過對流程的仿真，得到一系列關于工作流模型運行的統(tǒng)計數據，并分析業(yè)務過程、活動和資源等動態(tài)對象，從而來判斷、評估或評價真實流程的性能..

Petri網具有描述不確定和隨機特征的復雜系統(tǒng)的能力，它從關注過程的角度，兼顧嚴格語義和圖形語言兩個方面，既可以作為描述系統(tǒng)模型的圖形化工具，也可以建立描述諸如系統(tǒng)方程等系統(tǒng)模型行為的數字化工具，是一種描述和分析復雜系統(tǒng)的有效模型工具.

定義1（WF-net） 一個PN可以用一個5元組表示成為，如果以下條件成立[2]：

1、對結點i∈P，·i=?，則i稱源庫所；

2、對結點o∈P，o·=?，則o稱為匯結庫所；

3、對于每一個結點x∈P∪T而言，它必定都位于某一條從i到o的路徑上.

此時，可以認為PN=(P,T,F)是工作流網.

WF-net的有以下性質：

1、只有唯一一個源庫所，即i；

2、也只有唯一一個匯結庫所，即o；

3、如果在PN中添加一個連接匯結庫所o和源庫所i的變遷t*（即·t={o}且t*·={i}），得到PN是強連接的，而且對于每一個結點x∈P∪T，必定位于一條從i到o的路徑上.

定義2（合理性） 由一個WF-netPN=(P,T,F)描述的業(yè)務過程，如果以下條件成立：

1、對每個狀態(tài)M，假設它可以從初始狀態(tài)i達到，則必存在一個發(fā)生序列，而且它是從狀態(tài)M到狀態(tài)o的，即：?M(i→*M)?(M→*o)；

2、只有唯一一個正常結束狀態(tài)，即狀態(tài)o：?M(i→*M∧M≥o)?(M-o)；

3、不存在死變遷，即：?t∈T，?M,M1，使得(i→*M→tM1).

此時，可以認為該過程是合理的.

我們可以通過構造變遷—自由選擇子網距陣Bn×k與變遷—資源距陣Cl×k來分析多維工作流網模型PN的性能[3]，下面通過實例來說明.

圖1(a)為一個由有向網絡圖描述的工作流模型，假設其開始活動、結束活動及所有邏輯節(jié)點的時間、需求的資源等均為零，該業(yè)務過程中所消耗的資源{R1,R2,R3,R4}的狀態(tài)向量為{1，2，1，1}.圖1(b)為經模型映射后得到的自由選擇多維工作流網模型.

對圖1(b)的模型進行分解，得到兩個自由選擇子網，如圖2(a)-(b)，它們分別描述了兩種業(yè)務實例I1和I2的處理過程.

圖1　模型映射示例

圖2　模型分解

構造變遷-自由選擇子網距陣B2×13和變遷-資源距陣C，如下所示[6]：

假設總業(yè)務實例到達速率λ=0.2，業(yè)務實例1和業(yè)務實例2在總業(yè)務實例中所占的百分比β={β1，β2}={0.5，0.5}，得到λI={0.1，0.1}，即I1和I2的到達速率均為0.1.

下面其性能進行分析.對應于多維工作流網中的13個變遷可以得到μ={μ1,μ2,…,μ13}={0,0,0.2,1,0.5,0.167,0.167, 0,0,0.25,0}，其中從μ1至μ13分別表示變遷ts，t1A，t2A，tA1，tA2，tA3，tA4，tA5，tA6，tB，tC，tA7，tE的觸發(fā)延遲均值的倒數，即μi=1/α (ti)，從而得到：

λI×B2×13=[0.2,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.2,0.2,0.2,0.2]，ω=Cl×k×(λI×Bn×k)T=[0.20.20.20.2]T分別指資源{R1,R2, R3,R4}的業(yè)務實例到達速率.從圖中我們可以看出，資源R1參與變遷tA1，tA5的觸發(fā)，所以其平均服務速率為ηi=∑(μi× λti/∑λti)=0.183.通過同樣的計算可以得到R2，R3及R4的平均服務速率分別為0.75，0.33和0.25.由于資源R1的服務負載ρ1=ω1/η1=0.2/0.183=1.093>1，造成系統(tǒng)不穩(wěn)定，其配置顯然不滿足要求.如果我們增加數量至2，ρ1=ω1/η1=0.2/(2× 0.183)=0.546<1，此時資源R1的配置能夠滿足系統(tǒng)穩(wěn)定性的要求.通過同樣的方式我們可以驗證：資源R2，R3及R4的配置均滿足系統(tǒng)穩(wěn)定性的要求.

2　關鍵路徑優(yōu)化技術

工作流可以看成一個由串聯、并聯、選擇和循環(huán)4種控制結構組成和相互連接的活動網絡.運行時，活動的服務器服務時間服從指數分布并且用戶的服務需求的到達過程服從泊松分布.因此，根據工作流活動的可操作性這一特點，可以把工作流看成其中每個活動都是獨立的M/M/1排隊網.假設每個活動的到達率、服務率和選擇、循環(huán)的概率是確定的，那么我們可以計算出工作流活動網所有活動的到達和完成時間.各種結構的平均執(zhí)行時間按如下公式進行計算[4]：

1、順序結構wt=∑(1/μt-λi)；

2、選擇結構wt=max(∑(1/μt-piλi))，其中∑pi=1，pi表示各分支到達的可能性；

3、循環(huán)結構wt=(1/pμt-λ)+K+(1/pμn-λ)；

4、并行結構wt=max(∑(1/μt-λi)).

按圖3所示的規(guī)則將工作流模型轉換為樹形表達[5].算法如下：

Procedure

Calculated_Critical_Path(workflow.roott)

Begin

Object=workflow.root;

Ifobject.type=ActivityThen

SelectobjectforCalculated_Critical_Path(object);

Else

Begin

Forallchildrenobject;

Calculated_Critical_Path(object.child);

Ifobject.type=SerialThen

Object.Completion_Time=

Sum_Completion_Times_of_Children(object);

Ifobject.type=AndThen

Begin

Object.Completion_Time=

MaxCompletion_Times_of_Children(object);

Exclude_Nodes_in

圖3　基本工作流結構的樹形表示和完成時間的計算方法

Non_MaxChildren_Subtree_from_CP(object);

End

Ifobject.type=OrThen

Object.Completion_Time=SumCompletion_Times_of_

Children(object);

Ifobject.type=IterateThen

Object.Completion_Time=

Iterate_Formula_for_Completion_Time(object);

End;

End;

3　仿真機制及系統(tǒng)實現

基于上述研究基礎,筆者所在的課題組在開發(fā)了一個工作流仿真系統(tǒng)-JXWorkflow，它是運行在虛擬環(huán)境之上的.其工作流仿真機制如圖4所示，由表示層（即用戶操作界面,包括設置仿真環(huán)境及參數、顯示仿真動畫和生成仿真報表）、業(yè)務邏輯層(工作流仿真引擎)和數據庫層(包括工作流實例庫、工作流資源庫以及仿真信息庫)構成，它以時間、成本、資源利用率、等待隊列作為仿真指標，來綜合分析和評價企業(yè)業(yè)務流程模型的性能,其計算方法如表1所示[6].

指標計算方法時間（小時）　　活動時間=工作時間+等待時間（等待資源時間+阻塞時間+非活動時間）按價值類型：成本=增殖活動成本+業(yè)務增殖活動成本+非增殖活動成本按資源類型：成本=勞動力成本+設備成本+原材料成本+其他按時間類型：成本=標準成本+超時成本過程性能（%）　　資源利用率=∑資源忙時間/（資源時間-非活動時間-無效時間）成本（元）

JXWorkflow系統(tǒng)的仿真組織策略如下：首先確定活動執(zhí)行的組織單元，其次進行工作流模型的資源配置；然后對過程中的活動進行屬性配置；最后設置仿真運行環(huán)境.經過多次仿真，得到一組仿真數據，通過對仿真數據的分析來發(fā)現業(yè)務流程的瓶頸問題，找到關鍵路徑，進而達到優(yōu)化和改進業(yè)務流程的目的.

圖4　工作流仿真機制

4　結束語

目前大多數工作流系統(tǒng)對模型的合理性和有效性缺乏足夠的支持，不僅安全可靠性差，而且風險極高，資源浪費.就工作流仿真而言，難點在仿真內容的復雜性和仿真指標的確定，比如信息流的仿真和歷史數據挖掘等仿真機制的實現；對于工作流模型結構的優(yōu)化，縮短關鍵路徑的平均執(zhí)行時間是提高工作流執(zhí)行效率的有效方法，在使用優(yōu)化方法對工作流模型結構進行優(yōu)化時，還應該遵照企業(yè)運行過程，保留合理的業(yè)務邏輯關系，不能盲目優(yōu)化模型結構，造成無法實際應用.

〔1〕武星.成本最優(yōu)化工作流技術驅動的研發(fā)協同軟件即服務應用［J］.計算機集成制造系統(tǒng)，2013，19（8）：1750-1752.

〔2〕許春霞.基于隨機Petri網的工作流仿真［J］.計算機技術與發(fā)展，2009，19（4）：88-89.

〔3〕趙新曉.支持可定制建模方式的工作流系統(tǒng)的研究及實現［D］.山東大學，2012.71-75.

〔4〕高保強.工作流仿真結果分析［J］.計算機工程，2010，36（10）：45-46.

〔5〕李海波.基于時間關鍵路徑的工作流模型優(yōu)化方法［J］.機電產品開發(fā)與創(chuàng)新，2005（6）：205-206.

〔6〕文俊浩.基于WDAG的工作流模型優(yōu)化分析［J］.計算機工程，2010，36（1）：30-32.

TP311

A

1673-260X（2016）08-0019-03

2016-05-28

2015安徽省高校自然科學研究項目 《可拓學下的協同產品商務 （CPC）及其在安徽制造業(yè)中的應用研究》（KJ2015A390）；2014安徽省質量工程教學研究項目 《產教融合校內實訓基地培養(yǎng)制造類高素質技能人才的研究與實踐》（2014jyxm535）