Rapid and modular prototyping-based Petri nets and distributed simulation for manufacturing systems

This paper presents an approach to simulate and implement by stepwise refinement the whole manufacturing system (MS) by means of distributed simulation. This approach is based on the use of different classes of Petri nets to model different levels of a manufacturing system. Furthermore these classes may match the abstraction levels of a high-level Petri net used to model the MS. Each level can be simulated on a processor or a cluster of processors which can communicate between themselves using a network. The main contribution is to give the opportunity to combine simulation, performance evaluation and emulation. The emulation means that a part of the system can be run in real time while the other part is simulated. Moreover based on the abstraction levels of high-level Petri nets, subsystems can be integrated step-by-step from the design stage to the implementation one, allowing inter-changeability between simulated components and real-time physical systems. This approach is achieved by defining a simulation engine which involves a local simulator, an emulator and an interface to the physical process. Criteria are defined to use an emulator or a local control software for a physical process as a logical process for the conservative distributed simulation.     

Decomposing Timed Petri Net Models of Open Queueing Networks

This paper develops a Petri net-based decomposition approach to model and perform steady-state analysis of open queueing networks with multi-class customers. For each customer class we assume deterministic routeing and different service time distribution. The current decomposition may also consider equipment failures, defective units that have to be re-worked and on-line preparations (to switch from one mix of customers to another) as additional customer classes. In contrast to most of the published works on timed Petri nets, their present use is marked by input flows, originating from external sources. A simple method, directly derived from the timed Petri nets theories, is used for calculating the expected utilization of each server and eventually the maximal productivity of the system for the given deterministic routeing. An important application of the model is in validating discrete-event non-terminating simulation models.     

An asynchronous protocol for virtual factory simulation on shared memory multiprocessor systems

The development of parallel simulation technology is seen as an enabler for the implementation of the virtual factory concept, the integrated simulation of all the systems in a factory. One important parallel simulation protocol, the asynchronous deadlock avoidance algorithm proposed by Chandy, Misra, and Bryant, has usually been discussed in the context of distributed memory systems. Also, null messages have normally been associated with this approach for deadlock avoidance. This paper presents a new implementation of the CMB protocol designed for shared memory multiprocessor systems. We have successfully used this protocol, which we call the CMB-SMP protocol, to achieve useful speedups in a manufacturing simulation application, despite the fine granularity of event processing. The implementation eliminates the need for sending null messages, without causing deadlock in the simulation. Double buffering is also used to reduce the overhead of buffer locking. It is shown that the CMB-SMP protocol outperforms a synchronous super-step protocol in terms of the speedups achieved. The paper also discusses the cache behaviour of the CMB-SMP protocol implementation since cache misses are very expensive with today's high clock speed processors.     

Removing dead transitions in timed-arc Petri nets

Timed-arc Petri nets (TAPNs) are a timed extension of Petri nets where tokens are assigned an age indicating the time elapsed from its creation, and PT-arcs (place to transition arcs) are labelled with time intervals that are used to restrict the age of the tokens that can be used to fire the adjacent transition. This is a rather pathological model, as reachability is undecidable, whereas some other known properties of Petri nets, like boundedness, coverability and even termination, are decidable. This article focuses on the problem of detecting dead transitions, i.e. transitions that can be removed from the model since they can never become enabled. We prove that this problem is decidable for TAPNs with natural times, and we present an algorithm that can be used to find dead transitions in the particular case of 1-safe TAPNs.     

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.     

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.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

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.     

Fluid stochastic Petri nets: Theory,applications, and solution techniques

In this paper we introduce a new class of stochastic Petri nets in which one or more places can hold fluid rather than discrete tokens. We define a class of fluid stochastic Petri nets in such a way that the discrete and continuous portions may affect each other. Following this definition we provide equations for their transient and steady-state behavior. We present several examples showing the utility of the construct in communication network modeling and reliability analysis, and discuss important special cases. We then discuss numerical methods for computing the transient behavior of such nets. Finally, some numerical examples are presented and evidence of the accuracy of the fluid approximation is given.     

Preventing deadlock during anisotropic 2D mesh adaptation in hp-adaptive FEM

