دانلود کتاب Stochastic Petri Nets

Petri nets have been used in operations research and the mathematical modeling of discrete-event systems ever since they were invented in the early 1960s. The applications of Petri nets are immense, having permeated many different fields, some of these being network engineering, queueing theory, and automated manufacturing. This book gives a very clear introduction to the mathematical theory of stochastic Petri nets (SPNs), which were invented in the 1980s, and which are used to model discrete-event systems which undergo stochastic state transitions occur only at an increasing sequence of random times. The book should be viewed as a monograph rather than a textbook since there are no exercises (unfortunately), but readers could still gain a good understanding of stochastic Petri nets by its perusal. One could make up for the lack of exercises by perhaps thinking of new applications of SPNs. My interest in the book was motivated by my wish to use SPNs to model network and application servers, poker games, and machine curiosity and decision-making in artificial intelligence. I only read chapters 1-5 and chapter 9, and so my review will be confined to these.

The author defines an SPN as a graph composed of a finite set of `places’ and a finite set of `transitions’. A subset of these transitions are taken to be `immediate’ transitions, and the set of places consists of normal input places, inhibitor input places, and output places, given a particular transition. A (countable) set of markings denoting the number of `tokens’ in a place is also defined. In chapter 2, the author gives several examples of SPNs, such as a producer-consumer system, a queue with batch arrivals, a token ring network, a flexible manufacturing system, a particle counter, and a slotted ring network. Some of these examples illustrate the use of marking-dependent transitions, and the fact that SPN representations of discrete-event systems are not unique. The author also briefly discusses the SPSIM simulation language for SPNs. Also discussed briefly are restricted SPNs, wherein the marking set is not specified explicitly, and an accompanying notion of reachability.

The marking process of an SPN is described in terms of an underlying general state-space Markov chain in chapter 3. This allows sample paths to be generated, and one can utilize the results from the theory of Markov chains to study the long-time behavior of SPNs and define performance measures for them. The author gives an explicit algorithm for generating sample paths for the underlying chain and using this, for the marking process itself. This is followed by a discussion of sufficient conditions needed to guarantee infinite lifetimes for the marking process, thus avoiding “explosions”, wherein an infinite number of marking changes occur in a finite time interval with probability 1. The author also gives criteria for showing when the marking process is a time-homogeneous continuous-time Markov chain.

In chapter 4, the author discusses to what extent discrete-event systems can be modeled within the SPN framework. He does not answer this in general, claiming that it cannot be, but instead compares the modeling power of SPNs to that of generalized semi-Markov processes (GSMPs). These systems differ, he says, in their event-scheduling and state-transition mechanisms, and the form of the state-space. GSMPs are more general than SPNs, but the author shows that SPNs have at least the modeling power of GSMPs, in that for any GSMP there exists an SPN that `strongly mimics’ it: there is a marking process such that both of the processes have the same finite-dimensional distributions using an appropriate mapping between the underlying state spaces. Conversely, for any SNP with both timed and immediate transitions, the author shows that there exists a GSMP that strongly mimics the marking process of the SPN. A very brief but interesting discussion on the ability of Petri nets to mimic a Turing machine is given in the notes to the chapter.

The author turns his attention to stability issues in chapter 5. This attention is dictated by the fact the in order for SPNs to be practical for simulation purposes, their marking processes must have well-defined time-average limits. The stability of an SPN is shown, as expected, with reference to the underlying state-space Markov chain used to define the marking process. In this context, the author uses the notion of “Harris recurrence”, wherein Markov chains that have this property repeatedly return to a dense, compact set of states. Criteria for establishing Harris recurrence are given throughout the chapter. Readers will have to know some amount of measure theory in order to read this chapter. The author gives a brief review of it in one of the appendices.

Chapter 9 covers colored stochastic Petri nets (CSPNs), which have myriads of applications and so a thorough reading of it is essential for those involved in those applications. As the author explains, associating colors with tokens and transitions will allow the simplification of Petri nets that have large numbers of places and transitions. The tokens are removed and deposited deterministically, and so CSPNs have less modeling power than SPNs. The tradeoff though is the conciseness of the CSPNs. Noted in the definition of CSPNs is the presence of input and output incidence functions, which determine when a transition is enabled in a color and the number of tokens removed and deposited when a transition fires in a color. Several examples of CSPNs are discussed, including machine repair, a token ring network, a system of cyclic queues with feedback, and one dealing with customer complaint processing. As was the case for SPNs, the marking process of a CSPN is defined in terms of a general state-space Markov chain that describes the CSPN at successive marking changes. The author studies the stability of CSPNs , and considers what are called “symmetric” CSPNs, which are those that remain the same under permutations of its set of colors. The mathematical analysis of symmetric CSPNs is, as expected, simpler than non-symmetric CSPNs.