Timed Petri nets and prediction to improve the Chandy–Misra conservative-distributed simulation

The main contribution of this paper shows that distributed simulation of timed Petri nets (TPN) can take advantage of their structure to obtain a significant lookahead which is usually difficult to compute with other models. In this paper, we introduce a conservative-distributed simulation with a reduced number of control messages and without deadlock resolution. This approach is based on a part of optimism computed on the prediction time each logical process can determine for its advancement. Obviously this prediction time must be computed easily according to the structure of the simulated logical process. Timed Petri nets meet these requirements and we use their structure to evaluate the depth of the prediction. In conservative-distributed simulation, it is known that the deeper the prediction, the better the efficiency of the simulation. We present a method we have devised based on channel time prediction. We compare its performance to the Chandy–Misra method and to some related Petri nets approaches (Chiola). Experiments carried out on Sun stations show that there is more parallelism and a reduced number of null messages in the cases of deadlock avoidance. Moreover, considering deadlock detection and resolution technique we observe that in many cases no deadlock occurs with less control messages.     

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.     

Modelling,Synthesis, and Simulation of Supervisory Process Control Systems

Modelling, synthesis, and simulation issues of the supervisory systems in process control are investigated in the paper. Petri nets are used as a basic modelling framework for the supervisory part of the system. It is shown how the final verification effort can be minimised by applying formal synthesis methods. A straightforward approach to the industrial implementation of the developed solutions is suggested by means of sequential function chart representation. A batch process cell case study is used to illustrate the described concepts. Corresponding continuous and discrete event models of the process cell units are developed and a co-ordinating supervisor is designed by the method of place invariants. The system is simulated by the continuous simulation tool Matlab-Simulink, which is enhanced for simulation of the sequential control logic represented by sequential function chart.     

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.     

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.     

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.     

基于GSPN的实施延迟策略生产系统建模与性能分析

延迟策略是协调市场需求变化的绝对性和生产系统相对稳定性矛盾的一个重要战略手段。为分析实施延迟策略生产系统的性能,利用随机广义Petri-net(GSPN)的建模分析方法,并根据GSPN与马尔科夫链的同构关系,将GSPN模型转化成为等价的马尔科夫链模型。通过马尔科夫链及相关数学方法获得实施延迟策略生产系统的主要性能指标。该方法不仅可以分析实施延迟策略生产系统的整体性能,而且能够对系统的各个环节运作效率做出定量分析。最后,通过算例分析验证了该方法的科学性与有效性,丰富了延迟策略研究方面的方法理论。     

Categorical Approach to Horizontal Structuring and Refinement of High-Level Replacement Systems

Based on the well-known theory of high-level replacement systems – a categorical formulation of graph grammars – we present new results concerning refinement of high-level replacement systems. Motivated by Petri nets, where refinement is often given by morphisms, we give a categorical notion of refinement. This concept is called Q-transformations and is established within the framework of high-level replacement systems. The main idea is to supply rules with an additional morphism, which belongs to a specific class Q of morphisms. This leads to the new notions of Q-rules and Q-transformations. Moreover, several concepts and results of high-level replacement systems are extended to Q-transformations. These are sequential and parallel transformations, union, and fusion, based on different colimit constructions. The main results concern the compatibility of these constructions with Q-transformations that is the corresponding theorems for usual transformations are extended to Q-transformations. Finally, we demonstrate the application of these techniques for the special case of Petri nets to a case study concerning the requirements engineering of a medical information system.     

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.     

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.     

Simulation-based optimisation of wastewater flow and composition for on-site treatment in the food and beverage industry utilising reference nets in combination with genetic algorithms

This study introduces the concept of computer modelling and simulation of complex bioprocesses and systems using an approach that combines the reference net formalism with machine learning and optimisation techniques. Reference nets are an extension of high level Petri Nets, which can be used as a central visualisation and modelling tool. The net-in-net paradigm used by reference nets makes it possible to model complex processes, such as those found in the food and beverage industry. A plugin/interface system based on the java programming language allows implementation of advanced mathematical modelling techniques at specific points in entire system simulations. Separate optimisation tools can also run and modify existing reference net models for fast solutions to efficiency problems. We present an example system that simulates a specific section of a beer brewery using the reference net formalism, which is optimised using a genetic algorithm. We show in detail how the different software packages can be combined for a simulation based optimisation approach. The optimisation technique specifically addresses the wastewater pollution load in regard to its chemical oxygen demand. A beer brewery was chosen as an example for this study due to the constantly increasing requirements to lower energy and water consumption in this industry. One possibility to lower the energy and water demands is to effectively treat wastewater produced by the brewery, which can introduce cost savings by providing recycled water and biogas. Most approaches to wastewater treatment are end-of-pipe solutions that do not consider the brewery as a whole. A brewery contains many processes that can be running concurrently and interacting with one another (e.g. brewing, clean-in-place and bottling) with each process producing varying amounts of wastewater with different pollution loads. Optimisation of the scheduling of the different processes with respect to the wastewater production will allow for more effective wastewater treatment, and therefore cost and energy savings. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Randomized formal systems for specifying discrete stochastic models

