业务流程的时延预测多类型队列挖掘方法

曹芮浩，方贤文，王晓悦

(安徽理工大学理学院，安徽 淮南 232001)



业务流程的时延预测多类型队列挖掘方法

曹芮浩，方贤文，王晓悦

(安徽理工大学理学院，安徽 淮南 232001)

过程挖掘是业务流程管理的核心内容之一。现有的方法多是基于控制流观点进行过程挖掘的，但是在挖掘存在时延的业务流程时，此方法存在一定的局限性。目前基于队列观点进行过程挖掘的方法，为挖掘存在时延的流程提供了定量分析的技术支持，但是在多类别队列挖掘方面存在不足。笔者针对G/M/s+M，D/M/c+M和M/M/1三种不同的队列类型提出不同的时延预测方法，并且将服务流程中不同的顾客类别对时延预测产生的影响考虑在内，对特定顾客进行基于队列长度的时延预测。同时提出了通过总结时延数据得到事件的行为信息，以此优化初始流程模型的方法。文章提出的多类别队列挖掘方法，针对目前队列挖掘方法在考虑多队列类型方面的不足进行了完善，同时能运用在优化流程模型方面。最后通过实例验证方法的有效性。

队列挖掘；Petri网；时延预测；排队论

业务流程管理在各个领域都发挥着重要的作用，它不仅为企业准确、高效运行提供保障，并且对业务的运行具有指导意义。特别是在服务行业，业务流程管理在提高服务效率、降低服务成本、提高顾客的服务体验方面都发挥着重要的作用，因此如何运用过程挖掘、如何获得更准确、更完整的流程模型一直都是国内外关注的研究课题。

目前的过程挖掘的方法，多是基于控制流的观点，即通过对日志序列进行定性的分析，抽象出业务流程的模型。例如最早由vander Alst等学者在文献[1]中提出的挖掘方法。随后，国内外学者针对完善流程挖掘方面做了很多的创新，例如运用概率行为关系挖掘业务流程[2]，基于行为轮廓挖掘业务流程的方法[3]等。但是针对存在时延的业务流程挖掘方面，现有的方法存在局限性。同时由于现有方法的理论基础的约束，难以为模型的定量分析提供技术支持。Arik Senderovich提出的运用排队论的观点对业务流程进行挖掘的方法，在解决这一问题方面提供了创新的、有效的思路。A.Senderovich根据顾客类别数量的区分，在文献[4]中提出针对单一顾客类型的服务流程进行队列挖掘的方法，在文献[5]中提出针对多顾客类型的服务流程进行队列挖掘的方法。运用文献中的方法，不仅能够抽象出合理性高的模型，同时能够准确地反映出事件在存在时延的业务流程中真正的执行状态。但是，在针对多类别的排队系统进行队列挖掘方面，目前的方法存在不足。

就此，本文结合排队论的相关知识[6]，通过对G/M/s+M，D/M/c+M和M/M/1三种不同的队列系统的研究，提出了基于这三种不同类别的排队系统的队列挖掘方法。具体方法是在某一时刻下对特定顾客进行基于队列长度时延预测，通过顾客接受服务的平均时间以及服务台数量等参量对特定顾客接受服务的时延进行预测。该方法中的队列长度是运用排队论观点，结合顾客到达队列时间的概率分布和服务时间的概率分布进行计算得到的，所以不同的队列系统也就具有不同的队列长度，也就体现出不同的时延预测方法。因此文章针对目前队列挖掘在考虑队列类型方面的不足进行了完善。同时，将顾客的不同类别对时延预测产生的影响也考虑到多类别队列挖掘方法中。其次，文章中提出了利用完善后的多类别队列挖掘方法在流程模型挖掘方面的应用(优化初始模型)，最后通过实例检验了此方法和应用的有效性。

1 基本概念

在这一部分主要引出文章中需要的一些基本的概念。

定义1[7](Petri网) 满足下列条件的三元组N=(S,T,F)称为一个Petri网：

-S是有限库所集，T是有限变迁集；

-S≠Ø,T≠Ø,且S∩T=Ø；

-F⊆(S×T)∪(T×S)表示流关系。

定义2[8](弱序关系) 设(N,[i])是一个工作流系统，弱序关系≻⊆T×T包括所有活动变迁对(x,y)，若存在j∈{1,…,n-1}，并且j

定义3[8](行为轮廓) 设(N,[i])是一个工作流系统，变迁对(x,y)满足下面三种关系：

