协同虚拟样机的工作流时间管理研究＊

田丰春

（南京晓庄学院数学与信息技术学院，江苏 南京 211171）

1 引言

协同虚拟样机技术是在分布式的环境下，多领域专家协同建立和应用虚拟样机的方法和技术。它是一种基于一体化产品和过程开发IPPD（Integrated Product and Process Development）思想的新的设计／开发范例，其核心是IPT（Integrated Product Team）的实施，能够实现分布在不同地点、不同部门的IPPD 小组成员围绕逼真的虚拟样机，从不同角度、不同需求出发，对虚拟样机进行测试、仿真和评价，从而改进和完善其设计、缩短产品的开发时间［1］。为了提高虚拟样机设计效率，支持协同设计的工作流管理成为了协同虚拟样机支撑平台的重要组成部分。

工作流是一类能够完全或者自动执行的经营过程，根据一系列过程规则、文档、信息或任务在不同的执行者之间进行传递与执行。利用工作流技术可以描述和控制一个分布异地的多个集成化产品开发团队的动态协同设计过程，实现对虚拟样机协同设计过程全生命周期的管理，从而提高协同虚拟样机的工作效率。

本文根据协同虚拟样机对管理功能的需求，介绍了协同虚拟样机中的工作流管理的各组成部分，并重点对工作流时间管理进行了研究。

2 协同虚拟样机中的工作流管理

协同虚拟样机工程涉及多学科设计的集成技术，由各种应用、底层支撑技术和标准组成，支持虚拟样机的协同设计、建模和仿真。协同虚拟样机系统主要由协同设计支撑平台、模型库（构成产品、环境的各类模型）、虚拟样机VP（Virtual Prototype）引擎和VR（Virtual Reality）／可视化环境四大部分组成。协同设计支撑平台提供一个协同设计环境，它包括集成平台／框架以及团队／组织管理、工作流管理、虚拟产品管理、项目管理等工具［2］。

工作流属于计算机支持的协同工作的一部分，工作流管理平台是协同虚拟样机支撑平台的重要组成部分，主要包括工作流定义、工作流引擎、工作流监控和客户端工具等组成部分，用以完成对工程项目任务过程的描述与运行管理功能。

工作流管理系统用于定义、创建和管理工作流的执行。它通过建模工具创建流程，流程的创建首先需要对项目进行分解，这包括面向参与协同开发过程的某一协作群体的粗粒度划分和面向具体开发人员的细粒度划分。依据项目具体工作内容和人员要求，将项目分解为不同的任务和活动组合，组合中含有依赖、包含等各种逻辑关系。模型结构化分析工具对创建的流程进行解析和语法检查，然后将解析后的数据存入流程数据库。工作流引擎对流程的运转进行控制，处理各种工作流数据和信息，调用外部应用程序管理员通过监控工具对工作流运行过程进行监视和管理。用户通过消息管理接收消息并通过工作流客户端获得自己的任务，同时依靠信息交互工具实现用户间的协同设计开发。

3 协同虚拟样机中的工作流时间管理

工作流时间管理是协同虚拟样机工作流管理的关键部分。在工作流中，活动结束的最迟期限称为截止期限，若活动实例的结束时间超过了这个最迟期限，则称该活动违反了此截止期限的时间约束［3］。违反工作流的截止期限会产生额外的负担，增加业务成本并且浪费系统的资源，并导致严重的性能损失。工作流时间管理主要研究工作流执行的时间维计划，估计不同的活动执行延迟、避免活动／过程违反时间约束以及时间违反的异常处理，以提高过程管理的效率。

3.1 时间约束验证

实现工作流的可靠执行、成功实施工作流管理需要对工作流模型进行合理性验证与分析。常见的验证方法有静态验证和动态验证。静态验证是一种事前的验证方法，基于所建立的工作流模型结构，检查过程模型与时间约束的可能冲突，修改或松弛不一致的时间约束，为工作流设计者合理设定时间约束与有效建模提供帮助。动态验证是在实例执行过程中，基于实例的当前状态、绝对时间与关键路径，通过计算关键路径的执行延迟估算尚未调度活动的预期执行时间，判断时序一致性。随着实例执行进程的推进，即便一致的期限约束也无法保证它在将来的工作流执行中仍然满足。为此，需要对时间约束进行动态或多次验证。

动态的业务流程或不确定的活动执行时间常常破坏工作流执行的截止期限。因此，在运行时动态验证工作流的一致性十分必要。我们可以在实例运行过程中进行时间监控与仿真，监控前序活动的结束时间，重新计算后续活动的完成时间，尽早预测可能的时间违反，以避免时间错误和费用增加。

