基于广义随机Petri网的角色-任务系统模拟研究（仅供参考）.doc

窗体顶端、基于广义随机Petri网的角色-任务系统模拟研究（仅供参考）摘要: 在随机Petri网基础上扩展了对优先级实例处理的能力,提出了扩展的随机Petri网,以增强对各类任务的描述能力,并通过实例阐述了如何建立带优先级的随机任务系统模型.通过对模型的模拟数据分析,探讨了最优角色资源分配和服务率优先提高等管理决策问题解决方法.为以任务驱动型组织关于角色-任务互动机制的描述和分析提供了借鉴和参考.关键词:扩展随机Petri网; 角色-任务系统;资源分配; 互动机制Simulation of Role-Tasks System based on the Stochastic Petri NetsAbstract: In order to increasing description ability for tasks with priority, a extended Stochastic Petri Nets (XSPN) is provided based on classic Stochastic Petri Nets, and then an instance is given to explain how to modeling for the stochastic task systems with priority. As for simulation data of the model, the solution for the optimal resources allocation of the roles and priority services improved issues is proposed. Furthermore, it also provide a new idea to solve described and analysis of the interaction mechanisms of role-tasks for the task-driven organization.Key words: Expansion Stochastic Petri Nets(XSPN); Role - Tasks system; Resources allocation; Interaction mechanism0.引言组织的核心是人群与工作,组织的运转过程就是人群与工作的互动过程.随着经营环境的不断变迁,传统的功能型、官僚型组织以部门、科室和班组等功能部门为核心进行分工,但不熟悉过程,实施经营过程重组可能存在很多冲突,不再适合现代企业的发展实践经验表明,为了经营过程活动的的重组和资源的合理应用,以项目为驱动的矩阵型和网状型企业组织构架适合以过程为中心的企业发展.在传统的矩阵结构的基础上,依据业务流程,将人群和工作进行分解,构建一类角色-任务组织构架,如图1所示.将企业的工作分解为多条业务流程,即,每条业务流程可以由一项乃至多项任务实现,即;企业人群可分为多个角色,即,一个人可以充当一个或几个角色;实行一项任务可以由一个或多个角色完成,即.图1:基于角色-任务系统的组织构架关于组织中过程定义和任务描述,目前有不少的研究成果,主要有流程图、状态图、活动网络图、IDEF系列、ECAA(事件-条件-动作规则)、并发事务逻辑、超媒体结构、事件驱动的过程链模型、面向对象方法、Petri网等建模方法.这些方法虽然在一定程度上能解决过程的基本描述问题,但还是存在一些缺陷:基本上是用活动及其关系来描述过程的,对活动的资源(可以是人或其他的实体,如自动触发活动、外部工作机等)及其关系描述不够,进而导致流程管理系统对异常处理的表述和处理能力不够;模型的刚性较强,但柔性不够,大多数单一建模理论对任务处理环境变化考虑不够,当环境发生改变(增加请求和服务、经营流程变动等),过程模型不易做出相应的变动;描述能力不足,体现在对于复杂的流程的描述场合,会出现状态空间爆炸问题,即任务过程建模过程冗长和复杂;(4)不能描述动态并行任务的执行过程.研究表明高级Petri网及扩展Petri网建模方法能很好解决上述问题.高级对象Petri Nets12能很好的解决确定性动态流程描述问题,但不能描述具有随机特性的流程,而随机Petri Nets能解决随机流程的描述,但缺乏柔性,尤其是对含有多种优先级实例的描述问题,本文结合高级对象Petri Nets和随机Petri Nets的特点,对具有优先关系的角色-任务系统建模.模型建立后,为便于管理决策,还需对其进行性能分析.在角色-任务处理系统中还需要分析两类问题:(1)实现任务所需各类角色的资源数为多少时,任务的总工作时间最少,尤其是在多任务并行工作状态下,任务与任务之间存在共享资源时,也就是资源分配问题.(2)为提高任务处理的工作效率,应优先提高哪类角色的工作绩效呢?这两类问题与人力资源管理中的设岗后的定员问题以及优先岗位培训的决策策问题相似,不同之处,本文考虑的角色可以是人,也可能是用于处理任务中的其它资源,如机器和其它设备.现有研究工作中,关于时间性能分析的研究较多,但这类工作主要以理论分析为主,没有将时间性能与资源分配问题结合起来,也只考虑了静态多任务的并行工作状态,关于组织中资源分配问题,现有研究主要从约束理论入手,建立单目标或多目标模型,考虑资源的规划问题,但观察这些模型,不难看出,需要有确定的相关参数,如资源数的约束,任务的多少等,在企业实践中,组织建立之初,这些参数往往是不确定的,也就是难以用现有的单目标或多目标决策的求解方法求解.角色-任务处理中,考虑到多任务并发处理过程,这类决策问题往往是多目标问题,如使用足够少的资源数同时,力求总成本和总处理时间最短;在角色-任务系统中,任务的到来服从某概率分布,系统状态的变化,也服从随机分布,因此,该系统具有在随机性,故角色-任务系统的决策问题为一类随机多目标决策问题,这类问题的求解可采用基于随机模拟的方法,如遗传算法等,本文试图使用基于扩展Petri网模拟的方法,对角色-任务系统进行仿真分析,为资源管理提供理论基础和决策支持. 1.扩展随机Petri网1.1随机Petri网基础将变迁与随机分布延时联系起来的思想源于Molly,Florin和Natkin等人提出13,即给P/T网的每个变迁赋予实施速率,得到的就是随机Petri网(SPN),通常,SPN有两种形式:Molly和Florin-Natkin,本文探讨Molly形SPN模,其定义形式为:定义1:一个六元组是一个随机Petri网系统,其中:(1)是一个P/T系统,其中:为库所集,为变迁集,为转移函数,而:是弧权函数;是初始标识(2)是变迁实施速率集合.1.2 扩展随机Petri网通过定义1,可知,面对复杂系统,随机Petri网模型可能有:(1)面临状态空间爆炸;(2)不易描述动态任务并行工作机制(多任务之间和多任务实例之间的工作机制)等缺陷.为克服上述可能的不足,在SPN的基础上,加上面向对象分层处理和有色映射等机制,得到扩展随机Petri网.定义2:五元组,其中:(1)网系统,其中,为子网系统,且有为普通库所,为通道,能保存各种类型的托肯;为网系统输入接口,为网系统输出接口,且有;为变迁,且有,其中为延时变迁,为瞬时变迁;为转移函数;为颜色函数,且有;(2) 为系统资源,可以是人或物;(3) 为网系统实例的优先级别;(4)与经典随机Petri网的意义相同.2. 基于随机Petri网的角色-任务系统建模2.1排队系统的随机Petri网模型排队数学模型的描述能力不足20,如描述系统有(1)同步;(2)阻塞(blocking);(3)顾客的分裂(splitting)等情况时.针对这些分布系统,不能直接求解,需转换为马尔可夫链,这点与随机Petri网相似,但随机Petri网的描述能力更强,尤其是在描述带优先级别的排队系统时.因此,本文用随机Petri网描述排队系统,即将排队思想融入随机Petri 网模型中,一则可以清晰的描述排队现象;二来可以便于分析和求解.按信息系统实现优先排队的思路,先来先服务(FIFS)在系统实现中可以不要优先级,其它排队情形也可以用优先级来实现,如先来后服务(FILS),系统实现时完全可以将进入系统的对象优先级递减,还有非常规的排队系统,可以通过设定其不同优先级,按规则服务,因此,可以将排队模型分为两类: (1)先来先服务的排队模型如图1 所示.以文件审批为例说明.文件以速率率到达某部门,进入等待服务队列(用普通库所表示),系统判断当前该部门文件审批角色是否空闲,即当前是否还有资源,若有,则,系统以服务率进行文件审批,完毕就释放资源,若当前资源库为空,则文件等待,直到资源释放.图2:基于随机Petri网的FIFO排队模型(2)带优先级的排队模型如图1所示.带优先级别的文件以速率率到达某部门,进入对应优先级别的等待服务队列(用普通库所表示),系统判断当前该部门文件审批角色是否空闲,即当前是否还有资源,若有,则变迁以服务率依次从高优先级别队列中取文件审批,完毕就释放资源,若当前资源库为空,则文件等待,直到资源释放.图3:带优先级排队系统的随机Petri网模型2.2 基于随机Petri网的任务系统建模实例以制造企业新旧产品审批任务处理系统为例.当有新产品开发任务到达系统,系统根据其任务的优先级别进行排队,任务分发人员(角色a)将当前系统中优先级别高的资料分别送往市场部(角色b)和新产品研发部(角色c)进行处理,两部门经经过一段时间处理,系统将两部分处理的结果汇总,并送到总工程师处(角色d)进行审阅,审阅的结果再送到生产部门;而当有旧产品改造任务到达系统,与新产品开发任务一样,进系统进行排队,任务分发人员(角色a)将当前系统中优先级别高的资料送到旧产品改造研发部门进行改造设计(角色e完成),系统将处理结果送至开发部门处理.图4即为该问题的Petri网描述.图4:任务处理系统的随机Petri网模型图4中,t1(t3),t2, t5,t6,t7,t8分别为角色a,b,c,e,d的处理过程,q14为队列,q1(3)处理高优先级文档,而q2(4)处理低优先级文档,P16为一般库所,用于存储文档信息.上述任务处理过程包括两个子任务并行工作过程,即新产品研发任务和旧产品改造任务.设两任务的到达服从泊松分布,到达率分别为:,角色a,b,c,d的服务率分布为:;,其中,角色a处理新产品研发文档时,其处理速率为15份/天,而处理旧产品文档时,其处理速率为20份/天,角色d服务率服从beta分布,处理一份文档,最少得0.1天,最多得0.3天,而极有可能是0.16天.3基于XSPN的系统模拟图4基本描述了任务处理过程,但有几点不足:(1)对排队系统的描述能力不强,图4中用两个库所描述了高、低优先级文档的到达状态,但现实场景中,可能优先级不低于2种,面对如此情形,传统的随机Petri网可能采取的办法是随着优先级种类的增多,系统中描述各类优先级文档到达情况的库所也得不断的增加,显然不够灵活,即不能利用有限的库所、变迁或其他的工具就能灵活的描述多种优先级文档的排队情况;(2)不易描述系统中流动的多种资源;(3)可能出现状态空间爆炸.上述角色-任务系统选例状态较少,真实系统中,可能状态更多,需分层处理.3.1基于扩展随机Petri网的角色-任务系统模型本文利用Exspect仿真工具(.)提供的分层图形建模工具,辅以编程的方式,实现了3.1所述文档处理系统,如图5所示.该系统不仅能清晰的描述角色-任务互动过程,也克服SPN的不足,并且增加了系统数据采集功能.图5:基于Exspect的角色-任务系统模型图中为通道(Channel),与传统Petri网的库所相同;为存贮(Store),能保存不同颜色的托肯;为处理(Process),与传统Petri网中变迁功能一样,这类变迁一般有时延;为瞬时变迁,没有时延;为时间触发器,提供系统时钟;为随机数触发器.各元素功能见表:表1:角色-任务系统模型中各对象功能描述标号 功能i_id 用于连续产生任务编号(1,2,n) case_generator 用于产生两种带优先级任务,并分发至对应级别的队列中queue_num1(queue_num 2) 用于记录待处理新产品研发(旧产品改造)文档份数queue_buffer1(queue_buffer2) 用于保存新产品研发(旧产品改造)文档信息queue1(queue2) 保存正在处理文档信息t21(t22) 角色a从待处理队列中提出高优先级文档进行分发处理P1(P31,P32, P5, P6, P7, P8) 新产品研发文档通道P2(P33,p4) 旧产品改造文档通道t211(t221,t6,t7,t8,t10,t11) 瞬时处理变迁r0_num(r1_num, r2_num,r3_num, r4_num) 用于记录角色a(b,c,e,d)的资源数r01_total(r1_total, r2_total,r4_total) 用于记录角色a(b,c,d)处理新产品文档的份数和时间和r02_total(r3_total,) 用于记录角色a(e)处理旧产品改造文档的份数和时间和Total_store 用于记录所有文档的份数和时间和aver(aver1) 用于记录新产品研发(旧产品改造)文档份数和处理时间总和3.2 模型中主要组成部分的实现方法(1)初始文档的产生利用Random和Time工具随机产生带优先级的文档信息.当Random=0.6时,设定产生新产品研发请求文档,而当Random=0.8时产生高优先级别的文档,否则就为低优先级稳定;当Random=0.3,产生高优先级的旧产品改造请求文档,否则为低优先级文档;而Time工具提供文档初始时间数据.如产生新产品研发请求文档语句为:i_id =0.8 thenqueue_buffer1 - id:i_id, cid:1,i_time:time,s_time:time,f_time:time,e_time:time,pid:h ins queue_buffer1elsequeue_buffer1 - id:i_id, cid:1,i_time:time,s_time:time,f_time:time,e_time:time,pid:l ins queue_buffer1fi,queue_num1 - queue_num1+1 ,queue1- queue_num1 delay poisson(0.2,0.5) 对有多级优先级别的情况,可将在上述If选择分支中再加对应分支,不同之处就是修改优先级别号,如除上面高(h)和低(l)两种外,还可以加中(m)等优先级别.(2)带优先级的排队系统实现图5所示模型具有排队系统功能,能对多任务实例并行工作进行协同处理,即任务实例到达,系统将按其类别和优先级别进入相应等待队列queue_buffer1(queue_buffer2),角色a从中挑选等待时间长并且为当前优先级最高的任务实例进行处理.利用Store具有自动排序的功能,将所有进入等待队列的任务实例按编号进行排序,这样保证了初始时间最早的实例排在队列的前列,而在出队列时,按规则,先查询高优先级别的实例是否存在,若有,就将其出队进行处理,由于该系统匹配到符合条件(即高优先级)记录就是编号最小(即初始时间最早)的实例,这就保证了进队时间最早的高优先级实例先出等待队列进行工作的规则;若不存在,就挑选进队时间最早的优先级别次高的实例出队进行处理.实现排队和出队的主要功能程序如下:if h elt rng(x:queue_buffer1|xpid) thenp1 - pick(set(x:queue_buffer1|xpid=h)delay nexp(15.0,0.5),queue_buffer1 - set(x:queue_buffer1|xid!=(pick(set(y:queue_buffer1|ypid=h)id) elsep1 -pick(set(x:queue_buffer1|xpid=l)delay nexp(15.0,0.5),queue_buffer1 - set(x:queue_buffer1|xid!=pick(set(y:queue_buffer1|ypid=l)id) fi(3)基本统计功能的实现该模型一项主要功能是对各角色的处理时间进行统计,便于系统性能分析,如: aver - sid:aversid+1,totaltime:avertotaltime+p10e_time-p10i_time,该语句为统计系统处理所有新产品研发文档任务的总工作时间的功能语句,其它的统计功能实现语句与此相近,不再赘述.3.3 系统评价与分析关于随机Petri网的性能分析主要集中于网的可达性和时间性能上的分析.关于网的可达性可用活性分析和可达图等方法进行,图5所示模型,在建立过程完毕和仿真开始之前,Exspect调用其Check模块自动进行活性和可达分析,也就是调试通过的模型,基本都是可达的,因此本文将不探讨其可达性;关于随机网的时间性能分析,主要是利用随机过程等理论进行分析,现有的研究工作集中于简单环境下,对静态任务的分析,如服务率分布单一,任务与任务之间没有资源冲突.下文将针对多任务并行环境的任务系统给出分析.3.3.1 任务工作时间任务系统中可能由多个子任务组成,包括:串行、并行、选择和循环,若各变迁延时时间都服从指数分布,则这几种结构的延时时间可由下列公式分别求得: (1) (1) (3)(4)则任务总时间为:5),其中,是各串行变迁延时时间的指数分布参数,l为串行变迁总数,是并行变迁延时时间的指数分布参数,m为某个循环结构中的并行变迁个数;是选择变迁延时时间的指数分布参数,是该分支概率;,是各循环结构上变迁延时时间的指数分布参数,以概率循环.3.3.2 基于仿真的任务系统分析应用若任务系统中各变迁延时服务不服从指数分布,或者部分服从,部分不服从,就不能利用上述公式(1)-(4)进行时间参数求解,并且,多任务并行环境下,难以用确定性的数学模型描述动态并行任务处理系统,也难以进行系统分析.通过对任务系统进行可视化仿真分析,能方便地采集各性能数据,且精度较好,有利于结果分析,下文将探讨角色-任务系统分析和评价过程.角色-任务系统中,涉及到的相关管理决策问题主要有资源分配和服务率提高等决策问题,下文将针对这两类问题给出解决方案.(1)资源分配决策问题现有关于资源分配的研究集中于用规划的方法进行设定,但通过其限定条件不难看出,欲得出合理的人员匹配,必须有准确的参数,如资源的上限,不同优先级任务实例的并行情况等,此类模型可定义为一类确定性模型,但现实环境中,存在很多不确定,如某角色数上限问题,在组织建立之初,这些数据可能不确定的,事实上当某角色不够时,部门之间可以调整,甚至招聘新员工;在动态并行环境下的资源共享问题,如图5中新产品文档分发和旧产品文档分发的人员为一类角色,当前任务执行使用或消耗的角色资源数将可能制约其它任务的执行,系统运行的同时,存在有某项任务的多个实例,由于优先级不同,实例之间的资源约束问题.利用仿真的方法,按灵敏度分析思路,可以获取目标的变化,从而确定资源分配最优解.如何权衡其变动效果呢?即评价任务的性能.关于性能评价的相关文献较多,但绝大多数为定性描述,定量描述的较少.关于任务评价指标较多,主要有静态指标和动态指标,其中静态指标主要有:活动的总要性和资源的均衡度;动态指标主要有:时间、成本和产量.针对制造文档处理问题,假设,各活动的重要程度相近的前提下,用3个主要的指标来权衡资源的分配:(1)资源利用均衡度,即各角色的平均资源利用率均衡.平均资源利用率用公式求得:;(2)绩效相对提高率,即资源数增加前后资源平均工作时间相对资源变动前后的任务平均处理总时间提高幅度,用公式求得:;(3)绩效绝对提高率,即资源数增加后任务工作总时间相对资源数增加前任务工作总时间的提高幅度,用公式求得:下表为仿真500次后的数据:表2:角色-任务系统仿真数据(1)编号 角色 数量 角色总工作时间(天) 角色平均工作时间(天) 资源利用率 编号 角色 数量 角色总工作时间(天) 角色平均工作时间(天) 资源利用率1 r01 1 0.68638849 1.16738855 85.5% 4 r01 4 0.11247595 0.05865082 10.9% r020.48100006r020.12212731r1 3 0.06931550 0.02310517 2.9% r1 3 0.06915501 0.02305167 8.2% r2 2 0.05776292 0.02888146 3.7% r2 2 0.05776292 0.02888146 11.2% r3 2 0.16713536 0.08356768 14.5% r3 2 0.16713535 0.08356768 32.5% r4 2 0.06923924 0.03461962 4.4% r4 2 0.06931550 0.03465775 12.3% 任务1平均工作时间 0.78895258任务1平均工作时间 0.28085090任务2平均工作时间 0.57609681任务2平均工作时间 0.257245512 r01 2 0.41396757 0.27621042 33.4% 5 r01 5 0.09729842 0.03806437 7.7% r020.13845327r020.09302341r1 3 0.06931550 0.02310517 4.3% r1 3 0.06931550 0.02310517 8.5% r2 2 0.05776292 0.02888146 10.0% r2 2 0.05776292 0.02888146 12.9% r3 2 0.16713535 0.08356768 29.0% r3 2 0.16713536 0.08356768 37.3% r4 2 0.06931550 0.03465775 6.4% r4 2 0.06931550 0.03465775 12.7% 任务1平均工作时间 0.53994998任务1平均工作时间 0.27246324任务2平均工作时间 0.28812241任务2平均工作时间 0.224320643 r01 3 0.21052884 0.10718656 17.0% 6 r01 6 0.05472624 0.02217185 4.6% r020.11103083r020.07830485r1 3 0.07359822 0.02453274 6.8% r1 3 0.06931550 0.02310517 9.1% r2 2 0.05776292 0.02888146 10.7% r2 2 0.05776292 0.02888146 12.6% r3 2 0.16713536 0.08356768 31.0% r3 2 0.07428238 0.03714119 16.2% r4 2 0.06931550 0.03465775 9.6% r4 2 0.06931550 0.03465775 13.6% 任务1平均工作时间 0.36168473任务1平均工作时间 0.25397910任务2平均工作时间 0.26972230任务2平均工作时间 0.22951931通过计算相对提高率和绝对提高率,得到下图:图6:相对提高率和绝对提高率曲线图按灵敏度分析思路,即当某一资源数量变化时,假定其它参数不变,分析总其总的目标变动的幅度.对图5中模型,如先变动角色a的资源数,其它资源数不变,观察总工作时间的变动情况,详细数据见表1.通过对表1进行数据处理,得到图6,从中可以看出当角色a的资源数从3个变为4个时,相对提高和绝对提高率较高,并且此时的资源利用率为接近于平均水准的10.9%,因此,可以认为角色a的数量为4时最优,当角色数为5时,为资源瓶颈,即再增加资源,总工作时间下降也很缓慢,即效果不显著.同样的思路,通过模拟得到其它角色最优资源数分布为b:3,c:2,d:2,e:2,其中,由于角色b和角色c处于同步位置,也就是在处理同一个任务实例时,其中一个角色处理速率高于另一个,即一个先执行完毕,另一个还在执行,此时,由于同步特性,只有等两个角色执行完毕,任务实例才能通往下一个结点,因此,角色b与角色c的人员配置应根据其工作效率而定,亦即各角色数与工作效率的乘积比率接近1时效果较好.(2)工作绩效提高决策问题人力资源管理中一个主要管理决策问题是优先岗位培训问题,即优先考虑培训何种岗位,哪些角色呢?本文试图利用模拟的方法,通过采集和比较相关数据,按灵敏度的思路,即变动一角色的服务率,其它角色服务率不变,求出其当前总工作时间,比较最终所得的一组工作时间,我们可以认为,对总工作时间贡献率最大的角色信息,应是优先培训对象,提高他们的服务率,将能较好的提高任务的总服务效果.下表为通过仿真得到各角色提高服务率()后任务总工作时间的数据:表3:角色-任务系统仿真数据(2)初始状况 提高10% 提高20% 提高30% 提高40% 角色 总工作时间 总工作时间 总工作时间 总工作时间 总工作时间a 15 0.2290966 16.5 0.2174309 18 0.217129325 19.5 0.208340051 21 0.199897778b 10 0.2290966 11 0.2227952 12 0.217544032 13 0.247403018 14 0.247403018c 12 0.2290966