-交叉序‖，当且仅当x≻y∧y≻x；

这三种行为关系的集合BP={→,‖,+}称为工作流系统的行为轮廓。

由于本文的重点在于介绍运用排队论的观点进行过程挖掘，而关于Petri网和行为轮廓的相关知识是在过程挖掘之后的建模环节来运用，同时在文献[7,8]中对Petri网的结构，性质等以及行为轮廓相关概念做了详细的介绍，这里就不再详细给出了。为了针对存在时延的流程模型进行队列挖掘，下面给出服务流程中的基本概念。

定义4[5](事件) 满足下列条件的四元组S=(τ,ι,ε,ξ)称为服务流程的事件。其中：

-τ:S→N+,表示事件的时间戳.

-ι:S→N+,表示事件的唯一标识.

-ε:S→E={qArrive,qAbandon,sStart,sEnd}，表示服务过程.

-ξ:S→C，表示顾客的类型.

在定义4中，τ表示特定事件在服务流程中发生的时刻；ι表示那些进入系统，等待接收服务的顾客，为了方便记录通常赋予其某个特定的自然数；ε表示顾客进入系统之后的状态，其中包括进入队列，放弃队列，开始服务，服务结束；ξ表示顾客的类型，这决定了顾客如何接受服务。

定义5[5](服务日志) 设事件的迹Π⊆S*，如果〈s1,s2,…sw〉∈Π都有ι(si)=ι(sj)，且对于1≤i≤j≤w有τ(si)≤τ(sj).则称迹Π为一条服务日志。

所谓队列挖掘，就是在特定时刻下对特定顾客运用队列的观点进行时延预测。而这种的队列观点是建立在服务日志的基础上。因为服务日志能够反映出在服务流程执行过程中排队的事件的服务状态和它们之间关系。

2 基于不同类别的排队系统进行队列挖掘

在这一部分中，根据排队论的知识以及Kendall在文献[9]中提出的关于队列系统的符号表示方法A/B/C/x/y/z，将现实生活中的队列系统分类。其中A表示顾客相继到达时间的概率分布，B表示服务时间的概率分布，C表示服务台的个数，x表示系统容量(队列长度)，y表示顾客源数量，z表示服务规则。本文结合实际情况，选取三种排队系统，针对特定顾客进行时延预测。其中包括：G/M/s+M表示的是顾客到达时间的概率分布为泊松分布，顾客服务时间的概率分布为指数分布，并且与间隔时间是相互独立的，服务台个数为s，队列容量是无限的，服务规则是“先到先得”，顾客的放弃队列满足指数分布的排队系统；D/M/c+M表示的队列系统是：顾客到达时间为定长，服务时间为指数分布，服务台个数为c，队列容量是无限的，服务规则是“先到先得”，顾客的放弃满足指数分布排队系统；M/M/1表示的是顾客到达时间与服务时间的概率分布都满足指数分布，不考虑放弃队列的，单服务台的排队系统。

图1给出了不同类型的排队系统的结构。

图1 多类型排队系统结构图

图1(a)中根据顾客到达时间不同的概率分布，可以表示出G/M/s+M型和D/M/c+M型两种队列系统的结构，同时考虑了放弃排队的情况。图1(b)表示了单服务台且没有放弃队列情况的排队系统的结构。另外队列系统的排队法则并不单一，除了“先到先得”外还有“后到先得”(例如流水线生产中先选取后到的物品)以及“混合制”规则(“先到先得”规则结合优先权规则)。本文在讨论单一顾客类型的队列挖掘时，假设排队规则为“先到先得”；在讨论多顾客类型时，假设排队规则为“混合制”规则。

本文提出的针对特定顾客进行时延预测的方法，是在概率学的基础上，运用排队理论的观点进行的时延预测。首先设定几个参量的定义：设m表示平均服务时间，假设服务过程中时间满足指数分布，且到达时间与服务时间相互独立的。因此，某个服务台的服务率为μ=1/m。在考虑顾客放弃队列的情况下，设定某个顾客的放弃队列的概率为θ。

2.1 顾客类型单一的队列挖掘

(1) 针对G/M/S+M类型的队列[4]，在时刻t下，运用队列观点来进行时延预测，从运用排队论方法表示队列长度以及服务台的个数着手：

在t时刻，队列长度用服务状态只是qEntry的服务日志的数量来表示，服务台的数量用接受服务的顾客数来表示。接下来再表示服务率μ和放弃率θ，先给出辅助关系：

