Encoding the dynamics of deterministic systems

We present a model for the dynamics of discrete deterministic systems, based on an extension of the Petri nets framework. Our model relies on the definition of a priority relation between conflicting transitions, which is encoded by orienting the edges of a transition conflict graph. We provide a characterization in terms of a local consistency condition of those deterministic systems whose dynamic behavior can be encoded using our approach. Finally, we consider the problem of recognizing when an orientation of the transition conflict graph is valid for encoding the dynamic behavior of a 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.     

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.     

An upper bound on the cycle time of a stochastic marked graph using incomplete information on the transition firing time distributions

Stochastic marked graphs, a special class of stochastic timed Petri nets, are used for modelling and analyzing decision-free dynamic systems with uncertainties in timing. The model allows evaluating the performance of such systems under a cyclic process. Given the probabilistic characteristics of the transition times, the cycle time of the system can be determined from the initial marking. In this contribution, we compute an upper bound on the cycle time of a stochastic marked graph in case the probabilistic characteristics of the transition times are not fully specified.     

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.     

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.     

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.     

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.     

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.     

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.     

Hybrid and Hybrid Adaptive Petri Nets: On the computation of a Reachability Graph

Petri Nets (PNs) constitute a well known family of formalisms for the modelling and analysis of Discrete Event Dynamic Systems (DEDS). As general formalisms for DEDS, PNs suffer from the state explosion problem. A way to alleviate this difficulty is to relax the original discrete model and deal with a fully or partially continuous model. In Hybrid Petri Nets (HPNs), transitions can be either discrete or continuous, but not both. In Hybrid Adaptive Petri Nets (HAPNs), each transition commutes between discrete and continuous behaviour depending on a threshold: if its load is higher than its threshold, it behaves as continuous; otherwise, it behaves as discrete. This way, transitions adapt their behaviour dynamically to their load. This paper proposes a method to compute the Reachability Graph (RG) of HPNs and HAPNs.     

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.     

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.     

工程问题的Petri网模型及其分析

提出一种工程问题的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.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

Language Constructs for Modeling Stochastic Linear Programs

This paper introduces two tokens of syntax for algebraic modeling languages that are sufficient to model a wide variety of stochastic optimization problems. The tokens are used to declare random parameters and to define a precedence relationship between different random events. It is necessary to make a number of assumptions in order to use this syntax, and it is through these assumptions, which cover the areas of model structure, time, replication, and stages, that we can attain a deeper understanding of this class of problem.     

ON/OFF strategy based minimum-time control of continuous Petri nets

This paper focuses on the target marking control problem of timed continuous Petri nets (TCPN), aiming to drive the system from an initial state to a desired final one. This problem is similar to the set-point control problem in a general continuous-state system. In a previous work, a simple and efficient ON/OFF controller was proposed for Choice-Free nets, and it was proved to be minimum-time (Wang, 2010). However, for general TCPN the ON/OFF controller may bring the system to “blocking” situations due to its “greedy” firing strategy, and the convergence to the final state is not ensured. In this work the ON/OFF controller is extended to general TCPN by adding more “fair” strategies to solve conflicts in the system: the ON/OFF+ controller is obtained by forcing proportional firings of conflicting transitions. Nevertheless, such kind of controller might highly slow down the system when transitions have flows of different orders of magnitude, therefore a balancing process is introduced, leading to the B-ON/OFF controller. A third approach introduced here is the MPC-ON/OFF controller, a combination of Model Predictive Control (MPC) and the ON/OFF strategy; it may achieve a smaller number of time steps for reaching the final states, but usually requires more CPU time for computing the control laws. All the proposed extensions are heuristic methods for the minimum-time control and their convergences are proved. Finally, an application example of a manufacturing cell is considered to illustrate the methods. It is shown that by using the proposed controllers, reasonable numbers of time steps for reaching the final state can be obtained with low computational complexity.