（计算机应用技术专业论文）工作流系统中的时间管理算法研究.pdf

摘要 缺乏对时间管理的支持是当今工作流管理系统的一个重要不足，也是工作流技术实施复 杂企业应用的严重局限。开展工作流时间管理的研究，对于丰富工作流建模理论、开发灵活 和实用的工作流管理系统、确保工作流计划的高效执行和提高企业的竞争力具有重要意义。 本论文对该领域中的工作流时间约束一致性验证和时间约束工作流调度两个部分进行了较 为深入的研究。 论文工作的主要成果表现在以下几个方面： 1 ) 基于时间约束m ( t c n ) 的基本理论，提出了时间约束网“部分交”和“拆分”运算 的概念，并对其具有的主要性质做了深入的分析，从而扩充了时间约束网的运算理论，使其 能更好地运用于工作流时间约束的推理。 2 ) 基于论文中提出的t c n “部分交”和“拆分”运算，给出了工作流时间约束一致 性验证算法w f t c c v ，从工作流模型的整体上考虑了时间约束的一致性问题，从而保证了 工作流模型的时间可调度性，弥补了传统方法中存在的不足。 3 1比较全面地考虑了工作流执行期间任一时刻各活动的当前状态，给出了为当前待调 度活动制定最优执行计划的基于t c n 的时间约束工作流调度算法t c w f s ，弥补了相关研 究的不足。 关键词：工作流，时间管理，时间约束，时间约束网，一致性验证，调度 a b s t r a c t l a c ko fs u p p o r tf o rt i m em a n a g e m e n th a sb e e ni d e n t i f i e da so n eo ft h em o s ts i g n i f i c a n t s h o r t a g e so ft o d a y sw o r k f l o wm a n a g e m e n ts y s t e m s ，a n da l s oas e r i o u sl i m i t a t i o ni na p p l y i n g w o r k f l o wt e c h n o l o g i e st oc o m p l e xe n t e r p r i s e s d o i n gr e s e a r c h e so nw o r k f l o wt i m em a n a g e m e n t i si m p o r t a n tt oe n r i c h i n gt h et h e o r yo fw o r k f l o wm o d e l i n g , t oe n h a n c i n gt h ef l e x i b i l i t ya n d p r a e t i c a l i t yo fw o r l d l o wm a n a g e m e ms o f t w a r es y s t e m s ，t og u a r a n t y i n gw o r k f l o wp l a n st ob e e f f i c i e n t l ye x e c u t e d ，a n dt om a k i n ge n t e r p r i s e sm o r ec o m p e t i t i v e c o n s i s t e n c yv e r i f i c a t i o n f o r w o r k f l o wt e m p o r a lc o n s t r a i n t sa n ds c h e d u l i n gf o rt e m p o r a le o n s t r a i mw o r k f l o w sh a v e b e o n d e e p l yr e s e a r c h e di nt h i sp a p e r t h em a i nc o n t r i b u t i o n so f t h ep a p e ra l el i s t e da sf o l l o w s ( 1 ) b a s e do nt h eb a s i ct h e o r yo ft e m p o r a lc o n s t r a i n tn e t w o r k s ，t w oo p e r a t i o n s ，“p a r t i a l l y j o i n ”a n d s p l i t h a v eb e e np r e s e n t e da n dd e e p l ya n a l y z e d o p e r a t i n gt h e o r yo ft e m p o r a l c o n s t r a i n tn e t w o r k sh a sb e e ne x t e n d e dt of i tf o rr e a s o n i n gi nw o r k f l o wt e m p o r a lc o n s t r a i n t s ( 2 ) b a s e do nt h et c no p e r a t i o n s - - p a r t i a l l yj o i n a n d “s p l i t ，at c n b a s e dv e r i f i c a t i o n a l g o r i t h m w f t c c vh a sb e e np r e s e n t e df o rv e i l f y i n gt h ec o n s i s t e n c yo fw o r k f l o wt e m p o r a l c o n s t r a i n t s ，i nw h i c haw o r k f l o ww i t hs e v e r a li n s t a n c et y p e si sc o n s i d e r e da saw h o l e ，t om a k eu p t h es h o r t a g ei nt r a d i t i o n a lm e t h o d s ( 3 ) at c n b a s e ds c h e d u l i n ga i g o r i t h m - - t c w f sh a sb e e np r e s e n t e df o rm a k i n go p t i m i z e d p l a n sf o ra c t i v i t ye x e c u t i o n si nt e m p o r a lc o n s t r a i n tw o r k f l o w s ，i nw h i c ht h ec u r r e n te x e c u t i n g s t a t e so fa c t i v i t i e sh a v eb e e nc o n s i d e r e dc o m p l e t e l y ，t om a k eu pt h es h o r t a g ei nr e l a t i v e r e s e a r c h e s k e y w o r d s ：w o r k f l o w , t i m em a n a g e m e n t , t e m p o r a l c o n s i s t e n c yv e r i f i c a t i o n , s c h e d u l i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：坌垒堡日期：盟了 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：缝盗导师签名：玉茏日期：埘岁 第一章概述 1 1 选题依据及意义 第一章概述 工作流技术是实现企业业务过程建模、业务过程仿真分析、业务过程优化、业务过程管 理与集成，从而最终实现业务过程自动化的核心技术。至今，虽然已经有不少研究人员从不 同的角度开展了工作流管理及其相关技术的研究，但是有关工作流管理技术研究和应用中的 许多关键技术问题还处于探索阶段。 活动的动态特征是当今企业业务过程中一个公认的重要特征。一个业务过程是否能成功 执行往往依赖于其所含活动的执行是否符合约定的同步关系。在某些业务过程中，任何时间 约束方面的背离将导致额外的支出、危险。甚至是违法的。例如法律程序、航班调度和危险 品处理。为了适应这个重要特征，工作流系统必须具备业务过程时间管理的能力。然而，目 前的工作流管理产品还远远不能满足业务过程时间管理的需求，工作流系统中的时间管理仍 是一个有待深入研究的开放性问题。基于这样一个事实所有的业务过程都存在于一个 时间环境中，且带有时间约束，缺乏对时间管理的基本支持已被认为是当今工作流管理系统 的一个重要不足，也是工作流技术实施复杂企业应用的严重局限”1 。开展工作流时间管理的 研究，对于丰富工作流建模理论、开发灵活和实用的工作流管理系统、确保工作流计划的高 效执行和提高企业的竞争力具有重要意义“。 1 2 国内外研究现状 时间管理在项目管理、车间调度、人工智能、时序数据库与实时软件工程学科已经研究 多年“4 1 。可是，工作流建模与实例化的复杂性使上述领域的时间建模与管理技术都不适用于 工作流时间管理。工作流系统中的时间管理成为了一个极具挑战性的研究课题。自九十年代 末以来，国外的研究人员从不同的角度做了相关的研究“4 “”。国内对于工作流技术的研究 “”主要着重于工作流建模方法与系统实现技术，对业务过程时间管理的研究开展得较晚。 王海洋“”通过指定活动延迟上界，可在一定程度上弥补因任务执行拖延而引起全局的时间损 失，但是所考虑的时间约束相对比较简单，缺乏时间有关的验证，应用局限性较大。2 0 0 2 年， 李慧芳”1 等在软件学报发表论文“工作流系统时间管理”，综述了工作流系统中时间管 理的研究现状。此后，国内的一些学者“”1 在该领域开展了深入的研究。 工作流系统中时间管理的研究内容主要包括：时间信息的表示、时间约束一致性的验证、 时间性能的分析、实例化过程中的任务调度、时间异常的检测以及时间异常的处理等。其中， 时间约束一致性的验证和实例化过程中的任务调度包含t i 作流时间推理的主要方法，为工 作流时间性能的分析和工作流时间异常的检测及处理提供了核心技术。基于此，可以将上述 研究内容归纳为工作流系统中时间信息的表示和推理。 1 2 1 时间信息的表示 1 1 基于工作流图的方法 东南大学硕士学位论文 l 活动标识活动延迟 n d l 最早完成( d 最晚完成 l 时间n e 时间n l 图1 1 赋时活动节点 如 e d e r ”1 基于赋时活动图，建立包含活动时间属性的工 作流模型，如活动执行延迟、截止期限、固定日期以及时间 距离约束，并将所有的时间约束换算为活动执行结束的时 间点。图1 1 所示的赋时活动节点n ，n d n e n l 分别表示活 动n 的执行延迟最早完成时间最晚完成时间图1 2 是由 图1 1 的节点构成的赋时工作流图。 裹 图1 2 一个赋时工作流图例 m a r j a n o v i c “”基于好结构的( w e l is 咖c t i l r e d ) 工作流图模型”，利用延迟自由度描述活 动执行延迟的不确定性，将工作流模型中的时间约束分为四类：基本时间约束( b a s i c t e m p o r a lc o n s t r a i n t s ) 、有限延迟约束( 1 i m i t e dd u r a t i o nc o n s t r a i n t s ) 、最终期限约束o e a d l m e c o n s t r a i n t s ) 和相对时间约束( i n t e r d e p e n d e n tt e m p o r a lc o n s t r a i n t s ) ，同时引入延迟空间( d u r a t i o n s p a c e ) l 拘概念提出了一些时间约束的可视化表示方法。 k a f e z a ”1 着重于活动间的相对同步关系，将活动间的时序依赖转化为统一的二元时序约 束，通过为工作流图的有向边增加时间标签来包含业务过程的时问信息。时间管理的关键在 于活动的时序协调，考虑到活动延迟与截止期限约束。用活动开始完成事件发生的顺序来 表示工作流的时序约束，并将活动间的时序关系归纳为之前、汇合、重叠、同时开始、覆盖、 同时完成与相等7 种。 2 ) 基于p e t r i 网的方法 p e t r i 网利用触发延迟、保持延迟和使能延迟”等时间表示形式描述不同语义的实时系 统，例如为库所变迁扩展时间参数对，为t o k e n 赋予时间戳( t i m e - s t a m p ) 表示业务实例的全局 生命时间。”。l i n g ”通过扩展基本网系统包含业务过程的时间因素，提出了时间工作流网， 并将活动执行时间映射为工作流网”的变迁时间对，修改工作流网的分析方法，如活性、安全 性和合理性来分析时间约束工作流的行为性质。a d a m ”以p e t r i 网为建模分析工具，基于“操 作一元语”语义框架，将任务划分为操作集和任务元语集，全面描述任务在整个工作流执行中 所遍历的5 种状态一初始态、执行态、完成态、提交态与退出态，并借助于库所变迁时间 对以及t o k e n 时间戳来建模任务间的时序依赖约束，包括业务实例的到达时间和任务可执行 时间范围等。 1 2 2 时间约束一致性的验证 时间约束一致性的验证旨在确保工作流模型的时间可调度性。m a r j a n o v i c 通过计算活 动之间的最长最短时间距离，给出了有限延迟、时间距离和截止期限约束的一致性验证规则。 在此基础上，b e t t i n i 。1 引入了工作流模型中并发任务之间以及邻接任务之间的时间约束，同 时在时间约束定义中引入了多时间粒度的概念，提出了基于时间约束( t e m p o r a lc o n s t r a i n t 2 第一章概述 n e t w o r k s ，1 n ) 1 的时间约束一致性验证算法。 1 2 3 时间性能的分析 时间性能的分析是指验证集成时间约束的工作流模型的合理性、有界性与活性等，为工 作流的安全、可靠执行奠定理论基础。l i n g “”和a d a m 立足于工作流执行的每一步骤对时 间约束的影响，修改或扩展已有的工作流分析方法以分析时间约束工作流模型。l i n g ”引 入关联情形( c o n t a c ts i t u a t i o n ) ，精确定义了活动的时间安全性，提供了形式化方法以检测模 型错误及资源冲突。a d a m ”考虑了任务之间的控制流、价值流与时序依赖，利用p e t r i 网的 结构性质识别不一致的任务依赖说明，检验工作流的安全性，并验证工作流在特定时序约束 下的执行可行性，其缺点是对于稍微复杂的业务过程会遇到计算复杂性问题。 1 2 4 实例化过程中的任务调度 工作流模型中的时间约束具有强制性，即工作流的一次成功执行必须满足模型中所有相 关时间约束。任务调度的目标是：在工作流执行过程中，为当前待调度活动制定执行计划， 若每个执行计划都被相应活动执行体遵守，则工作流模型中的所有相关时间约束都将被满 足。b e t t i n i 用一个区间三元组表示活动执行计划：( 1 _ e b e g i n , l b e g i n ，【m ，n 】，【e e n d ，l e n d ) ， 给出了基于时间约束网的调度算法。 1 2 5 时间异常的检测 工作流执行过程中，活动执行的不确定性常常会违反工作流模型中的时间约束定义。时 间异常检测的任务是：监控活动的执行，尽早预测发现可能的时间约束违反。m a r j a n o v i c “3 引入控制点集合c ，通过c 中元素的动态增减，检测潜在的时间约束违反。 1 2 6 时间异常的处理 如果出现时间违反应采取适当的措施弥补时间损失或尽量减小这种影响的传播，力求 获得工作流执行的一致状态。e d e r ”在工作流模型中引入选择活动和替换活动，当违反截 止期限时，可采取如下措施：( 1 ) 扩展期限约束或缩短后续活动的调度周期；( 2 ) 改变后续替 换活动的选择策略；( 3 ) 删除后续的选择性活动；( 4 ) 请求人的干预，通过人与工作流系统的 交互，动态调整工作流计划、提高活动优先权、缩短后续活动调度周期、重新商讨截止期限 等，以重新获得有效的工作流状态。 1 2 7 其它有关研究内容 z h u g e 1 1 1 z 建立了面向多时区的超级时间约束模型，分布于不同时区的业务活动具有不 同的时间轴，其中一个作为参考轴，并将其他轴的时间映射至参考坐标轴。m m j a n o v i c “1 提出 了面向生产型的时间约束可视化模型，用活动持续空间及实例空间分别表示流程建立时相对 及运行时绝对时间约束。c h a n g “基于排队理论研究了时间约束工作流模型中的关键路径问 题，提出了计算关键路径的c p i 算法。 东南大学硕士学位论文 1 3 论文研究工作的主要内容 论文研究工作的主要内容包括如下几个方面： 1 ) 时间约束n ( t m p o r a ic o l l g t r a i n tn e t w o r k s 。t c n ) 的运算理论 时间约束网是用于表示和分析基于网状结构时间约束问题的数学模型。论文研究了如何 扩充时间约束网的运算理论，使其能更好地运用于工作流时间约束的推理。 2 ) 基于t c n 的工作流时间约束一致性验证算法 传统方法大都采用对工作流模型中各个实例类分别进行验证的模式，通过对各实例类中 时间约束一致性的验证结果推断整个工作流模型中时间约束的一致性。这类方法尽管可以验 证出工作流模型中可能存在的部分时间约束冲突，但存在严重的缺陷，无法保证被其验证为 时间约束一致的工作流模型具备时间可调度性。论文研究了如何从整体上考虑工作流模型中 时间约束的一致性问题，从而弥补上述缺陷。 3 ) 基于t c n 的时间约束工作流调度算法 相关研究的调度算法中，静态地处理了工作流的当前执行状态，没有考虑已调度未完成 活动的不确定性对当前调度的影响。论文研究了如何在调度过程中全面地考虑模型中各活动 的当前状态，从而弥补相关研究的不足。 1 4 论文研究工作的主要成果 论文研究工作的主要成果反映在以下方面： 1 ) 扩充了时间约束网( t c n ) 的运算理论 基于时间约束网的基本理论，提出了时间约束网“部分交”和“拆分”运算的概念，并 对其具有的主要性质做了深入的分析，从而扩充了时间约束网的运算理论，使其能更好地运 用于工作流时间约束的推理。 2 1 给出了基于t c n 的工作流时间约束一致性验证算法w f t c c v 为了深入而全面地分析工作流时间约束的一致性，将工作流模型中的时间约束分为如下 四类：结构约束、活动延迟约束、过程约束和同步约束。针对传统一致性验证方法中存在的 不足，给出了工作流时间约束一致性的完整定义。基于论文中提出的t c n “部分交“和“拆 分”运算，给出了工作流时间约束一致性验证算法w f t c c v ，从工作流模型的整体上考虑 了时间约束的一致性问题。从而保证了工作流模型的时间可调度性，弥补了传统方法中存在 的不足。 3 1 给出了基于t c n 的时间约束工作流调度算法t c w f s 论文将工作流执行期间活动所处的状态分为：已完毕( f i n i s h e d ) 、已开始未完毕( s t a r t e d a n du n f i n i s h e d ) 、已调度未开始( s c h e d u l e da n du n s t a r t e d ) 、调度中( b e i n gs c h e d u l e d ) 和未调 度( u n s c h e d u l e d ) ，进而比较全面地考虑了工作流执行期间任一时刻各活动的当前状态，给 出了为当前待调度活动制定最优执行计划的时问约束工作流调度算法t c w f s ，弥补了相关 研究的不足。 4 第一章概述 1 5 论文的组织和结构 论文共分六个章节。各章节摘要如下： 第一章作为论文的概述。说明了选题的依据和意义；在较为全面地介绍了国内外研究现 状后简要地介绍了论文研究工作的主要内容和成果，最后给出论文的组织结构。 第二章介绍了工作流的基本概念和定义，简要说明了其包含的过程建模、工作流执行控 制和工作流管理系统中的人机交互等部分。 第三章在介绍时间约束陌j ( t c n ) 基本理论的基础上，提出了时间约束网“部分交”和“拆 分”运算的概念，并对其具有的主要性质做了深入的分析，从而扩充了时间约束网的运算理 论，使其能更好地运用于工作流时间约束的推理。 第四章深入研究了基于t c n 的工作流时间约束一致性验证算法。将工作流模型中的时 间约束分为如下四类：结构约束、活动延迟约束、过程约束和同步约束。给出了工作流时间 约束一致性的完整定义。该章提出的一致性验证算法w f t c c v 运用t c n 的“部分交”和 “拆分”运算。从工作流模型的整体上考虑了时间约束的一致性问题，从而保证了工作流模 型的时间可调度性，弥补了传统方法中存在的不足。 第五章深入研究了基于t c n 的时间约束工作流调度算法。将活动在工作流执行期间所 处状态归纳为：已完毕( f i n i s h e d ) 、已开始未完毕( s t a r e da n du n f i n i s h e d ) 、已调度未开始 ( s c h e d u l e d a n d u n s t a r t e d ) 、调度中( b e i n g s c h e d u l e d ) 和未调度( u n s c h e d u l e d ) ，进而比较全面 地考虑了工作流执行期间任一时刻各活动的当前状态，给出了为当前待调度活动制定最优执 行计划的时间约束工作流调度算法t c w f s ，弥补了相关研究的不足。 第六章是对整个论文研究的总结，综述本论文在时间约束网运算理论、工作流时间约束 一致性验证和时间约束工作流调度等研究领域取得的成果，并指出现有研究工作的局限性和 有待提高和改进的方面，阐述了将要深入研究的要点。 东南大学硕士学位论文 第二章工作流技术简介 工作流技术是实现企业业务过程建摸、业务过程仿真分析、业务过程优化、业务过程管 理与集成，从而最终实现业务过程的自动化的核心技术。对企业利用工作流方法进行业务 过程的建模和深入分析不仅可以规范化企业的业务流程，发现业务流程中不合理的环节，进 而对企业的业务过程进行优化重组，而且所建立的业务过程模型本身就是企业非常重要的知 识库和规则库，可以成为指导企业实施计算机管理信息系统的模型。在深入分析企业需求基 础上建立的企业业务模型可以在最大程度上提高企业实施e r p 或者其他管理信息系统的成 功率。所以，大力发展并推广工作流技术对于促进我国企业管理规范化和信息化有重要的现 实意义。 2 1 工作流的基本概念和定义 1 9 9 3 年工作流管理联盟( w o r k f l o wm a n a g e m e n tc o a l i t i o n ，w f l v l c ) 的成立标志着工作流 技术开始进入相对成熟的阶段。 工作流管理联盟给出的工作流定义是：工作流是一类能够完全或者部分自动执行的经 营过程，它根据一系列过程规则、文档、信息或任务能够在不同的执行者之间进行传递与执 行。 工作流管理联盟给出的关于工作流管理系统的定义是：工作流管理系统是一个软件系 统，它完成工作流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实 例的执行。 虽然不同的工作流管理系统具有不同的应用范围和不同的实施方式，但它们还是具有许 多共同的特征。从比较高的层次上来抽象地考察工作流管理系统。可以发现所有的工作流管 理系统都提供了3 种功能“”： 1 ) 建立阶段功能：主要考虑工作流过程和相关活动的定义和建模功能。 2 、运行阶段的控制功能：在一定的运行环境下。执行工作流过程，并完成每个过程中活 动的排序和调度功能。 3 ) 运行阶段的人机交互功能：实现各种活动执行过程中用户与i t 应用工具之间的交互。 2 2 过程建模 2 2 1 简述 工作流管理系统建立阶段的功能主要完成经营过程的计算机化的定义。在这个阶段，利 用一个或多个建模技术与工具，完成实际的经营过程到计算机可处理的形式化定义的转化， 所得到的定义通常可称为过程模型、过程模板、过程元数据或过程定义。因此，在工作流管 理系统建立阶段主要完成过程建模工作。在工作流管理联盟定义的工作流管理系统中，将过 程建模得到的结果统称为过程定义。 工作流模型是对工作流的抽象表示，也就是对经营过程的抽象表示。工作流模型应该完 整地提出支持工作流定义的概念，为建模用户提供工作流定义所需要的组件或元素理想 的工作流模型能够清楚地定义任意情况下的工作流，能够适应用户在建模过程中所提出的 6 第二章工作流技术简介 各种要求。 2 2 2 工作流模型中的控制结构 b 旧吣 沪 顺宇 蚴与分叉 弋) 炉 ( c ) 黜 石b ( d ) 鼢叉( e ) 刺 循环 图2 1 工作流模型中的控制结构 2 2 3 工作流模型的表示 工作流管理联盟定义了工作 流执行的6 种控制结构它们分别 为：顺序( s e q u e n c e ) 、与分叉 ( a n d - s p l i t ) 、与合并( a n d - j o i n ) 、 或分叉( x o r - s p l i 0 、或合并 ( x o r - j o i n ) 以及循环0 0 0 p ) 。图2 1 中给出了上述控制结构在工作流 模型中的表示方式。 本小节举例阐明如何运用上述控制结构表示工作流模型。 例1 为了生产输送带，首先需熔解原料，然后对被熔解的原料进行聚合( 低分子专高 分子) ，聚合完成后对聚合生成物进行检验，如果不合格则解聚( 高分子专低分子) 后重新 聚合直到检验合格，然后将纺粗丝和纺细丝的生产任务分派到相应的生产线，当上述纺丝任 务都完成后进行最后的输送带编织工作。整个输送带的生产过程可表示为如图2 2 所示的工 作流模型。 2 3 工作流执行控制 图2 2 工作流模型的表示 带 在完成了过程建模的定义后，所产生的工作流模型由工作流执行服务软件进行实例创建 并控制其执行过程。工作流执行服务对使用工作流模型描述的过程进行初始化、调度和监控 过程中的每个活动的执行，在需要人工介入的场合完成计算机应用软件与操作人员的交互 这样，工作流执行服务实现了在模型中定义的经营过程与现实世界中实际过程之间的连接。 工作流执行服务中实现这个连接的核心功能是工作流管理软件，工作流管理软件又称工作流 引擎。 工作流执行服务是工作流管理系统的核心。实际上它是企业经营过程的任务调度器，在 某种程度上还是企业资源分配器。在采用工作流管理系统支持经营过程运行的企业中，工作 7 东南大学硕士学位论文 流执行服务可以看成是企业的业务操作系统。企业的业务过程在它的管理、监控和调度下运 行，因此，工作流执行服务系统的性能和可靠性就直接决定了企业经营过程的运行效率和安 全性。工作流执行服务由一个或多个工作流引擎( w o r k f l o we n g i n e ) 组成，它提供了过程实例 执行的运行环境，主要完成以下功能“”： 1 ) 实例化及执行过程模型：解释企业经营过程的过程定义，根据过程执行需要的初始条 件和执行参数生成过程实例，运行过程实例并管理其运行过程。 2 ) 为过程和活动的执行进行导航：根据过程定义和工作流相关数据，为过程实例的运行 进行导航，如根据过程的进入和推出的条件启动和终止一个过程实例。 3 ) 与外部资源交互完成各项活动：工作流执行服务通过两种途径完成与外部资源和用户 的交互：客户应用接口和直接调用应用接口方式。 4 ) 维护工作流控制数据和工作流相关数据：工作流在执行过程中要维护不同过程和活动 实例的内部状态信息，以及用于协调和恢复的各种检查数据和恢复重起信息，还包括用户 传送的必要相关数据。 2 4 工作流管理系统中的人机交互 在工作流管理系统的运作过程中。人和应用是完成整个业务过程的主体。工作流定义工 具、工作流执行服务和任务表管理器都是为完成业务过程和支持人员工作提供的运行环境和 工具。具体说来，在整个工作流执行中，不同的操作人员需要完成的工作大约可分为以下几 种： 1 ) 模型定义：刨建、修改和发布企业的业务过程模型，一般是企业的业务管理部门( 如 企管处) 的人员按照企业业务流程完成。 2 ) 人机交互：按照工作流任务管理器提供的任务项，完成具体的业务处理工作( 如填表 格、启动一个应用来计算生产计划、查询库存情况等) ，这个工作由企业的各个业务部门的 人员来完成。 3 ) 系统运行状态监控：检查、监视系统的执行情况，对于系统中出现的意外情况进行紧 急处理，如终止、恢复某个过程实例的执行，改变某个活动的状态以便整个系统能够继续执 行等。这个工作由具有较高职务的系统管理入员来完成。 2 5 本章小结 本章介绍了工作流的基本概念和定义，并对其包含的过程建模、工作流执行控制和工作 流管理系统中的人机交互等部分做了简要的说明，为将在第四、五章中讨论的算法提供了必 备的理论基础。 第三章时间约束网( t c n ) 第三章时间约束网( t c n ) 1 9 9 1 年，r i n ad e c h t e r 1 等在 a r t i f i c i a li n t e l l i g e n c e 上发表论文“t e m p o r a lc o n s t r a i n t n e t w o r k s ”，基于约束网理论1 提出了时间约束网( t c n ) ，用于分析连续型时间变量间基于网 状结构的约束满足问题。本章在简要介绍时间约束网基本理论的同时，提出并深入分析了时 间约束网的“部分交”和“拆分”运算，扩充了时间约束网的运算理论。为将在第四、五章 中给出的算法提供了理论依据。 3 1 引言 本节通过介绍一个时间约束满足问题( at e m p o r a lc o n s t r m n ts a t i s f a c t i o i lp r o b l e m ，t c s p ) 的 例子“引出时间约束网( t e m p o r a lc o n s t r a i n t n e t w o r k s ，t c n ) 。 例3 1 约翰开车去上班需要3 0 到4 0 分钟，若乘坐公交车则至少需要6 0 分钟。佛瑞德 开车去上班需要2 0 到3 0 分钟，坐出租车则需要4 0 至5 0 分钟。今天。约翰在7 ：1 0 至7 ：2 0 之间离开家，而佛瑞德在8 ：0 0 至8 ：1 0 之间到达上班地点。并且，我们知道约翰在佛瑞德离 开家后1 0 至2 0 分钟内到达上班地点。基于上述信息，我们希望能够回答这样一些问题：“故 事中所给出的信息是否一致? ”，“是否存在这样的可能，约翰乘坐公交车而佛瑞德乘坐出租 车? ”，“佛瑞德可能在何时离开家? ”。 设p 1 和如分别表示约翰和佛瑞德上班过程的时间延迟，x 1 和x 2 分别表示约翰离开家 和到达上班地点的时间点。x 3 和) ( 4 分别表示佛瑞德离开家和到达上班地点的时间点。由此， p 1 和p 2 可分别表示为区间【x l ，x 2 】和【x “】( 4 】。设时间点x o - - 7 ：0 0 。时间单位为分钟，上面例 子中给出的时间约束可分别表示为：“3 0 x 2 一x 1 4 0 或x 2 一x 1 6 0 ”，“2 0 ) ( 4 一x 3 3 0 或4 0 x 4 - - x 3 5 0 ”，“1 0 x l x o 2 0 ”，“6 0 x 4 一x o 7 0 ”，“1 0 x 2 - - x 3 2 0 ”。 时间约束网( t c n ) 是一个基于网状结构的数学模型。运用这个数学模型，可以表示和分 析类似于上例中提出的那些时间约束问题。 3 2 时间约束满足问题( t c s p ) 的约束网模型 一个时间约束满足问题包含一组连续型时间变量x i ，x 。，以及关于上述变量的一组 时间约束。其中，每个变量表示一个时间点，每个约束可表示为一组时间区间： i l i 。) = ( 【a 1 ，b l 】，b n 】) 。变量x l 的一元约束t i 可表示为：( a l x l b 1 ) v v k b n ) 变 量x 和x j 之间时间距离的二元约束t l j 可表示为：( a 1 x j x t b 1 ) v v ( a n x j x l b n ) 假设所有的约束都以上述形式给出。 一个时间约束网t 由一组时间变量 x 1 ，x 。和一组关于这些变量的一元 或二元时闻约束组成。一个时间约束网 可以表示为一个带权有向图。图中，点 表示时间变量，有向边 表示时间 变量x i 和x 。之间的二元时间约束t i i ( 用 区间集标示) 。设定一个特殊的时问点 ) ( 0 表示最早时间点( b e g i n n i n go ft h e w o r l d ) ，这样我们就可以将所有的一元 时间约束t l 转化为二元时间约束t m ，用 图3 1 例3 1 中时间约束的时间约束网表示 9 边 x o ，x 表示。 可用一个时间约束网表示一个时间约束满足问题中的所有时间约束。设最早时间点 x o - 7 ：0 0 ，时间单位为分钟，则例3 1 中时间约束的时间约束网表示如图3 1 所示。 下面给出时间约束网( t c n ) 的一些基本定义： 定义3 1 一个多元组x = ( x l ，蛐被称为时间约束网n 的一个解，当且仅当 x l = 。l 。 x 。= ) 【n ) 满足n 中所有时间约束。 定义3 2 一个数值v 是时间约束网n 中变量x i 的一个可能值，当且仅当n 存在一个解， 其中x l = v 。 定义3 3 称一个变量所有可能值的集合为该变量的最小域( t i 碡m i n i m a ld o m a i n ) 。 3 3 简单时间问题( s t p ) 约束网的表示方法 定义3 4 一个给定的时间约束满足问题( t c s p ) 被称为一个简单时间问题bs i m p l e t e m p o r a lp r o b l e m ，s t p ) ，当且仅当其所含任意两变量间的时间约束可以用一个区间表示。 如上所述，一个二元时间约束可表示为一对( 两个) 线性不等式，一个一元时间约束可等 价转化为一个二元时间约束。因此，一个s t p 中含有的时间约束等价与一组线性不等式， 并可采用图论中的晟短路径算法求解之“1 。本论文称s t p 的约束网模型为s t p 时间约束网。 s t p 时间约束网的两种表示方法： 图3 2s t p 时间约束网的约束图表示 1 ) 约束图 用一条带权有向边表示一个线性不等 式。如x 。一x l 钆，应表示为一条以x l 为 射出点，以x 为射入点，权重为a q 的有向 边 。若去除约束：x 2 一x l 6 0 及 2 0 x 4 一x 3 3 0 ，则例3 1 中的t c s p 成 为了一个s t p 。其时间约束网的约束图表 示如图3 2 所示。 约束图比较直观，易于理解，但其无 法反映s t p 中隐含的时间约束，不便于计 算。 2 ) 约束矩阵 表3 】为上述s t p 时间约束网的矩阵表示。其中 ) ( “x 2 】爿o 表示x 2 一x i 4 0 。 显然，当时间约束网中不存在任何约束时，其相应约束矩阵中的每个元素均为一。 约束矩阵不够直观，但可以全面地反映出s t p 中的时间约束，便于计算。表3 2 是对上 述s t p 时间约束网做最小化运算后的约束矩阵表示，其全面地反映了该s t p 中的时间约束 ( 包括其隐含的约束) 。有关时间约束网的最小化将在下一节中讨论。 表3 1s t p 时间约束网的矩阵表示 表3 2s t p 最小约束网的矩阵表示 x ox 1x 2x 3x 4 x o o2 07 0 x i 1 004 0 x 23 0ol o x 3 2 005 0 x 6 0_ 4 00 x ox lx 2x 3x 4 x o o2 05 03 07 0 x l l o04 02 06 0 x 2 - 4 03 0 o1 03 0 x 3 2 01 02 0o5 0 x 4 - 6 0- 5 02 04 00 1 0 第三章时间约束嗣( t c l o 3 4 时间约束网的基本运算 本节介绍s t p 时间约束网的基本运算。一个t c s p 可以被拆分为若干s t p 分别求解1 3 4 1 时间约束网的最小化 对二元时间约束问的一个偏序关系紧于( t i g h t e r t h a n ) 定义如下： 定义3 5 对于两个给定的二元时间约束t 和s ，称t 紧于s ( t 互s ) ，当且仅当每一对被 t 允许的值同时被s 所允许。 显然，最紧的约束为空约束，记为中。( - 一，一) 为最松弛的( m o s tr e l a x e d ) 约束。 将上述偏序关系推广到时间约束网中，引出最小约束网的概念： 定义3 6 设t 和s 为两个含有相同变量集的时间约束网，称t 紧于s ( t s ) ，当且仅当 对于t s 中任意两个变量i 和j ，满足l s i j o 定义3 7 设t 和s 为两个含有相同变量集的时间约束网，称t 等价于s ( t = s ) ，当且仅 当t 和s 拥有相同的解集。 定义3 8 称所有等价时间约束网中的最紧约束网为最小约束网( m i n i m a ln e t w o r k ) ，其中 所含的约束为最小约束( m i n i m a lc o n s t r a i n t s ) 。 定义3 9 将一个时间约束网等价转化为最小约束网的过程称为对该时间约束网的最小 化。 运用图论中求两点间最短路径的f l o y d w a r s h a l l 算法将s t p 时间约束网t 最小化( 算法 中，t n 为t 的约束矩阵) ： 算法3 1 最小化s t p 时间约束网t 腱用f l o y d - w a r s h a l l 算法将时间约束网t 最小化 n u m t n u m ； a gt 中所舍的时间变量个数赋值给n u m f o r ( i o ；i n u m ；i n f o r 0 = o ；j 剞u m ；j 十卜) f o r ( k = o ；k n u m ；i 【+ + 1 i f ( t n u ，i + t n i ，k 】 m u ，k 】) t h e n m j ，k 】2 姐d ，i + t n i ，k 】； ， 表3 1 中时间约束网经最小化后如表3 2 所示。 3 4 2 时间约束网的一致性判断 对于一个给定时间约束网，一个重要问题是如何确定它的一致性。 定义3 1 0 一个时间约束网被称为是一致的，当且仅当其至少存在一个解。 定理3 1 一个s t p 时间约束网是一致的，当且仅当其相应的约束图中不存在负回路。 判断s t p 时间约束网t 的一致性( 算法中。t n 为t 的最小约束矩阵) ： 算法3 2 判断s t p 时间约束网t 的一致性 n u m - 一t n u m ；将t 中所含的时间变量个数赋值给n u m f o r ( i 5 0 ；i n u m ；i + + 、 东南大学硕士学位论文 i f ( 恤【i ，妇 o ) t l l 哪 返回t 不一致的消息： 返回t 一致的消氪 由上述算法可知，表3 2 所示时间约束网是一致的。 3 4 3 时间约束网的求解 定理3 2 ( 可分解性) 设t 为含有一组变量( x l ) 【l - 及约束集 i l - i 。) 的最小约束 网且具备一致性，若赋值x i i a ，x i = b ，i n 满足约束集 i l ，。i 。 ，则t 含有包含上述赋 值的解。 定理3 2 的证明参见文献【3 2 1 。 根据定理3 2 ，可以对一致性最小约束网中所含的变量按任意次序逐个求解。 例如：对于表3 2 所示最小约束网，设x o - - - 7 ；0 0 ，逐个为 x l ，x 2 ，x 3 ，x 4 中变量赋值如下： ( 1 ) 依据x o 与x l 间的约束，为x l 赋值：x l = 7 ：1 2 ； ( 2 ) 依据) ( 0 、x l 和x 2 之间的约束为x 2 赋值：x 2 = 7 ：4 3 ( 3 ) 依据) ( o 、x 1 、x 2 和x 3 之间的约束，为x 3 赋值：x 3 = 7 ：2 7 ； ( 4 ) 依据约束网中所有约束，给) ( 4 赋值