Scheduling and control of real-time systems based on a token player approach

Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events.     

Relevant Timed Schedules/Clock Vectors for Constructing Time Petri Net Reachability Graphs

We consider here the time Petri nets (the TPN model) and its state space abstractions. We show that only some timed schedules/clock vectors (one per enabled transition) of the clock/firing domains are relevant to construct reachability graphs for the TPN. Moreover, we prove formally that the resulting graphs are smaller than the TPN reachability graphs proposed in the literature. Furthermore, these results establish a relation between dense time and discrete time analysis of time Petri nets and allow also improving discrete time analysis by considering only some elements of the clock/firing domains.     

The synthesis problem of Petri nets

The synthesis problem of concurrent systems is the problem of synthesizing a concurrent system model from sequential observations. The paper studies the synthesis problem for elementary Petri nets and transition systems. A characterization of the class of transition systems which correspond to elementary Petri nets is proven. It is shown how to generate all elementary Petri nets corresponding to a given transition system. If there is any such elementary Petri net, it is proven that there always exists a small one which has only polynomially many elements in the size of the transition system. Received October 5, 1992 / April 11, 1995     

Marking Optimization of Weighted Marked Graphs

Cyclic manufacturing systems can be modeled by marked graphs, which are an elementary class of Petri nets. To model systems with bulk services and arrivals and to reduce the size of the model, weighted marked graphs can be used. An important step when designing these systems is the definition of the number of manufacturing resources to be used in order to reach a given productivity. In terms of timed Petri nets, this is known as the marking optimization problem and consists of reaching a given average cycle time while minimizing a linear combination of markings. In this paper, a necessary and sufficient condition to obtain a feasible solution of the marking optimization problem of weighted marked graphs with deterministic times is established. A fast heuristic solution, based on an iterative process and using simulation, is given. An example and an application to manufacturing systems are presented.     

Sequential versus concurrent languages of labeled conflict-freePetri nets

For structurally deterministic labeled conflict-free Petri nets (PNs), we show that two PNs have identical sequential languages if and only if their concurrent languages are identical as well, and whether a given labeled conflict-free PN is structurally deterministic or not can be checked in polynomial time. We also investigate a number of language-related problems in supervisory control theory for this class of PNs. As it turns out, the properties of controllability, observability, and normality in the sequential framework coincide with that in the concurrent framework     

On the Regularity of Petri Net Languages

Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of theregularity problem(i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, includingconflict-free,trap-circuit,normal,sinkless,extended trap-circuit,BPP, andgeneralPetri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type ofcircuits.) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop adecomposition approachwhich, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived.     

New spectral lower bounds on the bisection width of graphs

The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ₂|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ₂|V|/4 iff all vertices are incident to λ₂/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ₂^β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.     

A computer network based control architecture for autonomous distributed multirobot systems

This paper presents the specification and implementation procedure using a microcomputer network based autonomous distributed control architecture for industrial multirobot systems. The procedure is based on the concept of data flow network controlled by communicating sequential processes to perform coordinated tasks. Robots and other computerized industrial devices such as conveyors and manufacturing machines are defined as object-oriented Petri nets. A modular and hierarchical approach is adopted to define a set of Petri net type diagrams which represent concurrent activities of control processes for such devices. Asynchronous and synchronous interactions are modelled by places and transitions, respectively, in global process interaction nets. The control software is implemented on a computer network using Inmos transputers with true parallel processing and message passing primitives efficiently handled in hardware. Petri net based models are directly and efficiently transformed to corresponding codes in occam, the high level parallel programming language defined for the transputer.     

Some decision problems related to the reachability problem for Petri nets

In this paper, we show that (1) the question to decide whether a given Petri net is consistent, M_o-reversible or live is reduced to the reachability problem in a unified manner, (2) the reachability problem for Petri nets is equivalent to the equality problem and the inclusion problem for the sets of all firing sequences of two Petri nets, (3) the equality problem for the sets of firing sequences of two Petri nets with only two unbounded places under homomorphism is undecidable, (4) the coverability and reachability problems are undecidable for generalized Petri nets in which a distinguished transition has priority over the other transitions, and (5) the reachability problem is undecidable for generalized Petri nets in which some transitions can reset a certain place to zero marking.     

Some observations on supervisory policies that enforce liveness in partially controlled Free-Choice Petri nets

Every arc from a place to a transition in a Free-Choice Petri net (FCPN) is either the unique output arc of the place, or, the unique input arc to the transition [M.H.T. Hack, Analysis of production schemata by Petri nets, Master’s thesis, Massachusetts Institute of Technology, February 1972; W. Reisig, Petri Nets, Springer-Verlag, Berlin, 1985; T. Murata, Petri nets: properties, analysis and applications, Proc. IEEE 77 (4) (1989) 541–580]. We consider FCPNs that are not live [J.L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; W. Reisig, Petri Nets, Springer-Verlag, Berlin, 1985; T. Murata, Petri nets: properties, analysis and applications, Proc. IEEE 77 (4) (1989) 541–580], and we investigate the existence of supervisory policies that can enforce liveness in partially controlled FCPNs. The external agent, or supervisor, can only prevent the firing of some (i.e. not all) transitions in a partially controlled FCPN.

We first present an observation on supervisory policies that enforce liveness in partially-controlled FCPNs. Using this observation, we solve the supervisory synthesis problem for the family of c hoice-controlled FCPNs, defined in this paper. We then identify a new, sub-class of partially-controlled FCPNs that posses an easily-characterized (and easily-enforced) supervisory policy that enforces liveness.     