3.2 关键路径法

本文主要通过确定工作流关键路径的方法来预测可能的时间违反。所谓工作流关键路径指的是从工作流的开始节点到结束节点形成的节点序列中，各节点平均执行时间之和最大的序列。关键路径上的活动称为关键活动［3］。如果关键活动的完工时间推迟，出现时间违反，将导致成本增加。为此，需要对关键路径上的活动加强管理，通过优先安排关键活动所需要的资源或者为关键活动分配额外资源等措施，尽量压缩关键活动的执行时间。

工作流执行过程由任务和条件构成，路由决定了哪些任务需要被执行，以什么次序执行。图1所示是一个包含顺序结构、AND 控制结构、OR 控制结构和LOOP控制结构的网络图例子［4］。在这里我们假设活动的服务器服务时间服从指数分布并且用户的服务需求的到达过程服从泊松分布，因为这种假定本身与现实多数系统实际相符合［5］。因此，我们可以把工作流模型看成M／M／1 排队网，在M／M／1队列中，平均执行时间为W＝1／（μλ），其中μ 是服务率，λ是到达率。

Figure 1 Example of network图1 网络图例子

关键活动的执行时间直接影响着工作流的执行时间，关键路径法是基于工作流控制结构和工作流实例的平均执行时间的。网络图中，除了控制块内部以外，所有顺序控制结构都属于关键路径；如果控制块内部是循环控制结构，则将其等价转换为顺序控制结构；如果控制块内部是AND 或OR 控制结构，则选取控制结构中平均执行时间最长的路径作为子关键路径。经过变换，可以将任何一个工作流模型简化为一个顺序控制结构。因此，整个工作流的关键路径是由各个模型控制块的子关键路径构成的。

为了识别整个工作流的关键路径，需要先求出每个控制块的子关键路径。下面给出四种控制结构的具体变换方法。

（1）顺序结构。

顺序结构中，第i个活动的平均执行时间是Wi＝1／（μi－λ），其中μi是服务器为第i个活动服务时的服务率，λ是到达率。图2所示的顺序结构的平均执行时间是每个活动平均执行时间的总和：

Figure 2 Transformation of a sequence图2 顺序结构的转换

（2）AND 控制结构。

图3 所示是工作流模型的AND 控制结构。设活动1，2，…，n的平均执行时间为随机变量X1，X2，…，Xn，因为第i个活动的平均执行时间就是Wi＝1／（μi－λi），所以Xi的概率密度函数为fXi（t）＝1－e－（μi－λ）t，i＝1，…，n。

设AND控制结构的平均执行时间为随机变量Y，Y 是max（X1，X2，…，Xn），其累计分布函数：

Figure 3 Transformation of an AND control structure图3 AND 控制结构的转换

AND 控制结构的平均执行时间为：

（3）OR 控制结构。

Figure 4 Transformation of an OR control structure图4 OR 控制结构的转换

OR 控制结构的平均执行时间为：

（4）LOOP控制结构。

图5所示是工作流模型的LOOP 控制结构。因为每个活动都被认为是独立的M／M／1 队列系统，我们可以把LOOP 控制结构转化为串行控制结构。因为LOOP控制结构的到达率Λ 是它的原始到达率λ 和它的回馈到达率（1－p）Λ 之和。LOOP控制结构的到达率为Λ＝λ＋（1－p）Λ，从而得到Λ＝λ／p。

Figure 5 Transformation of an LOOP control structure图5 LOOP控制结构的转换

LOOP控制结构的平均执行时间为：

3.3 工作流松弛时间分配方法

经过上述变换，任何一个工作流模型最终都能转换成一个顺序控制结构，从而可确定工作流的关键路径。在给定整个工作流的截止期限后，便可以计算出每个活动的截止期限。工作流的松弛时间是指工作流截止期限与工作流关键路径的平均执行时间之差。已完成活动的松弛时间是指该活动的截止期限与实际执行时间之差。未执行活动的松弛时间是指该活动的截止期限与平均执行时间之差。每个活动的松弛时间越多，工作流最终在指定时间内完成的可能性越大。

活动的实际完成时间与其静态分配的截止期限有满足和不满足两种状态。如果已完成活动呈满足状态，该活动就会将自身剩余的松弛时间按关键路径的平均执行时间的比例分配到该活动的后续活动中，那么每个后续活动分得的松弛时间就会增加；如果已完成活动执行超时，导致无法满足时间约束，呈不满足状态，此时应进入异常处理程序进行时间违反的处理。常见的异常处理方式有选择执行最好条件分支、放弃可忽略活动、选择较短可替换分支、分配额外的资源等。