sStart∧ε(s2)=sEnd}

=sStart∨ε(s2)=qAbandon)}

Q包含所有的事件对，它们同属于一个服务日志并且直接相邻。R1集合包含所有的变迁对，它们的服务状态相应的为服务开始和服务结束。R2集合包含所有的变迁对，它们的服务状态相应的为进入队列和服务开始或者放弃队列。也就是说此集合表示所有的在队列中等待的事件(s1)。R3集合包含所有放弃队列的事件。

用R1来定义平均服务时间m：

用放弃队列的顾客数以及所有的接受服务和放弃队列的顾客的时延来定义放弃率θ：

运用以上给出的参量，在t时刻运用排队论观点对业务流程进行时延预测为：

(2) 现在给出针对排队系统为D/M/c+M的系统进行时延预测。通过排队系统的比较得出，由于文章提出的是运用队列观点中事件以及服务日志的定义，基于队列长度来对队列中特定时刻进行时延预测的方法，因此到达时间对预测的影响很消极，即在给定的时刻下，不会影响队列长度的表示。所以时延预测表示为：

此类型排队系统的队列挖掘主要运用在例如流水线生产过程中。物品进入某工人负责的区域等待接收加工的时间间隔是一定的，而工人加工的时间是符合指数分布的。通过运用时延预测，对系统进行合理的分配，可以提升生产线的生产效率，同时能够为人员的管理工作提供数据支持。

(3) 针对M/M/1系统进行时延预测。该系统最大的不同就是在队列挖掘的过程中不考虑放弃的情况。因此时延预测可以通过队列长度和平均服务时间表示：

M/M/1型排队系统是一种“出生-死亡过程”。该系统的进行时延预测主要在于检测系统在单服务台情况下，业务流程的执行状态，有利于分析业务流程的执行事件的阈值与状态爆炸等问题。

2.2 顾客类别多样的队列挖掘

这一部分介绍在服务流程中，顾客的类别是多样的队列挖掘情况。这类服务流程在现实中是常见的，比如在金融行业中，存在VIP顾客，普通顾客以及受限制顾客(黑名单顾客)。通过顾客类别的区分来提高服务效率，提升顾客的服务体验以及提升收益等方面都有很好的帮助。因此在进行队列挖掘时，不可避免的需要对这种情况进行研究。文章通过上一部分的研究发现G/M/s+M类型更具有一般性，所以这一部分通过对此类型的队列进行分析，给出针对多类别顾客类型的队列挖掘方法。首先由于不同类别的顾客在服务流程执行的顺序是不同的，所以假设在服务流程中，优先权高的顾客总是先于优先权低的顾客接受服务。优先权相同的顾客按照排队准则(“先到先得”)接受服务。设顾客的优先权表示为ξ(s)={1,…,k}并且1表示最高优先权。

针对多类别的顾客进行队列挖掘，本文提出按照顾客的类别分别进行预测。总体的思想是，在t时刻下，如果是对优先权最高的顾客进行时延预测，则根据假设只需要考虑此刻的队列中排在该顾客前面的，同样具有最高优先权的顾客接受服务所产生的时延。如果是对优先权次高的顾客进行时延预测，则分为两部分进行预测。现在给出具体的时延预测方法：

(1) 对优先权最高的顾客进行预测。

挑选出优先权高的事件(顾客)集：

在S1的基础上给出在t时刻下，优先权为1的顾客队列的长度：

=qEntry∧τ(sw)≤t}|

同样在S1的基础上再给出基于队列长度进行时延预测的其他辅助关系：

sStart∧ε(s2)=sEnd}

=sStart∨ε(s2)=qAbandon)}

由此，根据排队理论给出平均服务时间和放弃率的计算方法与2.1提到的相同。但它们有实质性的区别，2.2给出的是基于优先权为1的事件集合的。最后给出在提取出事件集S1下的时延预测：

(2) 针对普通(次高的)优先权的顾客进行时延预测。

在t时刻，针对普通优先权的顾客进行时延预测可以分为两个部分：第一部分是整个队列系统中所有最高优先权的顾客执行产生的时延，第二部分是在这一时刻排在该特定顾客前面的，具有相同优先权的顾客执行产生的时延。(这种预测方法的前提是队列系统严格按照“先到先得” 的规则执行)

由于第一部分的时延预测已经给出，现在着重介绍第二部分的时延进行预测。首先也同样提出去优先权为次高的事件集合：

