第四章分析工作流

工作流引論第四章分析工作流主要存在兩種類型的工作流分析方法：定性分析和定量分析。定性分析（結(jié)構(gòu)分析）：主要關(guān)心所定義過程在邏輯上的正確性，以及異常結(jié)構(gòu)。定量分析：主要考察所定義過程的性能，其重點在于建立一些性能指標，比如平均完成時間，服務(wù)水平和能力利用率等。2分析技術(shù)引入高級的信息系統(tǒng)后，業(yè)務(wù)的流程結(jié)構(gòu)會變得比較復(fù)雜。當(dāng)使用順序、并行、選擇、循環(huán)同時定義同一過程時，判斷過程的正確性可能會比較困難。4.1結(jié)構(gòu)分析定義過程時常見的錯誤：1任務(wù)沒有輸入和（或）輸出條件44.1結(jié)構(gòu)分析2死任務(wù)：任務(wù)永遠不能被執(zhí)行3死鎖：在到達end前發(fā)生了阻塞4活鎖：把案例帶進無休止的循環(huán)5當(dāng)?shù)竭_end后，仍有活動執(zhí)行6案例完成后，定義過程中仍然存在標記工作流過程只有一個start和一個end一個工作流網(wǎng)是合理的，它必須符合下面三個要求：1對應(yīng)于庫所start的每一個標記，最終會有且只有一個標記出現(xiàn)在庫所end中；2當(dāng)庫所end出現(xiàn)時，其他所有庫所都是空的3對每個變遷（任務(wù)），從初始狀態(tài)都能夠到達該變遷就續(xù)的狀態(tài)。第一條保證了案例一定會結(jié)束；第二條保證了一個案例一旦結(jié)束就不會有活動依然在處理它；第三條排除了死任務(wù)，也就是任何任務(wù)都有機會被實施。

84.1合理性如何來判定工作流網(wǎng)的合理性呢？1可達圖2活性有界性判斷3合理替換法Petri網(wǎng)一旦確定，被建模過程的可能行為就是確定的。繪制可達圖是描繪工作流行為的方法之一?？蛇_圖是一種有向圖，由節(jié)點和有向箭頭構(gòu)成。每個箭頭表示一種可能的狀態(tài)改變。每種狀態(tài)用一個元組表示。104.2可達性分析——可達圖傳統(tǒng)Petri網(wǎng)11claimrecordUnderconsiderationreadypaySendletter（a,b,c）表示；a代表claim中標記數(shù)量，b代表庫所bunder_consideration中的標記數(shù)量，c代表庫所

cready中的標記數(shù)量。通過此圖可以看出這個petri網(wǎng)有10個可達狀態(tài)，每個節(jié)點代表一種給出一個Petri網(wǎng)，其可達圖是確定的，因此可以使用計算機來構(gòu)造可達圖12claimrecordUnderconsiderationreadypaySendletter初始狀態(tài)最終狀態(tài)非確定性選擇狀態(tài)13

兩組信號燈協(xié)同：可達圖描述重復(fù)性過程yr1rg1gy1red1yellow1green1yr2rg2gy2red2yellow2green2X(0,0,1,1,0,0,0)(1,0,0,0,0,1,0)

(1,0,0,1,0,0,1)(0,1,0,1,0,0,0)(1,0,0,0,1,0,0)14兩組信號燈協(xié)同的可達圖改進后的兩組信號燈在petri網(wǎng)的start中放入一個標記，繪制可達圖進行如下檢測檢查可達圖是不是只有一個最終狀態(tài)最終狀態(tài)時只在end有一個標記每一個任務(wù)的實施是否都對應(yīng)了可達圖中的狀態(tài)轉(zhuǎn)換

