Stochastic Petri nets with product form equilibrium distributions.
James L. Coleman · Adelaide Research & Scholarship (AR&S) (University of Adelaide) · 1993
Networks of queues with product-form equilibrium distributions are well established and have applications in a wide range of fields. With few exceptions these networks provide the only efficient means of analysis in large systems. The advantage that the product-form distribution provides is the abundance of efficient computational algorithms for calculating various performance measures either directly or through the normalising constant. These algorithms help to overcome the state space explosion problem which is inherent in large networks. For this reason large amounts of effort have been invested by researchers in extending the set of queueing networks that have this special form. In recent years the theory of product-form queueing networks has evolved beyond the single movement restriction to include networks of queues which allow batch movement of customers and correlated routing. Petri nets, a modelling tool attracting increasing interest, can be used to model such networks. Numerical algorithms based on the product-form equilibrium distribution of these batch movement networks have not been considered by many researchers. The state space explosion problem still exists for these systems, as it does for Petri nets in general. Increased effort is now being devoted to finding classes of Petri nets which possess product-form equilibrium distributions, and associated algorithms for evaluating performance measures. The purpose of this thesis is threefold: To survey the product-form results and associated algorithms which currently exist in Petri nets, extend the product-form results for certain classes of Petri nets, and derive and survey algorithms for evaluating normalising constants in product-form stochastic Petri nets. Chapter 1 introduces Petri nets, their time extended counterparts, and some related issues. The chapter concludes with a brief account of other Petri net extensions. Chapter 2 considers the analysis of timed and untimed Petri nets. Various classes of time extended nets are discussed followed by a survey of existing product-form results. In Chapter 3 we extend the knowledge of a specific class of product-form Petri nets initially proposed by other authors. In the remaining chapters we consider several methods for evaluating the normalising constants for product-form networks in general by identifying the important factors for the existence of convolution type algorithms. In the conclusion we present some ideas for further research which arises naturally from the work contained in this thesis. Throughout the thesis, vectors are denoted by bold face characters, matrices by bold face capitals and sets by curly capitals. In Appendix B we summarise the notation and symbols used.