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

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

cready中的標記數量。通過此圖可以看出這個petri網有10個可達狀態，每個節點代表一種給出一個Petri網，其可達圖是確定的，因此可以使用計算機來構造可達圖12claimrecordUnderconsiderationreadypaySendletter初始狀態最終狀態非確定性選擇狀態13

兩組信號燈協同：可達圖描述重復性過程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兩組信號燈協同的可達圖改進后的兩組信號燈在petri網的start中放入一個標記，繪制可達圖進行如下檢測檢查可達圖是不是只有一個最終狀態最終狀態時只在end有一個標記每一個任務的實施是否都對應了可達圖中的狀態轉換

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

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

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

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

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

2此過程中平均案例數量（即平均隊列長度）。平均系統時間（案例完成時間）

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

例1根據題意：

λ=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完成時間將變成接近兩個小時，而實際執行時間只有6min下表說明平均資源利用率與平均隊列長度之間的關系

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

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

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

由以上討論知,轉移概率決定了馬氏鏈的運動的統計規律.因此,確定馬氏鏈的任意n步轉移概率成為馬氏鏈理論中的重要問題之一.第一種方法是構造與“可達圖”同構的馬爾可夫鏈，并添加適當的成本函數，此方法的缺點是構造的馬爾可夫鏈需要計算機的支持而且非常耗時第二種方法是基于“合理構造塊”來確定每個任務被執行的次數88馬爾可夫鏈在工作流中的應用例3

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

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

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

任務

合并110情況4：彈性資源

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

22.28.014.22Parallel并行

154113Composition合并

9.57.02.54Flexibilization彈性

14.08.06.05Triage類選

31.18.023.16Prioritization優先級

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