几种满足汇合性质的Petri网子类

证明活的标识S-图、活的标识T-图、有界的冲突无关的Petri网、有界的标识T．图具有汇合性质,讨论共享合成与同步合成操作对Petri网汇合性质的保持性,得出由上述简单的Petri网子类通过共享合成及同步合成得到的复杂的网系统也具有汇合性质。通过一个具有汇合性质的复杂网系统实例验证该结论。     

P/T_网中的同步距离

同步距离既可以对两组事件之间同步程度进行定量分析,也可以刻画系统动态行为,然而Petri中同步距离计算一直存在难题。采用加权观察库所的原理讨论了P/T_网中任意两个变迁子集之间同步距离的计算,并通过本原权函数的定义指出了如何给连接变迁和加权观察库所之间的弧配置一个唯一的权值。为了得到处于同一个公平分支变迁子集之间的同步距离值,需构造一个带权同步观察P/T_系统,通过模拟原网系统的可覆盖树得到带权观察库所的最大和最小tokens,从而求得变迁子集之间的同步距离值,并给出相应算法,给出了求解P/T_网中任意两个变迁子集之间同步距离计算算法。     

混杂Petri网系统中同步距离的确定及同步控制器的设计

目前,对于广义混杂Petri网的变迁公平关系和同步距离都只有极少结论,本文对广义混杂Petri网,给出了两个变迁(组)之间公平关系和同步距离的形式定义,并通过修剪的不变行为状态(invariant behavior,IB)演化图给出确定变迁同步距离的方法,得出了判定变迁公平关系的充要条件,还证明了变迁公平关系、同步距离和修剪的IB演化图之间的联系.本文的方法对简单离散Petri网不仅能得到已有的相关结论,而且推广了同步距离概念适用的范围.最后,以混杂运输控制系统为例,以同步距离为基础设计同步控制器,说明同步距离在实现同步控制结构设计上的有效性.     

Petri网分解的保性条件分析

Petri网的分解技术是用于复杂网系统分析的一种有效手段 .基于库所指标的 Petri网分解方法 ,将一个复杂的网系统分解成结构满足 |· t|≤且 |t· |≤ 1的简单子网 ,通过分解得到的子网与原系统的状态和行为之间存在着一种投影关系 .但是 ,子网本身也增加了一些不必要的状态和行为 (原网系统在子网上的投影只是子网状态和行为的一个子集 ) .本文提出分解过程中的状态保性和行为保性的概念 ,证明了分解过程中行为和状态保性的充要条件 ,基于标识可达图给出了相应的判定算法 ,对复杂系统的 Petri网分析方法提供了更为有效的理论和可行的技术     

单触发Petri网的一个可达性判定方法

可达性判定问题是Petri网理论研究的一个重要课题.已有文献提出通过构造Petri网的可达树或可覆盖树来分析其可达性,但其中无界量ω的引入导致了无界Petri网运行过程中的信息丢失,使其可达性无法得到判定.众所周知,对于有界Petri网,通过构造其可迭性树或可达标识图来判定其可达性是容易的,但对于大量存在的无界Petri网,找到一个能判定其可达性的一般性算法却不太容易.本文给出一个Petri网子类--单触发Petri网,并给出它的一个可达性判定方法.     

Petri网的状态转换图

给出Petri网的状态转换图模型,并作为分析工具,分析Petri网重复引发序列在状态转换图中的表现特点,给出标注路径(回路)与引发序列(重复引发序列)的关系及其判定条件,并给出求基本重复引发序列的计算方法;定义了可重复序列之间的依赖性和依赖度,准确地给出了可重复序列之间依赖关系的形式描述;分析了Petri网语言的结构特点,证明了任意一个Petri网语言都是一个正规语言表达式与该网的可重复引发序列α闭包的同步.     

基于时延库所Petri网的动态联盟任务调度研究

针对动态联盟中任务调度的特点,提出了采用时延库所Petri网对动态联盟任务调度进行建模.给出了模型的形式化描述及变迁规则,对动态联盟中的产品加工类型进行了分类,并建立了各种加工类型的时延库所Petri网模型,分析了通过模型中零时差的库所求解关健路径和利用可达图求解合理调度方案的方法.最后,以实例表明了该方法的可行性和有...     

Petri网的同步距离计算

同步距离是刻画事件之间同步关系的一个重要的定量分析手段。本文提出了同步距离计算网SDCNet的概念模型并讨论了计算同步距离的几个结论,给出了S_元中初始标识的配置算法以及以此为基础计算同步距离的算法。分析表明该算法与可覆盖性树的生成算法具有相同的复杂性。     

基于同步合成的结构复杂Petri网的行为描述

首先分析了一类结构简单的Petri网--S-网的语言性质,得到了它们的行为描述方法.拓展了Petri网同步合成的概念,证明了给定一个结构复杂的Petri网都可通过一组S-网的同步合成运算而得到,并给出了相应的求解算法.引入语言的同步交运算,分析了结构复杂的Petri网与其同步合成子网之间的行为关系,给出了结构复杂Petri网的行为描述算法,为利用网语言分析实际系统的行为特征提供了可靠的理论依据和方法.     

基于库所指标的Petri网分解方法