This paper presents a method, based on the mathematical concept of formal systems, for writing high-level specifications of discrete stochastic models. This method is completely formal, suitable for information processing by computer and generally applicable. Moreover, it unifies analytic and statistical techniques. Concepts and notions are developed informally by means of four examples from the field of Petri nets and queueing systems. Processing algorithms (generating state-transition graphs, computing Markovian transition probabilities and simulating the specified models) are outlined. Basically, this method yields a “constructive” approach to discrete stochastic modelling.     

Categorical principles,techniques and results for high-level-replacement systems in computer science

The aim of this paper is to give an introduction how to use categorical methods in a specific field of computer science: The field of high-level-replacement systems has its roots in the well-established theories of formal languages, term rewriting, Petri nets, and graph grammars playing a fundamental role in computer science. More precisely, it is a generalization of the algebraic approach to graph grammars which is based on gluing constructions for graphs defined as pushouts in the category of graphs. The categorical theory of high-level-replacement systems is suitable for the dynamic handling of a large variety of high-level structures in computer science including different kinds of graphs and algebraic specifications. In this paper we discuss the basic principles and techniques from category theory applied in the field of high-level-replacement systems and present some basic results together with the corresponding categorical proof techniques.     

A two-level hedging point policy for controlling a manufacturing system with time-delay,demand uncertainty and extra capacity

This paper focuses on the production control of a manufacturing system with time-delay, demand uncertainty and extra capacity. Time-delay is a typical feature of networked manufacturing systems (NMS), because an NMS is composed of many manufacturing systems with transportation channels among them and the transportation of materials needs time. Besides this, for a manufacturing system in an NMS, the uncertainty of the demand from its downstream manufacturing system is considered; and it is assumed that there exist two-levels of demand rates, i.e., the normal one and the higher one, and that the time between the switching of demand rates are exponentially distributed. To avoid the backlog of demands, it is also assumed that extra production capacity can be used when the work-in-process (WIP) cannot buffer the high-level demands rate. For such a manufacturing system with time-delay, demand uncertainty and extra capacity, the mathematical model for its production control problem is established, with the objective of minimizing the mean costs for WIP inventory and occupation of extra production capacity. To solve the problem, a two-level hedging point policy is proposed. By analyzing the probability distribution of system states, optimal values of the two hedging levels are obtained. Finally, numerical experiments are done to verify the effectiveness of the control policy and the optimality of the hedging levels.     

Representation and analysis of behavior for multiprocess systems by using stochastic Petri nets

This paper proposes a new approach to visually represent the behavior of multiprocess in a computer network system using stochastic Petri net (SPN) and an aggregate approach of SPN and Markov renewal process (MRP) to conduct behavior analysis and performance evaluation for the system. SPN is employed because of its highly visual nature that can give insight into the nature of the modeled system and because of its expressive power for an exponentially distributed event. In order to increase the analytical power of the SPN model, MRP is introduced and an embedded transference probability matrix is applied to obtain the steady-state solution of the model, from which it is possible to obtain automatically the performance measures of the multiprocess computer network system.     

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.     

Analytical approximations to predict performance measures of markovian type manufacturing systems with job failures and parallel processing

Manufacturing or service systems with multiple product classes, job circulation due to random failures, resources shared between product classes, and some portions of the manufacturing or assembly carried in series and the rest in parallel are commonly observed in real-life. The web server assembly is one such manufacturing system which exhibits the above characteristics. Predicting the performance measures of these manufacturing systems is not an easy task. The primary objective of this research was to propose analytical approximations to predict the flow times of the manufacturing systems, with the above characteristics, and evaluate its accuracy. The manufacturing system is represented as a network of queues. The parametric decomposition approach is used to develop analytical approximations for a system with arrival and service rates from a Markovian distribution. The results from the analytical approximations are compared to simulation models. In order to bridge the gap in error, correction terms were developed through regression modeling. The experimental study conducted indicates that the analytical approximations along with the correction terms can serve as a good estimate for the flow times of the manufacturing systems with the above characteristics.