Ergodicity and throughput bounds of Petri nets with uniqueconsistent firing count vector

Ergodicity and throughput bound characterization are addressed for a subclass of timed and stochastic Petri nets, interleaving qualitative and quantitative theories. The nets considered represent an extension of the well-known subclass of marked graphs, defined as having a unique consistent firing count vector, independently of the stochastic interpretation of the net model. In particular, persistent and mono-T-semiflow net subclasses are considered. Upper and lower throughput bounds are computed using linear programming problems defined on the incidence matrix of the underlying net. The bounds proposed depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases). From a different perspective, the considered subclasses of synchronized queuing networks; thus, the proposed bounds can be applied to these networks     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Theoretical calculation of the phase diagram between one-dimensional long-period structures in the quasi binary sections: Pd3xRh3(1−x)V, Pt3xRh3(1−x)V, and Pt3VxTi(1−x)

The relative stabilities of L1₂, D0₂₂, D0₂₃, 21, and 3 structures in the Pd₃V, Pt₃V, Rh₃V, and Pt₃Ti compounds are investigated employing the Vienna ab initio simulation package. In the pseudobinary Pd_3xRh_3(1−x)V, Pt_3xRh_3(1−x)V, and Pt₃V_xTi_(1−x) alloys, the energy differences from L1₂ of D0₂₂, D0₂₃, 21, and 3 structures are assumed to be linear as function of the number of electrons per atom. At T=0K, the resulting energy diagram shows that the equilibrium between the limiting binary phases is the most stable state. At high temperature, the Gibbs energy curves are computed assuming a Bragg and Williams entropy of mixing in the pseudobinary sections. The D0₂₃ and 21 structures are stabilized in the pseudobinary Pd_3xRh_3(1−x)V, Pt_3xRh_3(1−x)V, and Pt₃V_xTi_(1−x) alloys. The phase diagram between the various structures is calculated in each pseudobinary section and compared with the experimental one.     

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

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

Timing constraint Petri nets and their application toschedulability analysis of real-time system specifications

We present timing constraint Petri nets (or TCPN's for short) and describe how to use them to model a real-time system specification and determine whether the specification is schedulable with respect to imposed timing constraints. The strength of TCPN's over other time-related Petri nets is in the modeling and analysis of conflict structures. Schedulability analysis is conducted in three steps: specification modeling, reachability simulation, and timing analysis. First, we model a real-time system by transforming its system specification along with its imposed timing constraints into a TCPN; we call this net N_s. Then we simulate the reachability of N_s to verify whether a marking, M_n, is reachable from an initial marking, M_o. It is important to note that a reachable marking in Petri nets is not necessarily reachable in TCPN's due to the imposed timing constraints, Therefore, in the timing analysis step, a reachable marking M_n, found in the reachability simulation step is analyzed to verify whether M_n, is reachable with the timing constraints. M_n is said to be reachable in the TCPN's if and only if we can find at least one firing sequence σ so that all transitions in σ are strongly schedulable with respect to M_o under the timing constraints. If such M_n can be found, then we can assert that the specification is schedulable under the imposed timing constraints, otherwise the system specification needs to be modified or the timing constraints need to be relaxed. We also present a synthesis method for determining the best approximation of the earliest fire beginning time (EFBT) and the latest fire ending time (LFET) of each strongly schedulable transition     

An object-oriented knowledge based Petri net approach to intelligent integration of design and assembly planning

Artificial intelligence can play an important role in the reduction of manufacturing costs and the enhancement of production efficiency and product quality. In order to assist designers in the early stages of a product development this paper develops an intelligent methodology for integration of design and assembly planning processes, including product design, assembly evaluation and redesign, assembly process planning, design of assembly system and assembly simulation, subjected to both econo-technical and ergonomic evaluations. A new unified class of object-oriented knowledge based Petri nets called OOKPNs, incorporating knowledge based expert systems and fuzzy logic into ordinary place–transition Petri nets, is defined and used for the representation and modeling of the distributed design processes. A prototype intelligent integrated design and assembly planning system (IIDAP) is implemented through distributed blackboard structure with concurrent integration of multiple cooperative knowledge sources and software. It consists essentially of the networked agents and the meta-system, each of which is a knowledge Petri net system with the capabilities of problem solving, learning and conflict resolution, and can be obtained through the inheritance, polymorphism and dynamic binding of instances of OOKPNs. In IIDAP system, both C/C++ language and COOL (CLIPS object-oriented language) are used to incorporate a Petri net tool, a geometric modeling and design tool, a planner and simulator and an evaluation tool. By use of this system, product design and assembly planning can be carried out simultaneously and intelligently in an entirely computer-aided concurrent design and assembly planning system. The design of manufacturable, cost-effective, usable products can therefore be achieved rapidly and flexibly. The developed methodology and system have been successfully applied to assembly design and planning of a micro switch.     

Casting Petri Nets into Programs

A programming system has been implemented in which annotated Petri nets are used as machine-processable high-evel design representations. The nets can be used to express the parallelism and the dynamic sequential dependencies found in complex software. They can then be interactively fired to facilitate debugging of the design. The nets are processed into a procedure language, called XL/1, to which a variety of transformations are applied in order to produce more efficient programs. These programs are generated for either a serial or a parallel processing environment. Finally, the XL/1 programs may be translated into PL/I or PL/S. The serial processing versions have been compiled and run successfully, but the parallel processing versions have not yet been run in a parallel processing environment.