使用可達圖判斷工作流網(wǎng)的合理性示例1：使用可達圖判斷工作流網(wǎng)的合理性c1c2c3c4c5c6c71大規(guī)模過程構(gòu)造可達圖需要大量的時間，沒有計算機的支持幾乎是不可能的2可達圖對于不合理過程定義的修改貢獻不大可達圖的局限性4.3計算機支持的方法c1c2c3c7t活性：對于變遷t，從初始狀態(tài)的任何狀態(tài)都能到達該變遷的就緒狀態(tài)，那么該petri網(wǎng)是活的有界性：如果每個庫所里的標記有上限，則該petri網(wǎng)是有界的交通燈模型是典型的活的且有界的如果一個工作流網(wǎng)添加上一個t*后，是活的且有界的，則這個工作流網(wǎng)是合理的。兩個著名特征假定開始有一組合理而且安全的工作流網(wǎng)，稱為“構(gòu)造塊”。如果能基于這一組構(gòu)造塊，通過對網(wǎng)進行一定次序的替換，得到我們的工作流網(wǎng)，則證明我們的網(wǎng)是合理且安全的214.4合理替換法如果W是合理的工作流網(wǎng)，那么經(jīng)過替換后V也是合理的。22合理且安全的網(wǎng)（合理的構(gòu)造塊）這也是合理的構(gòu)造塊26安全合理的過程27應(yīng)用AND結(jié)構(gòu)，讓任務(wù)a和任務(wù)b并行處理28對a應(yīng)用一個AND結(jié)構(gòu)對a應(yīng)用一個OR_split結(jié)構(gòu)29對a應(yīng)用一個OR_split結(jié)構(gòu)采用順序結(jié)構(gòu)：任務(wù)a后增加任務(wù)d30對a應(yīng)用一個順序結(jié)構(gòu)應(yīng)用順序結(jié)構(gòu),任務(wù)b后增加任務(wù)e31在b應(yīng)用一個順序結(jié)構(gòu)對任務(wù)b采用隱式OR_split結(jié)構(gòu)，增加任務(wù)f32對b應(yīng)用隱式選擇結(jié)構(gòu)對e應(yīng)用循環(huán)結(jié)構(gòu)，任務(wù)g被添加到工作流網(wǎng)中33對e應(yīng)用循環(huán)結(jié)構(gòu)采用順序結(jié)構(gòu)，任務(wù)e后增加任務(wù)h，最終得到最前面我們想構(gòu)造的工作流網(wǎng)。34對e應(yīng)用順序結(jié)構(gòu)這是一個合理構(gòu)造序列但是在工作流分析中，并非所有合理且安全的網(wǎng)都可構(gòu)造c1c2c3c4判別此網(wǎng)的合理性c1c2c3c4c5c6c7startend課堂習(xí)題1（1）過程定義正確么？

（2）有錯誤請指出4024131、如果c9是空的，就不能進行了；2、如果一個form被處理，evaluate產(chǎn)生為c7產(chǎn)生token，一個token就會留在c9；如果time_out發(fā)生，evaluate為c4產(chǎn)生一個token，c8,c4死鎖；3、如果c8先于c4產(chǎn)生token，process就不能進行了。42答案：三個圖都是錯的馬爾可夫分析法排隊論仿真444.5性能分析對給定的工作流，可以自動生成一個馬爾可夫鏈，利用它可以分析工作流某些方面。馬爾可夫鏈實際上就是增加了轉(zhuǎn)移概率的可達圖此方法的缺點是并不是每個方面的性能都能被分析出來，而且非常耗時。45馬爾可夫分析法排隊論適用于對系統(tǒng)的等待時間，完成時間和資源利用率等性能指標進行分析，因此用來分析工作流是非常合理的。單隊列系統(tǒng)但是，排隊論中的很多假設(shè)對工作流過程并不適合，例如對并行路由，通常無法用排隊論的成果。46排隊論仿真是一種靈活的分析技術(shù)，可以分析各種工作流。仿真最終歸結(jié)為跟蹤路徑，為此，要進行一定的概率進行路徑選擇。通過對BPR中應(yīng)用的分析技術(shù)進行研究，可以發(fā)現(xiàn)仿真是唯一可用的定量分析工具。仿真

