First-order hybrid Petri nets. An application to distributed manufacturing systems

In this paper we consider Hybrid Petri Nets (HPNs), a particular formalism that combines fluid and discrete event dynamics. We first provide a survey of the main HPN models that have been presented in the literature in the last decades. Then, we focus on a particular HPN model, namely the First-Order Hybrid Petri Net (FOHPN) model, whose continuous dynamics are piece-wise constant. Here the problem of designing an optimal controller simply requires solving on-line an appropriate linear integer programming problem. In this paper we show how FOHPNs can efficiently represent the concurrent activities of Distributed Manufacturing Systems (DMS), and some interesting optimization problems are also solved via numerical simulation.     

Hybrid observer design for linear switched system via Differential Petri Nets

The aim of this paper is to propose a hybrid observer design for linear switched systems modelled either via Differential Petri Nets (DPN) or via Timed Differential Petri Nets (TDPN). The switched systems, herein, considered are characterized by switching laws that can depend on the continuous states or on both of a given dwell time and the continuous states. In addition, the structure of the proposed observers is based on a discrete observer and a continuous observer on interaction. The discrete observer reconstructs the discrete mode, by estimating both of the discrete marking and the firing vector. Once, the active mode is obtained, the continuous states are estimated. Finally, the outputs of the continuous observer are used to update the marking and the firing vector. At the end of the paper, several simulation results are presented to illustrate the proposed approach.     

On the fluidization of Petri nets and marking homothecy

The analysis of Discrete Event Dynamic Systems suffers from the well known state explosion problem. A classical technique to overcome it is to relax the behavior by partially removing the integrality constraints and thus to deal with hybrid or continuous systems. In the Petri nets framework, continuous net systems (technically hybrid systems) are the result of removing the integrality constraint in the firing of transitions. This relaxation may highly reduce the complexity of analysis techniques but may not preserve important properties of the original system. This paper deals with the basic operation of fluidization. More precisely, it aims at establishing conditions that a discrete system must satisfy so that a given property is preserved by the continuous relaxation. These conditions will be mainly based on the marking homothetic behavior of the system. The focus will be on logical properties as boundedness, B-fairness, deadlock-freeness, liveness and reversibility. Furthermore, testing homothetic monotonicity of some properties in the discrete systems is also studied, as well as techniques to improve the quality of the fluid relaxation by removing spurious solutions.     

A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems

Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A^* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.     

Mathematical programming approach to the Petri nets reachability problem

This paper focuses on the resolution of the reachability problem in Petri nets, using the mathematical programming paradigm. The proposed approach is based on an implicit traversal of the Petri net reachability graph. This is done by constructing a unique sequence of Steps that represents exactly the total behaviour of the net. We propose several formulations based on integer and/or binary linear programming, and the corresponding sets of adjustments to the particular class of problem considered. Our models are validated on a set of benchmarks and compared with standard approaches from IA and Petri nets community.     

Hybrid stochastic approach for the modelling and analysis of fire safety systems

This paper approaches the problem of analysing control strategies for Fire Safety Systems. The components of Fire Safety Systems present behaviours of different nature and therefore the use of a hybrid modelling formalism is necessary. Petri net is used to model the discrete dynamics. Algebraic and differential equations are used for the continuous one. In order to realistically evaluate the performance of Fire Safety Systems, failures and other uncertainties, such as people’s behaviour, should be included in the model. Due to the model complexity, results are obtained by Monte Carlo simulation.     

SimHPN: A MATLAB toolbox for simulation, analysis and design with hybrid Petri nets

This paper presents a MATLAB embedded package for hybrid Petri nets called SimHPN. It offers a collection of tools devoted to simulation, analysis and synthesis of dynamical systems modeled by hybrid Petri nets. The package supports several server semantics for the firing of both, discrete and continuous, types of transitions. Besides providing different simulation options, SimHPN offers the possibility of computing steady state throughput bounds for continuous nets. For such a class of nets, optimal control and observability algorithms are also implemented. The package is fully integrated in MATLAB which allows the creation of powerful algebraic, statistical and graphical instruments that exploit the routines available in MATLAB.     

Adaptation as a Morphing Process: A Methodology for the Design and Evaluation of Adaptive Organizational Structures

