Stochastic Petri Nets: Modelling, Stability, Simulation Peter J. Haas Springer Springer Series in Operations Research Editors: Peter W. Glynn Stephen M. Robinson Peter J. Haas Stochastic Petri Nets Modelling, Stability, Simulation With 71 Illustrations PeterJ.Haas IBMResearchDivision SanJose,CA95120-6099 USA [email protected] SeriesEditors: PeterW.Glynn StephenM.Robinson DepartmentofManagementScience DepartmentofIndustrialEngineering andEngineering UniversityofWisconsin–Madison TermanEngineeringCenter Madison,WI53706-1572 StanfordUniversity USA Stanford,CA94305-4026 USA LibraryofCongressCataloging-in-PublicationData Haas,PeterJ.(PeterJay) StochasticPetrinets:modelling,stability,simulation/PeterJ.Haas. p.cm.—(Springerseriesinoperationsresearch) Includesbibliographicalreferencesandindex. ISBN0-387-95445-7(alk.paper) 1.Petrinets. 2.Stochasticanalysis. I.Title. II.Series. QA267.H32002 511.3—dc21 2002019559 Printedonacid-freepaper. 2002Springer-VerlagNewYork,Inc. All rights reserved. This work may not be translated or copied in whole or in part without the writtenpermissionofthepublisher(Springer-VerlagNewYork,Inc.,175FifthAvenue,NewYork, NY10010,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysis.Use inconnection withany formof informationstorageand retrieval,electronic adaptation,computer software,orbysimilarordissimilarmethodologynowknownorhereafterdevelopedisforbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if theyarenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornot theyaresubjecttoproprietaryrights. ManufacturingsupervisedbyJeromeBasma. Camera-readycopypreparedfromtheauthor’sLaTeX2efilesusingSpringer’smacros. PrintedandboundbyMaple-VailBookManufacturingCo.,York,PA. PrintedintheUnitedStatesofAmerica. 9 8 7 6 5 4 3 2 1 ISBN0-387-95445-7 SPIN10867072 Springer-Verlag NewYork Berlin Heidelberg AmemberofBertelsmannSpringerScience+BusinessMediaGmbH Preface Thisbookwasmotivatedbyadesiretobridgethegapbetweentwoimpor- tant areas of research related to the design and operation of engineering andinformationsystems.Thefirstareaconcernsthedevelopmentofmathe- maticaltoolsforformalspecificationofcomplexprobabilisticsystems,with an eye toward subsequent simulation of the resulting stochastic model on a computer. The second area concerns the development of methods for analysis of simulation output. Researchonmodellingtechniqueshasbeendrivenbytheever-increasing sizeandcomplexityofcomputer,manufacturing,transportation,workflow, and communication systems. Many engineers and systems designers now recognize that the use of formal models has a number of advantages over simply writing complicated simulation programs from scratch. Not only is it much easier to generate software that is free of logical errors, but variousqualitativesystemproperties—absenceofdeadlock,impossibilityof reaching catastrophic states, and so forth—can be verified far more easily for a formal model than for an ad-hoc computer program. Indeed, certain system properties can sometimes be verified automatically. Our focus is on systems that can be viewed as making state transitions when events associated with the occupied state occur. More specifically, we consider discrete-event systems in which the stochastic state transi- tions occur only at an increasing sequence of random times. The “Bedi- enungsprozess”(serviceprocess)framework,developedbyKo¨nig,Matthes, andNawrotzkiinthe1960sandearly1970s,providedthefirstsetofbuild- ingblocksforformalmodellingofgeneraldiscrete-eventsystems.Themod- ern incarnation of the Bedienungsprozess is the “generalized semi-Markov viii Preface process” (gsmp). Although useful for a unified theoretical treatment of discrete-event stochastic systems, the gsmp framework is not always well suited to practical modelling tasks. In particular, the modeller is forced to specify the “state of the system” directly as an abstract vector of random variables. Such a specification can be highly nontrivial: the system state definition must be as concise as possible for reasons of efficiency, but must also contain enough information so that (1) a sequence of state transitions and transition times can be generated during a simulation run and (2) the system characteristics of interest can be determined from such a sequence. StochasticPetrinets(spns),introducedinthe1980s,areveryappealingin thattheynotonlyhavethesamemodellingpowerasgsmps(seeChapter4) but also admit a graphical representation that is well suited to top-down and bottom-up modelling of complex systems. Inparalleltotheseadvancesinmodelling,arigoroustheoryofsimulation output analysis has been developed over the past 25 years. Much of this theorypertainstotheproblemofobtainingpointestimatesandconfidence intervals for long-run performance measures of interest. Such point and in- terval estimates are typically used to compare alternative system designs or operating policies. These estimates also form the basis for simulation- based optimization procedures. Confidence intervals can be particularly difficult to obtain, but are necessary to distinguish true differences in sys- tem behavior from mere random fluctuations. The basic idea is to view each simulation run as the sample path of a precisely defined stochastic process. Point estimates and confidence intervals are then established by appealing to limit theorems for such processes. Unfortunately,manyoftheresultsintheoutput-analysisliteraturehave not been provided in a form that is directly useful to practicing simula- tion analysts. Typically, a specified estimation or optimization procedure is shown to produce valid results if the output process of the simulation has specified stochastic properties—for example, obeys specified limit the- oremsorhasasequenceofregenerationpoints.Verificationoftherequired properties for a specific (and usually complicated) simulation model often turnsouttobeaformidabletask.Indeed,whenstudyingthelong-runper- formance of a specified system, it is often hard even to establish that the simulation problem at hand is well posed in that the system is stable and long-run performance measures actually exist. This book is largely concerned with making a connection between mod- elling practice and output-analysis theory. We illustrate the use of the spn buildingblocksformodellinganddiscussthebasicprinciplesthatunderlie estimation procedures such as the regenerative method and the method of batch means. Tying these topics together are verifiable conditions on the buildingblocksofanspnunderwhichthenetisstableovertimeandspec- ifiedestimationproceduresarevalid.Ourtreatmenthighlightsperhapsthe mostappealingaspectofspns:theformalismispowerfulenoughtopermit Preface ix accurate modelling of a wide range of real-world systems and yet simple enough to be amenable to stability and convergence analysis. When studying the literature related to spns, one quickly encounters a multitude of spn variants as well as a variety of other frameworks for modelling discrete-event systems. Partly for this reason, we provide—in additiontoourotherresults—methodsforcomparingthemodellingpower ofdifferentdiscrete-eventformalisms.Althoughweemphasizethecompari- sonofspnswithgsmps,ourgeneralapproachprovidesameansformaking principledchoicesbetweenalternativemodellingframeworks.Ourmethod- ology can also be used to extend recurrence results and limit theorems from one framework to another. This latter application of our modelling- power theorems both simplifies the proofs of certain results for spns and makes the material in this book relevant not only to spns but also to the general study of discrete-event systems. Indeed, this book can be viewed as a survey of some fundamental stability, convergence, and estimation is- sues for discrete-event systems, using spns as a convenient and appealing framework for the discussion. Our view of spns differs from many in the literature in that we focus on the close relationship between spns and gsmps. To some extent this viewpointisnecessary:becauseweallowcompletelyarbitraryclock-setting distributions, the underlying marking process of an spn is not, in general, a Markov or semi-Markov process. Our viewpoint also is advantageous, in that it lets us exploit the many powerful results that have been es- tablished for both gsmps and their underlying general state-space Markov chains.Weemphasize,however,thatspnshaveuniquefeaturesthatrequire extension—rather than straightforward adaptation—of results for gsmps. The prime example is given by “immediate transitions,” which have no counterpartinthegsmpmodelandleadtoavarietyofmathematicalcom- plications. Thepresentationisself-contained.Knowledgeofbasicprobabilitytheory, statistics, and stochastic processes at a first-year graduate level is needed to understand the theory and examples. We occasionally use results from the theory of Markov chains on a general state space—most of the techni- cal complexities for such chains can safely be glossed over in our setting, and the results we use are directly analogous to classical results for chains with finite or countably infinite state spaces. The Appendix summarizes the key mathematical results used in the text. To increase accessibility, we suppress measure-theoretic notation whenever possible—the Appendix containsadiscussionofbasicmeasure-theoreticconceptsandtheirrelation to the terminology used in the text. The more applied reader will wish to focus primarily on the discussion of modelling techniques and on spe- cific estimation methods. These topics are covered primarily in Chapter 1, Chapter 2, Section 3.1.3, Section 6.3, Sections 7.2.2–7.2.4 and 7.3.3–7.3.5, Sections 8.1, 8.2.2–8.2.4, 8.3.2, and 8.3.3, and Sections 9.1 and 9.3. x Preface IamgratefultotheIBMCorporationforsupportofthisworkandforthe resources of the Almaden Research Center. I also wish to thank Thomas Kurtz and the Center for the Mathematical Sciences at the University of Wisconsin–Madison for hospitality during the 1992–1993 academic year. I have benefitted from conversations with many colleagues over the years, including Sigrun Andradottir, James Calvin, Donald Iglehart, Sean Meyn, JosephMitchell,WilliamPeterson,KarlSigman,andMaryVernon.Thanks also are due to the students of the graduate course on simulation that I taught at Stanford University during the 1998–1999 and 2000–2001 aca- demic years. Shane Henderson provided valuable feedback on an initial version of the manuscript. As is apparent from the notes and references in the text, I am deeply indebted to Gerald Shedler, who introduced me to both spns and stochastic simulation and who has co-authored most of the papers I have written on these topics. Perhaps less apparent, but equally important,arethetechnicalinsightsandgeneralencouragementthatIhave received from Peter Glynn. The staff of Springer-Verlag has been exceed- ingly helpful throughout the production of this book—special thanks go to Achi Dosanjh for her help in jump-starting the project and to Kristen Cassereauforhermeticulouscopyediting.Finally,Iwishtothankmywife, Laura, and my children, Joshua and Daniel, for their love, patience, and support. San Jose, California Peter J. Haas March 2002 Contents Preface vii List of Figures xv Selected Notation xix 1 Introduction 1 1.1 Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Stability and Simulation . . . . . . . . . . . . . . . . . . . . 9 1.3 Overview of Topics . . . . . . . . . . . . . . . . . . . . . . . 13 2 Modelling with Stochastic Petri Nets 17 2.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1 Priorities: Producer–Consumer Systems . . . . . . . 24 2.2.2 Marking-dependent Transitions . . . . . . . . . . . . 31 2.2.3 Synchronization: Flexible Manufacturing System . . 41 2.2.4 Resetting Clocks: Particle Counter . . . . . . . . . . 45 2.2.5 Compound Events: Slotted Ring . . . . . . . . . . . 47 2.3 Concise Specification of New-Marking Probabilities . . . . . 49 2.3.1 Transition Firings That Never Occur . . . . . . . . . 50 2.3.2 Numerical Priorities . . . . . . . . . . . . . . . . . . 51 2.4 Alternative Building Blocks . . . . . . . . . . . . . . . . . . 64 xii Contents 3 The Marking Process 69 3.1 Definition of the Marking Process . . . . . . . . . . . . . . . 70 3.1.1 General State-Space Markov Chains . . . . . . . . . 70 3.1.2 Definition of the Continuous-Time Process . . . . . 72 3.1.3 Generation of Sample Paths . . . . . . . . . . . . . . 75 3.2 Performance Measures . . . . . . . . . . . . . . . . . . . . . 77 3.2.1 Simple Time-Average Limits and Ratios . . . . . . . 77 3.2.2 Conversion of Limit Results to Continuous Time . . 78 3.2.3 Rewards and Throughput . . . . . . . . . . . . . . . 81 3.2.4 General Functions of Time-Average Limits . . . . . 86 3.3 The Lifetime of the Marking Process . . . . . . . . . . . . . 87 3.3.1 Absorption into the Set of Immediate Markings . . . 87 3.3.2 Explosions. . . . . . . . . . . . . . . . . . . . . . . . 90 3.3.3 Sufficient Conditions for Infinite Lifetimes . . . . . . 91 3.4 Markovian Marking Processes . . . . . . . . . . . . . . . . . 92 3.4.1 Continuous-Time Markov Chains . . . . . . . . . . . 93 3.4.2 Conditional Distribution of Clock Readings . . . . . 95 3.4.3 The Markov Property . . . . . . . . . . . . . . . . . 102 4 Modelling Power 111 4.1 Generalized Semi-Markov Processes . . . . . . . . . . . . . 113 4.2 Mimicry and Strong Mimicry . . . . . . . . . . . . . . . . . 116 4.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . 116 4.2.2 Sufficient Conditions for Strong Mimicry. . . . . . . 120 4.3 Mimicry Theorems for Marking Processes . . . . . . . . . . 127 4.3.1 Finite-State Processes . . . . . . . . . . . . . . . . . 128 4.3.2 Countable-State Processes . . . . . . . . . . . . . . . 132 4.4 Converse Results . . . . . . . . . . . . . . . . . . . . . . . . 136 5 Recurrence 145 5.1 Drift Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.1.1 Harris Recurrence and Drift . . . . . . . . . . . . . . 146 5.1.2 The Positive Density Condition . . . . . . . . . . . . 150 5.1.3 Proof of Theorem 1.22 . . . . . . . . . . . . . . . . . 157 5.2 The Geometric Trials Technique . . . . . . . . . . . . . . . 164 5.2.1 A Geometric Trials Criterion . . . . . . . . . . . . . 165 5.2.2 GNBU Distributions . . . . . . . . . . . . . . . . . . 166 5.2.3 A Simple Recurrence Argument . . . . . . . . . . . . 172 5.2.4 Recurrence Theorems . . . . . . . . . . . . . . . . . 174 5.2.5 Some Ad-Hoc Recurrence Arguments . . . . . . . . 182 6 Regenerative Simulation 189 6.1 Regenerative Processes . . . . . . . . . . . . . . . . . . . . . 190 6.1.1 Definition of a Regenerative Process . . . . . . . . . 190 6.1.2 Stability of Regenerative Processes . . . . . . . . . . 193