排隊論（QueuingTheory），或稱等候線理論（WaitingLineTheory），是研究要求獲得某種服務(wù)對象所產(chǎn)生的隨機性聚散現(xiàn)象的一種數(shù)學(xué)理論和方法，它是運籌學(xué)的一個分支。所謂排隊，就是需要得到某種服務(wù)的對象加入等待的隊列，需要得到服務(wù)的對象泛稱為顧客，而從事服務(wù)的設(shè)施或人等泛稱為服務(wù)臺。顧客與服務(wù)臺構(gòu)成一個系統(tǒng)，成為服務(wù)系統(tǒng)。481排隊論模型概述

在一個服務(wù)系統(tǒng)中，若某一時刻顧客的數(shù)目超過服務(wù)臺的數(shù)目，則產(chǎn)生擁擠，這必然會導(dǎo)致一些顧客不能立即得到服務(wù)而需要等待。從而產(chǎn)生排隊現(xiàn)象，由于擁擠而產(chǎn)生排隊現(xiàn)象的服務(wù)系統(tǒng)稱為排隊系統(tǒng)。排隊論就是要解釋和反映各種擁擠現(xiàn)象的排隊系統(tǒng)的概率性規(guī)律，并借助相應(yīng)過程統(tǒng)計的推斷方法來解決有關(guān)排隊系統(tǒng)的最優(yōu)化問題。49在現(xiàn)實世界中，排隊系統(tǒng)是多種多樣的，從日常生活中的各種服務(wù)系統(tǒng)，諸如商店、收款處、營業(yè)柜臺、車站……以及各種生產(chǎn)系統(tǒng)、金融系統(tǒng)、運輸系統(tǒng)、交通系統(tǒng)……直到每個家庭的家務(wù)系統(tǒng)等等。排隊現(xiàn)象可謂司空見慣。排隊系統(tǒng)雖然千差萬別，然而它們確有一些共同的特征，能對其進行統(tǒng)一的處理。這些共同的特征是：顧客為了獲得某種服務(wù)而到達系統(tǒng)，若不能立即獲得服務(wù)而又允許排隊等待，則加入等待隊列，獲得服務(wù)后離開系統(tǒng)。50現(xiàn)在對于排隊系統(tǒng)普遍采用肯道爾（E.G.Kendall）于1953年提出（后經(jīng)他人擴展）的分類方法與記號。他按以下五個特征來確定一個排隊系統(tǒng)：輸入分布/服務(wù)分布/服務(wù)臺數(shù)/系統(tǒng)容量/顧客源數(shù)。例如M/M/S/∞/∞就表示泊松輸入、指數(shù)服務(wù)、s個并聯(lián)服務(wù)臺、系統(tǒng)容量為∞的排隊系統(tǒng)、顧客源數(shù)為∞的排隊系統(tǒng)。51概率論中常用的一種離散型概率分布。泊松分布P(λ)中只有一個參數(shù)λ，它既是泊松分布的均值，也是泊松分布的方差。在實際事例中，當(dāng)一個隨機事件，例如某電話交換臺收到的呼叫、來到某公共汽車站的乘客，以固定的平均瞬時速率λ(或稱密度)隨機且獨立地出現(xiàn)時，那么這個事件在單位時間（面積或體積）內(nèi)出現(xiàn)的次數(shù)或個數(shù)就近似地服從泊松分布。因此泊松分布在管理科學(xué)，運籌學(xué)以及自然科學(xué)的某些問題中都占有重要的地位。泊松分布泊松分布在電子元器件的可靠性研究中，通常用于描述對發(fā)生的缺陷數(shù)或系統(tǒng)故障數(shù)的測量結(jié)果。這種分布表現(xiàn)為均值越小，分布偏斜的越厲害。指數(shù)分布應(yīng)用廣泛，在日本的工業(yè)標準和美國軍用標準中，半導(dǎo)體器件的抽驗方案都是采用指數(shù)分布。此外，指數(shù)分布還用來描述大型復(fù)雜系統(tǒng)（如計算機）的平均故障間隔時間MTBF的失效分布指數(shù)分布比冪分布趨近0的速度慢很多,所以有一條很長的尾巴。指數(shù)分布很多時候被認為是長尾分布。指數(shù)分布的參數(shù)為λ，則指數(shù)分布的期望為1/λ，方差為(1/λ)的平方。指數(shù)分布指數(shù)分布冪律表現(xiàn)了一種很強的不平等性。*指數(shù)分布與冪律分布*隨機網(wǎng)絡(luò)與無標度網(wǎng)絡(luò)如果對呼叫中心的處理流程進行分析。我們不難發(fā)現(xiàn)，呼叫中心也是一個排隊系統(tǒng)，它具備排隊系統(tǒng)的基本特征。現(xiàn)將呼叫中心抽象成如圖的模型。58舉例：呼叫中心排隊論模型59下面研究呼叫中心電話輸入滿足怎樣的分布，我們隨機提取電話高峰時期兩個小時的電話來訪記錄，整理得到每分鐘到達的電話數(shù)量k和出現(xiàn)的頻數(shù)fk，詳情見表5.1：表5.1電話數(shù)量及頻數(shù)60電話輸入滿足怎樣的分布6162確認此呼叫中心排隊系統(tǒng)的輸入滿足參數(shù)的泊松分布。63下面研究呼叫中心的座席服務(wù)時間間隔滿足怎樣的分布，我們隨機提取200次座席服務(wù)時間的記錄，整理得到座席的服務(wù)時間與出現(xiàn)的頻數(shù)，詳情見表5.3：64服務(wù)時間間隔滿足怎樣的分布6566根據(jù)上表可計算出平均服務(wù)時間為：67查分布表確認此呼叫中心排隊系統(tǒng)的服務(wù)滿足參數(shù)的指數(shù)分布。68經(jīng)過上述的數(shù)據(jù)分析得出，該呼叫中心的排隊系統(tǒng)的輸入滿足泊松分布，服務(wù)滿足指數(shù)分布，且呼叫的到達和座席的服務(wù)相互獨立，因此可以得出如下結(jié)論：用戶的呼叫到達彼此之間相互獨立且都滿足參數(shù)為λ的泊松分布。座席的服務(wù)時間彼此相互獨立且滿足參數(shù)為μ的指數(shù)分布。呼叫中心的服務(wù)臺數(shù)量即座席的數(shù)量為m；呼叫中心的系統(tǒng)容量為k（k>=m）；呼叫中心系統(tǒng)提供排隊功能，排隊的最大數(shù)量為k-m。69如果用D.G.Kendall所規(guī)定的符號表示，該系統(tǒng)為一個參數(shù)為M/M/m/k的無限源有限容量的混合制排隊模型。通過該模型，我們需要研究呼叫中心的運行效率，評估和確定隨機服務(wù)系統(tǒng)的參數(shù)，以判斷其設(shè)計結(jié)構(gòu)和運營結(jié)構(gòu)是否合理，研究設(shè)計改良措施等等。主要需要考核的性能指標如表5.5所示：707172

