基于工作流程系统日志生成业务流程模型
tjdlut
摘要：工作流管理系统利用流程模型来管理业务流程模型，通常来说，该模型采用带有活动名称的图来表示。本文视活动的执行过程为一个时间间隔，并采用一种新的算法从系统日志集中生成业务流程模型。该模型图能够生成日志中所隐含的活动执行过程和活动和活动之间的依赖关系，并且能够保留活动中现存的平行性。
关键词：业务流程管理；工作流；工作流系统日志；流程模型
正文
1引言
对于公司来说建立起合适的业务流程模型是非常重要的，以自动化或者半自动化方式来管理流程能够大幅度提高业务执行的工作效率，降低成本，使公司更快地适应不断变化的需求和业务的增长[1]。因此，组建和管理业务流程的技术是当今一个非常活跃的研究领域。
工作流管理系统采用可视化信息流模型来监视和管理事先定义好的活动和任务。商业工作流系统和管理平台需要一个业务模型以执行动作、控制生产，等等。现今大多ERP/CRM产品采用嵌入工作流模型的方式来给业务流程建模。大多数企业中运行的信息系统中并不包含适用于该单位的业务流程模型，仅仅停留在对企业资源的操作上，因此，能够对企业业务流程建模的技术对于提高企业竞争力和提高企业在IT上的投资收益率非常重要。本文提出一种基于存在于工作流日志信息生成业务流程模型的方法。该模型采用向量图，图中的结点代表活动，从A结点到B结点的边代表在A活动结束和B活动开始之间有一个流程执行过程[2]。单独的一个业务流程模型里，流程执行过程所参与的边与边之间有一个布尔函数（0=false，1=true），该函数控制流是否通过该边。
2 模型特点
基于事件的模型和本模型不同的是，前者把一个活动的执行过程看作是一个单独的事件，而本模型将其看作是开始事件和终止时间的时间间隔，而这正是多数工作流系统日志中所记录的模式。通过这种方法，由于并发活动的生命周期是相互交叉的，我们可以识别处在一个单独流程执行过程中所包含的并发活动，而这正是基于事件的模型所不能发现的。此外基于工作流系统日志，本模型能够发现并发活动产生时所需的条件。
本模型定义了活动之间的因果关系以及描述了一种能够根据日志产生工作流图的算法。本模型的特点如下：
1） 完整性：在日志中所记录的每一个流程执行过程都依据该模型生成相应的流程图。
2） 正确性：日志中记录的所有依赖关系都存在于流程图中。
3） 保持并行性：如果在日志数据中体现出活动A和B是并发的，那么在生成的图中将会有两条路径，其中一条包含A而不含B，另一条包含B而不包含A[3]。
通过本文提出的算法，生成的流程图与原始的工作流图类似，但可能会产生一些多余边或者丢失一些边，多余或丢失边的数量依据日志的质量和大小而定，对于如何防止以上的错误的发生，现在仍无定论，只能提高日志的质量来保证生成流程图最大的准确性。
3 模型架构
一个工作流模型通常使用向量图来表示，向量图中包含代表活动的结点和向量边组成。在活动A和活动B之间有一个向量边代表在A执行后B能够立即执行；在这种情况下，边上的控制函数的值是1（true）。定义B是A的后继，A是B的前导。对于B是否能够在A执行后立即执行取决于AàB的控制函数的值（1代表能够执行，0代表不执行）[4]。在这个模型里，活动的执行被认为是原子性的，也就是说没有两个活动能够同时执行；一个业务流程就可以看作是串行的活动的集合。在下文中，本文将把这个模型扩展为更加精确的表达方式，其中，活动的执行被看作是时间轴上的间隔，而这两个间隔有可能有重叠（并发）。
首先定义工作流图的执行过程为一个线性化的流，这个流用一连串的活动来表示，例如A=a1,a2,……,an,该流以活动a1为起始点，以an为终点。在这个模型里，一个活动只能出现一次。
图1是一个简单的工作流模型图和两个有效的子流图。在流程（a）中，从A到C和从B到D的控制函数的值为0（false）。在流程（b）中从B到C的边上的值也是0。执行过程Execution（A，B，C，D）是在流程（a）和流程（b）中都是一个合法的，有效的过程，但是Execution(A,C,B,D)仅仅在流程（b）中是有效的[5]。
工作流图 流程（a） 流程（b）
图1 工作流模型图和两个有效流图
对于一个给定的工作流模型，定义以下连个条件：
[CA]在一个图中如果[a1,ai,aj,an]并且[ai,aj,ai,an] 成立那么ai和aj称为并发活动，也就是说两个执行过程中，其中一个过程里ai出现在aj前，在另一个过程里aj出现在ai前那么，ai，aj称为并发的活动。
[NS]在所有有效的执行过程里面，如果永远不出现ai=aj+1那么ai就不是aj的后继。
举例来说，在流程（b）中,B和C是并发活动，而D永远不是A的后继。
4 日志结构和间隔模型
工作流日志中包含监视流程执行的数据信息，每个执行过程由执行的活动按照时间顺序组成。WFMC提出的标准的日志格式包括每个活动的起始事件、终止事件。代数表达式为{ready, started, restarted, ended normally, force finished, terminated}。很明显，在一个执行过程中可能会包含噪声事件，比如一个forece finished的事件表明该活动含有噪声，那么我们可以将其删除掉[6]。如果一个事件是{started, restarted} 那么该事件就是起始事件；如果一个事件不是起始事件或者不是一个ready事件的话，那么该事件就是一个终止事件。
一个活动在它启动之前，它必须处于一个ready状态。一旦它启动了，那么它就应该能够正常结束，*结束或者消亡。一个执行过的活动的生命周期是从它的start状态到它的terminate事件的时间段，活动的扩展生命周期是readyàterminate的时间段。每个事件都代表在系统中的一次状态变化，比如，一个系统在start事件执行之前将会一直保持ready状态。
根据间隔模型可以将[CA]条件扩展如下：
[rCA] 对于一个给定的一系列活动事件，如果在活动ai和aj的扩展生命周期里面存在重叠，那么ai和aj就是一对并发的活动。
5 生成业务流程图
本章将描述如何从工作流系统日志生成一个业务流程图。一个图是由一系列执行或称产生的，活动执行过程中时间间隔交叉现象导致活动并发的发生[7]。在描述算法之前我们给出几个基本的定义：1）当前点集（Current Frontier,在以下简称为CF），下一点集（Next Frontier，以下简称NF），当前点集是最新加入图中的点的集合，这时他们的输出度为0。2）当前时间（Current Time,以下简称为CT），下一时间（Next Time，以下简称NT）。
算法：
图中第一个点是起始活动，第一个点是CF，它的终止事件的时间是CT。以下步骤一直执行到最后一个活动的终止事件的时间为CT。
1． NT= CT后第一个完成的事件的时间
2． 将NT和CT之间处于ready状态的活动所代表的点加入到图中，这些点作为NF。
3． 将CF中的每一个点和NF中的每一个点相连。
4． 把CF改为NT所包含的事件和NT后第一个处于ready状态的点之间所有完成的事件所代表的活动的点的集合[8]。把CT改为上面集合中最后处于完成状态的活动的终止时间。
5． 循环1à4
为了解释如上算法的含义，举例如下：
例1（A,A’,B,C,D,C’,E,B’,F,D’,F’,G,G’,E’,H,H’）
STEP1 STEP2
1. CF1=A,CT1=A’,NT1=C’; 1.CF2=C,CT2=C’,NT2=B’;
2. NF1=[B,C,D]; 2.NF2=E;
3. 
3.
4. CF2=C, CT2=C’. 4. CF3=B, CT3 = B’;
STEP3 STEP4
1. CF3=B, CT3=B’, NT3 =D’; 1. CF4=[D,F], CT4=F’, NT4= G’
2. NF3 =F; 2. NF4 =G;
3. 
3. 
4. CF4=[D,F], CT4 = F’. 4. CF5=[G,E], CT5=E’.
STEP5
1. CF5=[G, E], CT5= E’, NT5 = H’;
2. NF5=H;
3.
图2 例1的执行图
4. CF5=H,NT5=H’.
例2（A,A’,C,C’,F,E,E’,F’,H,H’）
图3 例2的执行图
例3（A,A’,D,D’,G,G’,H,H’）
图4 例3的执行图
6结论
本文提出的从工作流系统日志数据中生成业务流程的算法经实际检验中比其他同类方法更加迅速和精确，产生的冗余边和丢失边基本控制在5%以内，为了更好的减少误差，可以考虑在每个边上加上权重，用权重来表示执行和边之间的关系，这样噪声会更加少，此方法须进一步改进，最终会成为一套对如何正确完整地生成企业业务流程有很高参考价值的算法。
参考文献
[1] Agrawal, R., Gunopulos, D., Leymann, F.: Mining process models from workflow logs. In: Advances in Database Technology - EDBT’98, 6th International Conference on Extending Database Technology, Valencia, Spain, March 23-27, 1998,Proceedings. Volume 1377 of Lecture Notes in Computer Science., Springer (1998)
[2] Georgakopoulos, D., Hornick, M.: An overview of workflow management: From process modeling to workflow authomation infrastructure. Distributed and Parallel Database 3 (1995) 119–153
[3] Wastell, D., White, P., Kawalek, P.: A methodology for business process re-design:experiences and issues. Journal of Strategic Information Systems 3 (1994) 23–40
[4] Cook, J.E., Wolf, A.L.: Event-based detection of concurrency. In: Sixth International
Symposium on the Foundation of Software Engineering (FSE-6). (1998) 35–45
[5]. Hollingsworth, D.: The workflow reference model. Technical Report TC00-1003 issue 1.1, workflow management coalition, UK (1995)
[6] Ellis, C., Kkeddara, K.: A workflow change is a workflow. In: W.M.P. van der Aalst, J. Desel, and A. Oberweis, editors. Business Process Management: Models,Techniques, and Empirical Studies, volume 1806 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2000, Berlin, Germany, Springer-Verlag (2002) 45–63
[7] van der Aalst, W., van Hee, K.: workflow Management: Models, Methods, and Systems. Number TC00-1003 issue 1.1. MIT press, Cambridge, MA (2002)
[8] Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workflow evolution. In: In proceedings of ER 96, Cottubus, Germany (1996) 438–455