Petri网可达性的伪标识判定法

Petri网标识的可达性判定问题是进行Petri网分析的基础。在分析目前现有的判定Petri网可达性的求解方法的基础上,提出一种伪标识判定法。该方法在状态方程法的基础上,利用关联矩阵来判断变迁发射向量是否能够发生来筛除伪标识。通过对实例的求解说明了求解过程并证明了算法能够确保对所得结果的可靠性,减少了算法的时间复杂度。     

基于极小T-不变量增加的Petri网可达性分析

基于极小T-不变量增加的Petri网的可达性分析,首先对网的状态方程加以合理的约束,求得一组特征解向量;然后利用扩展极小T-不变量关系图和扩展借矩阵在这些特征解向量的基础上适当添加整数倍的极小T-不变量;最后再判断这个添加极小T-不变量后的解向量的可达性。该方法不仅能判定一类含T-不变量Petri网的可达性,而且能在可达的情况下求得一个合法的变迁发生序列,并在一定程度上简化了可达性分析的过程。     

非交互式Petri网可覆盖性验证的高效实现

近年来,基于Petri网可覆盖性的验证技术已经成功地应用于并发程序的验证与分析中.然而,由于Petri网的可覆盖性问题复杂度太高,这类技术在应用时有较大的局限性,对于输入规模较大的问题常常会出现超时的情况.而Petri网的一个子系统——非交互式Petri网,其可覆盖性和可达性复杂性均是NP完备的,同时表达力又可以作为某类并发程序的验证模型.设计并实现了可以高效验证非交互式Petri网可覆盖性的工具CFPCV.采用基于约束的方法,从模型中提取约束,并使用Z3 SMT求解器对约束进行求解,同时,通过子网可标记方法对候选解进行验证,从而保证每组解都是正确解.通过实验分析了该工具的成功率、迭代次数以及运行效率,发现该算法不仅验证成功率高,而且性能非常优异.     

一种基于进程验证的Petri网可达性判定方法

为了解决Petri网的可达性判定问题,提出了一种基于进程验证的可达性判定方法.通过分析Petri网基本进程段子段间偏序关系,该方法提出原子进程段概念,求得原子进程段集及其偏序关系集作为可达性判定的验证对象.基于原网状态方程解向量、原子进程段T-向量的线性纯整数规划问题解,选取该解中非零分量对应的原子进程段子集作为待验进程段集,选取待验进程段间的偏序关系子集作为待验推理规则集,通过验证是否存在这两个集合上的以初始标识M0为推导初态、目的标识Md为推导终态的序列而判定(M0,Md)是否可达.分析表明该可达性判定算法的时间复杂度是依赖于原子进程段集规模的,最坏情况下不超过变迁集规模.     

基于改进蚁群算法的维修拆卸序列规划

维修拆卸序列规划是整个维修性设计的重要内容。为了能够以较高的效率求解出产品中零件的拆卸方案,依据产品的基本信息和零件之间的约束关系,建立拆卸Petri网可达图,将拆卸序列规划问题转化为对Petri网可达图最优路径的搜索和寻优问题。同时利用蚁群优化算法对组合优化具有高强适应性的特征,改进基本蚁群算法,对可达图模型进行路径寻优,得到最优或次优的拆卸序列。最后通过实例验证了该方法的有效性。     

基于人工鱼群算法的混杂FMS优化调度

针对已有的调度方法难以找到混杂柔性制造系统调度全局最优解的问题,根据一阶混杂Petri网模型提出了一种基于人工鱼群算法的混杂柔性制造系统调度方法.利用混杂Petri网不变行为状态序列与时间序列的对应关系把寻找最优解转换成寻找最优时间序列.首先给出了合法时间序列的定义及其基于人工鱼群算法的判定方法;然后给出了最优时间序列求解的人工鱼群算法,同时提出基于最优解视野变异的人工鱼群算法以解决多次优化过程中只会得到某个局部最优解的问题.最后基于这些算法给出混杂柔性制造系统的最优调度求解方法.实验结果表明所提出方法正确有效.     

Web服务自动化测试技术

赋时Petri网为装配序列规划提供了有效的建模方法,但其在求解最优装配序列时受到组合复杂性的严重制约。零压缩二叉决策图(ZBDD)是处理大规模组合集合和0-1稀疏向量的一种有效符号技术,能够有效缓解组合爆炸问题。将赋时Petri网与ZBDD结合起来,给出了一种求解装配序列最优解的有效方法。首先通过转换算法将赋时Petri网转换为等价的普通Petri网,接下来给出普通Petri网可达状态及迁移引发函数的ZBDD表示方法,最后基于ZBDD给出最优装配序列求解算法。实例验证表明,该算法在求解过程中通过隐式符号操作实现了Petri网的可达状态搜索,有效缓解了计算过程中的组合复杂性。     

