第 26 卷 第 9 期
2003 年 9 月
计 算 机 学 报
CHIN ESE JOURNAL OF COMPU TERS
Vol. 26 No. 9
Sept . 2003
面向意外处理的工作流系统建模与执行
窦万春 席晓鹏 许列飞 蔡士杰
(南京大学软件新技术国家重点实验室 南京 210093)
(南京大学计算机科学与技术系 南京 210093)
收稿日期 :2001211209 ;修改稿收到日期 : 2002207218. 本课题得到南京大学博士后科研基金 (0202003013) 、南京大学人才引进基金
(0202005106)资助.窦万春 , 男 , 1971 年生 , 博士 , 副教授. 主要研究方向为可视化工作流技术、知识管理等. E2mail : wanchun
-
dou @
sina. com. 席晓鹏 ,男 , 1977 年生 , 硕士研究生. 主要研究方向为智能信息处理.许列飞 ,女 , 1976 年生 , 硕士研究生. 主要研究方向为计
算机支持协同工作 (CSCW) 、工作流管理等.蔡士杰 ,男 , 1944 年生 , 教授 , 博士生导师. 主要研究方向为计算机图形学、CAD 等.
摘 要 产生于工作流系统的执行阶段、未在系统建模阶段进行描述和定义的突发事件 , 称为工作流意外事件. 对
应意外事件的处理过程 ,称为意外处理. 该文针对意外事件 , 从系统建模与模型执行两个方面对工作流意外处理
进行了探讨. 在系统建模阶段 , 通过拓展 Petri 网中的基本概念 , 提出并构造了组成工作流的过程
单元
初级会计实务单元训练题天津单元检测卷六年级下册数学单元教学设计框架单元教学设计的基本步骤主题单元教学设计
, 在将工作
流内在的逻辑关系分解为控制流与数据流的基础上 , 讨论了一个面向意外处理的工作流系统复合建模方法. 对应
工作流的模型执行 , 定义了两类意外处理 , 用矩阵形式分别表示或标识控制流、数据流和意外事件 , 经过矩阵分析
与变换 ,对意外事件的影响区域进行范围界定. 最后 ,探讨了这种意外处理方法在数据流意外处理中的实例应用.
关键词 意外事件 ; 意外处理 ; 工作流系统 ; Petri 网 ; 矩阵 ; 控制流 ; 数据流
中图法分类号 TP14
Exception Handling Oriented Workflow Modeling and Its Performance
DOU Wan2Chun XI Xiao2Peng XU Lie2Fei CAI Shi2J ie
( S tate Key L aboratory f or Novel Sof tw are Technology , Nanjing U niversity , Nanjing 210093)
( Depart ment of Com puter Science and Technology , Nanjing U niversity , Nanjing 210093)
Abstract The exceptions of workflow system are those issues taking place during execution but ex2
cluded in modeling , and the corresponding handling process is exceptions handling. For better han2
dling the exceptions , the countermeasures are explored from workflow modeling and its performance.
A framework of process unit developed from Petri net underlies workflow modeling. Furthermore , an
approach of compound modeling is put forward oriented toward the exception handling after decompos2
ing the workflow relationship into control2flow and data2flow. In conformance with model’s perfor2
mance , the exception handling is categorized into two kinds according to the impact on workflow in2
f rast ructure caused by the exceptions. The control2flow , the data2flow and the exceptions are labeled
by matrix respectively and the sphere of the exception handling can be deduced from the transformation
of the matrices. At last , a handling instance oriented toward data2flow exceptions is presented.
Keywords exceptions ; exceptions handling ; workflow system ; Petri nets ; matrices ; control2flow ;
data2flow
1 引 言
最近几年 ,作为 CSCW 领域中的一项关键技
术 ,工作流技术得到了普遍的应用[1 ] . 但是 ,相比 E2
mail 系统、Web 浏览器以及组件平台 ( groupware
platform)等其它同时期、甚至晚些时候出现的应用
技术 ,其应用的成熟度和对其它领域的影响程度 ,与
预期目标相比还有许多差距[2 ] .造成这种状况的因素
很多 ,主要体现为系统执行过程中处理意外事件的能
力不强[2~8 ] . 为此 ,国际学术期刊《Computer Sup2
ported Cooperative Work (CSCW)》于 2000 年 11 月
推出了一期 Adaptive Workflow Systems 专刊[9 ] ,专
门就意外处理 (exceptions handling) 问题进行了探
讨 ,组织了 7 篇文章 ,分别从提高工作流模型在执行
过程中的动态修改[3~6 ]和模型在执行过程的动态
扩充[7 ]两个角度进行了探讨 ,并给出了一个应用系
统实例[8 ] . 鉴于意外处理问题在计算机应用领域的
重要性 ,2000 年《IEEE Transaction on Software En2
gineering》的第 9 期与第 10 期对包括工作流领域在
内的意外处理问题进行了集中探讨 ,为意外处理提
供了更多的解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
与参考手段[10 ,11 ] ;另外 ,文献
[12~15 ]从提高工作流技术的智能化程度、系统健
壮性或建立系统处理意外事件的 Case 库等角度对
工作流系统的意外处理进行了个例研究. 根据我们
的技术查新 ,该类问题在国内尚未得到重视 ,有关该
主题研究的文献资料还未有发现 ,对工作流系统的
研究重点大多集中在系统建模、功能分析与系统评
价等方面[16~19 ] .
为了促进并完善工作流技术在 CSCW 领域及
其它相关领域的应用与发展 ,本文通过对意外事件
与意外处理等基本概念进行定义 ,利用 Petri 网、矩
阵等分析工具 ,从建模和执行两个角度对意外处理
进行了研究 ,并对一个具体的应用实例进行分析研
究.本文第 2 节 ,通过对意外事件的归纳与分类 ,定
义了本文讨论的意外事件与意外处理等基本概念 ;
第 3 节通过对过程单元的递阶定义和对工作流系统
中的流关系分析 ,提出了一个面向意外处理的工作
流建模方法 ;第 4 节 ,对工作流模型执行过程中的意
外处理进行了分类探讨 ;第 5 节则探讨了一个具体
的意外处理应用实例 ;第 6 节对本文进行了总结和
归纳.
2 意外处理的基本概念
从功能上来讲 ,工作流技术大致可以划分为两
个方面 :对现实系统的抽象建模和模型执行中的过
程管理. 前者是理论分析阶段 ,往往利用模型机制 ,
对现实系统进行
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
化描述 ;后者则是模型的实际
操作阶段 ,即模型实例化及对应的过程监控等. 意外
情况或意外事件 (exceptions) ,则可以看作是产生在
模型的实际操作阶段、未在建模阶段进行描述和定
义的问题. 对这类问题的处理 ,称之为意外处理 (ex2
ceptions handling) . 意外处理过程中 ,对意外事件进
行标识和确认 ,并在意外事件的影响范围内消解意
外事件 (防止波及其它流程环节而造成更大范围的
意外处理)十分重要. 基于这种认识 ,根据意外事件
对整个工作流系统的影响范围 , Kammer[3 ]等将意
外事件划分为个人级 ( employee level ) 、群组级
(group level)和组织级 (organization level) ,并从属性
上将意外事件划分为可预见意外事件与不可预见意
外事件 ,认为可预见意外事件对应模型包含的条件2
活动分支在模型实例化过程中的取舍选择 ;而不可
预见意外事件则是产生在模型的实际操作阶段、未
在建模阶段进行描述和定义的矛盾冲突. Luo[13 ]将
意外事件划分为应用级 (application level) 、工作流级
(workflow level) 和基础框架级 ( inf rast ructure lev2
el) ;在此基础上 ,根据系统对意外事件的关注程度 ,
进一步将意外事件区分为可屏蔽型 (masking excep2
tions) 与可传播型 (propagating exceptions) ,对可屏
蔽型意外事件 ,系统不予理会 ,忽略其对过程执行的
影响 ;而对可传播型则需要从全局角度出发进行协
调处理. 本文所讨论的工作流意外事件和意外处理
的形式化定义如下.
定义 1 (意外事件) . 工作流模型在执行过程
中 ,背离理想化流程开展的分支事件 ,称之为意外事
件或意外情况 (exception) .
这里的理想化流程开展 ,是指在模型具体执行
前 ,根据模型内在的逻辑关系和包含的流程定义 ,从
理论角度进行推理与设想的一次虚拟执行过程. 产
生于模型的实际操作阶段、未在模型的理论分析阶
段进行描述和定义的问题 ,可以称之为不可预见的
意外事件. 而那些存在条件分支的节点 ,相对该次虚
拟执行过程 ,其它条件分支就可以看作是可预见的
意外事件. 需要说明的是 ,意外事件并非都具有消极
作用. 如知识应用与交互领域中的工作流系统的过程
特征与过程质量 ,往往体现为数据流概念下丰富的交
互内容 ,它在知识启发方面具有明显的积极作用.
定义 2 (意外处理) . 工作流模型 (主要针对可
以预见的意外事件)以及工作流管理系统 (主要针对
不可预见的意外事件) ,借助特定的处理方式或机
制 ,对意外事件的处理.
针对可预见意外事件 ,往往是在建模阶段对每
个条件分支定义对应的解决方案 ;对不可预见的意
外事件 ,往往涉及某些附加因素. 我们以产品设计制
造工作流系统为例进行具体分析. 该工作流系统中 ,
经常会发生这种情况 :设计阶段某些参数的确定和
设置 ,由于未考虑或不具备验证条件 ,直到工艺设计
阶段甚至制造阶段才会发现这些设计上的缺陷. 此
时的意外处理 ,往往是根据损失或代价最小原则首
先确定责任对象. 如工艺阶段发现零件 1 和零件 2
存在装配上的干涉 ,到底是对零件 1 进行修改 ,还是
对零件 2 进行修改 ,这就需要一定的仲裁机构进行
决策. 另外 ,意外发生的现场过程单元和造成意外发
59019 期 窦万春等 :面向意外处理的工作流系统建模与执行
生的原始过程单元之间数据流涉及的其它过程单元
理论上也是该意外事件的影响部分. 因此 ,为了保证
意外处理的闭环效果 ,避免意外处理的同时造成的
连锁反应失控 ,形成更大范围或更多的潜在的意外
事件 ,在发生意外事件时 ,还必须有效标识意外事件
的影响范围.
3 面向意外处理的工作流系统建模
提高模型在执行过程中的动态修改与模型在执
行过程的动态扩充能力 ,可对意外事件进行有效的处
理.鉴于意外事件和工作流模型之间的对应关系 ,还
必须尽可能地在建模阶段就将可能发生的意外情况考
虑在内 ,从模型机制上对可预见的意外事件进行规约.
3 . 1 过程单元的分析与构造
首先给出与 Petri 网有关的若干引理[20 ] .
引理 1 . 三元组 N = ( S , T ; F) 称为有向网
(directed net) 的充分必要条件是 :
(1) S ∩T = Á ;
(2) S ∪T ≠Á ;
(3) F Α S ×T ∪T ×S ;
(4) dom ( F) ∪cod ( F) = S ∪T .
其中 , S 和 T 分别称为 N 的库所集和变迁集 , F 称
为流关系. 符号“Á”和“×”分别表示空集和笛卡儿
积 ;dom ( F) = { x | ϖ y : ( x , y ) ∈F} 和 cod ( F) =
{ y| ϖ x : ( x , y) ∈F}分别称为 F 的定义域和值
域.
引理 2 . ∑= ( S , T ; F , K , W , M 0) ,
(1) N = ( S , T ; F)构成有向网 ,称为∑的基网 ;
(2) K : P →N + 称为 N 的容量函数 (capacity
function) , N +为正整数集合 ;
(3) W : F →N + 称为 N 上的权函数 ( weight
function) ;
(4 ) M 0 : P →N 称为 ∑的初始标识 ( initial
marking) , N 为整数集合 ;
引理 3 . x ∈X 为 N 的任一元素 ,
·
x = { y| ( y , x ) ∈ F}称为 x 的前集 (pre2set) 或
输入集 ;
x
·
= { z | ( x , z ) ∈ F}称为 x 的后集 (post2set )
或输出集.
根据以上叙述 ,我们不难发现 , Petri 网实质上
是对有向图的节点进行了分类 ,将其划分为代表活
动的变迁节点和代表资源的库所节点 ,十分适合描
述工作流系统中以“人”作为活动主体的资源消费或
利用过程. 引理 1 ,2 , 3 描述了网系统结构的静态特
性 ,而引理 4 则刻画了网系统的动态规律 ,即变迁规
则 ( t ransition rule) .
引理 4 . 变迁发生环境定义为
(1) ·t·= ·t ∪t·称为变迁 t 的外延 ;
(2) t 在标识 M 下有发生权 (f riable) 的条件是
( Πs ∈·t : M ( s) Ε W ( s , t) ) ∧
( Πs ∈ t·: M ( s) + W ( t , s) Φ K ( s) ) .
意外事件的发生 ,有一部分就是由于模型中 t
的发生权条件在执行过程中无法满足而造成. 截取
局部 Petri 网进行具体分析 (如图 1 (a) ) . 这一局部
网络由一个变迁和它的一个前集库所和一个后集库
所组成. 如果我们将变迁视为工作流开展当中的活
动 ,而其前集库所和后集库所为活动开展的输入条
件和输出条件 ,那么这一局部 Petri 网就构成了工作
流模型的基本过程单元[21 ,22 ] . 可以将对应输入条件
的资源需求划分为如下两类 :一类是整个工作流系
统执行前 ,根据模型要求 ,可以提前满足的资源配
置 ;另一类是工作流执行时 ,通过过程之间的动态交
互才能满足的资源. 在实际的工作流系统中 ,有些过
程单元可能只要拥有基本的资源配置就可以开展工
作 (如工作流的起始过程单元) ,并完成预期的技术
要求 ,有些过程单元必须借助其它过程单元执行产
生的结果才可以开展工作 ,而有些过程单元则必须
同时具备上述条件才能完成自身的活动. 因此 ,出于
分析的需要 ,首先给出 3 个基本概念.
定义 3 . 初始配置条件即工作流系统执行前 ,
根据活动条件的性质和系统现有的技术储备 ,可以
事先获得的活动初始化条件. 我们用 P2Set 表示初
始配置条件集合. 对应 Petri 网定义过程中的初始标
识 M 0 ;
定义 4 . 动态配置条件即工作流开展过程中
通过过程交互和互操作 ,活动主体从其它协作对象
处获取的支持条件. 我们用 D2Set 表示动态配置条
件集合.
定义 5 . 过程期望指标即活动单元通过自身
的活动 ,结合系统对其的技术要求 ,可以向其它过程
单元或系统提供的技术参数或指标. 我们用 E2Set
表示过程期望指标集合.
在这 3 个定义的基础上 ,对图 1 (a)的 Petri 网基
本部分进行扩展 :用两个库所分别表示对应变迁发
起前置条件的初始配置条件集合和动态配置条件集
合 ;用虚线库所表示过程期望指标集合 (如图 1 (b) )
(注 :本文涉及的库所不受容量限制 ;库所圆圈中的
黑点定性表示该库所非空 ,不具备定量意义) .
经过这种定义和图形表示上的扩充 ,我们可以
6901 计 算 机 学 报 2003 年
给出过程单元的具体定义 (如图 1 (b)所示) .
定义 6 . 过程单元即工作流模型中定义的初
始配置条件、动态配置条件和过程期望指标的活动
或活动集合.
过程单元的递阶定义 ,不仅是系统缩放控制的
基础 ,还可以有效区别并限制意外事件的影响区域.
为了突出过程单元的活动性 ,我们用过程单元中的
变迁名称标识过程单元.
3 . 2 工作流系统中的“流”关系分析
Petri 网主要研究模型系统的组织结构和动态
行为 ,而体现 Petri 网模型动态行为的是系统中可能
发生的各种状态变化以及变化之间的关系 ,往往由
Petri 网模型的实施规则规定[20 ] . Petri 网概念下 ,某
变迁的后置库所作为该变迁后续变迁的前置库所 ,
在 Petri 网中是作为一个节点对待 (如图 2 ( a) 所
示) . 而在过程单元概念下 ,这种对应关系进一步细
化为前一过程单元的过程期望指标集合与后续过程
单元的动态配置条件之间的对应关系 (如图 2 ( b) 所
示) . 这种明确化的需求路线 ,有利于区别并标识意
外事件及其发生的逻辑路线 ,也为采用有效的建模
语言进行系统说明提供了逻辑环境. 例如 ,针对图 2
(b)中的数据流逻辑 ,我们就可以利用如下 SQL 语
句的形式对变迁之间的实施规则进行描述 :
Select [ Related information ] From { t1 . E2Set and/ or
t3 . E2Set} Where〈 t2 . D2Set〉is satisfied
一般而言 ,相对工作流的起始过程单元 , D2Set
可能为空 ,相对形成工作流其它阶段的过程 , P2Set
也可能为空. 但针对某一过程 , P2Set 和 D2Set 不可
同时为空. 于是过程单元对应的局部活动可以用如
下形式进行抽象表示 : P2Set ∪D2Set →PU →E2Set .
在对过程单元进行理论化分析和形式化表示的基础
上 ,我们就可以按照一定的关联逻辑将过程单元连
接起来 ,构造特定的工作流系统. 这种关联逻辑 ,可
以从数据逻辑的角度出发 ,也可以从控制逻辑的角
度出发. 这里 ,我们首先进行工作流的数据逻辑分
析.显然 , ∑D2Seti Α ∑E2Set i ,数据逻辑宏观上可以
表示成这两个集合之间的关系 : Rd = ∑E2Set i ×∑D2
Set i . 由于数据流具有一定的动态性 ,导致过程单元
所包含的三个库所在条件内容上的不稳定. 数据流
之间如果存在“环”(对应意外处理过程的数据流是
一个典型的“环”现象) ,则容易造成“死锁”现象. 如
果缺乏有效的解决手段 ,则很可能造成整个工作流
系统的停滞.
为了解决这类问题 , Arprinar [15 ]首先认为工作
流系统是一种有向无环图 ,在此基础上构造一种偏
序关系. 而将环结构所在的区域看作一个局部单元
整体对待 ,从而从整体上消除环结构. 对环结构所在
的局部单元再采取特定的解决方案. 这种策略的优
点是过程单元之间的关系明确 ,易于从系统的控制
流和数据流的整体对应上对系统进行分析和控制 ;
但在极端情况下 ,如果工作流的起点和终点之间存
在一个环结构 ,就会导致这种策略的整体失效. 另外 ,
数据流并不都表现为一种偏序关系. Holloway[1 ]针对
Petri 网应用 ,从行为控制、逻辑控制与理论控制方
面 ,介绍了几种避免“环”结构现象中出现死锁问题
的常用方法. 但是 ,该文仅仅停留在方法的介绍上 ,
缺少具体的案例和适用环境分析. 为了便于系统的
意外处理 ,我们对数据流和控制流区别对待. 控制流
的确定 ,本质上是一种过程单元之间基于优先级的
权限设定 ,在具体的工作流系统中很容易确定 ,并且
一旦确定 ,就具有一定的稳定性 ,在发生意外事件
时 ,它是进行仲裁和协调的决策与路线依据. 为此将
控制流关系视为偏序关系较为合理 ,在图形表示上
为无环有向图. 而由于数据流存在交互内容与交互
对象方面的复杂性 ,往往不是偏序关系 ,具体的数据
交互在建模阶段往往无法完全确定 ,因此 ,建模阶段
的数据流定义采取语义丰富的规则方式较为合适.
工作流模型则是这两种“流”关系的复合体.
意外事件本质上是一种活动冲突现象. 针对控
79019 期 窦万春等 :面向意外处理的工作流系统建模与执行
制流和数据流 ,意外事件可以划分为对应控制流的
意外情况和对应数据流的意外情况. 对应控制流的
意外情况 (如操作过程中的权限冲突等) ,较容易解
决 ,只要参照对应控制流的偏序关系 ,就能从控制逻
辑上进行协调. 而对应数据流的意外情况 ,则较为复
杂. 显然 ,意外事件具一定的区域性 ,如果这种冲突
影响的范围局限在过程单元内部 ,在整个系统运作
中可以忽略不计 (属于 masking exceptions 类型) . 而
如果冲突影响的范围波及两个或两个以上的过程单
元 ,工作流管理系统必须结合控制流逻辑进行处理 ,
这就是我们下面将要讨论的意外事件的触发点和潜
发点问题.
定义 7 . 工作流执行过程中意外事件产生的
现场位置称为意外事件的触发点. 工作流模型中 ,对
应触发点所在的过程单元称为意外事件的触发过程
单元.
定义 8 . 工作流环境下导致意外事件发生并
对意外事件负责的原始位置 ,我们称之为意外事件
的潜发点. 工作流模型中 ,潜发点所在的过程单元称
为意外事件的潜发过程单元. 需要说明的是 ,对应一
个触发点的潜发点可能会超过一个.
定义 9 . 工作流模型定义的数据流关系中 ,意
外事件的触发点和潜发点之间具有数据流关系的所
有过程单元所形成的工作流区域 ,称之为意外事件
的理论影响区域.
3 . 3 面向意外处理的工作流系统复合建模
结合图 3 所示实例 ,我们对集成数据流逻辑和
控制流逻辑的工作流系统进行建模分析[23 ,24 ] . 图 3
(a)中的实线部分代表的是工作流系统的目标模型 ,
即工作流系统将要实现的功能目标集合. 根据前文
分析的控制流确定原则 ,结合目标模型内在的逻辑
约束 (实线部分 ,也是数据流执行的逻辑方向) ,形成
功能上的划分 (主功能 0 分解成三个子功能 1 , 2 和
3) 和控制关系 (带箭头的点划线部分) . 针对这种功
能上的划分 ,将每个功能看作是未来工作流局部活
动的预期技术指标集合 (对应过程期望指标集合 E2
Set) . 据此 ,为每个功能模块指定一个基于知识应用
的活动实体 (如图 3 ( b) 所示) . 在此基础上 ,结合第
3 . 1 节中过程单元的组成分析 ,形成如图 3 (c) 所示
的工作流复合模型. 该复合模型可以进一步分解成
控制流模型和数据流模型. 图 3 (d)是对应图 3 (c) 所
示工作流复合模型的控制流模型 ,它是意外事件处
理的逻辑仲裁机构. 图 3 (d) 中对应功能模块 0 的过
程单元 ,其 D2Set 为空集 ,在系统表示中可以省略.
结合第 3 . 2 节中的规则分析 ,可以在图 3 ( d) 的基础
上对数据流进行宏观上的定义.
图 3 (c) 中的两个椭圆虚线将该图划分为 3 个
区域 ,最内部的区域可以看作是组成工作流的功能
模型 ,这是工作流活动预期目标的集中体现. 在此基
础上形成的中间区域可以看作是工作流开展的组织
模型 ,它明确了工作流活动主体的职责. 最外层的区
域可以看作是工作流系统开展的资源模型或条件模
型 ,它定义了系统开展的资源需求. 在此基础上 ,利
用数据库中的视图机制 ,通过屏蔽模型中的无关信
息 ,可以大大降低模型理解的难度 ,为特定部门提供
专题服务 ,有利于提高效率. 例如 ,工作流管理系统
在资源调配时 ,根据建模阶段对资源的预期需求汇
总 ,就可以从宏观上对整个系统的资源耗费具有清
8901 计 算 机 学 报 2003 年
醒的认识 ,据此指导后勤规划 ,并将资源储备与流程
实例进行匹配并作标识. 否则 ,很容易造成由于建模
和执行阶段之间的时延而导致建模阶段预置的资源
被其它流程实例所侵占、进而导致该过程实例执行
时该资源的短缺. 这在多流程实例并行的环境下尤
其必要.
一般来讲 ,工作流模型执行过程中的意外事件 ,
往往会伴随着数据流中某个/ 些数据前后不一致、资
源冲突、模型中未定义的某个/ 些事件的突发等现
象[3 ] . 在这种情况下 ,系统往往会暂停执行 ,采取回
溯方式 ,查找导致意外发生的根源[9 ] . 这在单进程
串行工作流模式中 ,往往是一个有效的解决办法. 而
在复杂的基于并行过程交互的工作流模式中 ,由于
意外事件所在节点的父节点不止一个 ,而其父节点
的父节点可能会更多 ,这就为系统的自动化或半自
动化处理带来了困难. 通过控制意外事件的影响区
域来简化意外处理 ,往往以分层建模和递阶控制的
模式进行[7 ] ,如文献 [ 3 ]将意外情况划分为 Noise ,
Idiosyncratic Exception 与 Evolutionary Exception ,系
统对 Noise 可以不予考虑 , Idiosyncratic Exception 则
影响部分工作流环节 ,往往通过定义一个特殊的处
理规则进行处理 ,工作流模型基本上不变. 而 Evolu2
tionary Exception 则需要对工作流模型从整体上进
行完善或重新定义 ,并依据完善后的工作流模型 ,指
导以后过程实例的执行. 此外 ,为防止意外处理过程
中的“状态爆炸”问题 ,也往往需要结合模型的分层
机制 ,对意外事件的影响区域进行规约.
图 3 (c) 的区域划分可以看作是纵向的工作流
模型的分层过程 ,而横向的同一层次工作流模型的
分解 ,也经常在意外处理时采用. 作者在文献[25 ]中
曾提出一个面向知识应用的复杂工作流系统的分解
方法 ,就是针对后者的一种分解策略. 对应图 3 (c)
的区域划分 ,意外事件的性质分类包括 :功能设计上
的意外事件、组织管理上的意外事件、资源调配上的
意外事件. 因而 ,这种复合模型它不仅从模型机制上
为意外事件进行了性质分类 (控制流与数据流提供
的是逻辑分类) ,还为可能的意外处理指定了负责部
门 ,降低了模型在理解上的复杂度.
3. 4 复合模型的形式化描述以及模型的一致性分析
面向意外处理、集成数据流与控制流的复合模
型可以形式化地表示如下 :
W F2Model = ( PU , Fc , Fd) ,
其中 , PU 为过程单元集合 , Fc和 Fd分别为过程单
元之间的控制流关系和数据流关系. 这里我们讨论
的控制对象为抽象的数据流 ,如果数据流具体表现
为系统中的信息传输、物流、资金划拨与消耗、批文
传递等 ,则系统扩展为 ( ( PU , Fc 1 , Fd1) , ( PU , Fc 2 ,
Fd2) , ( PU , Fc 3 , Fd3) , ⋯, ( PU , Fc n , Fdn ) ) . 其中 ,
Fdn表示过程单元之间的物流关系、资金流关系等.
Fc n表示对 Fdn的控制流关系. 显然 ,模型中的过程
单元所包含的 P2Set i , D2Set i以及 E2Set i是构成数据
流与控制流的基本要素. 事实上 ,根据第 3 . 2 节的
“流关系分析”,我们可以发现 ,局部数据流本质上就
是 D2Set i与 E2Set j之间的动态关联 ;而整个数据流
定义则是集合 ∑D2Set i与 ∑E2Set j之间的一种整体
关联关系 ,即 ∑D2Set i R ∑E2Set j中的关系 R. 而控
制流则是从操作权限、优先级、隶属范围等方面定义
在 R 上的约束规则集合. 此外 ,控制流还包含作用
在 ∑P2Set i上的操作控制规则. 在实际的工作流管
理系统中 , ∑P2Set i往往是作为一个整体进行集中
管理的. 在这种集中管理方式下 ,基于独占策略的非
消耗性共享资源的释放规则、消耗性的非共享资源
的定向调配等 ,都需要考虑控制流中对 ∑P2Set i所
定义的操作控制规则.
4 模型执行中基于关联矩阵的工作流
意外处理
就模型执行过程中意外事件对工作流结构组成
的影响 ,我们将其划分为如下两种情况 :
(1) 组成现有工作流系统的过程单元的数量不
变 ,即工作流的 Petri 网表示中变迁元素数量不变 ,
发生变化的是过程单元之间的流关系 ,即对系统内
部原有流关系的二次定义或扩充以及对支持变迁发
生权的对应库所内容的变化. 这种意外情况不存在
系统元素的扩充 ,我们将这类意外处理称之为第一
类意外处理.
(2) 现有工作流系统的功能扩展. 体现为描述
工作流的 Petri 网所含变迁元素的增加 ,即有代表附
加过程单元的变迁元素的加入. 这种意外事件还可
能造成第一类意外处理所面临的情况. 所以 ,这种意
外情况 ,要结合第一类意外处理进行分析. 我们将这
类意外处理称为第二类意外处理.
4 . 1 第一类意外处理
该类意外处理中 ,根据潜发点和触发点之间的
矛盾性质 ,可进一步划分为如下三种情况 :
(1) 触发点需求的资源条件 ,潜发点在系统运
行过程中已经产生 ,但模型中的数据流定义没有在
两者之间建立关联或是在执行过程中没有在权限上
进行授权. 这种情况处理较为简单 ,即潜发点根据触
99019 期 窦万春等 :面向意外处理的工作流系统建模与执行
发点的技术要求 ,直接向触发点提供所需要的资源
条件. 这种情况还包括系统执行过程中对 P2Set 内
容的动态需求.
(2) 触发点所需的资源条件 ,潜发点所在过程
单元的 E2Set 中不存在. 这种情况要求潜发点所在
的过程单元必须经过一定的附加活动才可以产生 ,
并且附加活动对系统的影响仅仅局限在潜发点所在
的过程单元内部 ,对其它过程单元原有信息不产生任
何影响. 这种情况对系统的影响 ,可以认为是一种中
等程度的影响. 可以结合第一种情况进行意外处理.
(3) 触发点所需的资源条件 ,潜发点过程单元
的 E2Set 中不存在. 潜发点为满足触发点资源条件
的需求所组织的附加活动 ,对潜发点与触发点之间
数据流路径上的部分 (或所有) 过程单元有影响. 这
种意外事件的处理最为复杂 ,对系统的影响也最大 ,
必须从界定理论影响区域出发 ,对意外情况进行处
理. 这种意外处理是本文研究的重点. 如果这种附加
活动带来的意外波及了潜发单元上游的过程单元 ,
则根据本文所讨论的方法 ,结合模型的分层表示 ,适
当放大意外处理的影响区域 ,即可将这种情况涵盖
在内.
本文将利用矩阵形式对上述情况进行研究. 为便
于利用矩阵形式对用 Petri 网表示的工作流系统进行
逻辑表示 ,我们首先给出如下矩阵元素赋值规则 :
( t i j) n ×n =
1 c/ 1 d/ 1 e , ( PU i , PU j) ∈ F
0 , ( PU i , PU j) | D .
其中 F 为流关系 ,1 c ,1 d ,1 e分别表示控制流矩阵、数
据流矩阵和对应意外事件触发点和潜发点关系矩阵
中为“1”的元素 ,上标 c , d , e 不影响具体的代数运
算. 对应矩阵中的非零元素 ,可以利用规范化的建模
语言对其蕴涵的逻辑关系进行描述. 第 3 . 2 节中的
SQL 语言已经给出了对应数据流节点描述的范例.
意外事件处理本质上也是一种数据流交互 ,同样可
以采用这种规范化建模语言进行描述. 而对应控制
流矩阵 ,我们可以给出 SQL 语言形式的语言描述 :
Grant [功能描述 ] On PU i to [ Somebody or some
teams] With Grant Option to { PU j} ,其中{ PU j}为
和 PU i具有偏序关系的后集的过程单元[3 ,13 ,14 ,26 ] .
下面我们对图 4 所示的应用实例进行具体分
析. 图 4 (a)是某一控制流模型 ,图 4 ( b) 则是在控制
流模型下的数据流模型 (不包括虚线箭头部分) ,图
4 (b)中的虚线箭头 1 和 2 代表工作流执行过程中的
意外事件 ,即过程单元 t5在工作流执行过程中 ,需要
过程单元 t1和 t4向其提供信息 ,而对应这一要求的数
据流路线在原有数据流模型中没有定义. 根据上述矩
阵赋值原则 ,我们分别构造对应图 4 (a) ,图 5 ( b) ,图
5 (c)的控制流矩阵、数据流矩阵和意外事件触发点和
潜发点关系矩阵 ,分别如图 5 (a) ,6 (b) ,图 6 (c)所示.
为了利用上述矩阵识别意外事件的理论影响区
域 ,首先给出如下引理[ 27 ] .
引理 5 . 设具有 n 个结点的有向图 D 的相邻
矩阵是 M ,则 M l = ( ai , j ) 中的元素 ai , j的值表示从
结点 v i到 v j的长度为 l 的通路数目.
根据上述引理 ,我们很容易从定量计算的角度 ,
标识出意外事件的理论影响区域. 具体步骤如下 :
(1) 针对数据流矩阵 Md ,分别计算出 M1d , M2d , M3d ,
0011 计 算 机 学 报 2003 年
⋯, Mnd ;
(2) M ld中潜发点对应元素所在的行中的每个元素的
值 ,分别表示从潜发点到 t1 , t2 , t3 , ⋯, tn的长度为 l 的通路
数目. 如果元素值为零 ,则表示无长度为 l 的通路存在 ;
(3) 将工作流图形表示中的所有通路都标示出来 ,这就
是我们前面所提到的理论影响区域. 根据触发点的要求 ,将
潜发点的技术要求或所作的信息变动情况
通知
关于发布提成方案的通知关于xx通知关于成立公司筹建组的通知关于红头文件的使用公开通知关于计发全勤奖的通知
理论影响区
域中的所有过程单元 ,为后续过程单元的相应变化提供协同
工作的基本条件.
下面以数据流矩阵为例进行具体分析 ,对图 5 (b)
中的数据流矩阵进行计算(限于篇幅 ,仅计算 M2d) :
M2d =
0 1 d 0 0 0
0 0 0 0 1 d
0 1 d 0 1 d 0
0 1 d 0 0 0
0 0 0 0 0
×
0 1 d 0 0 0
0 0 0 0 1 d
0 1 d 0 1 d 0
0 1 d 0 0 0
0 0 0 0 0
=
0 0 0 0 1 d
0 0 0 0 0
0 1 d 0 0 1 d
0 0 0 0 1 d
0 0 0 0 0
.
从上述结果很容易看出通路的存在情况 ,即意
外事件的理论影响区域. 具体分析如下 :
(1) t1和 t5 (对应矩阵第 1 行) 之间存在一条长
度为 2 的路径 ,对照图 4 (b)即可发现其为 (〈 t1 , t2〉,
〈 t2 , t5〉) . 因为该行其它元素为零 ,所以 t1和其它过
程单元之间不存在长度为 2 的路径.
(2) t4和 t5 (对应矩阵第 4 行) 之间存在一条长
度为 2 的路径 ,对照图 4 (b) 即可发现其为 (〈 t4 , t2〉,
〈 t2 , t5〉) . 同样可以判断 t3其它过程单元之间不存
在长度为 2 的路径.
(3) 由于只有 t1和 t4为潜发点 ,所以 ,矩阵中其
它行元素不加分析.
根据数据流矩阵 M d , M3d , M4d等 ,可以做出类
似的判断 ,从而对意外事件的理论影响区域进行正
确的标识. 在这一标识范围内 ,将意外事件的处理结
果对这一标识范围进行公布. 如果在意外事件的处
理过程中出现“死锁”之类的事件发生 ,则根据系统
的控制流矩阵进行协调. 如果发生“死锁”关系的过
程单元之间直接存在一条控制路径 ,则比较容易按
照优先级或权限高低解决问题 ;如果两者之间不存
在直接的控制关系 ,则根据引理 5 ,对控制流矩阵进
行变换 ,从中发现两者之间的共同的上层控制关系 ,
据此进行系统协调[28 ] . 如在上述实例中 ,对应意外
路径 2 的过程单元 t4和 t5之间不存在直接的控制
关系 ,但是 ,从图中很容易发现 t3是它们共同的上
层控制节点 (通过矩阵变换也可以发现 ,如通过对比
Mc和 M2c对应第 3 行元素可以发现 t3到 t5存在一条
长度为 2 的路径 , t3到 t4存在一条长度为 1 的路径 ,
从而判断 t3是 t4和 t5共同的上层控制节点) ,从而
根据上述控制逻辑 ,进行具体的仲裁决策.
图 5 中的矩阵描述 ,包含了一种分层机制. 如图
5 (a) Mc中的虚线十字框将 t2和 t3进行了聚合 ,此
时 ,工作流模型中的过程单元组成可以表示为 ( t1 ,
( t2 , t3) , t4 , t5) (未分层以前为 ( t1 , t2 , t3 , t4 , t5) ) .
这种分层的模型表示同样有助于控制意外事件的影
响和处理范围. 意外事件的理论影响区域覆盖了意
外事件所有可能的影响范围 ,所以 ,这种处理策略具
有很强的包容性 ,有效地减少了“头痛医头 ,脚痛医
脚”式的意外事件处理方式所带来的二次影响. 而
Me则为建立对应意外事件解决方案的专家系统提
供了 Case 库索引机制[13 ] .
4 . 2 第二类意外处理
第二类意外处理是第一类意外处理的扩展. 第
二类意外处理关键要保证系统扩展的马尔可夫性 ,
确保在第一类意外处理解决方案的基础上 ,对意外
事件进行深化处理. 假设原有的工作流系统在执行
当中 ,根据一定的特殊需求 ,其对应的目标模型需要
增加一个模块 ,并需要增添一个对应的执行活动. 对
待这种意外事件 ,我们首先在原有工作流系统控制
流环境中增加一个活动实体 ,并根据原有的控制流
逻辑 ,在不破坏原有偏序关系的基础上 ,为其指定控
制流路线 (如图 6 (a) ) . 根据我们前面关于控制流逻
10119 期 窦万春等 :面向意外处理的工作流系统建模与执行
辑的制定原则 ,在控制流逻辑领域 ,显然很容易实
现[29 ,30 ] . 我们将结合图 6 中的实例 ,对这类意外处
理进行分析.
图 6 (b)是对应图 5 (a)的控制流扩充示例. 根据
第 4 . 1 节中的元素赋值规则 ,分别在原有控制流矩
阵的最下段和最左端增添一行和一列. 假设 2 到 6 ,6
到 2 ,6 到 5 之间分别存在数据流逻辑 ,同样根据第 4.
1 节中的元素赋值规则 ,对数据流矩阵进行扩充 ,将
其增加一行和一列 (如图 6 (c) ) . 显而易见 ,这种扩充
是一种基于马尔可夫过程的扩充. 系统扩充完毕 ,就
可以按照第 4. 1 节的处理方案进行意外处理.
这种基于矩阵表示的方法简单明了 ,类似整个
系统的坐标系. 结合具体的建模语言 ,它不仅可以从
静态角度对整个工作流系统进行刻画 ,而且在系统
执行时 ,经过简单的转换还可以从动态角度为工作
流的正常执行和意外事件的处理提供路径约束和方
向指导. 此外 ,在关联逻辑的基础上结合特定的技术
(如 CORBA ,Java ,Web 技术等) 就可以进行基于马
尔可夫过程的系统规模扩展 (如面向分布式环境的
工作流系统) [31 ] ,其系统的复杂度是原有系统上的
局部扩展 ,从而为系统扩展提供了理论分析基础.
5 面向数据流意外处理的工作流系统
应用实例
图 7 所示的应用实例是我们自主开发、在数据
流执行方面具有意外处理功能的工作流系统部分截
屏图. 图 7 中上层图示的数据交互窗口 ,表示某一过
程单元 (在该实例中为“活动 2”) 与其它过程单元进
行数据交互的情况 (即对应数据流矩阵中的某一
列) . 在数据交互窗口中 ,点击“缺省”按钮 ,则在右下
方的列表框中列出建模阶段定义的、与“活动 2”构
成数据流关系的所有过程单元 (前面图标为“< ”的
过程单元) ,“活动 323”则是根据需要 (对应意外事
件) 加入的活动单元 (对应 4 . 1 节第 1 种意外事件) .
图 7 反映的是 :建模阶段 ,定义“活动 1”、“过程 2”为
与“活动 2”形成数据流的过程/ 活动单元. 在“缺省”
按钮情况下 ,将“过程 2”所包含的内容都作为与“活
动 2”形成数据流的过程/ 活动单元. 这种基于范围扩
展的处理策略 ,简化了意外事件影响区域的标识 ,为
意外处理提供了参考空间. 如在实际应用中 ,“活动
223”与“活动 2”不发生数据交互 ,即不形成数据流 ,则
可以将其从列表中删除 ,即对应数据交互窗口中的
“删除”按钮. 借助于黑板或白板机制 ,其它过程单元
对此处 (触发点) 意外事件的连锁反应与对应的处理
过程形成了整个系统的意外处理过程. 显然 ,这里的
数据流意外处理在某种意义上是独立于过程定义的.
6 结束语
对意外事件的处理能力是衡量工作流系统性能
的重要指标. 本文所讨论的意外处理方法 ,兼顾建模
与执行两个方面 ,在问题描述与意外处理方面具有
很强的兼容性 ,适用于处理可预见的意外事件与不
可预见的意外事件. 技术应用上倾向于以“人为处
理”(human2centered) 为特征的复杂工作流系统. 而
较简单的自动化领域的工作流意外处理 ,采用增加
条件分支的方式即可以进行有效处理. 与其它方
法[2~7 ]相比 ,该方法应用阶段与应用对象明确 (如
对控制流和数据流的单独处理) ,方法运用对象的针
对性强. 如何将方法的原理分析与系统的设计与实
现进行有机的结合 ,则是我们未来的研究重点.
致谢 审稿专家富有建设性的
意见
文理分科指导河道管理范围浙江建筑工程概算定额教材专家评审意见党员教师互相批评意见
,扩展了作者的
研究思路 ,为本文的进一步完善提供了有益的指导
与帮助 ,特此向评阅专家表示诚挚的谢意 !
参 考 文 献
1 Holloway L E , Krogh B H , Giua A. A survey of Petri net meth2
ods for controlled discrete event systems. Discrete Event Dynamic
Systems : Theory and Applications , 1999 , 7 (2) : 151~190
2 Agostini A , DeMichelis G. A light workflow management system
using simple process models. Computer Supported Cooperative
Work (CSCW) , 2000 , 9 (3/ 4) : 335~364
3 Kammer P J , Bolcer G A , Taylor R N , Hitomi A S , Bergman M.
Techniques for supporting dynamic and adaptive workflow. Com2
puter Supported Cooperative Work (CSCW) , 2000 , 9 (3/ 4) : 269
~292
4 Ellis C , Keddara K. ML2DEWS : Modeling language to support
dynamic evolution within workflow systems. Computer Supported
Cooperative Work (CSCW) , 2000 , 9 (3/ 4) : 293~334
5 Divitini M , Simone C. Supporting different dimensions of adapt2
ability in workflow modeling. Computer Supported Cooperative
2011 计 算 机 学 报 2003 年
Work (CSCW) , 2000 , 9 (3/ 4) : 365~398
6 Klein M ,Dellarocas C ,Bernstein A. A knowledge2based approach
to handling exceptions in workflow systems. Computer Supported
Cooperative Work (CSCW) , 2000 , 9 (3/ 4) : 399~412
7 Faustmann G. Configuration for adaptation ———A human2centered
approach to flexible workflow enactment . Computer Supported
Cooperative Work (CSCW) , 2000 , 9 (3/ 4) : 413~434
8 Hayes N. Work2arounds and boundary crossing in a high tech op2
tronics company : The role of co2operative workflow technologies.
Computer Supported Cooperative Work (CSCW) , 2000 , 9 (3/ 4) :
435~455
9 Klein M , Dellarocas C , Bernstein A. Introduction to the special
issue on adaptive workflow systems. Computer Supported Cooper2
ative Work (CSCW) , 2000 , 9 (3/ 4) : 265~267
10 Perry D E , Romanovsky A , Tripathi A. Current trands in excep2
tion handling. IEEE Transaction on Software Engineering , 2000 ,
26 (9) : 817~819
11 Perry D E , Romanovsky A , Tripathi A. Cur