劉　磊，余汾芬

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

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

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

劉磊1，2，余汾芬3

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

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

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

過程改進(jìn)；工作流仿真；工作流優(yōu)化；Petri網(wǎng)；關(guān)鍵路徑

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

1　Petri網(wǎng)仿真

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

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

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

1、對(duì)結(jié)點(diǎn)i∈P，·i=?，則i稱源庫所；

2、對(duì)結(jié)點(diǎn)o∈P，o·=?，則o稱為匯結(jié)庫所；

3、對(duì)于每一個(gè)結(jié)點(diǎn)x∈P∪T而言，它必定都位于某一條從i到o的路徑上.

此時(shí)，可以認(rèn)為PN=(P,T,F)是工作流網(wǎng).

WF-net的有以下性質(zhì)：

1、只有唯一一個(gè)源庫所，即i；

2、也只有唯一一個(gè)匯結(jié)庫所，即o；

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

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

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

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

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

此時(shí)，可以認(rèn)為該過程是合理的.

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

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

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

圖1　模型映射示例

圖2　模型分解

構(gòu)造變遷-自由選擇子網(wǎng)距陣B2×13和變遷-資源距陣C，如下所示[6]：

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

下面其性能進(jìn)行分析.對(duì)應(yīng)于多維工作流網(wǎng)中的13個(gè)變遷可以得到μ={μ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ā)延遲均值的倒數(shù)，即μ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è)務(wù)實(shí)例到達(dá)速率.從圖中我們可以看出，資源R1參與變遷tA1，tA5的觸發(fā)，所以其平均服務(wù)速率為ηi=∑(μi× λti/∑λti)=0.183.通過同樣的計(jì)算可以得到R2，R3及R4的平均服務(wù)速率分別為0.75，0.33和0.25.由于資源R1的服務(wù)負(fù)載ρ1=ω1/η1=0.2/0.183=1.093>1，造成系統(tǒng)不穩(wěn)定，其配置顯然不滿足要求.如果我們?cè)黾訑?shù)量至2，ρ1=ω1/η1=0.2/(2× 0.183)=0.546<1，此時(shí)資源R1的配置能夠滿足系統(tǒng)穩(wěn)定性的要求.通過同樣的方式我們可以驗(yàn)證：資源R2，R3及R4的配置均滿足系統(tǒng)穩(wěn)定性的要求.

2　關(guān)鍵路徑優(yōu)化技術(shù)

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

1、順序結(jié)構(gòu)wt=∑(1/μt-λi)；

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

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

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

按圖3所示的規(guī)則將工作流模型轉(zhuǎn)換為樹形表達(dá)[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　基本工作流結(jié)構(gòu)的樹形表示和完成時(shí)間的計(jì)算方法

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　仿真機(jī)制及系統(tǒng)實(shí)現(xiàn)

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

指標(biāo)計(jì)算方法時(shí)間（小時(shí)）　　活動(dòng)時(shí)間=工作時(shí)間+等待時(shí)間（等待資源時(shí)間+阻塞時(shí)間+非活動(dòng)時(shí)間）按價(jià)值類型：成本=增殖活動(dòng)成本+業(yè)務(wù)增殖活動(dòng)成本+非增殖活動(dòng)成本按資源類型：成本=勞動(dòng)力成本+設(shè)備成本+原材料成本+其他按時(shí)間類型：成本=標(biāo)準(zhǔn)成本+超時(shí)成本過程性能（%）　　資源利用率=∑資源忙時(shí)間/（資源時(shí)間-非活動(dòng)時(shí)間-無效時(shí)間）成本（元）

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

圖4　工作流仿真機(jī)制

4　結(jié)束語

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

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

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

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

〔4〕高保強(qiáng).工作流仿真結(jié)果分析［J］.計(jì)算機(jī)工程，2010，36（10）：45-46.

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

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

TP311

A

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

2016-05-28

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