The paper presents a grammar for anisotropic two-dimensional mesh adaptation in hp-adaptive Finite Element Method with rectangular elements. Expressing mesh transformations as grammar productions is useful for concurrency analysis thanks to exhibiting the partial causality order (Lamport relationship) between atomic operations. It occurs that a straightforward approach to modeling this process via grammar productions leads to potential deadlock in h-adaptation of the mesh. This fact is shown on a Petri net model of an exemplary adaptation. Therefore auxiliary productions are added to the grammar in order to ensure that any sequence of productions allowed by the grammar does not lead to a deadlock state. The fact that the enhanced grammar is deadlock-free is proven via a corresponding Petri net model. The proof has been performed by means of reachability graph construction and analysis. The paper is concluded with numerical simulations of magnetolluric measurements where the deadlock problem occurred.     

基于随机Petri网理论的邮轮灾难事故预警机制研究

邮轮安全事故的严重后果凸显了预警机制的重要性。本文采用集合结构对邮轮安全事故的致因进行分析与描述,以此建立邮轮预警指标体系,通过对指标体系的分析并结合船舶航行实践,设计了邮轮安全预警机制。本研究综合考虑气象条件、通航环境对邮轮航行安全的影响,通过引入与构建随机Petri网理论模型,结合“东方之星”轮沉船事故,对恶劣气象条件下邮轮的安全预警机制进行仿真分析。实验显示风级、雨量等级增长速率与邮轮面临灾难危机的概率之间存在非线性关系,且浪级、风级及雨量等级对邮轮安全预警状态有交互作用,并产生了三者交互作用下的预警临界曲面,为邮轮是否可继续安全航行提供定量分析与决策支持。     

Approaching minimum time control of timed continuous Petri nets

This paper considers the problem of controlling timed continuous Petri nets under infinite server semantics. The proposed control strategy assigns piecewise constant flows to transitions in order to reach the target state. First, by using linear programming, a method driving the system from the initial to the target state through a linear trajectory is developed. Then, in order to improve the time of the trajectory, intermediate states are added by means of bilinear programming. Finally, in order to handle potential perturbations, we develop a closed loop control strategy that follows the trajectory computed by the open loop control by calculating a new state after each time step. The algorithms developed here are applied to a manufacturing system.     

About the stochastic and continuous Petri nets equivalence in the long run

Reliability analysis is often based on stochastic discrete event models like stochastic Petri nets (SPNs). For large dynamical systems with numerous components, the analytical expression of the SPNs steady state is full of complexities because of the combinatory explosion with discrete models. Moreover, the estimation of mean markings thanks to simulations is time consuming in case of rare events. For these reasons, Petri net fluidification may be an interesting alternative to provide a reasonable estimate of the asymptotic behavior of stochastic processes. Unfortunately, the steady states of SPNs and timed continuous Petri nets (contPNs) with the same structure, same initial marking and same firing rates are mainly often different. The region of SPN steady states (when firing rates are defined in a polyhedral area) contrasts with that of contPN ones. The purpose of this paper is to illuminate this issue in taking advantage of the piecewise-affine hybrid structure of contPNs. Regions and critical regions are defined in the marking space in order to characterize this structure. Based on this characterization, the main contribution is to propose a transformation of the considered SPN into a contPN with the same structure, modified firing rates and homothetic initial marking so that the corrected contPN converges partially to the same mean marking than the SPN. Consequently, a global understanding of an SPN steady state can be obtained according to the corrected contPN.     

A comprehensive approach of planning and scheduling based on petri nets

The main results available on the use of black-and-white Petri nets for modelling, planning and scheduling manufacturing systems are presented. In the first part of the paper, the basics of Petri nets necessary to understand the subsequent presentation are introduced. Particular attention is paid to event graphs, a particular type of Petri nets used for modelling and evaluating ratio-driven systems. The second part of the paper is devoted to ratio-driven systems, their modelling and their scheduling. Job-shops, assembly systems, and KANBAN systems are used to illustrate this section. Finally, the general case is investigated of manufacturing systems subject to changing demands. An approach based on conflict-free Petri nets with input and output transitions is proposed for planning and scheduling this type of system.     