Changes in objectives, in resources, or in the environment may necessitate the adaptation of an organization from one form to another. However, in many cases, the organizations need to continue functioning while adaptation takes place, i.e., it is not possible to stop the organizational activity in order to reorganize, and then start again. In this case, adaptation can be expressed as a morphing process in which the organization transitions from one form with its attendant task allocation to a different one through a series of incremental steps that preserve overall functionality and performance. Coordination between organization members during adaptation is critical. A computational model for this type of organizational adaptation at the operational level is presented. The model is implemented using the Colored Petri Net formulation of discrete event dynamical systems. A design methodology that utilizes this model is outlined and a simple example is used to illustrate the approach.     

Modelling and assessing ERP project risks: A Petri Net approach

Risk management of Enterprise Resource Planning (ERP) projects is largely recognized as a very complex task both by academics and practitioners. Strict interconnections among risk factors often occur so that indirect effects on the overall project performance are very likely. Unfortunately, the implications of interdependency are usually underestimated by project managers and decision makers since they are difficult to include in any risk assessment logic. This work shows how Colored Petri Nets (CPNs) can be used to model risk factors in ERP projects in order to deal with the problem of interdependence in risk assessment. The technique is presented through an application to a real case study. Findings highlight the importance of interdependence and the indirect links for an effective ranking of risks. Furthermore, results emphasize the valuable support of CPNs in risk factor modelling since they allow both a more structured and systematic risk analysis and a more accurate planning for effective risk treatment actions.     

Some contributions with Petri nets for the modelling, analysis and control of HDS

Petri nets (PN) are useful for the modelling, analysis and control of hybrid dynamical systems (HDS) because PN combine in a comprehensive way discrete events and continuous behaviours. On one hand, PN are suitable for modelling the discrete part of HDS and for providing a discrete abstraction of continuous behaviours. On the other hand, continuous PN are suitable for modelling the continuous part of HDS and for working out a continuous approximation of the discrete part in order to avoid the complexity associated with the exponential growth of discrete states. This paper focuses on the advantages of PN as a modelling tool for HDS. Investigations of such models for diagnosis and control issues are detailed.

Taking inspiration from the discrete event approach, sensor selection for diagnosis is discussed according to the structural analysis of the PN models. Faults are represented with fault transitions and a faulty behaviour occurs when a sequence of transitions is fired that contains at least one fault transition. Minimal sets of observable places are defined for detecting and isolating faulty behaviours.

Taking inspiration from the continuous time approach, flow control of HDS modelled with continuous PN is also investigated. Gradient-based controllers are introduced in order to adapt the firing speeds of some controllable transitions according to a desired trajectory of the marking. The equilibria and stability of the controlled system are studied with Lyapunov functions.     

Hybrid Monte Carlo on Hilbert spaces

The Hybrid Monte Carlo (HMC) algorithm provides a framework for sampling from complex, high-dimensional target distributions. In contrast with standard Markov chain Monte Carlo (MCMC) algorithms, it generates nonlocal, nonsymmetric moves in the state space, alleviating random walk type behaviour for the simulated trajectories. However, similarly to algorithms based on random walk or Langevin proposals, the number of steps required to explore the target distribution typically grows with the dimension of the state space. We define a generalized HMC algorithm which overcomes this problem for target measures arising as finite-dimensional approximations of measures π which have density with respect to a Gaussian measure on an infinite-dimensional Hilbert space. The key idea is to construct an MCMC method which is well defined on the Hilbert space itself.We successively address the following issues in the infinite-dimensional setting of a Hilbert space: (i) construction of a probability measure Π in an enlarged phase space having the target π as a marginal, together with a Hamiltonian flow that preserves Π; (ii) development of a suitable geometric numerical integrator for the Hamiltonian flow; and (iii) derivation of an accept/reject rule to ensure preservation of Π when using the above numerical integrator instead of the actual Hamiltonian flow. Experiments are reported that compare the new algorithm with standard HMC and with a version of the Langevin MCMC method defined on a Hilbert space.     

Extending Petri net to reduce control strategies of railway interlocking system

In our previous articles we gave step by step refinement process towards the development of safety properties of moving block interlocking system (MBRIS). The refinement process started from abstraction to fuzzy based safety properties using Z and then fuzzy multi agent specification language. However, one dimensional control of train passing through a switch and level crossing were not discussed. This paper reduces the existing two dimensional controls along the switch and level crossing to one dimensional for shifting it to a train only. For example, in the existing model the train movement along components switches and level crossings depends on both the train and components control. Whereas, in one dimensional control train is the only authority to control a switch and level crossing required for its desired operation. For this reduction, concurrent and mobile agent concepts are required. Therefore, we integrate mobile agent concepts with Petri nets to develop the mobile Petri net (MPN) a new class of PNs. This supports both mobility and concurrency. Further, we prove that the collection of different MPNs in a connected network is a PN. This proof allowed us to use the properties of PN to verify the system. Finally, we use MPN to model the safety properties of MBRIS along the switch and level crossing. This provides one dimensional control to a train along a switch and level crossing which increases the safety of the railway interlocking system. Moreover, we use reachability graph (RG) to verify the switch and level crossing models.     