无冲突Petri网系统活标识判定的结构化方法

为了有效求解无冲突Petri网系统活标识的判定及配置优化问题,提出无冲突Petri网系统活标识判定的一种结构化方法。该方法首先求取无冲突Petri网的各强连通分支;然后对每一含有元素个数大于2的强连通分支求取其无同步变迁库所索引集合;最终得到无冲突Petri网系统的无前置库所索引集合,基于该库所元素集合即可实现对活标识的快速判定及配置优化。通过例子具体说明了该方法的实现及应用。分析结果表明,所提方法具有多项式时间复杂度,较易于操作和程序化实现。     

针对一般线性约束的Petri网控制器设计方法

针对基于Petri网离散事件系统关于标识向量和Parikh向量的不等式约束反馈控制器设计问题,提出一种新的控制器设计方法.该方法首先利用Petri网的状态方程把关于标识向量和Parikh向量的不等式约束转变成关于Parikh向量的不等式约束,然后基于Petri网库所是关于Parikh向量的不等式约束的观点构造控制器.最后将该方法与Iordache和Moody提出的方法作比较,实验结果显示该方法更简单、有效.     

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

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

An algebraic approach to revising propositional rule-based knowledge bases

One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the problem. An algebraic approach is presented to revise propositional rule-based knowledge bases in this paper. A way is firstly introduced to transform a propositional rule-based knowledge base into a Petri net. A knowledge base is represented by a Petri net, and facts are represented by the initial marking. Thus, the consistency check of a knowledge base is equivalent to the reachability problem of Petri nets. The reachability of Petri nets can be decided by whether the state equation has a solution; hence the consistency check can also be implemented by algebraic approach. Furthermore, algorithms are introduced to revise a propositional rule-based knowledge base, as well as extended logic programming. Compared with related works, the algorithms presented in the paper are efficient, and the time complexities of these algorithms are polynomial.     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

Analysis of Hybrid Systems Based on Hybrid Net Condition/Event System Model

In thispaper, hybrid net condition /event systems are introducedas a model for hybrid systems. The model consists of a discretetimed Petri net and a continuous Petri net which interact eachother through condition and event signals. By introducing timeddiscrete places in the model, timing constraints in hybrid systemscan be easily described. For a class of hybrid systems that canbe described as linear hybrid net condition /eventsystems whose continuous part is a constant continuous Petrinet, two methods are developed for their state reachability analysis.One is the predicate-transformation method, which is an extensionof a state reachability analysis method for linear hybrid automata.The other is the path-based method, which enumerates all possiblefiring seqenences of discrete transitions and verifies if a givenset of states can be reached from another set by firing a sequenceof discrete transitions. The verification is performed by solvinga constraint satisfaction problem. A technique that adds additionalconstraints to the problem when a discrete state is revisitedalong the sequence is developed and used to prevent the methodfrom infinite enumeration. These methods provide a basis foralgorithmic analysis of this class of hybrid systems.     

Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets

Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.     

Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

基于有色Petri 网的时钟同步协议安全性分析

随着工业以太网的发展,作为其实时性保障核心技术的时钟同步协议的安全性变得至关重要。针对时钟同步协议的安全性问题,首先提出一种基于有色Petri网的时钟同步协议安全性分析方法;然后通过建立协议的有色Petri网模型,利用状态方程等工具针对不安全状态的可达性进行判断分析,从而实现时钟同步协议的安全性分析;最后具体分析了一种基于精密时钟同步协议(PTP)的时钟同步协议以及针对该协议的主时钟欺骗攻击,验证了所提出方法的有效性。     

Petri net dynamics-based scheduling of flexible manufacturing systems with assembly

This paper presents a heuristic search method based on Petri nets for scheduling flexible manufacturing systems with assembly (FMSA) by partially generating the reachability graph. FMSAs are modeled by two types of timed place Petri nets, called generalized symmetric (GSN) and asymmetric nets (GAN). GSN is a sub-class of GAN. The special Petri net structures of GSN and GAN allow us to efficiently solve their state equations for solutions that constitute a part of the proposed heuristic function. Considering the dynamic information of nets such as concurrency and synchronization, the part of the heuristic function is adjusted since state equation solutions may over-estimate the real cost. The adjustment is based on a lower bound of the real cost and on dynamically comparing the partial estimated cost and partial real cost during the search process. Extensive simulation study shows that in most cases this work obtain better solutions than prior work.