Method of workflow time performance analysis
X IA O Zhi - j iao, CH A N G H ui - you, YI Yang
( Dep. o f Computer Sci. , Sch. o f Info. S & T , Zho ng shan U niv . , Guang zho u 510275, China) Abstract: W orkflow Perfo rmance analysis is the basis of wo rkflo w evaluation and optimizatio n. T ime is an impor tant aspect of wo rkflo w perfo rmance. T her e a re usually several instances o f differ ent wo rkflow s r unning in the w orkflow manag ement sy stem so that different act ivities compete fo r resources. T o solve t his pro blem, a g ener al met ho d using queuing theor y was pr oposed to analyze the time perfo rmance of a wo rkflo w running in such a wo rkflow management sy stem. T he aver age thro ughput time o f w or kflow instances w as used as the indicator of w orkflow t ime perfo rmance. F ina lly, some ex amples were g iv en to illustrate the feasibility and validity of the method. F utur e research trends w ere also pr oposed. Key words: w o rkflo w; time perfor mance analy sis; queuing theor y
h
。
( 3)
若活动 a ij 的执行需要资源 r h 的参与, 则活动 aij 的平均处理时间为 tij = w h + 1 。 L ij 1. 2 工作流可执行路径平均处理时间 现说明第 i 类工作流的第 k 条可执行路径 A ik 的平均处理时间 t A ik 的计算过程。 由于可执行路径是通过- 或. 节点来划分的 , 在 可执行路径中不再存在 -或. 节点 , 则可执行路径中 的活动之间只可能构成如下 3 种结构关系: ( 1) 顺序结构 可执行路径 A ik = { aik 1 , a ik 2 , ,, aik | A ik | } 由一连 串顺序执 行的活 动组成 , 其平均 处理时 间 tA ik =
数, 分析其是否具有较高的性能, 主要反映工作流定 量方面的特性。时间是衡量工作流性能的一个重要 指标 , 对时间性能的分析主要是对工作流运行周期 时间的分析, 即工作流从开始到结束所使用的时间。 文献 [ 1] 提出了由任意多个变迁组成的串联、 并
收稿日期: 2005- 05- 16; 修订日期: 2005- 07- 18。Received 16 M ay 2005; accepted 18 July 2005. 基 金项目: 广东省自然科学基金资助项目( 031539) ; 广东省/ 十五0规划资助项目( 03/ 04L13) 。Foundation items: Project supp orted by the Natu r al Science Foun dation of Guan gdon g Province, China ( No. 031539 ) and th e 10th Five - year Plan of Guangdong, Chin a( No. 03/ 04L13). 作者简介: 肖志娇( 1980- ) , 女, 湖南隆回人, 中山大学信息科学与技术学院博士研究生, 主要从事工作流、 模型分析与优化等的研究。 E- m ail: mm ou secindy@ yah oo. com. cn。
q ij 为活动 a ij 的执行概率, q ij =
k= 1
E (p
ik
#R ij k ) 。
如果路径 A ik 的顺序或并行结构包含活动 a ij , 则 R ij k = 1; 如果路径 A ik 的循环结构包含活动 a ij , 则 Rij k 的 值见 1. 2 节 ; 如果路径 A ik 不包含活动 aij , 则 R ij k = 0。
E p #(1i= 1
]
q) i = p ( 1 - q) 。 q
肖志娇, 常会友, 衣 杨
广州 510275) ( 中山大学 信息科学与技术学院计算机科学系, 广东
摘
要 : 工作流性能分析是对工作流进行评价 和优化 的基础 , 时间 则是反 映工作 流性能 的一个 重要方 面。工
作流管理系统中通常有属于不同工作流的多个实例同时 运行 , 从而 在不同工 作流的 多个实 例之间 造成资 源竞争。 对此 , 从资源的角度出发 , 利用排队论提出了一种通用的工作流时间性能分析方法 , 其中采 用工作流 实例平均响 应 时间作为工作流时间性能的分析与评价的指标。最后 , 通过实 例说明 了该方 法的可 行性和 有效性 , 并提 出了未 来 的研究方向。 关键词 : 工作流 ; 时间性能分析 ; 排队论 中图分类号 : T P31 文献标识码 : A
第 12 卷第 8 期 20 0 6 年8月
计算机集成制造系统
Computer Integr ated M anufacturing Sy stems
V ol. 12 N o. 8 A ug . 2 0 06
文章编号 : 1006- 5911( 2006) 08- 1284- 04
工作流时间性能分析方法
|A | g= 1
p A = p + p # ( 1 - q) + p # ( 1 - q) # ( 1 - q) + ,=
i= 0
( 4)
E p # ( 1-
]
q) i = p ; q
( 5)
活动集 B 中所有活动的执行概率为 p B = p # ( 1 - q) + p # ( 1 - q) # ( 1 - q) + , =
第 8期
肖志娇 等: 工作流时间性能分析方法
1285
活动调度的时间 ) ; 每个活动的处理时间由执行时间 和等待时间两部分组成, 其中等待时间主要是资源 等待时间。目前 , 已有的分析方法大都假设系统中 只存在单个工作流的多个实例对资源的竞争, 或假 设某种资源只参与单个活动的实例的执行。而实际 上, 系统中不只存在多个工作流的多个实例, 同一工 作流实例的不同活动之间也有可能存在资源竞争 , 即资源有可能参与多种不同活动的执行。 文献 [ 3] 利用排队网络理论对工作流进行了性 能分析。本文利用排队论 , 针对系统中不同工作流、 不同活动的多个实例之间竞争资源的情况, 对工作 流的时间性能进行了分析。
i= 1 j = 1
E E ra
hij
# q ij # U i
因此, 可以将资源 r h 看作是一个 M / G/ ei 排队系统。 其中, e h 是服务台个数, 即系统中第 h 类资源的数 量。 这里要注意的是, K h 可看作是在单位时间内到达 的需要资源 r h 处理的客户数, e h # L h 可看作是资源 r h 在单位时间内能够处理的客户数。 由于必须使得 资源的处理速度大于客户的到达速度, 即 K h / ( eh # L h ) < 1, 才能保证系统稳定 , 要保证 eh > ( K h/ L h ) , eh 必须为整数。 根据排队论与随机服务系统 的相关知识 [ 4- 5] , 可求得活动实例在资源 r h 队列中的平均等待时间
n 为工作流管理系统中的资源种类数。 r h 为系统中的第 h 类资源。 K h 为资源 r h 的客户( 即需要该类资源参与执行 的工作流活动的实例 ) 到达率 , 可看作是单位时间 内到达的客户数。 L h 为资源 r h 的客户服务时间( 即需要该类资源 参与执行的工作流活动实例的执行时间 ) 均值的倒 数 , 可看作是单个资源单位时间内能够服务的客户 数。 eh 为系统中第 h 类资源的数量。 ra hij 表示资源 r h 是否参与了活动 a ij 的执行 , 其 取值分别为 1 和 0, ra hij = 1 表示活动 aij 的执行需要 资源 r h , ra hij = 0 表示活动 aij 的执行不需要资源 r h。 w h 为活动实例在第 h 类资源等待队列中的平 均等待时间。 1. 1 工作流模型活动平均处理时间 第 i 类工作流的第 j 个活动 a ij 的平均处理时间 t ij 的计算过程如下: 设第 i 类工作流的实例到达服从参数为 Ui 的泊 松分布 , 则 wm i 中的活动 a ij 的实例到达服从参数为 q ij Ui 的泊松分布。 对于资源 r h 而言, 它的客户 ( 即需 要该类资源参与执行的工作流活动的实例) 到达仍 然服从泊松分布, 参数为 K h =
m an
i
1
工作流时间性能分析
首先需要说明的是, 这里所考虑的工作流都是 结构正确的, 不存在行为上的错误; 另外, 由于现在 的绝大部分工作流管理系统都不提供对基于多资源 协调的任务执行方式的支持
[ 3]
, 这里假设每一个活
动的执行只涉及 1 种资源。下面给出相关参数: m 为工作流管理系统中存在的不同工 作流的 种数。 wm i 为第 i 类工作流的模型。 U i 为第 i 类工作流的实例到达所服从的泊松分 布的参数。 at t i 为第 i 类工作流的实例平均响应时间。 pn i 为第 i 类工作流的可执行路径的条数。 A ik 为第 i 类工作流的第 k 条可执行路径 ( k = 1, 2, ,, p n i ) 。 tA ik 为可执行路径 A ik 的平均执行时间。 p ik 为第 i 类工作流的实例按可执行路径 A ik 执 行的概率。 an i 为第 i 类工作流的活动数。 aij 为第 i 类工作流的第 j 个活动 ( j = 1 , 2, ,, an i ) 。 tij 为活动 a ij 的平均处理时间。 L ij 为活动 a ij 的执行时间所服从的指数分布的 参数。 R ij k 为活动 a ij 在可执行路径 A ik 中的执行系数。