一、引言 Petri网是系统模拟和分析的有效工具。对于一个规模较大的网系统,由于变迁和库所数目的增多,其分析显得比较麻烦。针对这个问题,国内外的许多学者作了大量的工作,他们提出了网化简、网运算,定义了化简子网、逐次化简以及针对特殊子网、特殊结构的化简方法。文[6]和文[7]分别给出了网系统的“和分解”和“并分解”方法,并讨论了通过这两种分解方法得到的子网同原网在结构性质方面的对应关系。本文通过指定库所集的指标函数,给出一种基于库所指标集的Petri网分解方法,通过分解得到结构简单的子网系统:|t|≤1且|t|≤1,原系统的状态和语言与子系统之间存在着一种投影关系,通过子网间的同步合成可得到原系统的状态和行为,对用Petri网分析大规模系统提供了一种有效的方法。由于篇幅所限,本文没有介绍Petri网的基本概念和术     

New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets

Timed Petri nets are useful in performance evaluation of concurrent systems. The maximum computation rate is achieved for minimal cycle time of timed Petri net. It is known that minimal cycle time problem for P-invariant Petri nets is NP-complete. In this paper we prove that the minimal cycle time problem, for non-P-invariant Petri nets and for a small subclass of P-invariant Petri nets called free-choice nets having live and safe marking, is NP-complete.     

基于Petri网建模的互斥问题优化方案

互斥是解决资源利用冲突、实现资源共享的一种有效方法,但是简单互斥方法给同步带来一些问题.为此从Petri网对互斥进程的表示入手,分析并提出了改进和优化的互斥进程解决方案,利用同步距离的概念对不同性质互斥进程的逻辑同步距离、时间同步距离和数据同步策略进行分析和计算,证明了优化方案在缩小同步距离、减少系统运行耗时和资源占用率方面的优势.     

A synthesis technique of general petri nets

The general Petri net (GPN) is useful for modeling flexible manufacturing systems with multiple robots and workstations [15] and for parallel programs [8]. A problem of using reachability analysis for analyzing Petri nets (PN) is the large number of states generated. Most of the existing synthesis techniques do not deal with GPN. Koh et al.[15] invented a synthesis technique for GPN. We propose to improve their achievement by adding the simple Arc-ratio rules to Yaw's knitting technique [37, 38, 39] based on the notion of structure relationship together with new path generations, which mark the most distinct feature compared with other approaches. The synthesis rules and procedures of how to update the temporal matrix and structure synchronic distance are presented. The Arc-ratio rules for GPN are also presented. One can successfully synthesize complicated Petri nets using these rules. An example to synthesize a Petri net in [15] is illustrated. The correctness of each synthesis rule with an appropriate Arc-ratio rule for GPN is proved.     

Performance evaluation of marked graphs by linear programming

Performance evaluation is an important issue for discrete event dynamic systems, which in many cases can be described in terms of the language of Petri nets. In particular, for marked graphs, a subclass of Petri nets, a formula for performance evaluation is widely known. That is, the ratio of the total execution time to the number of tokens in a cycle gives a lower bound for the cycle time of the system, and the maximum of these ratios over all cycles determines the overall system performance. However, we need to enumerate all directed cycles in a graph to apply this formula of performance evaluation. Carrying out this enumeration for an actual system is often impractical, since the number of cycles in a graph usually grows exponentially with the size of a system. We give a linear algebraic characterization for directed cycles, and based on this result, transform the problem of performance evaluation into a simple linear programming problem. A few explanatory examples are also given.     

一类受控Petri网的反馈控制

受控Petri网是离散事件动态系统(DEDS)的一种控制理论模型.通过模型来研究实现 禁止状态避免的最大允许反馈控制是DEDS控制理论中的一个重要课题.文中对受控Petri网 的一个子类(非受控变迁子集的外延子网为TC网)讨论控制综合问题,给出求这类受控网中实 现禁止状态避免的最大允许反馈控制的一个算法.     

应用必需信标的Petri网死锁预防策略

本文提出了表征一个Petri网子类,即S4R网(system of sequential systems with shared resources)中死锁问题的必需信标的概念和一种将混合整数规划算法与必需信标控制相结合的死锁预防策略.在该策略的迭代过程中,混合整数规划算法发现被控的Petri网中是否存在最大的死标识信标,若存在,则通过库所分类和迭代式的信标提取,得到必需信标,添加相应的控制库所,满足必需信标的最大可控性,从而实现被控的Petri网活性的目的.理论分析和算例验证表明了该策略的正确性和有效性.     

POC net,a subclass of Petri nets,and its application to timed Petri nets

Liveness is one of the most important properties of the Petri net analysis. This property is concerned with a capability for firing of transitions. On the other hand, place-liveness is another notion related to liveness, which is concerned with a capability for having tokens in places. Concerning these liveness and place-liveness problems, this paper suggests a new subclass of Petri net, ‘POC nets’, as a superclass of AC nets and DC nets. For this subclass, the equivalence between liveness and place-liveness is shown and a sufficient condition for liveness for this POC net is derived. Then the results are extended to liveness problem of timed Petri nets which have transitions with finite firing durations and the earliest firing rule. Although liveness of a (non-timed) Petri net is neither necessary nor sufficient condition for liveness of a timed Petri net, it is shown that liveness is preserved if the net has POC structure. Furthermore, it is pointed out that if a POC net satisfies some additional condition, Petri net liveness is equivalent to timed Petri net liveness. Finally, it is shown that liveness of timed POC nets with TC structure and the earliest firing rule is decidable with deterministic polynomial time complexity.     

正规语言闭包运算的Petri网构造方法

Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。