协同设计中基于混合Petri网的云工作流表示模型

焦合军， 张 璟， 李军怀， 施进发， 李 建

1.西安理工大学计算机科学与工程学院，西安710048

2.郑州航空工业管理学院管理科学与工程学院，郑州450015

3.河南工程学院计算机学院，郑州451191

4.西安理工大学机械与精密仪器工程学院，西安710048

工作流是多个参与者利用预定义的规则实现预期业务目标的过程.从云计算服务提供者的角度看，工作流提供了任务的自动调度、资源的优化和管理，从而优化云计算的运行服务.云工作流是工作流管理系统(workf low management system,WfMS)在云环境下的一种新的应用模式，就用户而言，云工作流能提供对复杂应用的抽象定义、灵活配置和自动化运行；就云服务提供商而言，云工作流能提供任务的自动调度、资源的管理和优化.云工作流的研究与应用正是在这种供求双方的双重推动下产生并发展起来的.

Petri网模型是一个基于图的数学形式化描述模型，可以描述并发系统.Petri网可以动态地表现一个系统，对活动的即时监控以及冲突和同步现象的描述非常有效，特别是在图形表达的直观性和易于编程方面优势明显，适合云工作流的建模需求.目前关于协同设计的工作流研究很多，文献[1]以专家系统的推论引擎作为工作流程管理系统的推进机制，提出了一种支持协同产品设计的以规则为基础的工作流管理系统模型架构；文献[2]对云制造环境下协同工作流采用状态机建模，构造一种基于分层有限状态自动机(hierarchical f inite state machine,HFSM)的协同工作流控制模型；文献[3]提出了一种基于代理的云工作流执行方案，定义了规范的模拟云资源部署的方法.虽然上述研究都注意到模型的复杂性,在某个方面对工作流程进行分解，但并不能充分表达产品协同设计工作流模型的特点.本文在前人的研究成果基础上，基于有色Petri网并结合定时约束和组合性，建立了一种在空间上三维分布的协同设计工作流模型，然后进行定量分析、评估以及优化，使创建的云工作流规范化、常态化.

1 产品协同设计云工作流建模分析

产品协同设计在业务逻辑关系和数据结构上体现出了自身的复杂性，目前协同设计不再局限于车间和组织内，更多的是跨地域、跨行业和跨组织的，这又体现出了执行环境的复杂性.云工作流技术是实现协同设计流程建模、流程管理以及流程自动化的核心技术，如果要高效地执行这些协同设计流程，就需要工作流技术的支持.

从建模的角度来看，设计人员必须相互协作和支持，减少摩擦和冲突，利用异构资源和分布式技术完成工作流.在云计算环境下，传统模式的工作流不能很好地满足云计算模式需求[4]，具体表现如下：

1)多用户并发性：在CSCW中云工作流的执行涉及多个用户，其任务单元可以在一定约束条件下并发运行，此时要充分利用协同机制来避免资源争用和死锁的发生.

2)可伸缩性：云工作流可实现底层计算资源自配置，即根据执行情况增加或减少可用节点数目，在保证任务调度的前提下控制成本.服务的底层资源可以根据业务需求实时伸缩，达到资源的有效利用.

3)可协同性：云工作流执行时，每个用户必须保持协同，这样才能保证各个项目分解的任务能有序执行，通过既相互独立又相互配合的多个设计团队或组织可以协同实现.一般的工作流虽然可以满足项目管理的部分特性，但是任务的定时约束不能很好地描述出来.定时约束描述序列任务之间的时间约束关系，一个项目由多个任务[s1,s2,···,sn]构成，每个任务si都由事件A界定，如任务的开始事件和完成事件，结束一个任务所需要的时间有两部分：执行时间e和等待时间w.任务间的约束是指某一任务的事件AS对另一个子任务的事件AT的时间约束，它来源于任务的时序控制，分别有时间上限约束u(AS,AT)和时间下限约束l(AS,AT).如果事件AS的结束事件发生在t0时刻，那么事件AT的开始事件发生在[t0+l,t0+u].

4)动态性：考虑到负载均衡，工作流的组成单元和行为控制可以在运行时动态调整.

5)组合性：云计算环境下的产品设计过程由概念设计、方案设计、技术设计构成.由于产品设计比较复杂，单一的组织或团队不能完成，这就需要分工完成，让不同的组织或团队承担不同的设计任务，体现了云工作流的组合性.

综合以上云工作流建模分析可以看出，云工作流不仅仅是传统工作流技术在云计算环境中的应用，作为新型的先进设计模式，它必须具有并发、敏捷、组合和全方位的典型特征，要求有更灵活、更高效以及多层次的云工作流模型，以实现云环境下的协同工作流管理.

