第四章分析工作流

工作流引论第四章分析工作流主要存在两种类型的工作流分析方法：定性分析和定量分析。定性分析（结构分析）：主要关心所定义过程在逻辑上的正确性，以及异常结构。定量分析：主要考察所定义过程的性能，其重点在于建立一些性能指标，比如平均完成时间，服务水平和能力利用率等。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上述六种情况汇总尽可能并行执行任务。争取提高资源弹性。尽可能按照处理时间为序来处理案例。可以使用类选