（机械制造及其自动化专业论文）基于有向图的工作流建模及其运行研究.pdf

基于有向图的工作流建模及其运行研究 摘要 在总结工作流模型的要求与分析现有工作流建模方法的不足 的基础上，针对这些建模方法在支持业务过程的自动化执行、模 型分析及模型插述等方面的不足，且结合业务过程的特点，提出 一种工作流建模方法及工作流实例的运行算法。首先提出了基于 有向图的工作流建模方法，利用建模方法中的描述元素可以直观 地、清晰地表达出业务过程的执行关系且便于一般用户使用：其 次，设计出一个包括过程模型、功能模型等多个子模型构成的综 合性的工作流模型，设计的工作流模型对业务过程中的执行者、 执行规则等元素提供了全方位的描述：之后，提出了工作流模型 的分析方法，主要就工作流模型的正确性证明和性能分析两方面 进行：最后，提供了一个执行工作流实例的运行算法，通过此算 法能够合理地、正确地执行各类业务过程。 关键词：业务过程工作流模型工作流模型分析工作流实例 r e s e a r c ho nw o r k f l o wm o d e l i n ga n d i t si m p l e m e n t a t i o n b a s e do nd i r e c t e dg r a p h a b s t r a c t b a s e do nt h es u m m a r i z a t i o no fr e q u e s t si nt h ew o r k f l o wm o d e la n dt h e a n a l y s i s o ft h ed e f i c i e n c i e so fp r e s e n tw o r k f i o wm o d e l i n gm e t h o d s ，a w o r k f l o wm o d e l i n gm e t h o da n dar u n n i n ga r i t h m e t i co fw o r k f l o wi n s t a n c e a r ep u tf o r w a r df r o mt h ep o i n to fc h a r a c t e r i s t i co fb u s i n e s sp r o c e s st oa v o i d t h ed e f i c i e n c i e so fp r e s e n tw o r k f l o wm e t h o d si nt h es u p p o r to fa u t o m a t i o n e x e c u t i n g 、m o d e la n a l y s i sa n dm o d e ld e s c r i p t i o no fb u s i n e s sp r o c e s s f i r s t l y ， w o r k f l o w m o d e l i n g m e t h o db a s e do nd i r e c t e dg r a p hi sp u tf o r w a r d ， d e s c r i p t i v ee l e m e n t so ft h em o d e l i n gm e t h o da r eu s e dt oe x p r e s se x e c u t i n g l o g i co fb u s i n e s sp r o c e s sv i s u a l l ya n dc l e a r l y ，a n dc o m m o nu s e r su s et h e m e t h o dc o n v e n i e n t l y ；s e c o n d l y , ac o m p o s i t i v ew o r k f l o wm o d e li sd e s i g n e d ， t h em o d e li sc o m p o s e do fm a n yc h i l dm o d e l s ，s u c ha sp r o c e s sm o d e la n d f u n c t i o nm o d e l ，d e s i g n e dw o r k f l o wm o d e lg i v e sg e n e r a ld e s c r i p t i o na b o u ta l l e l e m e n t so fb u s i n e s sp r o c e s s e s ，s u c ha se x e c u t o r s 、e x e c u t i o nr u l e s ；t h i r d l y , r e l a t i v ea n a l y s i sm e t h o d sa r ep r e s e n ti nt w oa s p e c t so fc o r r e c t n e s sv a l i d a t i o n a n dp e r f o r m a n c ea n a l y s i s ；a tl a s t ，ar u n n i n ga r i t h m e t i co fw o r k f l o wi n s t a n c e i sb r o u g h tf o r w a r d ，t h ea r i t h m e t i cm a ye x e c u t ea l lk i n d so fb u s i n e s sp r o c e s s l o g i c a l l ya n de x a c t l y k e y w o r d s ：b u s i n e s sp r o c e s sw o r k f l o wm o d e l a n a l y s i so fw o r k f l o w m o d e lw o r k f l o wi n s t a n c e 插图清单 圉1 1 活动的i d e f o 描述2 图2 1 无向图的图形表示1 2 图2 2 有向图的图形表示1 2 图2 - 3 无向完全图1 3 图2 - 4 活动节点的图形表示形式1 4 图2 - 5 有向边的图形表示形式1 6 图2 - 6 活动的启动方式图标1 6 图2 7 产品规划阶段开发过程模型1 6 图2 墙基于有向图的过程模型类图表示1 7 图3 - 1 工作组的组织结构图2 1 图3 2 资源模型的组织结构图2 2 图3 3 信息模型的组织结构图2 3 图3 - 4 工作流模型的基本关系图2 4 图4 1 过程模型的结构冲突2 6 图4 2 过程模型的语义错误2 8 图4 3 工作流模型的四种基本结构3 0 图4 - 4 新员工正式录用过程模型3 1 图5 一l 活动实例内部运行机制示意图3 8 图5 2 产品设计和验证阶段过程模型4 1 图5 3 工作流实例的执行过程4 4 表格清单 表3 1 产品规划阶段开发过程模型的控制数据表2 0 表4 1 产品规划阶段过程模型的入度及出度统计表2 7 表4 2 新员工正式录用工作流实例的执行时间规划3 2 表5 1 产品设计和验证阶段过程模型执行顺序表4 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果。也不包宙为获得金目b 王些本堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：尹：永i 刃名霞签字日期：沙石年妇纠日 学位论文版权使用授权书 本学位论文作者完全了解金a b 王些盔堂有关保留、使用学位论文的规定有权保留 并向国家有关部门或机柯送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 胆至些盔坐可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：7 6 i 刃壬醴 签字日期七州苫年厂月。f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师粥 签字目艳扣( 矽 p 电话； 邮编： 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至 终得到了我的导师刘明周教授的悉心指导，无论从课程学习、论文选题， 还是到收集资料、论文成稿，都倾注了刘老师的心血，由衷感谢刘老师在 学业指导及各方面所给予我的关心以及从言传身教中学到的为人品质和 道德情操，老师广博的学识、严谨的治学作风、诲人不倦的教育情怀和对 事业的忠诚，必将使我终身受益，并激励我勇往直前。 感谢曹国安副教授、周蓉老师、张铭鑫老师等工业工程教研室的老师， 在我的课题研究过程中给我的指导、帮助和大力支持。 感谢蒋增强、何晓军、吴俊峰、郝理想、葛茂根、陈静等研究生同学 的指导和帮助，也感谢我已经毕业的师姐和师兄给予我的关怀和支持。感 谢所有关心和帮助过我的老师和同学们! 感谢我的亲人、同学和朋友。感谢他们对我的学习、工作的全力支持 和生活上的照顾! 在此深深感谢并祝福他们。 最后衷心感谢在百忙之中抽出宝贵时间对论文进行评审的专家和学 者们! 作者：陈四根 2 0 0 6 年5 月1 0 日 第一章绪论 1 1 过程管理的必要性 1 1 1 业务过程概述 1 1 1 1 业务过程的定义 过程，英文“p r o c e s s ”，也译作流程；过程是指事物的起末或事物变化发展 的经历i jj 。 h a m m e r 认为业务过程是指接受一种或多种输入并产生对顾客有价值的输 出的活动集合 2 1 。 d a v e n p o r t 则认为，业务过程是跨越时间和空间的工作活动的有序集合，它 有开始、结束，能明确区别输入和输出f 3 】。 r u t hs a r a 认为，业务过程是一个企业中具有某种结构( 结构是指活动之间 的逻辑关系) 的活动组，通过这组活动实现预期的目标1 4 1 。 归纳地讲，业务过程是指为完成业务目标( 或任务) ，人员或设备( 执行者) 在一定的规则约束下。利用资源所执行的一系列逻辑相关的活动的有序集合【5 1 。 因此，业务过程中牵涉到的元素有：活动、活动间的相互作用、资源、执行者、 业务目标和规则。 1 1 1 2 业务过程的内容 业务过程的组成元素就是活动，活动与活动之间的相互作用就构成业务过 程；在执行业务过程中，由执行者在一定规则的约束下调用所需资源来执行过 程中的活动，从而完成预定的业务目标。下面就业务过程的内容即活动、活动 间的相互作用、资源、执行者、业务目标及规则进行详细的描述。 1 ) 活动 活动表示在一段不间断的时间间隔内为实现某一业务目标由人工或自动完 成的一个行为，是组成业务过程的最小功能单元。业务过程中的活动往往是接 收某一种类型的输入，在约束规则下，利用相关的资源，经过活动内部的处理 转化为输出。为了形象地描述活动，我们使用了i d e f 0 方法【6 1 ，活动的i d e f 0 描述如图卜1 所示，主要有方框和箭头组成。方框表示活动，箭头表示与此活 动相联系的数据。左边的输入箭头表示为完成此活动所需要的数据；上方的控 制箭头表示活动所受到的约束条件，即指明该活动为什么这么进行；右边的输 出箭头表示执行活动时产生的数据，同时输出又可以作为另一个活动的输入、 机制或控制；下方的机制箭头表示该活动所要求的执行环境或支撑条件，即指 明该活动如何进行，可以是执行活动的人或硬、软件设备。输入与输出的关系 就是活动，是将输入数据转变为输出数据的一种变换：整个活动的完成过程就 是相关人员、设备在控制的作用下，根据给定的输入和资源，产生特定输出的 过程。 输 入 机制 输 出 图1 - 1 活动的| d e f 0 描述 2 ) 活动间的相互作用 一个业务过程由两个以上的活动组成，活动之间必然存在着相互作用。构 成过程的活动数量、各活动的处理能力、各活动之间的相互作用不同，导致业 务过程的性质不同。分析活动间的相互作用，活动之间存在以下四种类型的联 系 7 】= 数据联系：一个活动的输出是另一个活动的输入。 控制联系：一个活动对另一个活动产生控制作用。 资源关系：两个活动共享资源。 任务联系：两个活动执行的任务可能部分相同或存在关联。 考察活动之间的结构联系，可以将联系归纳为以下三种形式f 7 】： 顺序型：活动间有先后顺序的约束，其间只存在着单向的依赖关系。一 个活动必在另一个活动完成之后才能开始，即下游活动需要上游活动的信息 或实物输出作为输入才开始进行，其动态特征表现为活动间的串行依赖关 系。 耦合型：两个活动在执行时存在着双向的信息交换关系，如活动1 需要 活动2 的信息，活动2 需要活动l 的信息；有时这种信息交换需要反复多次， 因此，活动闾的依赖程度较高。 并列型：两个活动同时独立进行，活动间无信息交换，相互依赖程度较 低。 3 ) 资源 资源是执行活动时调用的各种实体，如人、物料或设备等。资源的定义涉 及到两个概念。即资源的能力和资源的可用性；其中，资源的可用性可定义为： 是一个从时间维到集合 可用。不可用 的映射，资源的可用性涉及到资源的状 态和对资源的使用、调度问题；资源的能力定义为：是指资源支持某一活动的 能力，一般用能力集对资源的能力进行描述。资源在企业活动中扮演着不同的 角色，它描述了支持活动执行的对象及其能力以及在企业中的组织管理情况。 2 根据资源的物质状态。可以分为有形资源和无形资源；有形资源具体包括 原材料、在制品、产品，包括设备、资金、人员等；无形资源包括技术、文档、 数据、知识、无形资产等。 根据资源的角色不同，可以分为主动资源和被动资源；其中，主动资源用 于执行活动的资源，如人、智能设备等；而主动资源在执行活动时需调用的资 源为被动资源。例如，张三在车床上加工一根轴，那么张三就是主动资源，而 加工轴时使用的资源如车床、润滑油等则为被动资源。 4 ) 执行者 执行者表示执行活动的人或职能工具，由执行者控制业务活动的执行过程。 执行者也为主动资源，因此执行者为资源的一部分。 根据执行者的特性可分为人和职能工具，其中职能工具表示具有一定智能 的物体，如电脑、数控机床或机器人等。 5 ) 业务目标 业务目标表述了一种功能性的状态，即业务过程预期达到的一种状态或状 态集f5 1 。业务目标实质上就是业务过程的所要完成的任务，通过任务的状态如未 开始、正在执行等即可监控整个业务过程的执行状况。根据业务目标的范畴可 分为战略目标和具体目标，战略目标对应于总任务，具体目标对应于不同等级 的子任务。 6 ) 规则 规则表示管理业务活动的行为、关系和属性的约束1 5 1 。规则定义了控制活动 执行的约束条件，主要包括对活动输入、活动执行的条件、活动执行顺序以及 活动执行完成条件，涵盖了环境、技术、以及企业内部条件等各个方面的约束。 1 1 2 业务过程管理的必要性 2 0 世纪6 0 年代之前，人们只对基本生活用品存在巨大需求，且许多商品还 供不应求。在这种需求模式下，市场的竞争焦点为成本，企业只负责大量生产 低成本的产品即可。 自2 0 世纪7 0 年代初至8 0 年代末，入们的基本需求已经得到满足，消费水 平逐渐提高，人们开始追求优质产品；因此，在这个时期，质量成为市场的竞 争焦点。企业纷纷推行全面质量管理( t o t a lq u a l i t ym a n a g e m e n t ，t q m ) ，并以 通过i s 0 9 0 0 0 质量体系认证作为赢得客户的手段。 进入2 0 世纪9 0 年代后，需求模式发生了更大的变化，人们需要多样化、 甚至个性化的产品，而且需要与其配套的更加详细的服务。在这种需求模式下， 时间成为新的竞争焦点。基于时间的竞争特点是不仅要求快速开发新产品、快 速制造新产品，而且要求制造出的新产品快速上市、快速销售配送、提供快速 的技术服务支持等，这就需要企业各部门之间、企业与产品流通的每个环节之 间紧密协作，对完成工作的整个过程进行管理显得十分重要。因此，现代企业 强调以业务过程为中心的管理以及进行业务过程集成等，迫切需要相关的技术 作为支持。工作流技术正是在这种背景下发展起来的，工作流技术是实现业务 过程建模、业务过程仿真分析、业务过程优化、业务过程管理与集成，最终实 现业务过程的自动化的核心技术7 1 。 1 ，2 工作流概述 1 2 1 工作流问题的起源 工作流是从英文单词w o r k f l o w 翻译得来的。w o r k f l o w 是由单词w o r k 和f l o w 组合得到的词。单词w o r k 表示工作或者任务，单词f l o w 的含义是流动、流程或 者流量等。f l o w 反映了一种变化以及变化的过程，它本身的含义比较抽象，但 是，当它与某个具体的过程相联系对就有了具体的含义，如表示物料传输过程 的物科流、表示资金流动的资金流、反映信息处理和传递过程的信息流，同样 还有价值流、决策流、控制流等概念。依此类推，用活动及活动之间变化的过 程表示的业务过程就是工作流【8 1 。 工作流的概念起源于生产组织和办公自动化领域。它是针对日常工作中具 有固定程序的括动丽提出的一个概念。目的是通过将工作分解成定义良好的任 务、角色、按照一定的规则和过程来执行这些任务并对它们进行监控，达到提 高办事效率、降低生产成本，提高企业生产经营管理水平和企业竞争力。 在应用实际中，虽然工作流的概念相对于物料流、资金流、信息流等概念 要抽象一些，但是，工作流从更高的层次上提供了实现物料流、资金流、信息 流及其涉及的相关过程与应用的集成机制，从而使得企业能够实现业务过程集 成、业务过程自动化与业务过程的管理。在工作流概念下实现业务过程集成与 业务过程自动化的集成机制是通过定义不同任务之间相互关系的工作流模型 ( 也称为过程模型) 【7 j 来实现。在工作流模型中，无论是具体的物料转移动作、 实际物理装置的操作动作，还是抽象的信息处理动作与决策过程，都可以用工 作流的基本组成元素一一任务( 也称为活动) 一一来统一进行描述。同样，反 映不同任务之间的关系，无论是具体的车间中零件加工顺序关系、办公自动化 中的文件批转，还是抽象的决策流之间的关系，都可以用工作流的基本组成元 素一一连接弧一来统一地描述。连接弧反映了对业务过程的一种控制逻辑， 它定义了活动之间的连接关系和执行顺序【8 】。 1 2 2 工作流的定义 对于工作流的定义，目前尚没有完全统一的定义，不同的研究者和工作流 产品供应商从不同的角度给出了工作流的定义，文献 8 ，9 总结了以下几个具有 代表性的定义： 工作流管理联盟给出的工作流定义是；工作流是一类能够完全或者部分自 4 动化执行的业务过程，它根据一系列过程规则，文档、信息或任务能够在不同 的执行者之问进行传递与执行。 g i g ag r o u p 绘出的工作流定义是：工作流是业务过程中可运转的部分，包 括任务的顺序以及由谁来执行、支持任务的信息流、评价与控制任务的跟踪、 报告机制。 i b ma l m a d e n 研究中心给出的工作流定义是：工作流是业务过程的一种计 算机化的表示模型，定义了完成整个过程所需要的各种参数。这些参数包括对 过程中每一个步骤的定义、步骤问的执行顺序、条件以及数据流的建立、每一 步骤由谁负责以及每个活动所需要的应用程序。 a m i t s h e t h 给出的工作流定义是：工作流是涉及到多任务协调执行的活动， 这些任务分别由不同的处理实体来完成。一项任务定义了需要做的某些工作， 它可用各种形式来进行定义，包括在文件或电子邮件中的文本描述、一张表格、 一条消息以及一个计算机程序。用来执行任务的处理实体可以是人，也可以是 计算机系统( 比如一个应用程序、一个数据库管理系统) 。 以上这些工作流的定义，虽然表述方式略有不同，但是基本上都达成一个 共识f 8 】：工作流是一种反映业务过程的计算机化的模型，是为了在先进计算机环 境支持下实现业务过程集成与业务过程自动化而建立的可由工作流管理系统执 行的业务模型。这些工作流的定义分别反映了业务过程如下几个方面的问题， 即业务过程是什么( 由哪些活动组成，也就是结构上的定义) 、怎么做( 活动间 的执行条件、规则以及所交互的信息，也就是控制流与信息流的定义) 、由谁来 做( 人或者计算机应用程序，也就是组织角色的定义) 、做得怎样( 通过工作流 管理系统对执行过程进行监控) 。 总而言之，工作流就是将一组任务组织起来完成某个业务过程。工作流中 两个最基本的元素是活动和活动之间的连接关系。活动对应于业务过程中的任 务，主要是反映业务过程中的执行动作或操作；活动之闻的连接关系代表了业 务过程的规则和业务流程。一个工作流就是一个用一组连接关系组合起来的一 组活动组成的一个反映业务过程的模型。执行活动及活动之间的连接关系说明 了如何完成业务过程，包括完成业务过程需要完成哪些任务和采用的步骤。 1 3 工作流模型概述 1 3 1 工作流模型的定义及要求 在企事业单位的日常办公活动中，大量的业务处理是按照某种业务规则进 行的，如货物订单处理、购买设备审批流程。工作流模型就是将这种业务处理 过程用一种计算机可处理的方式来表示，这种表示就是工作流模型，有时也称 为过程模型或过程定义【8 1 。实际上，工作流模型就是对工作流的抽象表示，也就 是对业务过程的抽象表示；因此，工作流模型应该完整地提出支持工作流定义 的概念，为建模用户提供工作流定义所需要的组件或元素。具体讲，工作流模 型不仅需要明确地表达活动及活动之间连接关系，而且还要描述活动传递的信 息、活动的执行者、活动所需要的资源等。对活动及其路由的描述是工作流模 型的主要内容，因为过程最终都可分解为各类活动，模型能否方便、全面的描 述过程，并便于过程的分析优化，依赖于活动的类型和语义。 工作流模型应能适应用户在建模和分析过程中提出的各种要求。对工作流 模型通常有以下几点要求d o ： 1 ) 形式化语义。工作流模型是对工作流的抽象化表示，理想的工作流模型 能够提供各种情况下的工作流规则。现实中工作流多是非结构化的，使业务规 则具有多样化的特点，这就要求工作流模型的建模元素能够具有全面的描述能 力，其语义应当能够覆盖控制流和数据流。并能容易翻译成工作流引擎可以高 效运行的语言代码。 2 ) 直观性。从用户的角度讲，工作流模型应能直观地表达工作流，尤其是 业务逻辑。 3 ) 较完整的表达能力。工作流模型应能表达业务过程的活动、循环、路由 和约束条件等。 4 ) 层次性。这体现在工作流节点的层次上，某些节点可能是子工作流。工 作流模型应具有嵌套的层次，便于处理复杂的业务过程。 5 ) 便于工作流性能的分析和优化。工作流的设计过程是复杂的，为改善工 作流的性能和效率，在工作流模型实际运行之前对其进行检查，即检查是否存 在一致性、正确性和实用性等问题。基于此，构建的工作流模型应便于工作流 的分析和优化，即能够提供相关的分析技术，通过这些分析技术能够找出工作 流的瓶颈，并在此基础上优化工作过程。工作流运行涉及到各种性能参数，如 执行时间、资源占有率、运行成本等，找出影响工作流性能的主要因素且对这 些因素进行定性定量分析，在分析的基础上改善工作流性能，以实现业务过程 的运行时间、运行成本、资源使用效率等性能参数综合最优化。 6 ) 柔性。组织运行环境的变化，导致业务过程和组织的变革。工作流模型 应能适应这些变化并为变化提供灵活的支持。这体现在工作流模型能够处理工 作流可能的变化或异常情况。 1 3 2 工作流模型的描述方法 工作流模型的描述方法有两种：形式化描述和非形式化描述。 非形式化描述采用图形符号表示活动和活动之间的约束关系，这种方法简 单直观，在用户建模、浏览时，提供图形化用户界面是必要的，大多数工作流 产品都支持图形化用户界面描述业务过程。 形式化描述采用工作流描述语言，即使用某种语言符号来表示工作流模型 中的各种元素：活动和业务处理规则。工作流模型形式化的描述方式主要有两 6 种b 0 1 ：( 1 ) 用类似解释程序的计算机语言描述活动、数据和逻辑关系，这种工作 流模型描述可以直接被工作流引擎解释执行或被转化为其他形式再执行。( 2 ) 用 面向对象技术分析活动及其逻辑关系，确定对应的对象属性和方法。通常把活 动和关系都视为对象。 文献 9 】总结了两种常用的工作流模型描述方法。具体如下： w i n o g r a d 与f l o r e s 在语言行为( s p e e c h a c t ) 理论的基础上提出了一种基于对 话的工作流模型，这种工作流模型是从客户方与服务方这两个角色之间的语言 行为交互上对工作流程进行定义的。基于语言行为理论的工作流模型是由一系 列闭合的工作流环相互连接而成，每个工作流环被四个语言行为分为四个阶段： 需求阶段、协商阶段、执行阶段和满意阶段，a c t i o nt e c h n o l o g i e s 的工作流产品 a c t i o n f l o w 就采用了这种工作流模型。 p e t r i 网也被用来建立工作流模型，通常用库所表示活动，而变迁则表示活 动之间的顺序。用p e t r i 网建立的工作流模型有：e l l i s 和n u t t 提出的 i c n ( i n f o r m a t i o nc o n t r o ln e t s ) 模型；v a nd e ra a l s t 则在p e t r i 网的基础上定义了 w f n e t ，即工作流网，在工作流网中，变迁被用来表示活动，而库所则表示活 动的使能条件。 还有其它工作流建模方法，如利用统一建模语言( u n i f i e dm o d e l i n gl a n g u a g e ， u m l ) 对工作流进行建模【l l 】，基于协调理论的工作流建模方法1 1 2 l ，等等。 建模方法构建的工作流模型不仅需要明确地表达业务过程中的活动及活动 之间的关系，而且还要描述活动所传递的信息、活动所需要的各种资源等，因 此，在工作流模型中还应加入描述数据、组织、资源的元素。w f m c 工作流参 考模型i 硼中提出了工作流相关数据、工作流控制数据及工作流参与者、角色等概 念。为了使工作流模型对信息、组织、资源等方面具有较强的描述能力，一些 工作流产品的过程定义工具把相关的描述部分扩充为一个个较为完整的子模 型，例如，w i d e 项目提出的由组织模型、信息模型与过程模型等三个子模型共 同构成的工作流模型【引。 通过分析以上工作流建模方法可知，大多数建模方法只侧重于某个方面， 如基于语言行为理论的工作流模型侧重于角色间交互的描述，p e t r i 网侧重子对 工作流语义的分析，等等。此外，这些建模方法主要是对业务过程中活动、活 动间执行关系进行描述，但缺少对数据资源和执行者组织结构的描述，不能很 好地支持业务过程的描述及执行。w i d e 项目提出的由组织模型、信息模型与过 程模型等3 个子模型共同构成的工作流模型则能分别描述组织实体、各种应用 数据和工作流的功能，即分别从三个方面描述一个业务过程；然而w i d e 组提 出的工作流模型缺少对工作流模型的语义分析，而且，其形式化描述没有与对 象技术和数据库技术密切联系起来。 7 1 3 3 工作流模型分析的概念和主要内容 一个工作流模型定义完后，在其执行前需要通过各种分析方法或分析工具 验证其是否能够正确地执行，我们把这个验证过程称为工作流模型分析。工作 流模型在业务过程的理解、分析和重组方面起着关键性的作用，一个定义完善、 正确的工作流模型能使工作流运行效率和可靠性得到提高。工作流模型中任何 不足将使业务目标不能完成，因此，工作流模型分析是必不可少的一个环节。 目前，许多工作流产品尚未提供工作流模型分析技术，有的可能只提供简 单的手工分析方法或分析工具，无法验证复杂的工作流模型。对复杂的业务过 程进行建模时，建模期间可能会引进难以预料的建模错误。工作流模型也许能 够描述各类业务过程，在运行期间也可能依照应用和用户所提供的协调参数执 行活动，这就是说一个工作流模型在某些情况下能正确地执行，而在其它情况 下错误地执行；这些错误是难以鉴定，并且甚至可能会发生在投入生产很长一 段时间之后。 工作流模型分析主要包括以下3 个方面的内容【硌】： 1 ) 有效性分析；测试工作流的执行是否能实现预期的业务目标。 2 ) 正确性证明：验证工作流模型的正确性。 3 ) 性能分析：评价工作流的某些性能参数，如工作流平均执行时间、活动 平均等待时间、资源占有率、服务水平等。 工作流模型分析是工作流技术中的难点也是热点。其中，工作流模型正确 性证明是过程模型分析的必要条件，仅当保证了过程模型的正确性。才能保证 过程模型有效性分析和性能分析的正常进行。 1 3 4 工作流模型的运行控制 工作流模型定义完后，由工作流执行服务软件对其进行实例化并控制其执 行过程。工作流执行服务软件对使用的工作流模型描述的过程进行初始化、调 度和监控过程中每个活动的执行，在需要人工介入的场合完成计算机应用软件 与操作人员的交互。这样，工作流执行服务软件实现了在模型中定义的业务过 程与现实世界中实际过程之间的连接，这个连接通过工作流执行服务软件与应 用软件、操作人员的交互来完成，实现这个连接的核心功能是工作流管理软件， 工作流管理软件又称为工作流引擎【8 1 。工作流引擎除了完成过程的创建、删除、 活动的执行与控制外，它的另外一个重要功能是完成与应用软件及操作人员的 交互。在实际应用中，应用软件和操作人员是完成业务工作的主体，而工作流 引擎通过过程定义和活动之间顺序控制实现这些独立功能实体间的集成，从而 使整个业务活动成为一个协调运行的整体。业务过程的执行通常需要若干个应 用软件和若干个人员的参与才能够完成，但是，任何一个大型组织中的实际应 用都是具有分布性和异构性的计算机网络环境中运行的。分布性是指应用软件 8 运行在不同地点的不同计算机系统上，异构性是指应用软件运行在不同的计算 机硬件环境、操作系统、数据库管理系统上。 为了支持大型组织中的业务过程，作为工作流管理控制软件的工作流引擎 同样需要在分布异构的环境中运行。因此，一般采用由多个工作流引擎组成的 工作流执行服务软件来控制过程实例的执行，每个工作流引擎可分布在不同地 点、不同运行环境中负责完成各自的工作。例如，管理工作流相关数据的工作 流引擎负责给工作流操作提供参数，并将执行结果写入相应的数据库，在过程 实例执行结束后删除中间数据等喁1 。另外，分布在多个计算机节点上的工作流引 擎，可避免使用一个引擎时出现的集中负载等问题的出现。 1 4 论文研究的背景、意义和主要内容 1 ，4 。l 论文研究的背景和意义 通过前面对工作流模型的介绍可知，大多数工作流建模方法构建的工作流 模型在形式化语义、可视化、可理解性和描述的全面性等方面难以均衡。另外， 大多数工作流建模方法或建模工具，未提供验证工作流模型正确的分析方法或 分析工具。针对上述工作流模型存在的不足，本文提出了一种新的工作流模型 描述方法，即基于有向图的工作流建模方法，此建模方法构建的工作流模型满 足以下几点要求： 1 ) 形式化语义。所构建的工作流模型是一个包含过程模型、功能模型等多 个子模型的综合性模型，其中过程模型提供了对各种业务规则的描述，且直接 翻译为工作流引擎可以运行的语言代码。 2 ) 可视化特征。工作流模型直观地表达了各种业务逻辑。 3 ) 较完整的表达能力。工作流模型能够表达过程的活动、路由、时间等控 制和约束条件。 4 ) 层次性。本建模方法通过引入子过程节点，使工作流模型具有层次性， 便于描述和处理复杂的过程。 5 ) 全面性。工作流模型是一个由过程模型、功能模型等子模型构成的综合 性模型，对业务过程的描述和执行提供了全面的支持。 6 ) 分析性。提供了相关验证工作流模型正确性的分析方法。 总之，利用本文提出的工作流建模方法能够可视化地、清晰地描述业务过 程，包含了业务过程中各种元素的描述，如人员、资源及执行规则等，能够有 效地、全面地描述和处理企业中的业务过程或其它领域的业务过程。因此，本 文提出的过程建模方法具有很好的理论指导意义和明显的现实意义。 1 4 2 论文研究的主要内容 本文是在合肥工业大学与安徽江淮汽车股份有限公司汽车技术研究院合作 9 项目“产品研发生命周期管理系统开发”的支持下开展研究的，论文主要就工 作流建模技术这块展开研究，主要的研究内容包括： 第一章为绪论。首先对业务过程和工作流进行了概述，其次从工作流模型 的定义、要求、工作流模型分析及工作流模型的运行控制四个方面对工作流模 型进行了概述；最后阐述了论文研究的背景和意义。 第二章提出了一种新的工作流建模方法，即基于有向图的工作流建模方法。 主要根据工作流模型应具备可视化、层次性及可理解性等要求，且从建模方法 的描述元素入手设计了这种建模方法。 第三章阐述了工作流模型的设计过程，工作流模型是一个由过程模型、信 息模型、组织模型等多个子模型构建的综合性工作流模型，此模型全方位支持 业务过程的描述和处理。 第四章阐述了工作流模型的分析方法，主要从正确性证明和性能分析两方 面提供了如何验证工作流模型正确性及工作流模型性能分析的方法。 第五章详细阐述工作流实例的执行过程，主要通过活动实例的状态、工作 流实例的状态来描述工作流实例的执行过程。 1 0 第二章基于有向图的工作流建模 2 1 有向图的定义 2 1 1 图论 匿论是离数数学的重要分支，它以图为研究对象。图论中的密是盘若干给 定的点及连接两点的边所构成的图形，这种图形通常用来描述某些事物之间的 某种特定关系，用点代表事物，用连接两点的边表示相应两个事物间具有这种 关系。 图论是在民间游戏当中孕育和诞生的，创建于1 7 3 6 年，欧拉是图论之父。 其后两百年间发展迟缓，直到1 9 3 6 年，匈牙利著名科学家寇尼希发表有限图 与无限图和1 9 3 0 年波兰科学家库拉托夫斯基证明了平面图( 即可以画在平面 图上，任两条连线不交叉的图) 的充分必要条件后，图论得到长足的发展。由 于近十多年以来，随着科技的迅速发展，在计算机科学、化学、生物学、地理 学、运筹学、信息论、系统论、控制论、网络理论等学科领域产生了大量新兴 课题。对其中一些课题的研究，往往借助于图论这个有效的数学工具，才能达 到令人滚意的结果。这棒，鹜论在多领域的应忍过程中，喜身也得副了极大发 展，使图论的理论更丰富。 从数学自身角度出发，图论与数学的其它分支，如群论、矩阵轮、概率论、 拓扑学、数值分析、组合数学等都有密切的联系。一方面这些学科中一些理论 用图论来表示，会显得更简洁。另一方面这些学科中的一些理论与图论结合， 会成为充满活力的研究课题，例如，概率论中的随机理论与图论结合形成的随 机图理论成为现代图论的一个重要研究课题。而且图论中的一些问题的解决往 往也离不开这些学科中的理论【1 ”。 2 1 2 图的基本概念 在日常生活、生产活动和科学实验中，人们常用点表示某个或某类事物， 丽鼹线表示事物闾韵关系或具有的属性，这样得到的图形裁是匿。在圉论中讨 论的图就是这种抽象的概念，它是研究事物间联系的一种数学模型，在研究具 体问题时，我们只考虑画出的图简单明了，能表达事物间的关系就可以了，而 不考虑图的大小、形状和线的曲直，这和几何中的图是完全不同的概念。下面 给出图的一些基本概念f 1 4 1 副。 定义l 设彳，b 是任意的非空集合，称 ( d ，6 ide 彳八b 占l 为彳和曰的无 序积，记作盎b o 由集合的概念可知，无论曰，b 是否相等，都有 a b ) = 6 ，日) 。 为简单书写。常把 a ，b ) 记为( a ，b ) 。 定义2 一个无向图g 是指一个无序的二元组( k 句；其中( 1 ) 降a 叫顶点 集，v e e 元素叫做顶点或结点；( 2 ) e 叫边集，它是无序积y 矿的多重子集( 在 一个集合a 中，如果它的元素是可以重复出现的，则集合a 叫做多重集) ，占中 的元素叫做无向边，简称为边。对于无向边铲m ，占而言，即玎，l ，是边 o k 的两个顶点时，我们称v i ，吩是相邻的，同时称e t ：和砟、e k 和吩是彼此关联 的：如果功吩，则称o k 和巧，o k 和吩的关联次数为1 ，如果v , = v j ，则称o k 和 码，n 和吩的关联次数为2 ，此时为环否则关联次数为0 。在无向图中，如 果有无向边p ，e 2 ，并且它们存在公共的顶点，那么也说口，e 2 是相邻的。设无 向图中的顶点v ，与e j 的关联次数为m 。，则： f0 ，不是e j 的顶点 加f = j ，是拍句一个顶点 l zv f 是毋的两个顶点 定义3 一个有向图d 是指一个有序的二元组( 以助，其中( 1 ) v ：o 叫做 顶点集，v 中元素叫做顶点或结点；( 2 ) e 叫边集，它是笛卡尔积y v 的多重 子集，e 中的元素叫做有向边，简称边。为了区别在无向图中用“= ( v ，v j ) 表示 无向边，在有向图中用一对尖括号即用e k = ( v ，v ， 表示有向边，v ，叫做有向边 的起点，v ，叫做有向边 的终点，读作“v 。邻接到v ，”或“v j 邻接于v ，”； 同时称段和v ，、e k 和v ，是彼此关联的 如果顶点y ，= v ，则称e k 为d 中的环。 有向图中的顶点v f 与e j ( 8 ，不是环) 的关联次数川，为 i 仉v ，不是西韵顶点 m q = 厶v i 是e j 的起点 i j ， 是日台勺终点 无论在无向图还是在有向图中，如果存在某项点v f ，且h 不是任何边的顶 点时，则称顶点v ；为孤立点。 下面图2 1 和图2 - 2 分别为一个无向图和一个有向图的图形表示。 图2 1 图2 - 2 有向图的图形表示 在图2 - 1 中，无向图中的圆圈表示顶点，连接两个顶点的直线表示无向边； 在图2 - 2 中。有向图中的圆圈表示顶点，连接两个顶点的有向直线表示有向边。 1 7 零一霉 在有向图中，如果有一对项点巧，v j 之间起点和终点相同的有向边多于条， 则也称这些边是平行边。而平行边的条数叫重数。无环但含有平行边的图叫多 重图。既不含平行边，也不含环的图叫简单图。 定义4 设弘似和白= 仍，历，都是图，如果有巧以西妄厶则称岛是g 的子图，占是岛的母图。如果有巧玎历c e 则称毋是g 的真子图。如果有 硌= 以历e 则称g 是口的支撑子圈( 生成子图) 。 定义5 设无向图g 有力个顶点，如果任意两个不同的顶点之间有且仅有一 条边，称无向图占为无向完全图，记为尼。如下图为。 幽2 - 3 无向完全圈 定义6 设有向图d 有n 个顶点，如果将d 中的所有有向边都用无向边代替 后，所得的图g 是完全无向图，则称有向图d 是有向完全图， 2 1 3 有向图 有向图的基本定义在前面已给出，除此之外，有向图还有许多相关的术语 以及由有向图延伸出来的概念。下面给出与有向图相关的各种定义【1 6 ， 1 。 定义1( 顶点的度) 设胆( 以d 为一个有向图。若 丘顶点诈 的度指依附于吩的边数，通常记为t d ( 砖) 。顶点y ，的入度是指以吒为终点的弧 的个数，记为i d ( 巧) ；顶点n 的出度指以叶为始点的弧的个数，记为0 d ( n ) 。 t d ( n ) = i d ( n ) + 0 d ( 听) 。 定义2 ( 路径和路径长度) 设d = ( v ，e ) 为一个有向图，唯，e 圪 与k 的路径指顶点序列唯，v i ，v j 厶，v l 埘h ，其中， ， ， 分别为有向图中的有向边那么唯与v ，的路径长度为m + l ，若如= b ，则称 该踌径为回路。 定义3 设有向图d = ( v ，e ) 中有一条路径p = v ，v 2 ，v i 。当1 i k 时， 称顶点v 川为顶点的后继节点，路经p 的每一个元素v ，( 除最后一个元素外) 都有一个后继节点；当1 i k 时，称顶点v ，为顶点v 州的前驱节点，路经p 的 每一个元素v ，( 除第一个元素外) 都有一个前驱节点。 定义4 设有向图d = ( v 。) 。f r o m n o d c ( e ) 表示有向边g 的开始节点，表 示为v pe e - f r o m n o d e ( p ) ：e nt o n o d e ( e ) 表示有向边e 的结束节点，表示为 vee e ，t o n o d e ( e ) ：e 一矿。 定义5 设有向图d = ( ne ) 。i n e d g c ( v ) 表示结束节点为v 的有向边的集合， 称i n e d g e ( v ) 的边为节点v 的输入有向边，表示为v ee e ，i n e d g e ( e ) = e e 印 a t o n o d c ( e ) = v 。o u t e d g e ( v ) 表示开始节点为v 的有向边的集合，称o u t e d g e ( v ) 中的边为节点v 的输出有向边，表示为vee e ，o u t e d g e ( b ) = p i g e 八 f r o m n o d e ( e ) = v 。 定义6 设有向图d = ( 矿，e ) 。p