工作流中，建模和流程刚开始运行时，很难给出某些时间约束的准确状态，不能简单用满足或不满足来描述这些复杂的情况，而异常触发频率较高会导致流程执行细致程度的下降、运行效率的降低和成本的增加。因此，有必要引入一种中间状态，即弱不满足状态，将部分不满足的时间约束转化为中间状态，经过调整，弱不满足状态的时间约束可以转化至可满足状态或者仍为不满足状态，这样可以减少不满足时间约束的数量，降低异常发生频率，提高运行效率。

随着工作流程的运行，每个活动分得的松弛时间是动态变化着的，已完成活动若在分配的时间内完成，它的剩余松弛时间将按关键路径的平均执行时间的比例分配到该活动的后续活动中，使未完成活动具备更多的松弛时间。下一个活动如果也在分配的时间内完成，每个活动完成后的剩余时间又会汇聚到时间约束的松弛时间中。最终，随着工作流的运行，在活动完成及时率较高的情况下，某些原本处于弱不满足状态的时间约束可以达到可满足状态。

已完成活动若在分配的时间内完成，它的剩余松弛时间将按关键路径的平均执行时间的比例分配到该活动的后续活动中。松弛时间分配方法如下：

4 结束语

协同虚拟样机工程中的工作流管理是协同支撑平台的重要组成部分，支持和控制分布异地的多个开发团队的动态协同设计过程，实现对虚拟样机协同设计过程的有效管理。本文重点对工作流时间管理进行了研究，通过对路由结构的分析，采取松弛时间分配方法，调整部分弱不满足时间约束至可满足状态，使更多的工作流实例满足截止期限，降低异常的触发频率，节省了处理开销，提高了运行效率。

［1］Zhu Yao－qin，Wu Hui－zhong，Yang Yong.Research on information integration of collaborative virtual prototype［J］.Computer Simulation，2004，21（12）：136－138.（in Chinese）

［2］Li Bo－hu，Chai X－dong，Xiong Guang－leng，et al.Research and primary practice on virtual prototyping engineering of complex product［J］.Journal of System Simulation，2002，14（3）：336－341.（in Chinese）

［3］Tang Da，Liu Dan－ni.Method for dynamic verification of activity deadlines in timed workflow［J］.Computer Integrated Manufacturing Systems，2004，10（9）：1154－1159.（in Chinese）

［4］Son J H，Kim J H，Kim M H.Deadline allocation in a timeconstrained workflow［J］.International Journal of Cooperative Information Systems，2001，10（4）：509－530.

［5］Tao Ze，Xie Li－yang，Yuan Feng.Study of performance based on time－constrained workflow processing［J］.Machinery Design ＆ Manufacture，2004，10（6）：49－51.（in Chinese）

［6］Liu Li，Mao Fei.Workflow－based project management system for complex software prototyping［J］.Journal of Beijing University of Aeronautics and Astronautics，2007，33（5）：585－589.（in Chinese）

［7］Li Hui－fang，Fan Yu－shun.Overview on managing time in workflow systems［J］.Journal of Software，2002，13（8）：1552－1558.（in Chinese）

［8］Son J H，Kim M H.Improving the performance of time－constrained workflow processing［J］.The International Journal of Systems and Software，2001（58）：211－219.

［9］Li Hui－fang，Feng Fu－jian.Management and dynamic monitoring of deadlines in time－constrained workflows［J］.Transactions of Beijing Institute of Technology，2011，31（8）：937－943.（in Chinese）

附中文参考文献：

［1］朱耀琴，吴慧中，杨勇.协同虚拟样机的信息集成研究［J］.计算机仿真，2004，21（12）：136－138.

［2］李伯虎，柴旭东，熊光楞，等.复杂产品虚拟样机工程的研究与初步实践［J］.系统仿真学报，2002，14（3）：336－341.

［3］唐达，刘丹妮.一种工作流时间截止期限的动态验证方法［J］.计算机集成制造系统，2004，10（9）：1154－1159.

［5］陶泽，谢里阳，袁锋.基于时间约束的工作流进程的性能研究［J］.机械设计与制造，2004，10（6）：49－51.

［6］刘丽，毛菲.基于工作流的复杂系统虚拟样机项目管理系统［J］.北京航空航天大学学报，2007，33（5）：585－589.

［7］李慧芳，范玉顺.工作流系统时间管理［J］.软件学报，2002，13（8）：1552－1558.

［9］李慧芳，冯复剑.时间约束工作流的截止期限管理及其动态监控［J］.北京理工大学学报，2011，31（8）：937－943.