扩展模糊时间工作流网的建模与仿真研究-

1、1扩展模糊时间工作流网的建模与仿真研究杜彦华,范玉顺(清华大学自动化系, 北京 100084摘要:针对不确定性情况下工作流时间信息分析的实际需求,基于可能性理论,引入模糊时间的概念,提出一种扩展模糊时间工作流网(Extended Fuzzy Timing Workflow Nets -EFTWFN,使其对不确定性时间信息能够进行全面描述。然后,在考虑不同流程活动之间存在资源约束情况下,提出基于EFTWFN的多个并行流程建模方法。在此基础上,又对EFTWFN模型中模糊时间和变迁触发可能性的模拟分别进行讨论,从而给出了模型仿真分析方法。最后,以某一个制造企业为例,进行建模,并采用工具CPN Too

2、ls进行仿真分析,从而验证方法的有效性。关键词:不确定性; 可能性理论; 模糊时间; 工作流; 扩展模糊时间工作流网中图分类号:TP391 文献标识码:AModeling and Simulation Methods of Extended FuzzyTiming Workflow NetsDU Yan-Hua, FAN Yu-Shun(Department of Automation, Tsinghua University, Beijing 100084, China Abstract: According to the actual need for uncertain time mod

3、eling and analysis in WfMSs, based on possibility theory, in the paper we firstly introduce fuzzy time and put forward the concept of Extended Fuzzy Timing Workflow Nets (EFTWFN, which can describe all uncertain time information in a workflow. Then, the modeling method to construct the EFTWFN models

4、 of concurrent workflows with resource constraints is proposed. Subsequently, the simulation of fuzzy time and transition firing possibility of EFTWFN models are discussed, and the simulation method of EFTWFN models is proposed. In the end, the modeling and simulation methods are validated by explai

5、ning a real example of manufacturing enterprise with CPN Tools.Keywords: uncertain; possibility theory; fuzzy time; workflow; extended fuzzy timing workflow nets 0 引言为了保证工作流系统正常、有效的运行,必须处理大量与时间有关的问题,例如:估计不同的活动执行延迟、时间违反的异常处理以及运行性能等,从而提高过程管理的效率12。但在铁路运输、医学诊断、工矿控制等应用领域中,由于测量不精确、信息不完备、描述信息模糊、以及信息包含噪声等原因

6、,某些流程的时间信息往往会产生不确定性34。如何有收稿日期:Received基金项目:国家自然科学基金项目(60674080; 国家863高新技术研发基金项目(2006AA04Z151, 2006AA04Z166。Foundation item:National Natural Science Foundation of China (Grant No.60674080 and National High Technology R&D (863 Program of China (Grant No. 2006AA04Z151and 2006AA04Z166效地对这种不确定性时间信息的表

7、达和推理问题进行分析处理是非常重要的,对于增强工作流管理功能、丰富工作流建模理论以及推动工作流管理软件的应用具有重要意义2。已有的方法大都是以随机变量描述流程时间信息的不确定性5-9。具体如, 文5利用概率赋时活动图,对工作流模型运行的时间信息进行描述和分析;文6基于随机Petri网的工作流模型进行等价性能分析;文7在业务过程设计时,采用离散的随机变量表达业务活动的时间,通过推导进行优化设计;文8通过求出实例在整个模型的停留时间概率分布函数,再根据客户对停留时间的容忍限度,得出客户对业务处理过程的满意度。文9根据业务输入速率计算得到工作流网中变迁的输入速率, 进而讨论了工作流模型的系统静态性能

8、分析及动态性能分析的方法。5-9上述方法都需要大量历史数据, 通过统计得到随机变量的分布函数。但在有些情况下,这些数据是无法获得的。具体如:在铁路行业中,经常会出现新修的铁路区间和新的车型,如果进行列车行车方案制定时候,就没有相关的列车到发时间纪录,仅能通过相关人员的估计来实现34。在制造行业中,由于市场变化加速导致新产品推出速度加快,其相应流程很难积累大量的统计数据,或没有历史记录信息;同样对某些工艺流程进行改进或推出新流程,其时间信息也只能根据经验进行估计10。10因此,本文立足于工作流系统对不确定时间管理的这种实际需求,基于可能性理论,提出一种扩展模糊时间工作流网(Extended Fu

9、zzy Timing Workflow Nets -EFTWFN。然后,在考虑不同流程活动之间存在资源约束情况下,本文提出基于EFTWFN的多个并行流程建模方法。在此基础上,又对EFTWFN模型中模糊时间和变迁触发可能性的模拟分别进行讨论,从而给出了模型仿真分析方法。最后,通过对制造企业的一个实例分析,说明本文建模与仿真方法的有效性。在结构上,本文首先介绍EFTWFN定义;其次,给出并行流程的EFTWFN建模方法和相应的仿真方法;最后,进行实例分析说明。1 模糊时间表达Zadeh在1965年提出的模糊集合论的基础上,于1978年又提出了可能性理论(possibility theory10。可能

10、性理论作为处理不确定信息的一种方法,符合人类的思维方式,且具有较低的信息量和时间计算复杂度,因而得到了越来越多学者的关注。同时,它又经Dubois D., Prade H.等人的发展1112,已经在许多实际专家系统和推理系统中得到了广泛的应用。基于可能性理论,模糊时间可认为是从时间刻度(非负实数集到实数区间0,1的映射函数,函数值表示事件在时间点上呈现可能性的度量。其形式化说明如下:映射函数f: TE; T 是时间,E是模糊数集合u: R0,1| u满足如下条件 :存在一个x0R,u(x0=1;:u是模糊凸的(fuzzy convex;:u是上半连续的(upper semicontinuous

11、;:u0=xR:u(x0是紧的(compact。(a (b图1.表达示意图为了简化又不失普适性,通常采用时间轴上的梯形模糊时间区间来表示不确定性时间(包括时间点和时间段1112。也即对于图1(a的模糊时间映射函数,可以采用(b中的梯形模糊数进行逼近。对于模糊时间区间lsx, usx, lex, uex ,(lsx usx lex uex 如图2所示,可以简单认为usx, lex 表示活动肯定发生的时间区间, 区间lsx, usx 和lex, uex 表示活动有可能发生, 在模糊区间以外时间活动一定不会发生。当lsx =usx 和lex =uex 时,模糊时间区间退化退化为固定长度的时段。当ls

12、x =usx =lex =uex ,模糊时间区间退化为点。当需要对模糊时间进行更为精确表达时,可以采用梯形模糊区间叠加“”的方法14,如图3所示。 EFTWFN 的定义与建模上可以映射为一个工作流网:过程中的活动对应网中的变迁,活动的前置性质,则称这个Petri 网为一个工作流网,记为WFN : 出;对P T ,存在一条从初始库所到结束库所的路径C ,使得x 是C 上的一个结点,即;始状态为M 0=p i ,网的终止状态为M e =p o 。定义22.1 EFTWFN 的定义工作流过程在结构和后置条件对应网中的库所,托肯对应过程的实例。工作流过程的几种基本控制结构即顺序、选择、并发和循环均可以

13、用Petri 网来描述。工作流网结构和行为方面的正确性可以通过网的活性和安全性来验证。下面的讨论均假定工作流网的结构和行为都是正确的。 定义1 工作流网(Workflow Nets-WFN当一个Petri 网PN =(P , T, F , M 0具有如下 PN 中有两个特殊的库所:初始库所p i 和结束库所p o ,初始库所无输入,结束库所无输x x (C网的初2 扩展模糊时间工作流网(Extended Fuzzy Timing Workflow Nets -EFTWFN扩展模糊时间工作流网可以定义为一个三元组,即EFTWFN =WFN, S ,D : WFN 是一个满足定义1的工作流网; 映

14、射函数S: T (1,0,S (t 表示变迁t 和其他变迁发生冲突时触发的可能性值(po t 冲lex uex <,lsx, usx, lex, uex 表示模糊看以出,EFTWFN 的变迁和输出弧分别被赋予可能性值和模糊时间区间,其中糊时间(是托肯在时间到达某一库所的可能性分布。定义是t 所有输入库所中托肯的最迟时间可能性分布。假设存在n 托肯, 是使能的t 在时间触发的可能性分布。对于多个使能变迁,遵图ssibility ;当不存在与突的变迁时可能性为1; 映射函数D: T ×P lsx, usx, lex, uex | 0lsx usx 时间区间。从上述定义可可能性值表示

15、活动被执行的可能性,模糊时间区间表示活动完成所需要的时间。模糊时间中的lsx 、usx 、lex 、uex 均为相对时间,它们相对于变迁可实施的时刻,这个起始时间由系统决定。假如变迁在s 时刻可实施,实际实施的时间记为t *,则s + lsx t *s + uex ,即在模糊时段lsx , usx , lex , uex 内实施并完成。定义3 托肯的模糊时间EFTWFN 中托肯的模4 变迁的模糊使能时间变迁t 的模糊使能时间e (其相应模糊时间为i (, i =1, 2, , n, 则e (= Latest i (, i =1, 2, , n 。定义5 变迁的模糊发生时间变迁t 的模糊使能时间

16、o (2. 模糊时间区间图3. 模糊时间区间的叠加循“先来先服务”原则, 较早使能的活动赋予较高的优先权。假设t 存在m 个变迁, 它们相应的使能时间为e i (,i=1,2,m ,则o (=mine t (, Earliest e i (| i t, e i (, i=1,2,m 。上述定义中涉及的相应具体运算如下13:设X =lsx , usx , lex , ex 、Y =lsy , usy , ley , uey u 分别,minlex , ley ,minuex , uey ; 基下:1 有输入库所的个数;表示模糊时间区间,p X 、p Y 为相应变迁的可能性值,EarliestX

17、,Y = maxp X , p Y minlsx , lsy ,minusx , usy Latest X ,Y = minp X , p Y maxlsx , lsy ,maxusx , usy ,maxlex , ley ,maxuex , uey ; X +Y =minp X , p Y lsx +lsy, usx +usy, lex +ley, uex + uey ;于上述定义,EFTWFN 模型的状态演进或计算过程如取得变迁t 的所有输入库所内托肯的时间信息i (;2 计算t 的使能时间e t ( = Latest(|i=1,2,k , k 是所i (| i t, e 3 计算t 的

18、触发时间o t (=mine t (, Earliest e i i (为与t 冲突变迁的使能时间; 5对计算。形叠加方法(如图3所示:首先将X 和Y 分别j (模糊时间区间i ( =i1(i2(im (; j (, 计算l (= Earliest ir (, jk (2.2的资源支持,例如文档、数据库表、或者打印机等。资源中,每个资源都具有唯一标示号r 。被任务t i 使用的资源可通过映射函数R 表示W i 和W j (i j 分别包含任务t ik 和t jl ,且t ik 与t jl 是资源相关的,则工作流W i 和W j 是的EFTWFN 定义只能描述单个工作流的时间约束现象。但是在现实

19、的业务环境个工作流流程W 1,W 2, W m ,分别构建其单个流程的EFTWFN 模型。4 如果t 的输出库所为空,则添加托肯,时间信息为i (= o t (+ D (t ;否则,更新已有托肯的时间信息max o t (+ D (t ,old (;于其余的使能变迁,逐个采用1 to 4进行当需要对模糊时间进行更为精确表达时,可采用梯分解为若干梯形模糊区间,再分别进行计算,最后进行叠加运算。具体Earliest 运算的步骤如下,其它运算类似14:Compute ( = Earliesti ( , 首先将(,i j (分解成多个梯形j ( =j1(j2(jn (;对每一对ir ( and i j

20、k ( 合并所有 (=l (并行流程的EFTWFN 建模工作流在执行时,通常会需要相应15可被分为共享资源和私有资源两种。共享资源可被同一个工作流或者不同工作流的活动使用;私有资源只能被特定的活动使用。私有资源不会造成工作流出现各种时序约束,因此本文仅考虑共享资源的情形。为方便描述, 本文假定共享资源在被活动使用时都是独占模式,且遵循“先来先服务”原则(FCFS 。定义6 资源相关在工作流系统, R (t i =r 1,r m 。如果两个任务t 和t i j (i j 处在一个工作流模型中,或者分别处在两个工作流模型中,且R (t i R (t ,则任务t j i 和t j 是资源相关的。定义

21、7 相关工作流如果两个工作流相关的。上述3.1节中中,一个工作流系统中通常存在多个并行的工作流过程,并且这些过程之间可能会出现资源冲突,也即相关工作流。例如:在铁路行业中,一个列车的运行就对应于一个工作流过程,但是在特定的区域内通常会存在多个列车(即列车群,并且可能会对某些资源冲突(如站台、区段或车位等。 因此,本文提出资源约束情况下多个并行流程的EFTWFN 建模方法, 其具体步骤如下:1 对于系统中多2 增加两个变迁T init 和T end ,使T init 作为所有EFTWFN 模型输入库所P i 的输入变迁, T end 作为所有EFTWFN 输出库所p 的输出变迁, 同时增加两个库

22、所P 和P o init end ,使P 为变迁T init init的输入库所, P end 为变迁T end 输出库所。用弧连接P 3 FN 模型输入库所P i ;用弧连接各个EFTWFN4 M 0(P i =0,令初始标识 M 0 (P init =1, 其5 活动间的资源冲突情形,在对冲突的变迁之间增加一个库所P x ,3 EFTWFN 模型的仿真分析量方法、可达图(树方法、模型化简推理方法、Petri 网语言分性值,且输出弧上被赋予模糊时间区间。这虽然增强了模型的表达描述能力,使其可以充分描述工作流系统中的不确定时间因素和属性。间区间和拟,d 进行模拟时,本文采用文13方法,定义函数

23、Fuzzydelay (a,b,c,d 如下如下步骤,直到计算出一个值:ime ;个产生一随机值V ,并计算可能性值D (a 所示:和T 以及T 和各个EFTW init init init 输出库所p 和T o end 以及T end 和P end 。改变EFTWFN 模型各个输入库所P i 的初始标识余位置标识不变。对多个相关工作流中并分别添加从P x 到相应冲突变迁的输出弧,以及变迁到P x 的输入弧,作为公共部分。Petri 网的分析方法包括:不变4析方法、以及模型仿真的方法等等。模型仿真方法作为直接、有效解决问题的方法,目前已经获得许多Petri 网工具或平台的支持,例如PetriS

24、im 、TimeNET 、WebSP 、COSA BPM 、GreatSPN 、HPSim 、CPN Tools 等17。EFTWFN 模型的变迁被赋予触发的可能但目前已有的仿真工具或平台却不支持模糊时间区间和可能性值等概念,需要进行相应的模型改进,同时还需在模型中添加一些附加的结构以便对仿真的结果进行收集和统计。下面基于CPN Tools 18来进行EFTWFN 模型的仿真分析研究,也即着重讨论模糊时变迁触发可能性值的模拟过程。CPN Tools 是Aarhus University 提供的用来编辑、仿真及分析CPN 的工具,具有友好的界面和高效的仿真引擎,且能够动态实时检查错误语法,得到了

25、较为广泛的应用。3.1 模糊时间的模对模糊时间区间a,b,c :循环执行 a.在区间a,d 范围内产生一个随机值at b.如果atime 在区间b,c 范围内, 则返回atime c.如果atime 在区间a,b ,c,d 内,然后在0,1内time ;如果D (atime V , 则返回atime ,否则执行步骤a.EFTPN 模型中被赋予模糊时间区间的变迁转换如下图 4.2 变迁触发可能性的可能性值,本文定义函数Choice (进行模拟3。假设变迁(a原来网结构 (b转换后网结构图4. 函数Fuzzydelay 转换示意图3值的模拟针对EFTPN 模型中的变迁被赋予t 1, t 2, t

26、3存在冲突,触发的可能性分别为0.5, 0.3, 0.2; 则Choice (定义如下:a.在区间0,1范围内产生一个随机值d ;b.如果d 在区间0,0.5范围内, 则t 1触发;c.如果d 在区间0.5,0.8范围内, 则t 2触发;d.对于其它情况，t3触发。 相应的网结构转换如下图 5 所表示： (a原来网结构 (b转换后网结构 图 5. 可能性值 possibility 转换示意图 在仿真系统运行中，为了便于进行多次的循环仿真，需在模型中添加相应的标示库所， 其中托肯的个数就是将要执行的仿真次数。另一方面，为了收集和记录所需的仿真信息，可 以采用日志文件监控器(Log-File Mo

27、nitor对特定库所的信息进行记录，进行数据分析。具体 内容可参阅文18。 4 实例说明 4.1 实例说明和建模 为验证本文建模和仿真方法的有效性，下面结合制造企业的一个实例进行细分析说明。 假设一个企业中存在两种并行流程16：新产品开发流程及旧产品改造流程。 1 新产品开发制造流程主要分为两种情况：通过企业研发和销售部门的调研设计，然 提交生产部门进行新产品制造； 另外一种情况是直接由其它研发 后由总工程师审核修改后， 单位进行设计，直接进行制造；两种情形的可能性分别是 50%和 50%。具体如图 6(a所示。 2 旧产品改造流程主要是由研发部门进行旧产品改造报告，改造技术分析，然后由总 工

28、程师审核批准，最后报给生产部门进行改进后的旧产品制造。具体如图 6(b所示。 3 图 6(a中各变迁和位置含义：pi1流程起点，p11研发部门，p12销售部门，p13总工程师， p14生产部门，po1流程终点；t11新产品开发建议，t12新产品开发技术分析，t13新产品开发市 场分析， t14总工程师批准，t15新产品制造，t16提交其它研发单位。 4 图 6(b中各变迁和位置含义： pi2流程起点, p21研发部门，p22总工程师，p23旧产品改 造部门，p24生产部门，po2流程终点；t21旧产品改造报告，t22旧产品改造技术分析，t23总工 程师批准，t24旧产品制造。 5 图 6(a和

29、(b中变迁被赋予的模糊时间由四元组表示，没有标出触发可能性值的变迁 均默认为 1。为了便于描述, 时间计算以统一的时间单位(天为标准，并设两流程起始时间 相同。 由上述描述可知,两个流程中存在对相同资源(总工程师的竞争, 因而流程并行执行中对 首先添加pinit, tinit, pend, tend， 使两个模型的输入输出唯一化。 竞争性的资源使用具有时间约束。 增加库所PRl, 表示总工程师, 合并后的EFTWFN模型如下图 7 所示。 6 (a. 新产品开发制造流程 (b. 旧产品改造流程 图 6. 企业内存在的新旧两种流程 图 7. 合并后的流程 4.2 仿真分析 CPN Tools 目

30、前只支持整数仿真时间，首先设整个系统的仿真初始时刻为 0，并将仿真 时间都放大 100 倍，如18,20,25,27表示为1800,2000,2500,2700。 为了使CPN tools支持，首先结合上述EFTWFN模型定义如下颜色集(Standard ML格式 18 ： color set WTYPE=with W1|W2 timed; color set RTYPE=with R1|R2 timed; color set RTYPExT=product RTYPE*T timed; color set PATH=int with 1.2; color set WTYPExT=produc

31、t WTYPE*T timed; color set WTYPExTxT=product WTYPE*T*T timed; 函数 choice( 表示新产品改造流程的不同路径选取的可能性： fun choice(= let val d= uniform(0.0,1.0 in if (d<0.5 then 1(W1,1 else 1(W1,2 end 函数 Fuzzydelay(a,b,c,d表示流程活动的模糊时间： fun Fuzzydelay(a,b,c,d= let val dis3=uniform(a,d val x:real=(b-dis3/(b-a val y:real=(dis3-c/(d-c in if ( b<=dis3andalso (dis3<=c then Real.round(dis3*100.0 else if( a<=dis3andalso(dis3<=b then if (uniform(0.0,1.0<=x then Real.round(dis3*100.0 else Fuzzydelay(a,b,c,d else if (uniform(0.0,1.0<=y then Real.round(dis3*100.0 else Fuzzydelay(a,b,c,d e