現(xiàn)令m=1，也就是資源為一M/M/1排隊模型對于任務(wù)x，每小時有8個案例到達，處理此任務(wù)的資源平均每小時能處理10個案例。請計算1該資源的利用率。

2此過程中平均案例數(shù)量（即平均隊列長度）。平均系統(tǒng)時間（案例完成時間）

平均等待時間（也是完成時間-處理時間）

例1根據(jù)題意：

λ=8

μ=10（每個案例6分鐘）解：ρ=λ/μ=8/10=80%L=ρ/(1-ρ)=0.8/0.2=43S=1/(μ-λ)=?=0.5h=30minW=L/μ=ρ/(μ-λ)

=0.8/(10-8)=0.4(h)=24minS=W+6如果ρ提高到95%，則μ=10/95%=10.526S=1/(μ-λ)=1/0.526=1.9h完成時間將變成接近兩個小時，而實際執(zhí)行時間只有6min下表說明平均資源利用率與平均隊列長度之間的關(guān)系

利用率ρ對完成時間S的影響772馬爾可夫過程的概念1.馬爾可夫性(無后效性)馬爾可夫性或無后效性.即:過程“將來”的情況與“過去”的情況是無關(guān)的.782.馬爾可夫過程的定義具有馬爾可夫性的隨機過程稱為馬爾可夫過程.用分布函數(shù)表述馬爾可夫過程恰有79或?qū)懗刹⒎Q此過程為馬爾可夫過程.3.馬爾可夫鏈的定義