根据排队系统的类型为G/M/s+M，即不同类别的顾客到达队列系统的过程满足泊松分布，不妨设其概率为(λ1,…,λk)。那么此时普通顾客(优先权次高的顾客)的队列长度表示为：

其中s∈S1，且τ(s)

再给出普通顾客的平均服务时间，在不考虑此时普通顾客放弃队列的情况下，针对普通顾客的时延预测就可以给出。所以在S2的基础下给出时延预测的辅助关系：

sStart∧ε(s2)=sEnd}

由此可以定义出普通顾客的平均服务时间m：

则在t时刻开始，队列中普通顾客的时延预测为：

综上所述，在t时刻下，针对优先权次高的顾客的时延预测为：

3 应用分析

在第2部分较为完整的介绍了队列挖掘的方法之后，这一部分通过某电话服务中心的实例，介绍此方法在现实生活中的应用：运用队列挖掘优化流程模型的方法。具体的步骤为：第一步根据实例中事件的执行状态，整理出事件表，如表1。第二步选择对优化模型有利的特定顾客以及时刻t，运用文章给出的队列挖掘方法对其进行时延预测。第三步根据得到的时延数据整理出该特定顾客在流程执行中的行为信息。第四步运用Petri网和行为轮廓的相关知识，结合挖掘得到的行为信息，优化流程源模型。

表1 某电话中心事件表

首先，针对该电话中心的业务流程进行分析，运用现有的过程挖掘方法抽象出流程模型作为源模型，图2给出了该实例的源模型M0。在图2中，当顾客致电电话中心寻求服务后，如果选择智能语音服务能够解决问题，则流程结束；若不能解决则会重新选择人工服务，或者顾客在进入电话中心后直接选择人工服务。然后顾客接受服务，如果解决问题，则离开进程；若没能解决，则顾客重新选择服务人员服务或者直接离开进程。

图2 源模型M0

通过图2中源模型的描述，该中心业务流程的基本状态都能反应，但是，在顾客“接受服务”环节的描述存在局限性。考虑到同时打进该电话中心寻求服务的顾客人数，以及服务人员的数量问题，这一环节是存在排队情况的。而源模型M0没能反映出此流程信息，因此需要优化。

现在开始运用多类别队列挖掘方法，对该业务流程模型进行挖掘。该电话中的业务流程可以用G/M/s+M型来进行预测。

首先通过信息系统记录的数据，将该电话中心在一段时间内的事件进行整理，事件的信息在表1中给出。

再次，运用第2部分的时延预测方法对顾客分别进行预测发现：顾客1先于顾客2进入队列，但是顾客1接受服务的时延为10 m，而顾客2的时延为1 m。结合顾客的事件类别可以整理出顾客的行为信息：事件的执行顺序与事件的类别存在正相关的关系。即事件的类别越高，接受服务的越快。

最后根据得到的顾客的行为信息优化源模型，得到的模型不仅能够很好的反映出业务流程执行的各种状态，同时能够为管理流程结构提供动态的分析模型，而且还能表现出不同类别的事件，在存在时延的业务流程中所表现出的执行信息，这为业务流程管理提供了动态的数据支持。关于文章中的实例，图3给出优化后的模型M1:

图3 优化后的模型M1

在这一部分中，主要通过挖掘不同顾客类型在业务流程中的执行信息来优化模型，根据图3可以看出，优化后的模型不仅能够反映出该电话中心的业务流程的执行状态，同时能反应流程中的事件在执行过程中的行为和相互关系。这是源模型无法做到的，而这些行为信息对分析顾客、提高服务质量都有很大的帮助。值得注意的是，通过本文提出的多类别队列挖掘的方法所挖掘到的信息不局限于此。运用队列观点描述在t时刻下队列的长度，同样可以分析出顾客更多的行为信息。例如可以预测顾客放弃队列的时间，系统容量问题等。这些信息在管理业务流程方面有重要的指导意义。

4 结语

过程挖掘在业务流程管理中发挥重要的作用，为流程管理提供模型基础，为正确指导流程运行提供重要的保障。现有的方法多是基于控制流观点对业务流程进行定性分析，从而挖掘流程模型的。但是在处理流程模型存在时延的情况时，现有的方法是存在局限性的。目前通过队列观点针对流程模型进行挖掘的方法，在解决局限性问题的方面提供了方法，但是在多类别队列挖掘方面存在不足。

