（机械设计及理论专业论文）分散式跨组织工作流执行模型的研究.pdf

摘要 随着互联网的普及和电子商务的迅猛发展，业务外包和虚拟企业等成为现代 企业应对经济全球化的主要方式，作为实现企业业务过程重组、过程管理与过程 自动化的核心技术，跨组织工作流被越来越广泛地应用，跨组织工作流的执行方 式也成为工作流研究领域的一个重要方向。目前应用较多的执行方式多为集中 式，即中央系统对任务的执行条件等具有绝对的控制权限，各个执行代理只负责 接收、执行任务以及结果的反馈，互相之间不存在信息交换。在工作流执行之前， 每个任务的代理被预先定义，一旦代理出现异常，整个工作流的运行受阻。 本文在前人工作的基础上，提出了分散式跨组织工作流执行模型和自描述子 工作流的概念，根据分散式的执行方式对系统功能的要求给出了模型的框架实现 构想，并解释了每个结构的功能，对每个模块进行了详细划分，用逐步分割工作 流的方法实现工作流的分散式执行。每个代理执行完自身的任务之后将剩余的工 作流进行分割并传递给后序任务的执行代理，工作流在运行的过程中被动态地分 割，降低了工作流执行系统对于处于核心位置的工作流引擎的依赖，提高任务执 行代理的自主权。根据先决条件评估类型的不同，论文研究了系统响应时间、信 息交换量等几个性能指标，并与集中式的执行方式进行了比较，证明了工作流分 割算法的优越性。 针对现有研究的不足，结合去除冗余分割之后各个代理的负载状态，论文考 虑了工作流运行过程中代理的替代选择，主要针对仅指定角色而未指定代理的情 况进行了详细讨论，由相应任务的前序代理根据用户的要求选择执行代理。之后 就工作流执行过程中可能出现的问题进行了详细讨论并给出了解决方案，包括连 续代理之间的合作通信情况及其对任务的预调度。 最后，论文考虑了由于权力分散导致的合作组织中的利益冲突问题，根据冲 突关系的类型进行了算法说明，并以个性化订制自行车为例，分析了参与合作的 企业之间可能出现的问题，并通过分散式的执行方法安全高效地完成订单，说明 了本文方法的有效性和可行性。 关键词：跨组织工作流；分散式；工作流分割； 预调度：中国墙安全规则 a b s t r a c t w i t ht l l ep o p u l a d 够o ft h ei i l t c m 烈m l dm er a p i dd e v e l o p m e n to fe - c o m m e r c e ， o u t s o u r c i i l g 觚dv i r t u a l le n t e 印r i s e sh a v eb e c o m eam 旬0 rw a yt 0c o p e 谢吐1e c o n o n l i c g l o b a l i z a t i o nb ym o d 锄e n t e 叫s e 缸t 1 1 ec o r e 僦l l i l o l o g i e sf o re n t e r i 嫡s eb u s i n e s s p r o c e s sr n g i i l e e r i n g ，p r o c e s sm a n a g e m e n ta i l dp r o c e s sa u t o m a t i o i l ，c r o s s o 唱a i l i 骆 t i o n a lw o f i 【f l o wi sm o r cw i d e l yu s e d ，c m s s o 玛a l l i z a t i o n a lw o 舳0 w se x e c u t i o nl 璐 a l s ob e c o m ea ni 加p o r t a ：n tr e s e a r c hd i r e c t i o n w 1 1 i l e l e 戗肛嘲i z c 避w a 弘也a t 协e 伽砌s y s t 咖h a sa b s 0 l u t ec 0 曲o la u t h o r i 够f o ra l lt a s k s ，m a yb l o c kt 1 1 ee x e c 而o no f n l e 觚r ew o r k n o ws y s t e m 1 1 l “sp a p e r ，o n 吐l eb 弱i so f 吐1 ee x i s t i i l gr e s e a r c kad i 矧b l l t c dc r o s s o 玛a i l i z a t i o i i a lw o r k 以o wm o d e l锄ds e l f 二d e s c r i b i i l gw o d m o wc o n c e p t s a r e p r o p o s e d w o r ! k 丑o w s a r e 孕a d l l a l l yp a r t i t i o n e dd 埘n gm eq h 蒯o np r o c e s sf o rd i s t r i b u t e d e x e c u t i o 玛r c d l l c i i l g 吐l e 、o 湖o ws y s t e m sd 印e n d e mo nt h ec 0 佗w o r k f l o we n g i l l e ，t 0 i i l l p r o 、他也e 龇r t o n o i n yo f t a s ke x e c u t i o na g e n t t h e n 自o mm es y s t e mf e s p o n s et i i l l e ， t h c 舡咖唧n to f 洫f b m l a t i o ne x c h a n g ea n do 也e r 嬲p e 吐so f t h ei l n p l e m e n t a t i o i l ，a c 唧a i i s o n 、析mc e m r a l i z e da p p r 0 ha r e西v e nt 0p r o v e 血e 鲫p e r i o r i t ) ，o fm e a l g o r i n l m a c c o r d i n gt ot h e 佗q u i r e m e n to fd i s t r i b u t e di m p l 锄e m a t i o no fm es y s t e m ，a 丘a m e w o r kf o r l l i e v i n gt h ev i s i o no ft l l em o d e li sp p o s e d ，a n dm ee x p l a i l a t i o i 坞 f o rt h e 如n c t i o no fe a c hs 劬】c t u r ea r ef o l l o w e d 觚e rt l l e mi n c o r d 觚c ew i mn l e p r o b l 伽n s 也a tm a y o c c l l rd l l r i l 培t l l ep m c e s so f i i i l p l e m e m a t i o 玛s o m ea r ed i s c u s s e di n d 鲥l 锄ds o l u t i o 璐a r ef m m l yg i v e i l ，i i l c l u d i n gc o o p l e r a t i o n 锄dc o m m 砌c a t i o n k 小啪c o m i i l u o u sa g e m s ，n l ep r e d i s p 日t c l l i n go ft 豁l 【sa n di m a v o i d d b l ec 0 i l | 1 i c to f i i l t e r e s ti s 吼l e sk 小e e nd i 丘e r e mo 唱砒l i z a t i o n sd u r i n gc o o p e r a t i o n a sf o rt 1 1 es i ! _ c u a t i o n 也a to n l yr o l e sa r ed e s i 黟脚e di 1 1 s t e a do f 雄i p | 删a t ea g e n t ，p r e - 0 柑e ra g e mi s 弱s i g n e d t 0c h o o a p r o p e r o n e 嬲也e 惦e r 嬲k e d f i i l a l l y ，ac 戚o m i z a t i o nb i c y c l ec a s ei sc i t e dt 0 锄【a l y z et h ep r o b l e m st h a tm a y a r i 锄o n gt h ep a r t i c i p 锄：t s 蛐i 培e x e c m i o 玛t h eo r d r e ：r i sc o n l p l e t e d 鼹f e l y 锄d e 蚯c i e n n yi n d e c e l l t r a l i z e da p p r o a 也w h i c hs h o w s 廿1 ee 仃e c t i v 锄e s sa n d 觚i b i i 毋 o f 也e m e t h o dp r i 唧s e d i nn l i s p a p e r k e ，w o r d s ：c m s s 帕玛锄娩a t i o n a lw o r k f l o w ；d e c e n t m l i z e d ；w o r 姐o wp a r t i t i o n ； p r e - d i s p a t c h ；c h i n e 砌ls e c 砸t ) ，m o i d a l 第一章绪论 工作流技术是近几年来飞速发展的一项技术，它最基本的特征就是能够结合 人与机器的行为，特别是能够与应用程序和工具交互，从而完成业务过程的自动 化处理过程【。工作流技术从出现到现在，发挥了越来越重要的作用，已经逐渐 成为企业信息化建设方案中必不可少的内容之一。从简单的办公自动化系统的开 发，到企业e r p 系统的实施，再到为提高企业运营效率而出现的b p r 及b p m 系统，工作流技术都为其提供了有力的支撑。 1 1 工作流理论 1 1 1 工作流技术的起源和发展 工作流( w 6 r k n o w ) 就是“业务过程的部分或整体在计算机应用环境下 的自动化实现”，它主要解决的是“使在多个参与者之间按照某种预定义的 规则传递文档、信息或任务的过程自动进行，从而实现某个预期的业务目标， 或者促使该目标的实现 【2 1 。工作流的概念起源于生产组织和办公自动化领 域，是针对日常工作中具有固定程序活动而提出的，它不同于具体的物料流、 信息流、资金流等，而是包括这些概念流的业务流过程，具体的设计与企业 的经营过程密切相关。工作流的目的是通过将工作分解成定义良好的任务或 角色，按照一定的规则和过程来执行这些任务并对其进行监控，达到提高工 作效率、更好地控制过程、改善对客户的服务、有效管理业务流程等目的。 简单地说，工作流就是一系列相互衔接、自动进行的业务活动或任务。一般 情况下，一个工作流包括一组任务( 或活动) 及它们的相互顺序关系，还包 括流程及任务( 或活动) 的开始和终止条件，以及对每个任务( 或活动) 内 容的具体描述。 工作流在大多数实际应用中的情况可以这样来简单地描述：在网络、服 务器和多台计算机客户端的硬件平台上，按照预先设定的规则，借助某些应 用程序和入对相关数据的处理而完成业务过程。例如，在日常办公中，当撰 写好某份报告之后，需要将其提交给领导进行审阅或批示，而审批意见需要 汇集并提交给另外一个人，以便对报告进行进一步的修改，这样，可能会形 成同一篇文档在多个人之间的顺序或同时传递。对于这样的情况，我们可以 使用工作流技术来控制和管理文档在各个计算机之间自动传递，而非手工传 递，这个过程就可以称之为工作流。类似的关于文档的自动化处理只是工作 流技术的一种简单应用。事实上，工作流技术在现实应用中能够完成更多更 复杂的任务，如企业( 或机构) 内部的各种数据或信息的自动化处理，不同 类型业务流程的整合，企业( 或机构) 之间的数据交换，借助i n t e m e t 技术 实现跨地域的数据传输和处理等等。 工作流技术发端于1 9 世纪7 0 年代中期办公自动化领域的研究工作，当 时对工作流的研究所得到的s c o o p 和o f j f i c e t a l k 系统，不但标志着工作流技 术的开始，而且也是最早的办公自动化系统。但是当时计算机尚未得到普及， 网络技术水平较低，理论基础匮乏，工作流作为一项新技术并未取得成功。 含有工作流特征的商用系统的开发始于1 9 8 3 年至1 9 8 5 年间，早期的商用系 统主要来自于图像处理领域和电子邮件领域，在这些早期的工作流系统中只 有少数获得了成功。进入1 9 世纪9 0 年代以后，随着个人计算机和网络技术 的普及、推广，以及信息化建设的日益完善，工作流系统的开发与研究进入 了一个新的热潮。1 9 9 3 年8 月，工作流技术标准化的工业组织工作流管理 联盟( w 6 r k n o wm a n a g e m e n tc o a l i t i o n ，简称w f m c ) 成立，标志着工作流 技术在计算机应用领域之中被明确地划分出了自己的一席之地，工作流技术 开始进入相对成熟的阶段。 近年来，在计算机网络技术和分布式数据库技术迅速发展、多机协同工 作技术日益成熟的基础上，于2 0 世纪8 0 年代中期发展起来的工作流技术为 企业更好地实现经营目标提供了先进的手段。1 9 9 4 年，工作流管理联盟发布 了用于工作流管理系统之间互操作的工作流参考模型，并相继制定了一系列 工业标准。与此同时，关于工作流技术的学术研究也十分活跃，许多原型系 统在实验室里开发出来。进入二十一世纪以来，工作流技术已被越来越多的 人认可，与之相关的标准规范、工作流引擎及商业产品不胜枚举。人们在开 发推广工作流产品的同时，更加注重工作流的理论研究，以推动该项技术走 向成熟。至今，工作流技术已经成功应用到消费品行业，制造业，电信服务 业，银证险等金融服务业，物流服务业，物业管理，大中型进出口贸易公司， 政府事业机构，研究院所及教育服务业等，具体应用包括关键业务流程，行 政管理，人事管理，财务，客户服务等。 企业实施工作流管理所带来的好处是非常明显的，包括提高企业运营效 率、改善企业资源利用、提高企业运作的灵活性和适应性、提高工作效率、 集中精力处理核心业务、跟踪业务处理过程、量化考核业务处理的效率、减 少浪费、增加利润、充分发挥现有计算机网络资源的作用。实施工作流将达 到缩短企业运营周期、改善企业内( 外) 部流程、优化并合理利用资源、减 2 少人为差错和延误，提高劳动生产率等目的。正是基于上述原因，工作流技 术在较短的时间内得到了突飞猛进的发展，并越来越受到各界的重视。 1 1 2 工作流技术的研究现状及发展趋势 作为过程建模和过程管理的核心技术，工作流技术可以与其他系统有效结 合，生成符合企业需求的各种业务管理系统，具有高度的灵活性，能够在信息应 用平台层面上配合企业迅速地进行业务重组，以满足企业不断变化的管理和生产 需求。因此，工作流技术正在迅速发展并不断地被成功应用。目前，商业开发的 工作流系统种类繁多，但是有关标准的制定还未完善，从规范市场和便于消费者 选用的角度，对这些系统的分类就显得尤为重要，文献2 中列举了常见的几种分 类方法，此处就不赘述。另外，市场的需求大小导致了各类工作流产品发展的不 平衡，也为更多的商家提供了机遇和挑战。根据d e l p l l i 觚u p 的报告，早期的工 作流产品市场几乎被过程类产品独占，到1 9 9 7 年，以过程为中心的产品仅占5 4 的市场，以文档为中心的占3 2 ，以通讯为中心的占1 4 。在各个行业中，商 业( 包括银行业和保险业) 依旧是工作流产品的最大用户，政府行政部门其次， 制药业和卫生业超过了制造业，成为影响工作流产品的第三大行业，通讯业也在 3 年内从2 上升到5 7 【3 j 。 随着工作流应用的日益广泛，对工作流技术的研究也正在向更深层次进行， 但是总体来说，工作流研究方面的进展落后于商业应用。工作流技术的研究主要 有以下两个方向：第一，为工作流技术的发展解决理论上存在的问题，探讨工作 流模型和语义的形式化表示方法等；第二，从工作流技术实现的角度探讨利用先 进的技术提高工作流管理系统的性能和可靠性。细分之后具体包括以下几个方 面：l 、工作流管理系统体系结构的研究；2 、工作流模型与工作流定义语言的研 究，3 、工作流的事务特性研究，4 、工作流的实现技术：包括面向对象技术、异 构分布式计算、图形用户界面、消息通信、数据库、w w w 等在内的与工作流系 统的设计实现有关的各项技术、方法，5 、工作流的仿真与分析方法，6 、工作流 的集成与互操作技术：研究异构应用系统的集成以及不同工作流系统之间的互操 作问题，7 、工作流与经营过程重组：研究如何通过工作流系统的实施来有效地 实现企业的经营过程重组1 4 】。 目前，国外取得研究成果较多的包括i b m 公司触m a d e n 研究中心开发的分 布式工作流管理系统e x o t i c a f m q m ，美国佐治亚大学计算机系研究开发的具有 自适应性的工作流管理系统m e t e o r ，欧洲多个研究机构合作开发的基于分布式 主动数据库技术的w i d e 工作流系统，瑞士联邦银行和萨尔兰大学共同研究的 3 基于状态和活动图的m e n 幻r 工作流系统，惠普实验室的o p e i l p m 工作流系统， 德国埃朗根大学的m o b i l e 工作流系统等【5 】。国内在该领域的研究尚处于起步 阶段，但是近年来已经有越来越多的学者和研究机构投身于工作流领域，并且取 得了一定的成果。此外，许多专注于工作流研究的组织机构也应运而生，在国际 上，主要有国际工作流管理联盟w f m c ，国际工作流与重组协会w a r i ，a ，国 际工作流联盟姊妹站e w b 棚o w ，i b m 公司下属的a l m a d e n 研究中心；国内 这方面的机构还较少，主要有清华大学建立的s m 伍l o w 工作流网站。值得一 提的是，由企业发起的“工作流管理系统技术研讨会在工作流技术商业开发和 应用标准制定等方面做出了很多工作。 在看到工作流得到迅速发展的同时，我们必须意识到，无论是工作流技术还 是它所衍生出来的商业产品，都还存在很多缺点和不足。理论方面，工作流技术 相关的术语还没有得到统一，各种标准的制定也还有待完善，这就导致了大多数 工作流产品之间互不兼容，缺乏互操作性，要真正实现不同产品之间的无缝互操 作，工作流技术还有很长的路要走。此外，对工作流管理系统的分析仿真方面， 目前还没有比较系统的工具和方法，这对工作流技术的普及是极为不利的。并且 目前市面上的工作流产品性能还不够卓越，难以同时处理大规模的流程等。工作 流管理系统的安全性也还不能得到较好的保障，权限、职责分工、利益冲突等都 是威胁工作流系统安全的因素。另外，工作流系统对于异常事件的处理能力也还 有待加强，其系统结构上广泛采用的集中式容易形成瓶颈，导致整个系统的崩溃。 以上这些既是目前工作流技术存在的不足也是未来的发展方向。 另外，工作流技术不仅仅是一门计算机应用技术，对它的研究和应用还要与 管理科学、协同设计等其他学科紧密结合起来，它是一个涉及多学科交叉的研究 领域。 1 2 集中式工作流 从工作流的建模和执行角度，工作流管理系统的体系结构可以是集中式，也 可以是分散式，而目前应用较多的工作流模型多为集中式。集中式工作流主要应 用在两种情况下，企业内部的工作流和分布式工作流中，前者一般采用自顶向下 的建模方法，由工作流定义人员采用一个工作流定义工具或b p r 工具，按照逐 步分解、逐步细化的方法完成工作流模型的建立。完成这项定义工作的前提条件 是这些工作流定义人员要熟悉全部的企业业务过程，并且这些业务过程对他们都 是开放的；在组织结构上，所有这些业务过程必须都处于一个统一的组织结构管 理下，也就是说它们是结构对称的。对于分布式工作流，一般用于跨组织业务之 间，处于合作关系的多个企业处于不同的地理位置，在组织形式上，它们组成一 4 个虚拟企业，整个运作过程会涉及多个合作伙伴企业的业务过程。在这种条件下， 要将这些合作企业的相关业务过程全面了解清楚是一件费时又费力的工作，并且 一般来说，一个企业的业务流程尤其是关键业务流程属于一个企业的商业机密， 不会因为加入了一个战略的动态联盟而全部对外开放。另外由于每个企业是相对 独立的组织单位，即它们不在同一个组织结构的管理下，各个合作单位处于一种 协作的对等关系，每个参与企业负责完成自身分配到的任务，所以没有任何一个 组织能够对整个虚拟企业的运作流程进行管理。此时，比较可行的实现方法就是 由不同的企业各自完成其内部流程模型的建立，这些内部模型对外公开其交互的 接口，以便实现不同企业工作流模型之间的连接，这样所建立的工作流模型就不 完全是一个自顶向下的分解过程，而是自底向上综合和自顶向下分解两种方法的 组合。自顶向下的分解过程完成整个跨企业流程的分解，各个合作企业完成内部 流程建模后，采用自底向上的综合方法进行模型的连接和匹配，从而形成整个的 工作流模型1 6 j 。 无论是上述的哪种情况下，从工作流的执行方式上看，所有任务的执行由处 于核心地位的工作流引擎控制，它负责对组织和资源的调度，确定每个任务的执 行条件满足之后将任务发送给相应的执行代理，并且接收执行代理对任务执行的 反馈和结果，评价处理之后再转向下一个任务，依次类推直至所有的任务执行完 毕，处于核心地位的工作流引擎得到工作流的最终执行结果。图1 是集中式工作 流中中央系统与各参与组织之间信息交换过程的示意图，中央系统参与所有任务 的信息交换，包括发送信息流给相应的组织，并负责接收组织反馈的信息，处于 满负载状态；而其他的参与组织只在特定的时间段内参与活动，其余时间处于空 闲状态。 总之，集中式的工作流系统在可靠性、可扩展性、实用性和吞吐量等方面都 不能满足企业执行大规模的复杂应用的需求。处于核心地位的中央系统承担了大 部分的决策和调度工作，极有可能成为整个工作流模型的瓶颈，出现单点失效而 导致整个系统的崩溃。 中 央 系 统 信息流 组织l 组织2 组织3 图1 集中式执行系统中的信息交换示意图 1 3 分散式跨组织工作流 与集中式工作流不同，分散式跨组织工作流主要应用在多个企业合作的场 合。随着经济的全球化，各行各业的竞争愈演愈烈，越来越多的企业认识到，仅 依靠个体的力量无法在竞争中取得绝对优势，因此，利用自身优势，与其他组织 进行合作，合理整合企业外部资源，形成临时或较为稳定的动态联盟，成为较好 的选择【7 l 。互联网和电子商务的发展进一步加速了这种跨组织合作，跨组织工作 流也因此成为可能。目前对于跨组织工作流的研究很多都集中在对工作流建模， 即将商业过程转化为计算机可以执行的语言1 8 1 l 】。 分散式跨组织工作流强调不同组织之间任务的分散式执行，即将权力下放到 具体的任务执行单位，我们称之为任务的执行代理，而不是由中央系统统一控制， 以便克服集中式工作流系统中中央系统可能成为模型的瓶颈，出现单点失效和可 扩展性差的问题。需要说明的是，这里的分散式强调的是任务的执行方式是权力 分散的，而不仅仅是说参与合作的企业在地理位置上是分散的。 分散式跨组织工作流不同于协同工作流，后者强调的是多个用户为完成一项 共同的任务而协同工作，保证不同部门或不同组织间的数据能够同步更新、协同 共享，从而提高设计开发效率和工作质量【1 2 1 3 l 。而在本文的分散式跨组织工作流 中，不同的组织或企业单独完成分配的任务，并且保证企业自身的自治性和业务 流程的保密性，除了工作流定义中的连续代理对任务信息的传递不存在业务方面 的信息共享和数据交换【1 4 】。 目前对于分散式跨组织工作流也有了一系列研究。v ：a t l u d 等人采用分割工 作流的方法建立了组织间工作流的分散式执行模型，各执行代理在执行工作流分 割体时具有评估和分割工作流的权限【1 5 】。李从东等人采用网络地址查询方式建 6 立了分散型合作工作流系统( d c w s ) ，通过注册服务器实现各主机之间的通信 并确保系统的安全性【1 6 j 。武陵等人提出状态信息的概念，并以此作为流程的执 行依据建立了分散式的执行模型i l7 。胡晶晶等人引入基于a g e m 的工作流和评估 工作流引擎的概念，完成对虚拟企业的分布式工作流控制【1 3 1 。庄兵等人基于工 作流和元组空间技术，提出了分布式执行协同逻辑的方法，实现了所有个体组件 对流程导航所产生的工作流的分担【1 9 】。文献2 0 以p 嘶网为模型载体，提出了动 态工作流模型的片段式分布执行算法，通过工作流片段的迁移实现工作流的连续 运转，增强了商业职能的可测量性和动态指派的灵活性等。文献2 l 中为了保护 参与合作的企业间的机密信息，提出了由o b i e c t 的创建者决定其他用户是否可以 获取相关信息的观点。文献2 2 提出了时序一致性的理论，为任务的执行设置了 时序限制，包括内含的和强制的，避免任务之间出现时序冲突。另外，提出用 v i e w 作为手段防止参与合作的组织隐私的外泄，同时又可以保证彼此之间获得 足够的信息进行合作。 已有的研究虽取得了一定的成就，但这些工作或者是建立在集中式工作流管 理系统基础之上的修改，在工作流的执行模型中仍旧以中央系统调控为主，集中 式系统的缺点仍旧存在，也有一些系统为了追求分散式的执行方式而造成了对资 源的闲置浪费。对于工作流分割的研究多为静态分割，工作流在中央服务器处被 预分割并发送给相应的执行代理，这样的处理方式降低了系统的执行效率，没有 考虑制定的代理出现异常甚至不可用的情况，并对中央服务器具有较强的依赖 性。此外，现有的研究没有考虑由于分割造成的不同组织之间的利益冲突，此类 安全问题会损害部分参与合作企业的利益，产生不期望的结果。 1 4 本文研究内容 本文旨在对分散式跨组织工作流的执行模型进行相关研究，改变传统的集中 式的执行方式，通过分割工作流的方法，削弱中央系统对整个工作流系统的控制， 增强任务执行代理的自主权，达到控制方式的平衡。文中引入了自描述子工作流 的概念，它携带了分割工作流之后所得到的部分任务及其之间的约束关系，以及 执行这些任务的代理和所需要的全部信息，同时又可以有效避免冗余信息，在提 出模型分割算法之后举例进行了说明，并考虑了出现循环体的复杂工作流的情 况。由于跨组织工作流中的约束关系往往会超越单一组织的边界，如何对这些任 务的先决条件进行评估也是本文的研究内容。此外，从任务正常执行和时间优化 的角度，文中考虑了对任务的预调度，包括对任务开始执行条件的评估验证，若 干自由活动的预调度以及任务执行代理的选择等。通过时序图的方式列举了增加 预调度之后几个连续代理之间的负载情况和相关活动的执行顺序。在此基础之 7 上，文中列举了不同并行度的工作流，并分别考虑了“与”分支和“或”分支的 情况，从响应时间、信息量等方面将本文的分散式的执行方法与集中式进行了系 统化的比较，证明了分散式执行方式的优越性。另外，考虑到跨组织合作中不可 避免会产生的利益冲突问题，在中国墙安全规则的基础上制定了基于本文的分散 式的执行模型的安全读写规则，根据客体对主体是否敏感，分别考虑了工作流分 割时可能出现的三种情况。最后，以个性化订制自行车为实例，对本文的理论进 行了验证。 本文的章节安排如下：第一章绪论，主要介绍工作流的起源、定义、应用和 发展情况。列举了集中式工作流和分散式跨组织工作流各自的优缺点以及现有的 相关研究，并对二者进行了比较，指出分散式的跨组织工作流将是未来工作流发 展的主要方向。第二章中根据对工作流分散式执行的要求提出分散式跨组织工作 流执行系统的总体构想，给出了系统的总体框架以及各部分的具体作用。第三章 对本文的工作流模型中基本用语做出定义并最终给出自描述子工作流的定义。对 先决条件进行了定义和分类。提出了模型分割算法并举例进行了详细说明。第四 章引入预调度的方法，并列举了不同并行度的多个工作流，从响应时间和信息量 等方面与集中式的执行方式进行了比较。第五章基于中国墙安全模型理论，提出 了基于工作流分割的安全读写规则。第六章对全文内容进行总结，提出存在的缺 点和不足，并对今后的研究方向进行展望。 8 第二章分散式跨组织工作流执行系统的总体设计 2 1 引言 模型是对所描述客观对象的抽象表示，而工作流模型则是对业务过程的一 种抽象描述，将企业的实际经营过程转化为计算机可处理的数字化的工作流模 型。作为实现企业信息化的重要底层支撑技术，流程建模是工作流管理应用于电 子商务、企业资源规划等信息管理领域中必须解决和无法回避的一个关键问题 目前比较典型的工作流建模方法有，基于p 咖网的建模，基于e p c 的建模，事 务工作流建模，基于协调理论的建模，协作工作流建模，基于活动网络的建模瞄】。 工作流执行模型是对工作流执行方式的抽象和描述，是在工作流模型的基础 上进行的建模方法，是工作流引擎实现执行服务的重要基础。简单地说，工作流 模型的建立是为企业的业务流程进行数字化规划，而工作流执行模型是探索实现 该规划的方法。目前专门研究工作流执行模型的文献还比较少，文献2 4 中为u m l 活动图定义了一种执行语义。基于时间转变系统模型，将工作流系统的执行描述 为时间转变和数据转变两个交替进行的过程。时间转变描述时间的前进，数据转 变修改工作流案例的状态，这种语义比层次状态图具有更强的描述并行的能力， 比p e t r i 网和进程代数更适合描述工作流模型。文献2 5 从可重构的角度出发，面向 不同应用领域中活动行为的相异性和动态性，研究了一种具有高度适应性的工作 流执行模型，给出了该模型中过程状态精化的两种实现方法和状态转移关系的自 动生成算法，并结合实际应用，对模型可重构性的具体实现进行了探讨。提出了 一种可重构的工作流执行模型，提高了工作流系统的适应性和可维护性。 上述工作流执行模型都建立在集中式工作流模型的基础之上，对于分散式跨组 织工作流而言，考虑到地域的分布性、工作流的可用性和执行效率等，集中式执 行模型的实现帮控制都不具备较大的可操作性。工作流的分散式执行不是一种特 定的工作流执行方式，也不同于分布式执行是由合作企业地理位置的分布决定 的，分散式执行是对控制方式的描述，是为了适应处于平等合作位置的各参与企 业既共享信息谋求合作共赢又要保持自身独立自治的需求，满足工作流管理系统 的工作流模型的执行。文献2 6 将二者进行了比较研究，集中式的执行模型中中 央系统可能成为模型的瓶颈，可能出现单点失效和可扩展性差的缺点，而而分散 式执行模型，可以较好的解决这些问题，但是会带来额外的运行代价即执行协调 的信息量增加。因此，如何降低组织间的信息量代价对于分散式执行模型的研究 来说是一个不得不面对的挑战。 9 本文旨在对跨组织的工作流进行分散式执行模型的研究，根据所要实现的功能 对系统的架构进行设计构造，并对可能出现的闻题进行系统讨论解决。 2 2 系统架构及各部分作用 为了克服集中式工作流执行模型的不足，提出分散式跨组织的工作流执行模 型的构想，中心思想是采用分割工作流模型的方法，按照执行代理的不同，将工 作流的形式化模型分割成若干子工作流，发送给相应的任务执行代理，并随着任 务的执行完成工作流的流转，达到分散式执行的目的。在这个过程中中央系统的 角色与普通的任务执行代理基本相同，弱化其对整体工作流的控制权限，增强普 通任务执行代理的自治能力。根据这样的构想，我们的工作流执行系统中应该满 足以下假设：1 、工作流的执行请求由客户发出，中央系统通过用户接口获得工 作流的形式化模型，并根据工作流中对于执行代理的定义，首先将整个工作流传 递给第一个任务的执行代理a ( t 1 ) ，a ( t 1 ) 执行完毕t l ，将除t l 之外的工作流进行 第一次分割，形成第一个工作流分割体p l ，并将其连同t l 的输出结果等信息发 送给下一个任务的执行代理，如此按照工作流模型的顺序顺次完成工作流流转； 2 、每个工作流分割体中都包含尚未执行任务的全部信息，以便后续代理能够根 据这些信息完成相应任务的执行；3 、代理的工作内容包括对相应任务的执行， 以及剩余工作流的分割并发送给后序的代理；4 、由于每个任务的执行需要满足 一定的先决条件，在执行之前需进行先决条件的评估，对前序任务不存在依赖的 任务可以考虑预执行以便提高系统的效率；考虑到跨组织合作中依赖关系的无边 界性，以及任务之间的继承性，每个任务的执行结果应该与工作流分割体一起发 送给后续代理；5 、系统建立在p 2 p 方案下，每个代理的地位相当，它们的结构 也应该相同，并且应该包含管理，工作流分割，先决条件评估，接口等功能性结 构，另外，中央系统应该比普通代理增加用户接口以便于用户交互接收工作流。 此外，考虑到现实应用中系统的具体实现，尚有若干问题需要考虑，1 、代 理的负载量和系统对时间精度、执行效率的要求可能导致部分代理无法按照预定 的模型要求执行相应的任务，这就需要前序代理提前做出选择，类似的问题在 “或”分支的工作流中也存在，前序代理要在分割工作流之前确定后序的任务由 谁执行即选择分支路径和相应的任务执行代理；2 、组成单个任务的各个活动中， 有若干是与前序任务等无依赖约束的，这部分活动可以提前执行，也有一部分任 务的执行可能存在类似的情况，也就是说任务开始执行的先决条件为空，这种任 务也可以考虑提前执行；3 、考虑到跨组织合作中不可避免会出现的由于组织间 利益冲突导致的安全问题，应在分割算法的基础上有所体现。因此，本文将就以 上问题进行相应的研究。 l o 根据上述的设想，系统的基本结构框图如图2 所示。 工作流请求用户 图2 分散式执行系统结构图 对各个结构具体作用的说明如下： 用户接口：接收用户提交的工作流请求，是只有中央系统才有的结构； 分割池：保存分配给该代理的所有分割体的信息。由于分割池的存在，当前 代理除了自身要执行的任务之外，也能够掌握分割体中后序其他任务的信息，这 对于存在利益冲突的跨组织合作来说，埋下了安全隐患，在对工作流进行分割的 时候应进行适当的处理，这也是本文要解决的问题之一； 分割管理器：作为驱动工作流流转运行的引擎。当有一个新的分割体加入分 割池，分割管理器检查首任务的先决条件是否满足，并与条件评估单元进行通信， 在先决条件满足后将首任务添加到任务寄存器中，然后对工作流进行分割形成新 的分割体，连同当前任务的执行结果发送给后序的代理，同时对后序任务的先决 条件进行管理，将不依赖于其他任务的独立的自由活动直接发送给后序代理的任 务寄存器，并通知条件评估单元对后序任务的先决条件进行评估。通过这种方式 保证工作流的执行不断进行，驱动工作流的流转，直到所有任务都执行完毕。对 于没有指定代理的任务，与代理管理器通信获知代理的选择结果，存在“或 分 支的工作流，根据分支条件进行执行代理的判断；先决条件涉及执行代理及其后 序代理的，根据情况判断是否存在利益冲突，这些工作都要在分割工作流之前完 成。 任务寄存器：保存该代理执行的所有任务的清单，包括已经执行的和从分割 管理器接收的即将执行的当前任务，接收到新任务时与执行器通信驱动任务的执 行； 条件评估单元：接收分割管理器发送的信息，对任务的先决条件进行评估， 评估的类型包括当前任务的先决条件和后序任务的先决条件，在与前后代理的条 件评估单元配合下完成所有先决条件的评估； 任务监测器：为分配给该代理的每个任务保存日志，包括它们的完成情况、 某项服务的资费或者需要调用的应用程序等。任务监测器在虚拟企业的合作环境 中具有非常重要的地位，它为商业过程的监督和改善提供了反馈和依据。 执行器：负责任务的具体执行，必要时可通过接口调用相关的应用程序支持 任务的完成； 代理管理器：负责对多代理的任务选择执行代理，通过计算和比较，最终选 择最佳的代理并通知分割管理器，此外，代理管理器负责获取并传递所有参与合 作的企业或组织的负载状态，初始时默认所有企业或组织为可用状态，按照工作 流对代理的指定进行工作流的传递，个别单位出现满负载或其他突发状况时通知 中央系统，之后按照工作流的流转顺序依次更新每个代理中代理管理器的状态信 息【2 7 】； 接口：与其他代理和服务器进行交互通信。 1 2 逝婆态堂殛迨塞墓三重岔熬式匿缰丞王佳远垫在丕统鳆望馇遮让 2 3 系统运行过程说明 本节中将以网上购物为例，对上述的系统运行情况进行说明，为了突出主要 问题，对实例过程进行了简化。顾客a 向商城b 购买商品，商城b 在接受订单 之后查询库存，如果有现货则通过物流公司c 发货给顾客a ，否则向厂家d 申 请进货之后再进行上述步骤，顾客a 签收之后工作流结束。图3 所示为流程示 意图。 abca 图3 网购流程图 按照本文对跨组织合作工作流的分散式执行设想，中央系统通过用户接口接 收工作流，发送给首任务的执行代理，例子中为商城b 的客户端，工作流作为 一个整体进入b 的分割池，分割管理器检查首任务即根据订单查看库存的先决 条件是否满足，显然，该任务要执行必须先生成订单，分割管理器与条件评估单 元通信，条件评估单元对订单是否符合要求进行评估之后反馈信息给分割管理 器，如果条件满足，后者便将该任务添加到任务寄存器，执行器开始执行任务并 得到最终结果，此时分割管理器应该分割工作流生成新的连续分割体并发送给后 序的执行代理，此处由于存在“或”分支，在分割工作流之前应进行代理即路径 的选择，这里的分支条件是由任务的执行结果决定的，只需判断即可，我们假设 库存不足，则工作流转向厂家d ，b 的分割管理器将分割后的工作流发送给d 的分割池，并对该分割体首任务的先决条件进行判断，涉及到商城b 的数据或 者资源的条件交由b 的条件评估单元进行评估，与此同时，判断该任务中是否 存在对其他任务不存在依赖的自由活动，将该部分活动直接发送给d 的任务寄 存器，由d 的执行器与b 中条件评估单元并行运行。在实际应用中，任务“进 货 在任务“库存 完成之后便可执行，因此，此处的自由活动为整个“进货 任务，可以预执行，在d 的条件评估单元评估完毕，任务继续执行至结束。之 后，d 的分割管理单元继续分割工作流，并发送给后序的代理即物流公司c ，对 于没有特别指定代理的情况下，此处还需增加代理选择环节，接下来d 的分割 管理器对于任务“发货 先决条件的处理以及后序的其他操作与前面相同，此处 不再赘述。 1 3 整个过程中，相应代理中的任务监测器对任务的执行记录日志，用于对任务 完成情况的记录和改善，例如对于商城b ，假如库存不足的情况较多，加上对于 订单金额和频率的调查，则可以考虑采取扩大仓库增加库存等措施。 2 4 论文拟解决的主要问题 根据2 1 3 节中实例运行时存在的问题和跨组织工作流的分散式执行对模型的要 求，本文拟解决的问题如下： ( 1 ) 通过对工作流进行分割降低系统对于单一工作流引擎的依赖性，避免集中 式的控制方式；在对工作流分割时要去除冗余分割，减少信息交换量，并且要考 虑存在循环体的复杂工作流情况，即所采用的算法要具有普适性。 ( 2 ) 解决代理的选择问题，包括未指明执行代理的任务中代理的选择问题和“或” 分支路径的选择，这两者决定了工作流的走向，须由前序代理在分割工作流之前 完成。 ( 3 ) 对每个任务执行前必须要满足的先决条件进行评估，考虑到跨组织合作中 信息超越边界，根据先决条件所涉及的数据和条件的范围以及代理对信息的处理 能力，对先决条件进行分类并指定相应的代理。 ( 4 ) 考虑跨组织合作中的不同组织之间的利益冲突问题。由于每个代理掌握以 自身所执行任务为首任务的分割体的所有信息，对于存在利益冲突的不同组织， 按照工作流的走向，本来不存在直接通信的代理可能因为执行顺序的先后导致不 公平的结果，本文将对此类问题提出有效解决方案。 1 4 3 1 引言 第三章分散式跨组织工作流的分割设计 在跨组织合作中，参与合作的组织会形成一个动态联盟，整个合作的业务流 程可以用一个虚拟企业的工作流表示，每一个任务由相应的组织执行。本章将提 出工作流分割的方法，实现跨组织工作流的分散式执行。工作流分割的目的是将 完整的工作流分割成可由不同代理分别执行的子工作流，形成自描述子工作流， 每个代理掌握所接收到的分割体的全部信息，但是只负责当前分割体中首任务的 执行。这样的方法可以克服集中式工作流受中央系统限制的缺点，增强工作流的 动态性和可扩展性。 本章中首先会给出分散式执行工作流中涉及到的基本名词定义，然后提出分 割工作流的算法和自描述子工作流的定义并举例进行说明，之后对使用该算法得 到的自描述子工作流与原工作流进行等价性证明。在此基础之上对工作流中每个 任务执行所必须满足的先决条件进行详细说明。 3 2 基本定义 3 2 1 任务 根据w f m s 的定义，工作流中没有任务的概念，只有活动的概念，但是对 于跨组织的工作流而言，基于对参与合作组织内部流程的保密的考虑，我们定义 任务的概念，它可能只是一项活动，也有可能包含若干活动，这与任务所要实现 的目标相关。任务是根据所执行代理的不同进行定义的，具体定义如下： ( a ，o p ，哪，o 州) 其中，a 代表执行该项任务的代理，0 p 代表执行任务所需进行的操作集，i n p u t 是任务执行的输入条件，o u 印u t 为任务执行后的输出结果。如果某项任务t i ，在 工作流中不存在任一任务k ，使得t k _ t l ，其中x 为条件表达式，则成t i 为该工 作流中的首任务。 需要说明的是，在有些情况下，a 所指的可能是一部分或者具有某一职能公 司的总称，例如提供钢材这一任务的执行代理是钢铁厂，而可以不必特指某一钢 铁厂，这对提高整个工作流运行的灵活性具有重要意义【3 l 】。o u t p i i t 在多数情况下 指的是任务期望输出的结果或者是某个统计名词而非具体的值，就如上述的提供 钢铁的例子，o u ：t p u t 就有可能是“钢材的数量 而不一定是具体的数值例如 1 5 “1 0 0 0 0 t ”。 一般情况下，一个任务在执行时需要经历4 个