理论教育 深入探析时间Petri网理论

深入探析时间Petri网理论

时间:2023-06-13 理论教育 版权反馈
【摘要】:为了满足描述事件所经历的需求时间,Ramchandani率先在Petri网中移入了时间,提出了时间或称赋时Petri网。时间Petri不仅能表现出基础Petri网具有的逻辑层次,同时还可以从时间范围或是延迟方面对系统性能进一步分析。当变迁满足触发条件后,时间Petri网包括变迁延迟发生,和变迁瞬间发生但延迟输出托肯两种情况。由于在基本Petri网建模应用中启动了的变迁通常不予跟踪,因此必须设置额外的跟踪机制。若时间为确定时间,则得到确定赋时Petri网,简称为赋时Petri网。

深入探析时间Petri网理论

连锁零售企业供应链中有些功能要求仅涉及系统的逻辑结构与行为,如可达性、有界性、可逆性等;它们与时间无关。而有一些性能要求与时间,即敏捷性要求有关,如及时到货率、生产周期等。由于基本Petri网不包含时间,因此它们不可能建立考虑时间的连锁零售企业供应链中的一些功能节点模型用于系统分析。为了满足描述事件所经历的需求时间,Ramchandani率先在Petri网中移入了时间,提出了时间或称赋时Petri网(Timed PetriNets,TPN)。

时间Petri网在变迁中引入了变迁实施的相对时间因素,对于系统行为和时间属性都可以进行分析,其中可达性(Reachability)和可调度性(Schedulability)可以同时作为系统性能的参考,分析实时并发的复杂系统性能较为有效。时间Petri网是用时间区间来表示活动持续时间的上限和下限的Petri网,它在原型Petri网基础之上定义一个从变迁到时间的映射集,这个时间集可以用有理数、有理数区间或随机数表示。时间Petri不仅能表现出基础Petri网具有的逻辑层次,同时还可以从时间范围或是延迟方面对系统性能进一步分析。当变迁满足触发条件后,时间Petri网包括变迁延迟发生,和变迁瞬间发生但延迟输出托肯两种情况。

基于引入时间的方式不同,时间Petri可以划分为以下三种:

1)用变迁表示经历一定时间的事件或操作,则将时间与变迁关联,得到赋时变迁Petri网(Timed Transition PetriNets,TTPN)。一旦变迁使能,则立即从该变迁的每一输入库所中移去一定数量的token,但是变迁要延迟一定时间后再激发,并在输出库所中放入一定数量的token。

2)用库所表示经历一定时间的事件或操作,则将时间与库所关联,得到赋时库所Petri网(Timed Place PetriNets,TPPN)。变迁一旦使能就立即激发,从该变迁的每一个输入库所中移去一定数量的token,并在输出库所中放入一定数量的token,但是这些token只有延迟一定后才可使用。只有可使用的token才能够使变迁使能。

3)若用从变迁到库所的输出弧表示经历一定时间的生产、运输过程或配送过程,则将时间与输出弧关联。使能的变迁立即激发,但输出token要延迟一定时间后再达到输出库所中。

赋时变迁的时间Petri定义:一个五元组Petri网系统∑=(PTFIM0)为一个时间Petri网系统,其充分必要条件如下:

1)PN=(PTF)为有向网,称为∑的基网。(www.daowen.com)

2)ITR0×(R0∪{∞}),变迁集上的I为时间区间函数,R0表示非负实数集。

3)对∀tT,若It)=[,β],若当变迁t在标识M发生权时,为最短变迁触发等待时间≥0;β为最长变迁触发等待时间β≤∂。

4)原型Petri网使用的一些分析方法也可用分析时间Petri网,但必须加上对时间集的考察。

在TTPN中,同时启动多个变迁的激发表示不同时进行的操作,因此必须跟踪与每一变迁关联的时延从而刷新系统的表示。由于在基本Petri网建模应用中启动了的变迁通常不予跟踪,因此必须设置额外的跟踪机制。而且,在任何时刻都存在着标识的不确定性,这是由于启动了的变迁已从其输入库所中移走了托肯,而在变迁的时延结束前token又不能到达输出库所。对于TPPN,时间与库所关联,同时标识的库所表示操作的同时进行。在任何时刻,都不存在表示的不确定性。将时间与弧关联的方法定义为赋时彩色Petri网(Timed Colored Petri Nets,TCPN),本书不予介绍,感兴趣的读者可以依照关键字去查阅相关文献资料。

若时间为确定时间,则得到确定赋时Petri网(Deterministic Timed Petri Nets,DTPN),简称为赋时Petri网(TPN)。若在TTPN中,与变迁关联的时间为随机的(服从一定的概率分布),则得到的随机Petri网(Stochastic Petri Nets,SPN);若部分变迁的时间为随机的,部分变迁为即时变迁,即所关联的时间为0,则得到广义随机Petri网(Generated Petri Nets,GPN)。

马小颖等(2003)讨论了基于时间Petri网的供应链、企业之间工作流的运作效率问题,主要研究了供应链的时间Petri网建模及分析方法,提出了原有时间Petri网可达树算法应用于资源调度问题中的不足之处,并改进了原有算法。通过对供应链上资源的优化利用,可以实现对电子商务、协作商务及虚拟企业的有效管理。汪亚男等(2005)提出将赋时概念与着色概念相结合,赋时着色Petri网(TCPN)在着色Petri网(CPN)基础上引入时间概念,更适于复杂系统建模仿真。其库所赋时实施规则同CPN,变迁赋时实施规则将令牌移入变迁的输出库所。基于TCPN优先权服务排队系统,用CPN的元语言实现优先权排队,由于时间引入,可真实模拟顾客到达时间和服务台服务时间。刘振峰等(2006)讨论了供应链网络中如何选择优化路径的问题,提出采用时间Petri网对供应链网络关键路径建模的方法。此方法根据顾客需要货物的情况,有条件地选取供应链网络图中可跨越活动和可替换分支,将网络图分别描述成Ebs图和Ewf图,结合时间Petri网的可达算法,求得Ebs和Ewf的关键路径.通过基本供应链的分析,得到网络的优化路径。周涛等(2012)为了使当前供应链协同管理货物流程面临的时间效率得以提高,提出了一种将网格技术和供应链协同管理相结合的货物流程触发时间求解方式。在该求解方式中,为获得供应链货物流程的触发时间值,利用基于时间Petri网的可达性分析算法模型进行仿真计算,以在从订货、发货到收货的流程中,得到每个流程相对应的最早、最晚触发时间值,进而通过在网格环境下改善后的流程触发时间与相应的传统供应链流程触发时间值进行对比,明显地减少了时间上的浪费,提高了货物流程的时间效率,体现了将网格技术应用于供应链协同管理的优势。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