在过程挖掘技术不断需要完善的研究背景下，本文将排队论的观点与过程挖掘相结合，运用排队论的思想，提出了针对存在时延的业务流程进行过程挖掘方法。同时根据排队论中关于队列系统类型的概念，针对不同的队列系统进行相应的队列挖掘。文章中具体的挖掘方法，首先在排队论的基础上，根据事件和服务日志所记录的信息，结合概率论知识，在某一时刻下针对特定顾客接受服务的时延进行基于队列长度的预测。同时，提出了基于队列挖掘优化流程模型的方法，即将时延信息整合为顾客行为信息后，在Petri网以及行为轮廓的技术支持下优化流程源模型。本文中通过实例应用也证实了这一方法的有效性。

过程挖掘本身具有的不安全性决定这一技术需要不断完善，进一步的研究将集中在以下方面：首先一部分工作将在进一步完善队列挖掘的理论方面，例如考虑不同的排队规则以及不同的服务台类别对时延预测的影响。其次，由于队列挖掘的应用方面具有广阔的前景，下一步的工作将着眼于将队列挖掘的思想运用到其他实际的应用中。

[1]W.M.van der Aalst, W.M.P., Weijters, T., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs[J]. IEEE Trans. Knowl. Data Eng. 2004,16(9):1128-1142.

[2] Sander J.J.Leemans, et al. Discovering Block-Structured Process Models from Incomplete Event Logs[J]. Computer Science, 2014(8489):91-110.

[3]Xianwen Fang, Junzhi Wu, Xiangwei Liu. An Optimized Method of Business Process Mining Based on the Behavior Profile of Petri Net. Information Technology Journal.2014,13(1):86-93.

[4]Arik Senderovich, Matthias Weidlich, Avigdor Gal, and Avishai Mandelbaum. Queue Mining-Predicting Delays in Service Processes[J]. Advanced Information Systems Engineering Volume 8484 of the series Lecture Notes in Computer Science.2014(8484):42-57.

[5]Arik Senderovich, et al. Queue Mining for Delay Prediction in Multi-class Service Processes [J]. Information Systems, 2015(53): 278-295.

[6]孙荣恒，李建平.排队论基础[M].北京：科学出版社，2002.

[7]袁崇义.Petri原理与应用[M].北京：电子工业出版社，2005.

[8]MatthiasWeidlich, Jan Mending, Mathias Weske. Efficient consistency measurement based on behavioural profiles of process models[J].IEEE Transactions on software engineering.2010.

[9]D.G. Kendall, Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain[J]. Ann. Math. Stat. 1953,24(3):338-403.[10]MarkusDohing, Hajo A. Reijers, Sergey Sergey Smirnov. Configuration vs. adaptation for business process variant maintenance: An empirical study[J].Information System. 2014(39):108-133.

Method ofTime Delay Prediction for Multi-class Queue Mining

CAO Ruihao, FANG Xianwen, WANG Xiaoyue

(CollegeofScience,AnhuiUniversityofScience&Technology,Huainan232001,China)

The process mining is one of the core content of business process management. The existing methods are most based on the view of control-flow. However, there are some limitations in the existing methods for the execution of the business processes which hold delay. At present, the method of process mining based on queue view provides quantitative analysis for the process of time delay, but it is insufficient in multi class queue mining. This paper put forward different delay prediction algorithm according to G/M/s+M, D/M/c+M and M/M/1 three different type of queue system. In addition, in consideration of the effect of different customer categories in the service process, predict the time delay based on the delay of the queue length for target-customer at the instant. At the same time, the method of optimizing the initial process model is introduced by summarizing the behavior information which mined by the data of delay prediction of the event. Multi-class queue mining method is proposed in this paper, which not only can accurately mining the business process with time delay, but also but also improve the problem of queue mining in the case of multi-class queue system. At the same time, the proposed multi class queue mining method can be used in the optimization process model, and finally through an example to verify the effectiveness of the method.

2016-01-10

国家自然科学基金项目(61572035，61402011，61272153)；安徽省自然科学基金(1508085MF111)；安徽省高校自然科学基金重点项目(KJ2014A067)；安徽省优秀青年基金项目(ZY290)资助。

曹芮浩，男，山西长治人，硕士，研究方向：队列挖掘；方贤文，男，河南信阳人，博士，教授，研究方向：Petri网；王晓悦，女，安徽六安人，硕士，研究方向：过程挖掘。

TP391.9

A

1009-9735(2016)02-0055-07