Research On Symbolic Analysis Techniques Of Petri Nets And Their Applications

Petri nets (PNs) are a graph-based mathematical formalism suitable to model, analyzeand control the behavior of discrete event concurrent systems. PNs have the ability todescribe large-scale systems transparently, directly and compactly. And then theproblems associated with the systems can be solved through the operations based on thePNs model. One of the focuses in the research of PN’s application is on obtainingefficient methods for analyzing the properties of complex PNs, and then these methodsare used to solve large-scale industrial application problems based on PNs. We study theproblems arising in the symbolic analysis of PNs, and the Flexible ManufacturingSystems (FMS) scheduling and the assembly sequence planning based on PNs model. Indoing so, Ordered Binary Decision Diagram (OBDD) and Zero-suppressed BinaryDecision Diagram (ZBDD) are used as the data structures for formal specification of thestructures and dynamic behaviors of PNs.The contributions of this paper are as follows.1) The symbolic OBDD analysis technique of PNs given by Pastor is analyzed and animproved image computation algorithm used in the symbolic OBDD analysis techniqueof PNs is presented, in which it is not necessary to introduce another set of variables asthe Pastor’s algorithm does. A novel symbolic approach based on OBDD for theanalysis of PNs is presented. By using this symbolic approach, the computingcomplexity of the analysis of PNs is farther alleviated.2) For representing sets of combinations efficiently, encoding methods for k-boundedPNs and the specification approach of transition firing functions based on ZBDD arepresented. Then the novel ZBDD-based symbolic technique to formulate, generate andmanipulate the reachability marking vectors is developed, thereby the performances ofPNs are evaluated symbolically. The experimental results show that the symbolictechnique can handle large-scale PNs more efficiently and compactly.3) By integrating symbolic OBDD analysis technique of PNs with the productionscheduling problems based on PNs model, a novel symbolic algorithm for FMSproduction scheduling is presented. As ZBDD is more suitable for representing thereachable marking sets of PNs, symbolic ZBDD-based algorithm is developed forproduction scheduling in FMS based on timed PNs model. In this scheme, the markingvectors or states in Petri nets are formulated compactly, and the search processes aremanipulated explicitly, thereby the time and space efficiency of searching PNs isimproved. It is shown that symbolic OBDD and ZBDD based algorithms outperform thetraditional ones. 4) An approach for estimating assembly timed PNs model is proposed. In thisapproach, all possible assembly operations are analyzed and local geometricallyfeasibility of subassemblies are estimated layer by layer, then all feasible assemblysequences satisfying geometrically feasibility could be generated. The assembly timedPetri net model provide data support for the evaluation, optimization and selection ofassembly sequences.5) Based on assembly timed PNs model, a heuristic algorithm for assembly sequencesplanning is presented. Using the heuristic functions, the assembly planning algorithmfinds a globally optimal or near optimal feasible assembly sequence in terms of thefiring sequence of the transitions of the PNs model. Experimental results demonstratedthe effectiveness and feasibility of the algorithm.6) Timed PNs are one of the efficient modeling formalisms for assembly sequenceoptimization problems. The state combination complexity, however, renders it hard andeven impossible to solve large scale assembly sequence optimization problems. OBDDand ZBDD are two data structures that provide canonical and compact representation ofstate sets. As parts of efforts to handle the state combination complexity occurring inassembly sequence planning, two algorithms for selecting optimal assembly sequencesbased on OBDD and ZBDD are presented, respectively. These two symbolic schemesguarantee to produce optimal assembly sequences, and are capable of dealing withlarge-scale assembly sequence planning. The algorithms can find the optimal assemblysequence between any two assembly states through setting deferent initial marking andfinal marking. Compared with OBDD based algorithm and heuristic algorithm, the timeand space performances of ZBDD based algorithm are improved.