時間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾可夫鏈,簡記為80馬爾可夫過程的概率分布研究時間和狀態(tài)都是離散的隨機序列1.用分布律描述馬爾可夫性有81稱條件概率說明:

轉(zhuǎn)移概率具有特點2.轉(zhuǎn)移概率由轉(zhuǎn)移概率組成的矩陣稱為馬氏鏈的轉(zhuǎn)移概率矩陣.此矩陣的每一行元素之和等于1.它是隨機矩陣.823.平穩(wěn)性有關(guān)時,稱轉(zhuǎn)移概率具有平穩(wěn)性.同時也稱此鏈是齊次的或時齊的.稱為馬氏鏈的n步轉(zhuǎn)移概率83一步轉(zhuǎn)移概率特別的,當(dāng)k=1時,一步轉(zhuǎn)移概率矩陣的狀態(tài)記為P84解例2858687

由以上討論知,轉(zhuǎn)移概率決定了馬氏鏈的運動的統(tǒng)計規(guī)律.因此,確定馬氏鏈的任意n步轉(zhuǎn)移概率成為馬氏鏈理論中的重要問題之一.第一種方法是構(gòu)造與“可達圖”同構(gòu)的馬爾可夫鏈，并添加適當(dāng)?shù)某杀竞瘮?shù)，此方法的缺點是構(gòu)造的馬爾可夫鏈需要計算機的支持而且非常耗時第二種方法是基于“合理構(gòu)造塊”來確定每個任務(wù)被執(zhí)行的次數(shù)88馬爾可夫鏈在工作流中的應(yīng)用例3

平均每天有50個新案例到達start，計算每一個任務(wù)需要處理的次數(shù)。其中，assess評估時，有63%在完成后得到了肯定，27%得到了否定，剩下10%需要重新評估。計算每個任務(wù)執(zhí)行的次數(shù)

（a）計算性能指標：每個資源的利用率；每個任務(wù)的平均等待時間和完成時間；流程的平均等待時間和完成時間（b）task2是個檢查任務(wù)，管理人員有選擇的執(zhí)行，如果只檢查25%的案例，那么task2的平均服務(wù)時間是6mins。再次計算性能指標。綜合性能分析1（a）計算性能指標：每個資源的利用率；每個任務(wù)的平均等待時間和完成時間；流程的平均等待時間和完成時間（b)任務(wù)task1a和task1b相結(jié)合，兩個資源也合作，每次共同處理一個案例，平均處理時間是2分鐘，再次計算性能指標，性能提高還是下降？綜合性能分析2任務(wù)1a：λ=10 ρ=0.833 S=0.5μ=12 L=5 W=0.04167任務(wù)1b：λ=10 ρ=0.33 S=0.05μ=30 L=0.5 W=0.0166任務(wù)2：λ=20 ρ=0.66 S=0.1μ=30 L=2 W=0.066總共：ST=1/2*0.5+1/2*0.05+0.100=0.375（22.5分鐘）任務(wù)1：λ=20 ρ=0.66 S=0.100μ=30 L=2 W=0.066任務(wù)2：λ=20 ρ=0.66 S=0.100μ=30 L=2 W=0.066總和：ST=0.1+0.1=0.2(12分鐘)△=-10.5分鐘我們總是假設(shè)每個資源類的資源數(shù)量已經(jīng)確定，而實際并不是這樣；資源規(guī)劃總要基于特定的資源需求，資源規(guī)劃說明每個時期都需要什么資源以及資源的類型；資源規(guī)劃分為短期規(guī)劃和長期規(guī)劃；如果能夠預(yù)測新案例的到來，就很容易估算資源的分配原則。984.5資源規(guī)劃63%的案例在assess完成后得到肯定，27%的案例得到否定，剩下的10%需要重新評定。最后70%被肯定，30%被否定。99例4100record、collect、file為自動執(zhí)行，不需要耗費資源和時間，則每個task每天平均耗用的分鐘數(shù)如下101102資源類組成和案例對資源類的需求任務(wù)角色組織單元recordcontact-clientcontact-dept.collectassesspaysend-letterfile-EmployeeEmployee-AssessorEmployeeEmployee--ComplaintsComplaints-ComplaintsFinancesComplaints-資源數(shù)量計算：資源利用率=每天完成的分鐘數(shù)/(全天工作時間x資源數(shù))Finances平均每天需要完成的分鐘數(shù)為350所以80%=350/N(60x8)N=0.91資源類資源EmployeeJohnJimLizJackMandyCarlAssessorMandyCarlComplantsJohnJimMandyCarlFinancesLizJack1使用馬爾可夫鏈計算每個任務(wù)的單位工作量2依據(jù)“資源分類”計算每種資源需要的單位總工作量3使用“排隊論”的公式，依據(jù)“資源利用率”計算所需的資源個數(shù)4根據(jù)計算結(jié)果重新分配資源資源規(guī)劃的計算步驟：仿真是一種靈活的分析技術(shù)，可以分析各種工作流。仿真最終歸結(jié)為跟蹤路徑，為此，要基于一定的概率進行路徑選擇。通過對BPR中應(yīng)用的分析技術(shù)進行研究，可以發(fā)現(xiàn)仿真是唯一可用的定量分析工具。通過一下案例進行分析1063仿真圖中資源無彈性，可計算得資源利用率為80%使用仿真的方法（也可使用排隊論M/M/2，但計算公式不能使用原來介紹的公式），可得出案例的平均完成時間是22.2分鐘，但實際上只有8分鐘在工作107案例分析：情況1（基本串聯(lián)）實現(xiàn)并行后，使用仿真的方法可得出案例的平均完成時間是15分鐘，資源的利用率不變，但完成時間縮短了7分鐘108情況2

