（控制科学与工程专业论文）广义良构工作流业务过程实例时间性能分析.pdf

摘要企业在激烈的市场竞争和频繁变化的服务需求下，必须经常性地调整自身的内部架构和业务过程以应对挑战。工作流技术，由于其高效、自动的任务调度模式及对业务过程重组的适应能力，正受到广泛关注。工作流管理系统实施过程中，运行中的业务过程实例的完成时间是企业和用户都十分关心的问题，它直接影响到企业的各项相关工作的安排以及客户服务质量。本文研究业务过程实例完成时间预测中的几个关键问题。在分析现有工作流良构性约束的不足的基础上，提出了广义良构工作流模型，扩展了工作流模型的描述能力，给出了建立符合广义良构性约束的工作流网的方法。为了便于实现广义良构工作流时间性能的自动计算，提出了工作流实例子图路由概率的计算方法、实例子图中基本工作流模式的识别规则和广义良构工作流时间性能计算方法。研究了执行中的变迁和包含它们的工作流模式的时间性能分析问题，详细分析了一个业务过程实例运行中相应工作流网中的变迁的各种状态，对不同状态的变迁提出了不同的处理方法。针对执行中的变迁，提出了活跃变迁概念及其性能等价模型，在此基础上推导出了活跃模式的概念及相应的性能计算公式，验证了一个实例的时间性能动态计算过程。由于业务实例的时间性能仅与其己访问和将来可能访问的网元素相关，而与被旁路的其它网元素无关，因此，提出了业务实例的可达子网概念及其建立算法，并利用实例子图分解算法将广义良构的可达子网时间性能求解问题转换为更为简单的实例子图的性能求解问题进行处理，从而得到业务实例的时间性能。文中对算法的时间复杂性进行了分析，并给出了数学证明，提出了计算优化方法。为进一步改善业务实例时间性能分析过程的计算效率，通过对广义良构工作流网的仔细分析，提出了业务实例的归属子图集、实例子图拐点集、工作流网拐点集以及业务实例拐点集的概念，并数学证明了实例子图与其拐点集之间的一一对应关系，推导出了寻找业务实例的归属子图集的简便方法。在此基础上提出的业务实例完成时间分析算法避免了可达子网的建立与分解，从而降低了性能分析时间。为准确预测业务过程实例在不同的系统负载状态下在各活动处的等待时间，提出了根据系统中各服务台上的排队状态估计业务过程实例在各服务台上的等待时间的仿真计算方法；设计了相应的多级串联排队系统仿真软件，利用蒙特卡罗方法进行了仿真计算并对计算结果进行了分析，在同样的环境设置下，多次仿真得到的排队等待时间较为一致，表明了仿真方法的可用性。本文通过深入研究预测业务过程实例完成时间中的几个关键问题，构建出了一套合理的业务过程实例的实时时间性能分析框架，从而改善企业的服务质量并帮助其合理安排生产经营活动，并为工作流自动调度程序提供依据。关键词：工作流，性能分析，广义良构工作流，可达子网，实例子图，串联排队系统a b s t r a c tn o w a d a y s ，e n t e r p r i s e sf a c et h ef i e r c em a r k e tc o m p e t i t i o na n df r e q u e n t l y c h a n g i n gd e m a n df o rs e r v i c e s ，t h u si t si n t e r n a la r c h i t e c t u r ea n db u s i n e s sp r o c e s s e sm u s tb ea d j u s t e dr e g u l a r l yt om e e tt h ec h a l l e n g e w o r k f l o wt e c h n o l o g y ，b e c a u s eo fi t sh i g he f f i c i e n c y ，a u t o m a t i ct a s ks c h e d u l i n gm o d e la n da b i l i t yt oa d a p tt ob u s i n e s sp r o c e s sr e e n g i n e e r i n g ，h a sb e e nr e c e i v i n gm u c ha t t e n t i o n i ni m p l e m e n t e dw o r k f l o wm a n a g e m e n ts y s t e m s ，c o m p l e t i o nt i m eo fr u n n i n gi n s t a n c e so fb u s i n e s sp r o c e s si sak e yi s s u et h a tr e c e i v e sm u c hc o n c e r nf r o mb o t he n t e r p r i s e sa n di t sc l i e n t sb e c a u s ei th a sad i r e c ti m p a c to nb o t hr e l e v a n tw o r ka r r a n g e m e n t so fe n t e r p r i s e sa n dc u s t o m e rs e r v i c eq u a l i t y t h i st h e s i sf o c u s e do ns e v e r a lk e yp r o b l e m si np r e d i c t i n gc o m p l e t i o nt i m e o fb u s i n e s sp r o c e s si n s t a n c e s i nt h i sp a p e r , b ya n a l y z i n gs h o r t a g eo fe x i s t i n gw e l l f o r m e dw o r k f l o wm o d e l s ，g e n e r a l i z e dw e l l f o r m e dw o r k f l o wm o d e l ( g w f w m ) w a sp u tf o r w a r dt oe x t e n dt h ea b i l i t yo fw o r k f l o wm o d e lt od e s c r i b eb u s i n e s sp r o c e s s ；a l s o ，a na l g o r i t h mt ob u i l dw o r k f l o wn e t si nc o n f o r m i t yw i t hg w f w mw a sp r o p o s e d i no r d e rt of a c i l i t a t ea u t o m a t i cc a l c u l a t i o no ft i m ep e r f o r m a n c ef o rg e n e r a l i z e dw e l l - f o r m e dw o r k f l o w ，m e t h o dt oc o m p u t er o u t i n gp r o b a b i l i t yo fi n s t a n c es u b g r a p h si nw o r k f l o wn e t sw a sp r o p o s e d ，a n dr u l e st oi d e n t i f yb a s i cw o r k f l o wp a t t e r n sw e r eg i v e n l a s t l y ，a na l g o r i t h mt oa n a l y z et i m ep e r f o r m a n c ef o rg e n e r a l i z e dw e l l f o r m e dw o r k f l o ww a sp u tf o r w a r d t oa n a l y z et i m ep e r f o r m a n c ef o rr u n n i n gw o r k f l o wi n s t a n c e s ，f i r s to fa l l ，s t a t e so ft r a n s i t i o n sw e r ec l a s s i f i e d ，a n dd i f f e r e n tm e t h o d st oc o m p u t et i m ep e r f o r m a n c ef o rt r a n s i t i o n si nd i f f e r e n ts t a t e sw e r ep r o p o s e d s p e c i a l l y ，f o ri ue x e c u t i n gt r a n s i t i o n s ，a c t i v et r a n s i t i o np e r f o r m a n c ee q u i v a l e n tm o d e l sw e r ep r o p o s e dt oc o m p u t et h e i rt i m ep e r f o r m a n c e ；f u r t h e r m o r e ，p e r f o r m a n c em o d e l sf o rw o r k f l o wp a t t e m si n c l u d i n ga c t i v et r a n s i t i o n sw e r ed e d u c e d 1 _ o to rw o r k t l o wn e t sme n v i r o n m e n t ss u b je c tt oc h a n g e s ，t h ec o n c e p to fr e a c h a b l es u b n e t sw a sp r o p o s e d ，a n da np e r f o r m a n c ea n a l y s i sa l g o r i t h mb a s e do nt e c h n o l o g yt od e c o m p o s es u b n e t sw a sg i v e n ，i nw h i c hg e n e r a l i z e dw e l l f o r m e dr e a c h a b l es u b n e t sw e r et r a n s f o r m e di n t om o r es i m p l ei n s t a n c es u b g r a p h s ，t h u se x i s t i n gr e d u c i n ga p p r o a c h e sc a nb eu s e dt oc o m p u t et i m ep e r f o r m a n c ef o ri t a l s o ，c o m p u t i n gc o m p l e x i t yo ft h ea l g o r i t h mw a sa n a l y z e d ，a n do p t i m i z i n ga p p r o a c hw a sp r o p o s e d f o rw o r k f l o wn e t sr e l a t i v e l ys t a b l ei ns t r u c t u r ea n dr e s o u r c e s ，c o n c e p t so fp o t e n t i a li n s t a n c es u b g r a p h ss e t ，i n f l e x i o ns e to fi n s t a n c es u b g r a p h ，i n f l e x i o ns e to fw o r k f l o wn e t ，a n di n f l e x i o ns e to fw o r k f l o wi n s t a n c ew e r ep r o p o s e d ，a n dt h ec o r r e s p o n d i n gr e l a t i o n s h i pb e t w e e nw o r k f l o wi n s t a n c ea n di t si n f l e x i o ns e tw a sd e m o n s t r a t e d ，t h u sa nm o r ee a s ya p p r o a c ht of i n dp o t e n t i a li n s t a n c es u b g r a p hs e tf o rw o r k f l o wi n s t a n c ew a sd e d u c e d b ya v o i ds t a g e st ob u i l da n dd e c o m p o s er e a c h a b l es u b n e t s ，t h i sa p p r o a c hc a nr e d u c et i m es p e n ti np e r f o r m a n c ea n a l y s i sf o rw o r k f l o wi n s t a n c e s w a i t i n gt i m eo fw o r k f l o wi n s t a n c e sa ta c t i v i t i e sw a si m p o r t a n tp a r to fi t sc o m p l e t i o nt i m e ，w h i c hv a r i e dd r a m a t i c a l l yd e p e n d e n to ns y s t e ml o a d i nt h i sp a p e r , am e t h o dt oe s t i m a t ew a i t i n gt i m eo fw o r k f l o wi n s t a n c ea te v e r ya c t i v i t ya c c o r d i n gt oc u r r e n tl o a do fw h o l es y s t e mw a sp r o p o s e d t h i sa p p r o a c hw a sb a s e do nm o n t ec a r l os i m u l a t i o n w a i t i n gt i m ei nt a n d e mq u e u i n gs y s t e m sc a nb ee s t i m a t eb yas i m u l a t i o np r o g r a md e s i g n e df o rt a n d e mq u e u i n gs y s t e m sw i t hn m l t i p l es e r v i c es t a t i o n s r e p e a t e ds i m u l a t i o nu n d e rs a m ee n v i r o n m e n ts e t t i n g sa c h i e v e dc o n s i s t e n tr e s u l t s ，i n d i c a t i n gt h ea v a i l a b i l i t yo ft h es i m u l a t i o nm e t h o d b a s e do nt h er e s e a r c ho na n a l y s i sf o rw o r k f l o wi n s t a n c e s ，s e v e r a lk e ya s p e c t so ft i m ep e r f o r m a n c et h i sp a p e rt r yt ob u i l das o u n dp e r f o r m a n c ei va n a l y s i sf r a m e w o r kt oi m p r o v eq u a l i t yo fs e r v i c ea n dw o r ka r r a n g e m e n tf o re n t e r p r i s e s k e yw o r d s ：w o r k f l o w ，p e r f o r m a n c ea n a l y s i s ，g e n e r a l i z e dw e l l f o r m e dw o r k f l o w ，r e a c h a b l eq u e u i n gs y s t e ms u b n e t ，i n s t a n c es u b g r a p h ，t a n d e mv中南大学博士学位论文第一章绪论1 1 研究背景与意义第一章绪论过去二三十年来，信息技术的快速发展与广泛应用极大地提高了各种企业和组织的生产效率并改进了其服务质量，而经济全球化的不断发展使得企业和组织面临着不断变化的复杂竞争环境和更高的服务要求，这导致公司内部和公司之间的工作组织日益复杂，因此需要开发出更加灵活高效的信息系统以支持业务过程管理与过程协调。当前，很多非i t 领域的企业和组织都专门组建了信息技术部门以应对这些需求。传统信息系统擅长于各种业务信息的收集、处理和交换，但复杂、多变的市场环境要求企业的各种任务调度和执行更加高效和自动化，并且各种信息能够在分布式环境中得到集中监控，及时发现效率瓶颈，并能对生产过程的频繁调整作出快速反应，这就对传统信息系统提出了巨大挑战。工作流管理系统【卜4 】正是为应对上述挑战而生。在传统的信息系统中，业务逻辑内建在应用程序之中，一旦业务流程发生调整，信息系统将会部分或全部失效。工作流管理系统将业务过程定义分离出来作为单独的文件存在，实现了业务逻辑与应用程序的分离，使业务过程的变更更加轻松快捷，此外，工作流管理技术通过利用计算机控制业务过程自动或半自动地运行h 1 ，帮助企业和组织降低业务重组的代价、提高生产效率、降低生产成本、改善服务质量。当前，工作流管理系统已经受到了工业界和学术界的广泛关注。每年都有大量相关的国际会议、论坛召开，国内外涌现出了一批优秀的工作流产品，世界五百强公司和国内的一些著名公司也部署了不同层次的工作流支撑系统。然而，由于工作流技术发展时间还不长，在理论和应用方面还存在一些急需解决的问题，这一方面给工业界和研究界提供了很大的研究和发展空间，另一方面也存在着很大的挑战。各种组织部署工作流管理系统后，往往对其运行效率与实时运行状态十分关心，主流工作流厂商如u l ti m u s 拍1 、t i b c o 陋1 等都在工作流平台上提供了相应的分析与监控工具，为组织提供工作流管理系统的各种性能指标诸如吞吐量、生产周期、生产成本以及资源利用率的统计与分析。上述分析工具虽然能从宏观角度给出工作流管理系统的运行状态，但对于组织而言，日常微观管理尤为重要。工作流管理系统上部署的往往是组织的关键业务过程，对这些业务过程的运行实例进行合理的调度、控制对提高系统效率、改进客户中南大学博士学位论文第一章绪论满意度意义重大。在直接面向用户的工作流应用如保险索赔7 1 、订单处理【8 1 以及期刊审稿流程9 】等中，用户一方面对业务处理速度有较高要求，另一方面希望得知一个大概的完成时间，以便安排其他工作。而在企业内部业务过程如产品开剔1 0 域生产过程【1 1 】中，合理估计业务过程实例完成时间有利于组织调配生产资源、合理安排配套工作、提高生产运作效率。由于业务处理时间在工作流管理系统处于不同繁忙程度时差异较大，简单地提供在用户提交业务处理要求时反馈一个统计意义上的平均处理周期无法令用户满意。此外，对于涉及到大量处理阶段的业务过程，在其处理期间系统繁忙程度变化较大，需要在其处理期间在不同的处理阶段对其完成时间进行预测，以提高预测准确度。在对处理时间要求苛刻的工作流管理系统中，业务过程的某些分支往往有多条可相互替代的执行路径，其中最佳执行路径通常包含更多处理阶段，需要更多时间或代价，而替代路径虽然达不到最优路径的处理效果，但包含更少处理阶段以及更小处理代价。自动调度程序可在业务过程实例处理的过程中动态地检查业务实例的完成时间，一旦发现可能超时，即放弃最优执行路径而转到替代路径执行以满足处理时间约束，即进行所谓的调整( e s c a l a t i o n ) 1 2 - 1 4 】。在这种情况下，在业务过程实例执行过程中合理地动态预测其完成时间以判断是否超时尤为重要。此外，即使某些业务过程实例的超时是无法避免的，合理的完成时间预测也有助于企业管理人员掌握各项业务执行进度，对可能的延误及时做好补救措施，并改善客户服务质量。实时动态预测业务过程实例的时间性能主要涉及到如下问题：( 1 ) 业务过程建模约束模型组织在开发业务过程时，必须选择合适的工作流模型以建立无逻辑错误的业务过程定义。当前简单的工作流模型通常描述能力不足，但相应的工作流管理系统实现更加简单，而复杂的工作流模型虽具有更强的描述能力，但相关的设计过程、分析技术与实现技术更加复杂。当前还缺乏既有强大描述能力又易于在设计业务过程时遵循的工作流模型。此外，不同的工作流模型由于其结构特征上的差异，其分析技术也呈现不同的特点与困难程度，因此，必须首先明确所使用的工作流模型才能在其基础上研究实时动态预测业务过程实例的时间性能的技术。( 2 ) 用户要求的随机性对于运行中的业务过程实例，在其生命周期中大部分时间都存在正在执行的活动，而用户可能在其运行的任意时刻提出估计其完成时间的要求，忽略正在执行的活动的状态可能导致其估计的完成时间与实际值存在较大出入，从而影响整个工作2中南大学博士学位论文流业务过程实例的完成时间估计，因此必须充动以及包含这些活动的基本工作流模型结构的( 3 ) 时间性能估计的实时性工作流管理系统中运行的业务过程一般都求虽然不如工业控制系统苛刻，但仍然需要番( 4 ) 与系统工作状态的相关性整个工作流管理系统内部的不同业务过程过程实例的完成时间与其运行期间的系统繁十f时间性能必须考虑系统工作状态对业务过程完基于上述背景，本文通过扩展现有业务过能力与易设计性的工作流模型，并设计基于该方法，同时充分考虑用户要求的随机性对执在进一步改善业务过程实例完成时间预测的准形实例排队等待时间预测方法，从而为自动调度例分析依据，提高工作流管理系统的服务质量1 2 工作流技术1 2 1 工作流技术的起源与发展工作流 1 , 2 1 是从英文单词w o r k f l o w 翻译而乡示工作或者活动，而f l o w 表示流程或流动。奋既可表示物料传输过程的物料流，也可表示信和控制流等。工作流的概念最早起源于二十世纪八十年工作中固有程序的活动而提出的一个概念。提解成定义良好的任务、角色，按照一定的规则监控，以达到提高办事效率、降低生产成本、；企业或组织在业务活动过程中，各种资料的干乇公自动化系统通过表单传递将各种信息资料集员工，可以提高组织的工作效率。早期的办公前身。二十世纪八十年代中期，一些厂商陆续扦f i l e n e t 推出了w o r k f l o 商用系统，1 9 8 8 年，第一章绪论虑不特定时刻这些正在执行的活时间估计。向人类的服务系统，其实时性要受的时间内作出响应。之间存在着资源竞争关系，业务；息息相关，研究业务过程实例的间的影响。构设计约束，研究兼具强大描述：的复杂业务过程的时间性能求解j 动的处理时间的影响，此外，为研究与系统状态相关的业务过程一和过程管理人员提供业务过程实，o r k f l o w 是一个合成词，w o r k 表t 的经营管理与生产组织中，f l o w理和传输过程的信息流、决策流办公自动化领域，它是针对日常：作流技术的目的是通过将工作分程来执行这些任务并对它们进行夸业服务质量和竞争能力的目标。收集是一个效率低下的工作，办放，并按照需要自动传递到各个化系统可看作工作流管理系统的自己的工作流产品。1 9 8 4 年， ，s t a r 推出了v i e w s t a r 工作流系中南大学博士学位论文第一章绪论统，而i b m 公司也于1 9 8 8 年推出了i m a g e p l u s 。这批产品将图像扫描、复合文档、结构化路由以及光盘存储等技术结合在一起，形成了全面支持某些业务流程的工作流软件系统。由于市场需求强劲以及因特网和计算机的进一步发展，9 0 年代中后期出现了数十种工作流产品，工作流产品的市场增长率超过了3 5 。截止到2 0 0 0 年，提供工作流产品软件的公司已达到2 0 0 家，发展出了一批广受市场认可的产品，如a c t i o nt e c h n o l o g i e s 公司的a c t i o nw o r k f l o w ，l e yg m b h 公司的c o s a ，s t a r f f w a r e 公司的s t a f f w a r e 等。尽管这一时期工作流产品相当多，但由于其发展历史还不长，因此还存在一些不足之处，如功能有限、可靠性不高、各种标准还比较缺乏等等。特别是标准的缺乏使得不同工作流系统之间进行过程定义共享与交换、业务过程对接等方面遇到很大困难，而这在频繁发生公司兼并重组的市场尤为重要。近年来，工作流管理联盟陆续制定了一系列标准，以规范工作流产品的设计与实现，主要包括过程定义语言n 明、互操作性n6 l 、参考模型h 1 、应用程序调用接口n 刀等。很多大型知名软件厂商也开发出了自己的工作流产品或者在原有产品中增加了工作流支持以优化流程处理。o r a c l ew o r k f l o w n 鲫是o r a c l e 公司开发的工作流产品，它是一个支持基于业务过程集成的完整工作流管理系统。它提供了过程建模、自动化、以及连续的业务过程改善和根据用户定义的规则路由任意类型的信息。i b m 公司的w e b s p h e r ep r o c e s ss e r v e r n 町是一个高性能的业务过程自动化引擎，它建立在开放的标准之上，它能在非面向服务和面向服务的环境部署和执行业务过程。m i c r o s o f t 公司推出的b i z t a l ks e r v e r 脚1 是一个用于开发，部署，管理业务流程和基于x m lw e bs e r v i c e s 的集成服务器，此外，m i c r o s o f t 公司还推出了支持工作流应用程序开发软件支持包及相应的工作流引擎。b e a 则通过一系列的收购行动，成为能够供应集业务流程、应用和传统环境于一身的统一的基于s o a 的流程管理软件。t i b c o 公司在收购了s t a r f f w a r e 后，在其基础上推出的t i b c oi p r o c e s ss u i t e 哺1 ，能够自动执行并优化，包括日常任务到关键性的、长时间运行的以及涉及到跨组织和地域的各种类型过程。国内近年来也涌现出了一批成功的工作流产品，如杭州信雅达的s u n f l o w 【2 。西安协同的s y n c h r o f l o w 心剀，上海东兰的l i v e f l o w ，北京有生博大的r i s e o f f i c e ，北京世纪金政的k o o fm e t a l o g i c 以及清华大学研发的c i m f l o w 乜3 1 等等。此外，一些传统软件厂商在其已有平台里增加了工作流支持以改善其性能，如金蝶软件公司的b o s ，用友软件的u a p 以及普元软件公司的e o s 等。4中南大学博士学位论文第一章绪论1 2 2 工作流管理系统的架构工作流管理系统发展早期，各软件厂商各自为政，推出的工作流产品互不兼容导致工作流应用的开发难度大，升级维护困难，企业与合作伙伴的信息系统无法又-接沟通，过程定义无法共享等问题。为了解决上述问题，工作流管理联盟( w f m c j于1 9 9 3 年在欧洲成立。作为一个国际化的组织，w f m c 现在在全球已经拥有了超爻3 0 0 个的包括产品提供商、咨询机构、用户和研究机构的不同类型组织。w f m c 的主要目标是创建工作流相关的各种标准，并就工作流相关的问题对市龙进行培训，当前是唯一专注于工作流的标准化组织，其推出的w f x m l 和x p d l ， ，经被8 0 多个知名的工作流系统用来存储和交换过程模型。w f m c 做出的重要贡献之一是提出了工作流管理系统的参考模型，如图卜1 所示该参考模型的目的是为提高异构工作流产品的互操作性，并改善与其他i t 服务如电子邮件和文档管理的集成能力，从而增强工作流技术在i t 市场的竞争力。接口1图卜1 工作流参考模型从图1 1 可知，工作流管理系统主要包括过程定义工具、管理与监视工具、二，作流执行服务以及工作流客户端应用程序等组件，其中工作流执行服务是其核一d - 言- 1分。( 1 ) 工作流执行服务工作流执行服务是工作流管理系统的核心组件，其主要功能是创建业务过程戛例、基于过程定义生成工作项、匹配资源和工作项、支持活动的执行等。为了提蒿中南大学博士学位论文第一章绪论系统的可扩展性以及执行效率，执行服务可由多个工作流引擎组成，而用户任务可以被分布到多个引擎上执行。工作流引擎提供完成业务过程实例的关键支撑功能，其主要功能是创建新的业务实例、路由业务实例、管理业务实例属性、调度工作项给合适的雇员、在活动中启动指定的应用程序、记录执行历史并提供相应的统计信息，在多工作流引擎的系统中，各工作流引擎之间还需要协调机制以共同完成一项任务。( 2 ) 过程定义工具工作流过程定义是工作流执行服务工作的依据。工作流过程定义可由过程定义工具生成。一个过程定义既要包含活动的内容，又要说明执行活动的人或设备，此外，过程定义完毕还需要对其进行验证以保证其正确性，因此一个完整的过程定义工具通常包括过程定义组件、资源分类组件以及分析组件。( 3 ) 工作流客户端应用程序工作流客户端应用程序是普通用户执行工作流活动的接口，每个用户都有一个工作列表，其中持有该用户近期应执行的工作项，每个工作项还可标出截止期限、收益等以便决定工作项应被执行的次序。工作列表是由属于相应用户的工作项形成的集合，它是工作流客户端应用程序与工作流执行服务进行交互的桥梁。w f m c 提供了专用的接口描述对工作列表的操作，包括工作项的删除、转让工作项的撤销以及未完成工作项的挂起等等。此外，工作列表还可以包括那些执行条件尚不成熟但已安排让该用户执行的工作项，如此可以让用户了解未来工作内容及工作量大小。用户对工作列表的操作都可以通过客户端应用程序用户界面进行。( 4 ) 被调用的应用程序任务的执行通常要用到一个或多个外部程序。这些外部程序可能是通用的文字处理程序或表格处理程序，也可能是为完成某项任务特意编制的应用程序。这些外部程序并非工作流管理系统的组成部分，但由于它们与实际执行的工作相关，因此仍然属于具体的工作流应用。应用程序由工作流引擎启动以完成相应的工作。外部程序的应用有交互式应用和全自动应用两种方式，在交互式应用中，外部应用程序总是用户通过选中工作列表处理器中的某工作项来启动的，而在全自动应用中，外部程序无需用户干涉就能被执行。( 5 ) 工作流执行服务间的互操作性一个工作流管理系统中可能存在多个工作流引擎，这些工作流引擎可以接受相同的工作流定义，并协作完成任务。部分业务实例的处理可能不仅需要工作流管理系统内部协作，还需要与与其他部门或其他企业的异构工作流管理系统之间进行协作，只要这些工作流管理系统都实现了互操作性接口( 接口4 ) ，这种协作就是可行的。6中南大学博士学位论文第一章绪论( 6 ) 管理和监控工具管理和监控工具为管理员控制、监督和调整工作流管理系统的行为提供了合适的手段。这些工具可分成工作流运行管理工具和工作流的记录和报告工具。工作流运行管理工具涵盖了所有与工作流管理相关的工作，包括：用户信息管理：增加或删除用户，以及管理用户的详细信息的增加和删除：实施新的工作流定义；工作流系统技术参数的重新配置；业务实例的后勤状态的管理与检查等等。工作流记录和报告工具负责记录工作流运行过程中发生的大量数据，这些数据既可以在工作流运行期间生成统计报表共用户查看，也可以保存起来供以后的挖掘学习之用，以发现系统瓶颈、改进工作流过程定义以及其它有用的信息。管理和监控工具是通过调用运行服务的a p i ( 接口五) 完成上述各种操作的。1 3 国内外研究现状工作流管理系统一旦实施，企业业务过程管理人员就需要经常使用管理和监控工具对其进行监控、分析和调整，其中，预测业务过程实例的时间性能( 完成时间)是一个频繁操作。对工作流实例进行实时时间分析基于一个前提，即工作流模型必须是合理的阱1 。当前有两类方法保证工作流模型的合理性：( 1 ) 模型验证乜r 3 引：模型验证能检测设计出的工作流模型是否合理，但不能为模型设计人员提供避免设计出错误模型的指导原则；( 2 ) 模型构造约束啪恤1 ：模型构造约束方法通过提出构造模型的指导原则，使得按这些原则设计出的模型均满足合理性，但当前给出的约束过于严格，导致模型的描述能力受限。工作流模型是工作流管理系统的重要基础，针对不同的工作流模型，其相应的工作流设计方法与分析方法、工作流实例时间性能分析方法以及运行控制都有较大差异。简单的模型通常描述能力不足，但相应的工作流管理系统实现更加简单口町；复杂的工作流模型具有更强的描述能力，但相关的分析技术与实现技术更加复杂【7 6 o根据工作流过程的时间性能分析与业务过程生命周期的关系，当前的研究可大致分为三类：静态分析方法口9 5 4 1 ：在业务过程实施前对过程模型进行性能分析；动态分析方法畸5 飞7 1 ：在业务过程实施时对业务实例完成时间进行估计；历史分析方法嘞：根据业务过程执行产生的历史数据对过程性能进行挖掘评估并改进。在静态分析分析方面，工作流模型中活动的时间约束可以用其完成时间的概率7中南大学博士学位论文第一章绪论分布或者上限与下限描述，在此基础上，可以求取业务过程的平均周转时间“旷侧，最长完成时间“吼咖和完成时间的概率分布璐r 刚。在动态分析方面，主要是通过合理的调度使业务实例在截止期限前完成。文献n 3 1 提出业务实例可以根据实际情况改变执行路径以满足截止期限要求，文献n 4 1 给出了调整的3 d 框架，( d e t e c t ，d e c i d e ，d o ) 即超时检查，调整路径选择和执行，但没有给出超时检查的实现方法。由于超时检查是一个费时的工作，文献哺n 33 在工作流网的特定位置设立检查点对业务实例的时间约束进行检查，但其要求实例的截止期限比业务过程的最大完成时间还要大。动态调度程序自动调整以避免超时的前提是对超时的检测。即根据当前状态看，工作流实例是否能够如期完成。文献呻1 提出用待执行活动的当前队列长度与历史平均队列长度之比作为活动的负载因子，将其与活动的历史平均完成时间的乘积作为活动的预测完成时间，进而推算出整个业务实例的完成时间。文献嘶3 通过已完成活动的实际执行时间和未完成活动的最短和最长执行时间，估计出业务实例的最短和最长执行时间。考虑了不同工作流之间发生资源冲突而导致案例完成时间延长的情况，但没有考虑每个工作流的多个业务实例间资源竞争的情况。业务实例一旦启动，在其终止之前的绝大部分时间内都存在正在执行的活动( 以下简称活跃活动) ，因此，若要提供对业务实例实时、随机的完成时间估计，就必须对活跃活动及包含其的活跃模式( 构成工作流的基本结构) 的时间性能进行合理分析，而当前文献均没有给出活跃活动和活跃模式的性能计算模型。此外，由于分支路由的存在，业务实例只会经过业务过程的部分结构，只有这部分结构的性能对业务实例的性能会产生影响。除了资源的服务能力和业务过程的路由结构外，决定特定业务实例完成时间的还有一个重要因素，即业务实例运行时整个系统的负载，在资源有限的系统中，这将显著影响到业务实例的排队等待时间。文献m 6 钉对新到任务与历史数据的相似性进行判断，从而估计其执行时间。文献阳4 删根据任务属性和资源负载状态寻找历史数据中的相似者，从而估计排队等待时间。文献旧1 使用一个基于模板的方法对活动进行分类并预测其执行时间，进而通过模拟调度器的行为推导出排队延时。其准确性与任务的执行时间预测关系密切。文献汹。考虑到系统中一般有多个调度算法，管理员会根据不同的情况采取不同的调度算法，而这种变化通常不为用户和性能预测程序知晓，提出了一个根据预测失误率的增加动态修订预测策略的等待时间预测方法，且无需对队列中的活动执行时间进行预测。文献嘲鹪 髓1 对排队等待时间的预测都是针对活动的当前队列，而在工作流系统中，不但要估计业务实例的当前队列的等待时间，还要估计其未来将到达的资源处的排队等待时间。文献呻1 提出用待执行活动的当前队列长度与历史平均队列长度之8中南大学博士学位论文第一章绪论比作为活动的负载因子，将其与活动的历史平均完成时间的乘积作为活动的预测完成时间，进一步计算出整个业务实例的执行时间。文献嘞1 在t 时刻业务实例预测在各服务台的等待时间虽然考虑到了各服务台的当前负载，但是对于某个具体的实例而言，当它在t + a 时刻运行到其后面的某个服务台时，该服务台的负载( 队列长度) 可能与t 时刻的负载有较大差距。1 4 主要研究内容本文通过分析现有业务过程结构设计约束的不足，提出了广义良构工作流模型，本文的业务过程实例时间性能分析工作都是针对该模型下的业务过程进行：同时充分考虑用户或自动调度程序估计业务实例完成时间的随机性对执行中活动的处理时间的影响，提出了执行中活动的时间性能分析模型以及包含执行中活动的工作流模式的时间性能计算模型；研究工作流实例性能分析与其过程定义的关系，提出了与时间性能分析相关的可达子网的概念及其建立算法，改善了时间预测的合理性；为进一步提高工作流实时时间性能计算效率，提出了高效的可达子网追踪算法以快速确定工作流实例的可达子网结构；此外，还研究与系统繁忙状态相关的工作流实例在各服务台的等待队列长度预测方法，从而为其等待时间估计提供依据，以进一步提高整个业务实例完成时间估计的准确性。本文的研究工作从以下五个方面展开：( 1 ) 研究扩展工作流结构设计约束的广义良构工作流概念及相关算法包含“部分覆盖”的工作流模式的工作流过程定义的时间性能分析无法用常规的约简方法实现，而禁止工作流过程定义中出现工作流模式的“部分覆盖”现象又会降低过程定义设计的灵活性、引入不必要的冗余节点、增加过程定义的规模并导致难以描述复杂业务过程。为了解决上述问题，本文通过扩展现有工作流良构性的概念，提出了广义良构工作流的概念，其中允许业务过程定义中出现工作流模式的“部分覆盖”现象，但不允许其出现在业务过程定义的任一实例子图中，从而放宽了对工作流过程定义的约束，增强了其描述能力。此外，为了满足业务过程时间性能频繁计算的需要，提出了自动计算工作流过程的每个实例子图的时间性能及路由概率的算法，据此，又可以进而计算整个工作流过程的时间性能。( 2 ) 研究活跃活动及活跃模式的时间性能计算模型工作流管理系统中，业务实例的时间性能是业务管理和调度的重要依据。首先提出了活跃活动的概念，并研究了其在资源竞争条件下的性能等价模型；随后提出了活跃模式的概念及四种基本活跃模式的性能计算公式；最后用一个实例说明了利用上述成果对业务实例进行完成时间估计的计算过程；提出的方法可用于在任意时刻估计业务实例完成时间，并易于构造高效的估计算法。9中南大学博士学位论文第一章绪论( 3 ) 研究基于可达子网建立与分解的业务实例性能分析方法由于选择模式的存在，工作流网中的部分活动将被业务实例旁路，工作流业务实例的时间性能仅与已完成的活动和将来可能执行的活动构成的工作流子网有关，业务实例的性能估计只能针对该子网进行。文中研究了业务实例可达子网的特征及建立业务实例可达子网的规则和算法，随后结合活跃活动及活跃模式性能计算模型化简广义良构的业务实例可达子网，并将因工作流模式的部分覆盖而不能完全化简的可达子网转换为更为简单的归属子图以简化其性能求解。最后用例子演示了业务实例性能分析过程及方法的有效性。( 4 ) 研究基于可达子网跟踪的业务实例性能分析根据业务过程实例的运行状态建立其可达子网，并通过分解该子网实现计算业务实例时间性能的方法对于频繁更改的业务过程十分有效，但计算效率不能完全令人满意。提出业务过程实例的动态归属子图集概念以跟踪实例的可达子网的动态变化，并将复杂的实例时间性能求解问题转换为更为简单的归属子图的性能求解问题，此过程中，避免了可达子网建立与分解的开销，从而降低了业务过程实例时间性能计算的开销。( 5 ) 研究工作流实例排队等待时间预测方法除了资源的服务能力和业务过程的路由结构外，决定特定业务实例完成时间的还有一个重要因素，即业务实例运行时整个系统的负载，在资源有限的系统中，这将显著影响到业务实例的排队等待时间。排队等待时间与业务实例排队时的队列长度直接相关。当系统负载变化不大时，用每个活动的期望排队长度作为特定业务过程实例在该处的估计排队长度误差不大，若系统负载变化较大，则期望排队长度与特定业务实例在该活动处的排队长度可能会相去甚远，从而严重地影响业务实例完成时间估计的准确性和可信度。通过详细的理论分析，设计了用蒙特卡罗方法求解业务过程实例在各服务台的等待队列长度的仿真系统，根据该系统的模拟运行求出了一些样例情况下的等待队列长度，并对仿真结果进行了分析。1 5 论文的组织结构论文全文共七章。在提出广义良构工作流和活跃活动与活跃模式的基础上，提出了两种求解广义良构工作流业务实例的实时时间性能的算法，这两种算法分别适用于业务流程结构相对稳定和变动相对频繁的情况，对提出的算法进行了计算复杂性分析，并采取了必要的优化措施。此外，用蒙特卡罗仿真方法分析并求解了特定状态下业务实例在不同服务台上等待队列的长度，以此获得其在各服务台的等待时间的更准确估计。第一章为绪论。首先综述工作流技术的发展、产品以及体系架构，随后分析了1 0中南大学博士学位论文第一章绪论工作流过程时间性能分析的国内外现状，最后介绍本文研究的内容及所做的工作以及本文的组织结构和各章研究的内容。第二章为广义良构工作流。首先介绍了本文所要用到的p e t r i 网和工作流网的相关知识，随后分析现有工作流良构性的不足之处