2 某系列汽车传动系协同设计云工作流建模

2.1 混合Petri网

传统的Petri网是一个双重有向图，可以描述异步且并发的计算机系统模型，具有模拟性、流动性和同步并发性.基于传统Petri网的模型在过程描述中应用广泛，但大多数侧重模拟控制流，对于可伸缩性、协同性的云工作流描述能力有限，无法表示数据的传递方式以及类型，对于角色和数据的表达也很缺乏.

由于传统Petri网的局限性，本文提出了将颜色、定时约束、组合进行扩展的混合Petri网(hybrid Petri nets)作为云工作流建模和分析的有效工具.颜色说明事物的属性以区分不同的令牌(token)，为了描述数据流和任务，将各类数据和任务映射为令牌类型.令牌类型的多样性使云工作流受关注的不仅仅是令牌的数目，连接库所和变迁的有向弧也可以进行相应的扩展.令牌的值需要设置前置条件，变迁只能在其输入库所中至少有一个标记而且满足前置条件时才能就绪.这样在描述非常复杂的协同设计过程时,建模会产生一个无所不包的大网.因此，考虑将基本Petri网的五元组在面向云工作流的数据和任务方面进行相应扩充.

混合Petri网中的令牌可以带有数据值的含义，即颜色类.该数据值可以是任意复杂类型的数据，对于某一个特定的令牌来说，它包含的所有颜色被称为库所的颜色集.一个库所上可能包含两个或两个以上不同数据值的令牌，即为多重集.变迁用来描述任务或动作，其输入弧表示变迁将从相应的库所移走令牌，输出弧表示变迁将增加令牌到相应的库所，即∀t∈T，∀pin∈Pin，变迁h的执行需要输入pin，当且仅当pin⊆·t；∀t∈T，pout∈Pout，变迁t的执行产生输出pout当且仅当pout⊆t·.

2.2 基于HPN的云工作流建模

HPSim仿真软件具有方便的图形用户界面，可以对HPN网模型进行单步或连续的模拟运行.本文采用HPSim对某系列汽车底盘传动系云工作流模型进行建模仿真.

2.2.1 传动系云工作流模型

为在HPSim下对某系列汽车协同设计工作流模型建立的传动系模型如图1所示.在Begin库所中含有3个令牌，分别定义一个值，例如第2个令牌的值定义包含文档号、运行环境、状态及内容.SF表示设计分解，分解为总体设计ZS和详细设计XXS.之后ZS和XXS并行进行，在下一个库所之前如果延迟在时间上限约束tu(XXS/ZY,XCG)和时间下限约束tl(XXS/ZY,XCG)之间，系统运行正常；如果计时在时间上限约束tu(XXS/ZY,XCG)和时间下限约束tl(XXS/ZY,XCG)之外，系统会产生报警信号.XT0和XT表示协同设计，云工作流Cloud W负责管理和分配虚拟资源，对于详细设计还需要活动变迁GT和调度的资源库所ZY，接着将方案设计信息分别授权给初始详细设计XCG和初始总体设计ZCG.评审人员ZJ在此基础上可进一步进行评估，不合格的通过重新设计变迁T12从头开始.任务CS1、CS2、CS3分别完成传动系不同部件的验收工作，考虑到提高资源的利用效率，建模时采用了并行处理.因为它们是相互独立的，所以可以并行执行，这样可以在很大程度上缩短完成时间.对于设计结果需要修改的情况，分别发送给维修人员组合WHZ1、WHZ2和WHZ3，经过验收和维护WH，得到最终的CAPP结果，Re为下一次设计变迁，通过它可以进行其他零部件的协同设计.

图1 某系列汽车传动系混合Petri模型Figur e 1 Hybrid Petri model about a certain type of automobile power-transmission system

2.2.2 传动轴协同模型

传动轴是汽车传动系中传递动力的重要部件.本文将设计任务SR分解为轴管设计AeTB、伸缩套设计SJS和万向节设计Cp TJ，设计完成后分别发送给设计校验JyFF，之后再审核CCSH，经过延时完成后，本次的输入、输出库所对应于图1中的XT替代变迁.具体模型见图2，SR代表任务开始，RW1、RW2、PRW3为分解的部分任务，JyY1、JyY2、JyY3表示校验员，P7为审核员，XXS1、XXS2、XXS3为协同完成的部分结果.

图2 传动轴设计模型Figur e 2 Shaft design model

2.2.3 半轴协同模型