并聯(lián)有時候把兩個任務(wù)合并也是有益的，現(xiàn)把task1和task2合并成task12，新任務(wù)的處理時間是7mins，我們假定合并的任務(wù)比原來執(zhí)行兩個分離的任務(wù)少花費1min（節(jié)省預(yù)熱時間），此時平均資源利用率降低到70%使用仿真的方法可得出案例的平均完成時間是9.5分鐘這種顯著改進的原因是提高了資源的彈性109情況3

任務(wù)

合并110情況4：彈性資源

為了說明彈性資源的影響，現(xiàn)把task1和task2的資源合并，使用仿真的方法可得出案例的平均完成時間是14分鐘，與第一種情況對比提高了6分鐘111情況5：類選法仿真后平均完成時間上升到31.1分鐘，明顯惡化了類選法是一個早在BPR和WFM出現(xiàn)前就存在的術(shù)語。戰(zhàn)爭或者天災(zāi)大量出現(xiàn)傷亡人員（排隊）時，可以根據(jù)種類和受傷的程度進行選擇和優(yōu)先處理分類，能夠起到良好的效果。再比如在超市結(jié)帳時。兩種情況適合類選法：專門資源的分配降低了平均處理時間小顧客（時間短）不用等待大顧客（時間長），降低了總平均等待時間情況5的類選法之所以起不了好的效果是因為降低了資源的彈性類選法（1）超市引入類選法總能縮短時間是因為那些購買了少量東西的顧客不需要等待大宗購買的顧客，在這種情況下引入了優(yōu)先級的原則。優(yōu)先級原則可以單獨使用而不采用類選。見情況6優(yōu)先級原則114情況6優(yōu)先級原則，仿真后處理時間縮短為14分鐘描述平均完成時間平均處理時間平均等待時間1Sequential串行

22.28.014.22Parallel并行

154113Composition合并

9.57.02.54Flexibilization彈性

14.08.06.05Triage類選

31.18.023.16Prioritization優(yōu)先級

14.08.06.0115上述六種情況匯總盡可能并行執(zhí)行任務(wù)。爭取提高資源彈性。盡可能按照處理時間為序來處理案例。可以使用類選