Scheduling of piecewise constant product flows: A Petri net approach

Scheduling a manufacturing system is usually an NP-hard problem. This means that only heuristic algorithms can be used to provide near-optimal schedules. In this paper, we show that a manufacturing system can be modeled using a particular type of Petri nets, called Controllable-Output nets, or CO nets for short. These Petri net models are then used to introduce a two-stage scheduling algorithm for problems in which the product flows can be considered as piecewise constant. The first stage consists of distributing the workload among the resources. The second stage derives a schedule from the resource workload. The deterministic case is considered. Numerical results are proposed.     

一种基于Petri网的工程管理模型

提出了用Petri网建立工程管理模型.为了适应在工程管理中的应用,对Petri网理论进行了扩充,提出了判定库所的概念,设计了托肯移动的规则,使用优先矩阵描述了托肯的移动.     

Behavior prediction of washing system in a paper industry using GA and fuzzy lambda–tau technique

Availability analysis has been an important issue in the design field of any Industrial system as the system structure has become more complicated. Also, the system availability is affected by many factors such as design, manufacturing, installation, etc., and so it may be extremely difficult to model, analyze and predict the failure behavior of the system. The purpose of this paper is to develop a new approach for computing various performance measures, namely reliability, availability, MTBF (mean time between failures), ENOF (expected number of failures), failure rate and repair time, for any industrial system. In the proposed approach, the failure rates and repair times of all constituent components are obtained using genetic algorithms and then various performance measures are computed using fuzzy lambda–tau methodology. Washing system, the major part of paper industry is the subject of study. The interactions among the working components are modeled using Petri nets. Failure and repair rates are represented using triangular fuzzy numbers as they allow expert opinion, linguistic variables, operating conditions, uncertainty and imprecision in reliability information to be incorporated into system model. Based on calculated reliability parameters, a structured framework has been developed that may help the maintenance engineers to analyze and predict the system behavior.     

Epistemic irrelevance in credal nets: The case of imprecise Markov trees

We focus on credal nets, which are graphical models that generalise Bayesian nets to imprecise probability. We replace the notion of strong independence commonly used in credal nets with the weaker notion of epistemic irrelevance, which is arguably more suited for a behavioural theory of probability. Focusing on directed trees, we show how to combine the given local uncertainty models in the nodes of the graph into a global model, and we use this to construct and justify an exact message-passing algorithm that computes updated beliefs for a variable in the tree. The algorithm, which is linear in the number of nodes, is formulated entirely in terms of coherent lower previsions, and is shown to satisfy a number of rationality requirements. We supply examples of the algorithm’s operation, and report an application to on-line character recognition that illustrates the advantages of our approach for prediction. We comment on the perspectives, opened by the availability, for the first time, of a truly efficient algorithm based on epistemic irrelevance.     

A single server model for packetwise transmission of messages

We study a discrete-time single-server queue where batches of messages arrive. Each message consists of a geometrically distributed number of packets which do not arrive at the same instant and which require a time unit as service time. We consider the cases of constant spacing and geometrically distributed (random) spacing between consecutive packets of a message. For the probability generating function of the stationary distribution of the embedded Markov chain we derive in both cases a functional equation which involves a boundary function. The stationary mean number of packets in the system can be computed via this boundary function without solving the functional equation. In case of constant (random) spacing the boundary function can be determined by solving a finite-dimensional (an infinite-dimensional) system of linear equations numerically. For Poisson- and Bernoulli-distributed arrivals of messages numerical results are presented. Further, limiting results are derived.     

Parallel permit grammars and some graph representations of Petri nets

The graph of a set grammar is introduced in such a way that each set rule of the grammar is represented by a cartesian subgraph of it. The correspondence between cartesian subgraphs and transitions of Petri nets (which satisfy the axiom of extensionality) is established. The set grammars with input (initial) and output (terminal) elements are studied in an analogy to Chomsky's string grammars and their strong equivalence. Permit rules and parallel permit rules are introduced in such a way that parallel permit grammars are more general tools than Petri nets themselves, because the equivalence between homogeneous parallel permit grammars and set grammars (and Petri nets) is proved.