Supply chain modelling and its analytical evaluation

A model-based analysis of supply chains (SCs) is proposed as a means of estimating performance measures like lead times and resource utilisations. SCs are regarded as discrete event dynamic systems (DEDS), described as process chains in an application-specific formalism, and analysed by state-of-the-art techniques developed for queueing networks (QNs) and Petri nets (PNs). The theoretical approach is accompanied by a toolset that provides automatic translations between a process-chain-specification front end and analysis engines for QN and PN models. In addition, the analysis technique also supports a hybrid approach, in which dedicated sub-models are mapped into a PN model, numerically analysed, and replaced with an aggregate. Finally, the resulting QN models may be analysed using analytical as well as simulative techniques. As an example application, we investigate the impact of an additional SC channel between a manufacturer and web-consumers on the overall performance of an SC. The example was inspired by the trend towards retail trade via the internet and illustrates the new challenges of electronic commerce for SC management.     

Petri net modelling of biological regulatory networks

The complexity of biological regulatory networks often defies the intuition of the biologist and calls for the development of proper mathematical methods to model their structures and to delineate their dynamical properties. One qualitative approach consists in modelling regulatory networks in terms of logical equations (using either Boolean or multi-level discretisations). The Petri Net (PN) formalism offers a complementary framework to analyse the dynamical behaviour of large systems, either from a qualitative or from a quantitative point of view.

Our proposal consists in articulating the logical approach with the PN formalism. In a previous work, we have already defined a systematic re-writing of Boolean regulatory models into a standard PN formalism. In this paper, we propose a rigorous and systematic mapping of multi-level logical regulatory models into specific standard Petri nets, called Multi-level Regulatory Petri Nets (MRPNs). We further propose some reduction strategies. Consequently, the resulting models become amenable to the algebraic and computational analyses used by the PN community.

To illustrate our approach, we apply it to a multi-level logical model of the genetic switch controlling the lysis-lysogeny decision in the lambda bacteriophage.     

Diffusion approximation for signaling stochastic networks

This paper introduces an unified approach to diffusion approximations of signaling networks. This is accomplished by the characterization of a broad class of networks that can be described by a set of quantities which suffer exchanges stochastically in time. We call this class stochastic Petri nets with probabilistic transitions, since it is described as a stochastic Petri net but allows a finite set of random outcomes for each transition. This extension permits effects on the network which are commonly interpreted as “routing” in queueing systems. The class is general enough to include, for instance, G-networks with negative customers and triggers as a particular case. With this class at hand, we derive a heavy traffic approximation, where the processes that drive the transitions are given by state-dependent Poisson-type processes and where the probabilities of the random outcomes are also state-dependent. The objective of this approach is to have a diffusion approximation which can be readily applied in several practical problems. We illustrate the use of the results with some numerical experiments.     

Hybrid abstractions of affine systems

This paper considers the problem of building a set of hybrid abstractions for affine systems in order to compute over approximations of the reachable space. Each abstraction is based on a decomposition of the continuous state space that is defined by hyperplanes generated by linear combinations of two vectors. The choice of these vectors is based on consideration of the dynamics of the system and uses, for example, the left eigenvectors of the matrix that defines these dynamics. We show that the reachability calculus can then be performed on a combination of such abstractions and how its accuracy depends on the choice of hyperplanes that define the decomposition.     

Supervisory controller design to enforce some basic properties in timed-transition Petri nets using stretching

Supervisory controller design to enforce boundedness, reversibility, and liveness in timed-transition Petri nets with firing durations is considered. It is assumed that both controllable and uncontrollable transitions may be present and more than one transition may fire simultaneously. The approach of stretching is used to represent the state of the system. Algorithms are presented to design a supervisory controller using the forbidden states approach to enforce boundedness and reversibility simultaneously. The designed controller also guarantees T-liveness for the largest possible subset T of the set of transitions. In particular, boundedness, reversibility, and liveness are simultaneously enforced whenever it is possible. The designed controller is also the least restrictive controller which enforces boundedness and reversibility simultaneously.