Analyzing-Workflows-课件.ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,Analyzing Workflows,Outline,ANALYSIS TECHNIQUES,REACHABILITY ANALYSIS,STRUCTURAL ANALYSIS,Soundness,Method with computer support,Method without computer support,PERFORMANCE ANALYSIS,CAPACITY PLANNING,Method to calculate capacity requirements,Some basic queuing theory to take variability into account,ANALYSIS TECHNIQUES,The process should contains,no grave errors,and be designed that the,completion times,of and,capacity required,for cases are kept,as small as possible,.,By,parallelizing,tasks,completion times can usually be reduced.,ANALYSIS TECHNIQUES,It is useful to,analyze,it thoroughly prior to its enactment.In doing so,we differentiate between the analysis of,The,qualitative,aspects,and,mainly concern the,logical correctness,of the defined process.,The,quantitative,aspects,of workflows.,mainly concern the,performance,of the defined process.,ANALYSIS TECHNIQUES,Begin with a simple technique designed to illustrate all the states attainable in a case.,The errors which can be made when drawing up the definition of a process.,Based upon the structure of the underlying Petri net,we can decide whether a process definition is correct.,ANALYSIS TECHNIQUES,C,oncentrate upon the analysis of quantitative aspects.,Using a number of examples,to,show how,to,improve the performance of existing processes.,S,tudy the subject of capacity planning.,REACHABILITY ANALYSIS,As learned in Chapter 2,a process can,be,define,d,in terms of a Petri net.,REACHABILITY ANALYSIS,(Cont.),One way to illustrate the behavior is to draw up a,reachability,graph,.,Non-deterministic choice,End state,(,a,b,c,),where,a:,the number of tokens in the place,claim,b:,the number in,under_consideration,and,c:,the number in,ready,.,REACHABILITY ANALYSIS,(Cont.),Reachability,graph can,embody the behavior of the process being modeled,.,We can compile a,reachability,graph,shows that Petri nets are an unambiguous and precise means of description.,We used the network shown in,Fig 4.4,to model the traffic lights at the junction of two one-way streets.,A 7-tuple,shows the number of tokens in,red1,green1,y,ellow1,red2,green2,yellow2,and,x,respectively.,REACHABILITY ANALYSIS,(Cont.),the traffic lights,operate safely,:in every possible state at least one of the sets of lights is at red.,it is also possible that,the first set always changes to green,while the second set remains constantly at red.,Can ensure that each set of lights,changes to green in turn,.,Fig 4.6,shows how this can be modeled.,REACHABILITY ANALYSIS,(Cont.),REACHABILITY ANALYSIS,(Cont.),REACHABILITY ANALYSIS,(Cont.),It is easy to work out that the,reachability,graph associated with Fig 4.6 has a total of six states.,Just as we can verify the correct operation of traffic lights using the,reachability,graph,we can use it to determine the,correctness of a workflow,.,Business processes generally had a simple structure.,By using databases and networks,information can be shared.Because different people can,work on the same case at the same time,it is no longer necessary for tasks to be performed sequentially.,STRUCTURAL ANALYSIS,STRUCTURAL ANALYSIS,But the use of sequential,parallel,selective and iterative routing in the same process can make it very difficult to assess the correctness of the defined process.,STRUCTURAL ANALYSIS,(Cont.),STRUCTURAL ANALYSIS,(Cont.),STRUCTURAL ANALYSIS,(Cont.),Common,errors,during defining a process:,Tasks without input and/or output conditions.,Dead tasks:tasks which can never be carried out.,Deadlock:the jamming of a case before the condition end is reached.Livelock,:the trapping of a case in an endless cycle.,Activities still take place after the condition end is reached.,There remain tokens in the process definition after the case has been completed.,STRUCTURAL ANALYSIS,(Cont.),Tasks without input and/or output conditions.,When a task has no input conditions,it is,unclear when it may be performed,.,When a task has no output conditions,it,does not contribute to the successful completion,of a case and so it can be dropped.,STRUCTURAL ANALYSIS,(Cont.),Situation A in Fig 4.8 contains one task without input conditions(,task4,)and one without output conditions(,task5,).,STRUCTURAL ANALYSIS,(Cont.),Dead tasks:tasks which can never be carried out.,It is obvious that a process definition containing,dead tasks,is undesirable.,STRUCTURAL ANALYSIS,(Cont.),In situation B,task2,can never be performed;the same applies to,task3,in situation D.,STRUCTURAL ANALYSIS,(Cont.),Deadlock:the jamming of a case before the condition end is reached.,If,task1,in situation B places a token in one of the two uppermost places,then the case will,wait ad infinitum,for,task2,.,Only if,task1,delivers a token directly to the place,end,will this deadlock be avoided.,STRUCTURAL ANALYSIS,(Cont.),In situation D a token can be jammed waiting for,task3,.,STRUCTURAL ANALYSIS,(Cont.),Livelock,:the trapping of a case in an endless cycle.,In situation C,every case will,remain ad infinitum in the cycle,consisting of,task2,and,task3,.There thus exists iterative routing without an opportunity to escape.,STRUCTURAL ANALYSIS,(Cont.),Activities still take place after the condition end is reached.,A good process definition has a clear beginning (the condition,start,)and end(the condition,end,).,Once the condition,end,is reached,no more tasks should be carried out,.,STRUCTURAL ANALYSIS,(Cont.),In situation C,task2,and,task3,will be fired after the condition,end,is reached.In this way,an infinite number of tokens will reach the place,end,.This is clearly an undesirable situation.,STRUCTURAL ANALYSIS,(Cont.),There remain tokens in the process definition after the case has been completed.,Once a token appears in the place,end,all other,references to the case,must have disappeared,.,STRUCTURAL ANALYSIS,(Cont.),In situation D,if the case is completed as a result of the firing of,task2,there will remain a token in one of the places before,task3,.,STRUCTURAL ANALYSIS,Soundness,E,very process must meet:,A process contains,no unnecessary tasks,and every case submitted to the,process must be completed in full,and with,no,references to it(that is,case,tokens)remaining,in the process.,STRUCTURAL ANALYSIS,Soundness,T,he,soundness,property of a process,STRUCTURAL ANALYSIS,Soundness,A sound workflow net must fulfill 3 requirements:,For each token put in the place,start,one(and only one)token eventually appears in the place,end,;,Every case will be completed successfully over a period of time.,When the token appears in the place,end,all the other places are empty;,Once the case is completed,no references to it will remain in the process.,For each transition(task),it is possible to move from the initial state to a state in which that transition is enabled.,Excludes dead tasks;that is,each task can in principle be carried out.,STRUCTURAL ANALYSIS,Soundness,whether a given process corresponds to a sound workflow net?,first check,whether,the Petri net representing the process,is a workflow net,.,using a,reachability,graph to check the three soundness requirements,The first two requirements are checked by confirming that the,reachability,graph has only one final state,and that this is one in which there is precisely one token in,end,.,To check the last requirement,we examine whether there is for each task a state transition in the,reachability,graph which corresponds to the firing of that task.,STRUCTURAL ANALYSIS,Soundness,Two drawbacks attached to this approach:,The construction of the,reachability,graph for large-scale processes can take up,a lot of computer time,.,The,reachability,graph provides little support in repairing a non-sound process definition.,there are techniques available for Petri nets which do not suffer from these drawbacks.,The first method is based on advanced computer support;,The second one can be used manually.,STRUCTURAL ANALYSIS,Method without computer support,The translation of soundness to,liveness,and,boundness,allows for the application of efficient analysis techniques.,We add one requirement to good workflow nets in addition to soundness:,the workflow nets are also,safe,which means that,the number of tokens in each place will never be larger than one,.(This means that they are bounded by value one.),STRUCTURAL ANALYSIS,Method without computer support,Suppose we have some set of sound and safe workflow nets,called“,building blocks,”to start with.,If it is possible to derive the workflow net under consideration by a sequence of substitutions of nets from this set of building blocks,then we have proved that our net is sound and save as well.,STRUCTURAL ANALYSIS,Method without computer support,STRUCTURAL ANALYSIS,Method without computer support,STRUCTURAL ANALYSIS,Method without computer support,STRUCTURAL ANALYSIS,Method without computer support,F,ind the derivation presented in the subsequent Figs.The method starts with the,basic building block,shown in 4.13.,STRUCTURAL ANALYSIS,Method without computer support,In the,1,st step,the AND construct is applied to,put task,b,in parallel with task,a,.,The resulting workflow net is shown in Fig 4.14.,(,applied the,AND construct,in Fig 4.11 with,x=a,and,y=b,.,),STRUCTURAL ANALYSIS,Method without computer support,In the,2,nd step,the,explicit OR-split,construct is applied to,a,i.e.,the explicit OR-split“pattern”shown in Fig 4.11 is applied with,x=a,and,y=c,.,The resulting workflow net,:,STRUCTURAL ANALYSIS,Method without computer support,In the third step,apply the,sequence construct,:Task,a,is followed by,task,d,.,STRUCTURAL ANALYSIS,Method without computer support,Then,the,sequence construct,is applied to,b,.,STRUCTURAL ANALYSIS,Method without computer support,In the,5,th step an,implicit OR-split construct,is applied to,b,with the addition of,task,f,as result.,STRUCTURAL ANALYSIS,Method without computer support,Then,the,iteration construct,is applied to task,e,.As a result,task,g,is added to the workflow net.,STRUCTURAL ANALYSIS,Method without computer support,Finally,the,sequence construct,is applied to task,e,.,The resulting workflow net,:,STRUCTURAL ANALYSIS,Method without computer support,Not all sound and safe nets have a derivation as is shown in the example presented in Fig 4.21.,STRUCTURAL ANALYSIS,Method without computer support,P,erformance,quantitative aspects as,completion times of cases,the number of cases which can be processed per time unit,the utilization of staff,and,the percentage of cases which can be completed within a preset standard time,.,PERFORMANCE ANALYSIS,Queuing theory.,the analysis of systems in which the emphasis is placed upon such performance indicators as,waiting times,completion times and utilization of capacity.,In a workflow,there occur,queues waiting for resources,which cannot process a particular inflow of cases immediately.,If we wish to evaluate the entire workflow,then we need to consider a network of queues.,disadvantage,:,many of the assumptions used in queuing theory are not valid for workflow processes.,EX,:in the presence of,parallel routing,.,PERFORMANCE ANALYSIS,Cont.),Simulation.,a very flexible analysis technique.,almost always possible to use it to analyze a workflow.,simulation boils down to the following of a path in the,reachability,graph.In doing so,particular choices are made based upon various distributions of probability.,results in a better insight into the operation of the process being modeled.,the establishment and analysis of a model for a detailed simulation can be a,time-consuming,business.,processing of simulation results requires thorough,statistical knowledge.,PERFORMANCE ANALYSIS,(Cont.),To illustrate the use of an analysis technique like simulation,we shall use the process definition shown in Fig 4.24.,24 case(,每小時到達數目,),60,分鐘,/4=15 case(,一小時處理,15case),15 case x 2 resource=30 resource(,一小時需要,30,資源服務,),24/30=0.8(,平均一個,case,的資源利用,),利用負指數分配得到完成時間,=22.2,分鐘,(14.2,分鐘是等待時間，,8,分鐘是執行時間,),PERFORMANCE ANALYSIS,(Cont.),parallel process,reduce completion time with the same resource,completion time approximately 15 minutes.,PERFORMANCE ANALYSIS,(Cont.),combine two tasks into one larger tasks,average processing time for this new task is 7 minutes(elimination of set-up time),resource-capacity utilization has fallen to 70 percent,completion time=9.5 minutes(waiting time=9.5-7=2.5 minutes),consume resource=4,PERFORMANCE ANALYSIS,(Cont.),positive influence of resource flexibili,ty,average completion time is only 14.0 minutes,waiting time has fallen from 14.2 to 6 minutes,PERFORMANCE ANALYSIS,(Cont.),assumed that the cases are indistinguishable from one another,easy case takes an average of 2.66 minutes,hard case takes an average of 8 minutes,25 percent of the cases are classified as hard,75 per cent as easy,the principle also known as,triage,the average completion time rises to no less than 31.1 minutes!,PERFORMANCE ANALYSIS,(Cont.),PERFORMANCE ANALYSIS,(Cont.),There are two circumstances in which triage can be useful:,(1)when the allocation of specialized resources reduces the average processing time,(2)when small-scale clients no longer have to wait for large-scale ones to be processed,which reduces the overall average waiting time.,PERFORMANCE ANALYSIS,(Cont.),Fig 4.29 shows a situation in which for each task the easy cases(average processing time=2.66 minutes)are given priority over the hard ones(average processing time of 8 minutes).,average completion time of approximately 14 minutes,So,prioritization rules,can also deliver considerable savings in completion time.,PERFORMANCE ANALYSIS,(Cont.),PERFORMANCE ANALYSIS,(Cont.),Fig 4.30 lists all the situations again in summary.,PERFORMANCE ANALYSIS,(Cont.),CAPACITY PLANNING,The,capacity plan,is always based upon a particular,capacity requirement,.,The plan shows what resources,and of which type,are needed for each period.Capacity planning may be both short term and long term.,Capacity planning may be both short term and long term.,It is easy to estimate the capacity requirement.,To illustrate this,Fig 4.31 shows the average processing time for each task.,CAPACITY PLANNING,(Cont.),If we assume that 50 new cases arrive each day,then we can calculate the capacity requirement for each task.,Fig 4.32 shows that,assess,requires the most capacity.,CAPACITY PLANNING,(Cont.),Based upon the capacity requirement per task,we can calculate the capacity requirement of each resource class.,K,now from which resource class a required resource will come.,Fig 4.33 shows the capacity requirement per resource class.,CAPACITY PLANNING,(Cont.),Method to calculate capacity requirement,To determine the capacity required it is important to know the average number of times each task is executed.,How to calculate the average number of times each task is executed?,1.Markov chain,2.Design patterns,as Fig 4.34,Design patterns,Queuing Theory,針對某特定問題來分析，其基本型式都是導出一組公式，以分析某些現象，例如：,資源的使用率,(,),系統內的,case,數目,(,L,),等待時間,(,W,),資源的總工作時數,(,S,),等候線系統,F,ormula,of,Queuing Theor