全浮式半轴的任务相对简单一些，如图3所示.继续将其分解为半轴AxSH设计和半轴套管ASSL设计，之后经过内部装配协商ICoN和热处理工艺设计THP，在一定的定时约束完成全浮式半轴的设计.装配设计和后续的验收维护都可以根据实际的任务和人员分配情况进行建模，从而完成整个传动系的协同设计过程模型.其中，SS、SF1、SF3、ZPY1、ZPY2、P5、P6均为下一个活动变迁的执行库所.

图3 半轴设计模型Figure 3 Half shaft design model

2.3 传动系性能指标定量描述

为了定量描述系统的性能，可以利用马尔科夫过程对随机Petri网进行定量分析，每一个变迁关联一个实施速率，每个实施速率λi服从一定的概率分布，得到的模型就是随机Petri网[5].一个SPN同构于一个连续时间马尔科夫链(Markov chain,MC)[6]，如图4所示.λi可以表示成变迁实施延时的倒数.在一个连续时间随机Petri网中，变迁的实施存在时间延时，这个延时可以看成是一个服从于负指数分布的连续随机变量.对任意一个随机Petri网，利用式(1)可以得到转移矩阵Q=[qij]n×n

图4 同构的马尔科夫链Figure 4 Homogeneous Markov chain

设MC中n个状态的稳定状态概率是一个行向量X={x1,x2,···,xn}，则根据马尔科夫链可得

求解式(2)可以得到每个可达标识稳定概率P[Mi]=xi(n≥xi≥1).

稳态下每个库所中所包含的标记数量的概率为标记概率密度，对∀s∈S，∀i∈N，令P[M(s)=i]表示位置s中包含i个标记的概率，则可从标识的稳定概率求得位置s的标记概率密度函数

式中，Mj∈[M0且Mj=i.

变迁的利用率是使变迁可实施的所有标识的稳定概率之和.设U(t)为∀h∈T的利用率，使得h为可实施的所有标识的稳定状态之和

式中，E为使h可实施的所有可达标识集合.

3 模型性能分析

各变迁的时间变量体现的是输入库所从可实施到实施的时间延时，该变量服从负指数分布.本文结合定时约束，设定给出变迁SF、XT0、GT、XT、JL、T12、BM、CS1、CS2、CS3、WH、Re的平均发生时延为t1、t2、t3、t4、t5、t6、t7、t8、t9、t10、t11、t12，如表1所示.由此可以得到各个变迁的平均发生率，即每个平均发生时延的倒数，分别表示为λ1、λ2、λ3、λ4、λ5、λ6、λ7、λ8、λ9、λ10、λ11、λ12，根据方程组可以求出各个状态标识的稳态概率，如表2所示.根据式(3)计算各库所标记概率密度，从库所概率密度的数据中可以看出，库所XXS、ZCG及ZS的概率较大，于是可将上述业务单元作为进一步优化的重点.

表1 变迁发生时延Table 1 Time delay of transitions

表2 各状态标识的稳态概率Table 2 Steady-state probability of status identif ication

由式(4)可计算变迁利用率，得到的计算结果见表3.变迁的标记流速是指单位时间内流入该变迁y的后置位置s的平均标记数，其计算公式为

式中，λ为变迁y的平均实施速率.表4给出了变迁标记流速的计算结果.

表3 变迁利用率计算结果Table 3 Transitions utilization

表4 变迁标记流速计算结果Table 4 Tag velocity of transitions

4 云工作流模型评价及优化

在HPSim中根据初始状态对云工作流模型进行仿真，从图5中可以清楚地看到令牌从初始状态顺利到达最终状态[7-8]，这说明建立的模型是可达的.

根据第3节性能分析的结果可以看出，库所XXS、ZCG、ZY和ZS的概率密度较大，即协同设计的详细设计、总体设计、初始总体设计及云资源库所等任务的调度环节最容易产生信息的堆积.因此，在实际协同设计中，可将上述任务单元作为优化的重点；从变迁利用率来看，变迁XT0、XT、SF和JL的触发情况对于整个协同设计有着非常重要的影响，会直接影响到专家评估及后面的编码和验收任务执行概率，直至最终影响整个协同设计业务流程的工作效率.该Petri网模型可以进一步从业务冲突和模型分解两方面入手进行优化[9-11].

在基于定时约束Petri网的产品协同设计模型中，当两个或多个业务产生自由选择的设计结果时，其中一个变迁的实施阻止另一个变迁的发生就会导致冲突.在对某系列汽车传动系产品协同设计模型的仿真过程中，在业务ZJ处有发生冲突的潜在性，也就是说协同设计模型需要考虑专家评估情况.从整个过程来看，由于协同设计是个复杂的工程，错误的设计结果会导致部分业务的迭代或重复设计，这也是可以理解的.为了避免模型中的冲突，让每一个业务都能找到适合自己的路径到达终点，需要将变迁T12细化到图5阴影部分的每个变迁中.

图5 HPSim运行结果Figure 5 Run results of HPSim

在实际的协同设计过程中，可以将业务集中的或相似的划分为一个子系统，从而使设计过程有条理.在Petri模型中，将图5的阴影部分作为一个子系统，由平均标记流速计算公式得到，R(SF)=R(SF,XXS)+R(SF,ZS)，这样流入子系统的平均标记流速为R(SF)，其值在表4中有体现.比较所有变迁的标记流速不难发现，整个协同设计过程中大部分流速快的变迁都发生在这个子系统内，尤其是GT变迁，这就要求充分调动总体和详细设计可调动的闲置资源，将其放在云平台中供工作流调度，从而降低库所XXS、ZCG、ZY和ZS的概率密度.另外，在变迁XT0和XT之间减少调度时间，必要时可以通过增减变迁的方法来缓解子系统的拥堵.

5 结语

本文提出了一种基于定时约束Petri网的协同设计云工作流建模方法.首先从组合性、并发性和协同性等五方面分析产品协同设计过程的特点；然后建立了一个在空间上以定时约束、有色和组合三维分布的多层次模型.本文通过库所概率密度、变迁利用率和变迁标记流速，对协同设计各流程流转、工作效率等进行分析，并从业务冲突及模型分解等方面验证模型的可达性，从而进行了优化.

[1]王浩，武凌.基于专家系统的协同设计工作流管理系统研究[J].计算机工程与科学，2012,34(12):183-188.

WANGHao,WU Ling.Research of collaborative design workf low management system based on expert system[J].Computer Engineering&Science,2012,34(12):183-188.(in Chinese)

[2]谭貌，段斌，彭邦伦，张建和.云制造环境下协同工作流控制模型研究[J].计算机工程，2012,24(3):21-26.

TANMao,DUANBin,PENGBanglun,ZHANGJianhe.Research on control model of collaborative workf low in cloud manufacturing environment[J].Computer Engineering,2012,24(3):21-26.(in Chinese)

[3]GUTIERREZ-GARCIA J O,MIM K W.Agengt-based cloud workf low execution[J].Integrated Computer-Aided Engineering,2012,(19):39-56.

[4]柴学智，曹健.面向云计算的工作流技术[J].小型微型计算机系统，2012,33(1):90-95.

CHAI Xuezhi,CAO Jian.Cloud computing oriented workf low technology[J].Journal of Chinese Computer Systems,2012,33(1):90-95.(in Chinese)

[5]潘隆涛，涂海宁.基于随机Petri网的连续型制造系统建模与性能分析[J].组合机床与自动化加工技术，2013,(9):25-27.

PANLongtao,TUHaining.Modeling and analysis on continuous manufacture system based on stochastic Petri net[J].Modular Machine Tool&Automatic Manufacturing Technique,2013(9):25-27.(in Chinese)

[6]林闯．随机Petri网和系统性能评价[M].第2版.北京：清华大学出版社，2005．

[7]TOLOSANA-CALASANZ R,JOSÉÁB,CONGDUC P,OMERF R.Enforcing QoSin scientif ic workf low systems enacted over cloud infrastructures[J].Journal of Computer and System Sciences,2012,78(4):1300-1315.

[8]LIU Xiao,YANG Yun,YUAN Dong,ZHANG Gaofeng,LIWenhao,CAODahai.A generic QoSframework for cloud workf low systems[C]//2011 IEEE Ninth International Conference on Dependable,Autonomic and Secure Computing,2011:713-720.

[9]JENS-SÖNKE V,GIDEON J,EwA D,MATS R,BERRIMAN G B.Experiences using cloud computing for a scientif ic workf low application[C]//Science Cloud'11 Proceedings of the 2nd international Workshop on Scientif ic Cloud Computing,2011:15-24.

[10]WU Zhangjun,LIU Xiao,NI Zhiwei,YUAN Dong,YANG Yun.A market-oriented hierarchical scheduling strategy in cloud workf low systems[J].Journal of Supercomputing,2013,63(1):256-293.

[11]SOFIANE B,THOMAS W.Cloud transition: integrating cloud calls into workf low petri nets[C]//Proceeding of Petri Nets and Software Engineering,2012:215-216.