Muutke küpsiste eelistusi

E-raamat: Numerical Methods for Solving Discrete Event Systems: With Applications to Queueing Systems

,
  • Formaat: PDF+DRM
  • Sari: CMS/CAIMS Books in Mathematics 5
  • Ilmumisaeg: 05-Nov-2022
  • Kirjastus: Springer International Publishing AG
  • Keel: eng
  • ISBN-13: 9783031100826
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 67,91 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Numerical Methods for Solving Discrete Event Systems: With Applications to Queueing SystemsSuurem pilt
  • Formaat: PDF+DRM
  • Sari: CMS/CAIMS Books in Mathematics 5
  • Ilmumisaeg: 05-Nov-2022
  • Kirjastus: Springer International Publishing AG
  • Keel: eng
  • ISBN-13: 9783031100826
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

This graduate textbook provides an alternative to discrete event simulation.  It describes how to formulate discrete event systems, how to convert them into Markov chains, and how to calculate their transient and equilibrium probabilities. The most appropriate methods for finding these probabilities are described in some detail, and templates for efficient algorithms are provided. These algorithms can be executed on any laptop, even in cases where the Markov chain has hundreds of thousands of states. This book features the probabilistic interpretation of Gaussian elimination, a concept that unifies many of the topics covered, such as embedded Markov chains and matrix analytic methods.

The material provided should aid practitioners significantly to solve their problems. This book also provides an interesting approach to teaching courses of stochastic processes.





 

Arvustused

This monograph is an exciting addition to the queueing/stochastic processes literature, written by two highly respected senior researchers. The writing is precise and clear. Well-known models are used as examples to illustrate the methods presented. It has a huge number of powerful techniques that are not given sufficient focus elsewhere. This may be one of the best books to introduce graduate students . This monograph is essential for the bookshelf of every serious queueing theorist. (Myron Hlynka, Mathematical Reviews, December, 2023)

1 Basic Concepts and Definitions
1(26)
1.1 The Definition of a Discrete Event System
1(3)
1.1.1 State Variables
2(1)
1.1.2 Events
3(1)
1.2 Markov Chains
4(6)
1.2.1 Discrete-time Markov Chains (DTMCs)
5(3)
1.2.2 Continuous-time Markov Chains (CTMCs)
8(2)
1.3 Random Variables and Their Distributions
10(12)
1.3.1 Expectation and Variance
10(2)
1.3.2 Sums of Random Variables
12(1)
1.3.3 Some Distributions
13(4)
1.3.4 Generating Functions
17(5)
1.4 The Kendall Notation
22(1)
1.5 Little's Law
23(1)
1.6 Sets and Sums
24(3)
Problems
25(2)
2 Systems with Events Generated by Poisson or by Binomial Processes
27(30)
2.1 The Binomial and the Poisson Process
28(1)
2.2 Specification of Poisson Event Systems
29(2)
2.3 Basic Principles for Generating Transition Matrices
31(1)
2.4 One-dimensional Discrete Event Systems
32(5)
2.4.1 Types of One-dimensional Discrete Event Systems
32(1)
2.4.2 The M/M/1/N Queue
33(2)
2.4.3 Birth-Death Processes, with Extensions
35(1)
2.4.4 A Simple Inventory Problem
36(1)
2.5 Multidimensional Poisson Event Systems
37(6)
2.5.1 Types of Multidimensional Systems
38(1)
2.5.2 First Example: A Repair Problem
39(2)
2.5.3 Second Example: Modification of the Repair Problem
41(2)
2.6 Immediate Events
43(4)
2.6.1 An Example Requiring Immediate Events
44(2)
2.6.2 A Second Example with Immediate Events: A Three-way Stop
46(1)
2.7 Event-based Formulations of the Equilibrium Equations
47(2)
2.8 Binomial Event Systems
49(8)
2.8.1 The Geom/Geom/1/N Queue
50(2)
2.8.2 Compound Events and Their Probabilities
52(1)
2.8.3 The Geometric Tandem Queue
53(1)
Problems
54(3)
3 Generating the Transition Matrix
57(18)
3.1 The Lexicographic Code
58(2)
3.2 The Transition Matrix for Systems with Cartesian State Spaces
60(4)
3.3 The Lexicographic Code Used for Non-Cartesian State Spaces
64(4)
3.4 Dividing the State Space into Subspaces
68(2)
3.5 Alternative Enumeration Methods
70(2)
3.6 The Reachability Method
72(3)
Problems
74(1)
4 Systems with Events Created by Renewal Processes
75(20)
4.1 The Renewal Process
76(4)
4.1.1 Remaining Lifetimes
77(1)
4.1.2 The Age Process
78(2)
4.1.3 The Number of Renewals
80(1)
4.2 Renewal Event Systems
80(7)
4.2.1 Description of Renewal Event Systems
81(3)
4.2.2 The Dynamics of Renewal Event Systems
84(3)
4.3 Generating the Transition Matrix
87(8)
4.3.1 The Enumeration of States in Renewal Event Systems
88(1)
4.3.2 Ages Used as Supplementary State Variables
89(2)
4.3.3 Remaining Lifetimes used as Supplementary State Variables
91(2)
4.3.4 Using both Age and Remaining Life as Supplementary State Variables
93(1)
Problems
93(2)
5 Systems with Events Created by Phase-type Processes
95(20)
5.1 Phase-type (PH) Distributions
96(10)
5.1.1 Phase-type Distributions based on Sums, and the Erlang Distribution
97(2)
5.1.2 Phase-type Distributions Based on Mixtures, and the Hyper-exponential Distribution
99(3)
5.1.3 Coxian Distributions
102(1)
5.1.4 Renewal Processes of Phase type
103(1)
5.1.5 Discrete Distributions as PH Distributions
103(3)
5.2 The Markovian Arrival Process (MAP)
106(1)
5.3 PH Event Systems
107(3)
5.3.1 Immediate Events in PH Event Systems
108(1)
5.3.2 Two Examples
109(1)
5.4 Generating the Transition Matrix with Immediate Events
110(5)
Problems
113(2)
6 Execution Times, Space Requirements, and Accuracy of Algorithms
115(16)
6.1 Asymptotic Expressions
116(3)
6.2 Space Complexity
119(3)
6.2.1 The Sparsity of Transition Matrices
119(2)
6.2.2 Storing only the Non-zero Elements of a Matrix
121(1)
6.2.3 Storage of Banded Matrices
121(1)
6.3 Time Complexity
122(2)
6.4 Errors due to Inaccurate Data, Rounding, and Truncation
124(7)
6.4.1 Data Errors
125(1)
6.4.2 Rounding Errors
125(3)
6.4.3 Truncation Errors
128(1)
Problems
129(2)
7 Transient Solutions of Markov Chains
131(24)
7.1 Extracting Information from Data Provided by Transient Solutions
132(2)
7.2 Transient Solutions for DTMCs
134(1)
7.3 Transient Solutions for CTMCs
135(3)
7.4 Programming Considerations
138(3)
7.5 An Example: A Three-Station Queueing System
141(2)
7.6 Waiting Times
143(10)
7.6.1 Waiting Times in the M/M/1 Queue under Different Queuing Disciplines
147(5)
7.6.2 Comparison of the Queueing Disciplines
152(1)
7.7 Conclusions
153(2)
Problems
154(1)
8 Moving toward the Statistical Equilibrium
155(32)
8.1 Structure of the Transition Matrix and Convergence toward Equilibrium
157(5)
8.1.1 Paths and Their Effect on the Rate of Convergence
157(1)
8.1.2 Communicating Classes
158(2)
8.1.3 Periodic DTMCs
160(2)
8.2 Transient Solutions using Eigenvalues
162(22)
8.2.1 Basic Theorems
162(3)
8.2.2 Matrix Power and Matrix Exponential
165(2)
8.2.3 An Example of a Transient Solution using Eigenvalues
167(1)
8.2.4 The Theorem of Perron-Frobenious
168(1)
8.2.5 Perron--Frobenius and Non-Negative Matrices
169(1)
8.2.6 Characterization of Transient Solutions
170(3)
8.2.7 Eigenvalues with Multiplicities Greater than One
173(3)
8.2.8 Coxian Distributions Characterized by Eigenvalues
176(2)
8.2.9 Further Insights about PH Distributions Gained through Eigenvalues
178(2)
8.2.10 Eigenvalues of Zero
180(1)
8.2.11 Eigensolutions of Tridiagonal Transition Matrices
181(3)
8.3 Conclusions
184(3)
Problems
185(2)
9 Equilibrium Solutions of Markov Chains and Related Topics
187(54)
9.1 Direct Methods
188(16)
9.1.1 The State Elimination Method
189(3)
9.1.2 Banded Matrices
192(2)
9.1.3 Gaussian Elimination as Censoring
194(4)
9.1.4 A Two Server Queue
198(1)
9.1.5 Block-structured Matrices
199(2)
9.1.6 The Crout Method
201(3)
9.2 The Expected Time Spent in a Transient State
204(12)
9.2.1 The Fundamental Matrix
204(5)
9.2.2 Moments of the Time to Absorption
209(4)
9.2.3 Finding Expectation and Variance for M/M/1 Waiting Times
213(3)
9.3 Iterative Methods
216(22)
9.3.1 Equilibrium Probabilities Found as Limits of Transient Probabilities
218(2)
9.3.2 Methods based on Successive Improvements
220(2)
9.3.3 Convergence Issues
222(5)
9.3.4 Periodic Iteration Matrices
227(7)
9.3.5 Examples
234(4)
9.4 Conclusions
238(3)
Problems
240(1)
10 Reducing the Supplementary State Space Through Embedding
241(24)
10.1 The Semi-Markov Process (SMP)
243(4)
10.1.1 Using Age as the Supplementary Variable
244(2)
10.1.2 Using the Remaining Lifetime as Supplementary Variable
246(1)
10.2 Embedding at Changes of the Physical State
247(5)
10.2.1 Creating the Supplementary State Space
247(1)
10.2.2 The Physical States of Embedded Markov Chains can Form Semi-Markov Processes
248(4)
10.2.3 Numerical Experiments
252(1)
10.3 Embedding at Specific Event Types
252(13)
10.3.1 The Main Formulas
253(3)
10.3.2 An Example where the Embedding Event is Never Disabled
256(2)
10.3.3 An Example where the Embedding Event can be Disabled
258(2)
10.3.4 The Embedded Markov Chains of M/G/1/N and GI/M/1/N Queues
260(2)
10.3.5 Finding Random Time Distributions from Embedding Point Distributions
262(1)
Problems
263(2)
11 Systems with Independent or Almost Independent Components
265(20)
11.1 Complexity Issues when using Subsystems
266(2)
11.2 Mathematical Tools for Combining Independent Subsystems
268(5)
11.2.1 Combining DTMCs via Kronecker Products
268(3)
11.2.2 CTMCs and Kronecker Sums
271(1)
11.2.3 Using Kronecker Products in Almost Independent Subsystems
272(1)
11.3 Jackson Networks
273(10)
11.3.1 Simple Tandem Queues
273(4)
11.3.2 General Jackson Networks
277(3)
11.3.3 Closed Queueing Networks
280(3)
11.4 Conclusions
283(2)
Problems
284(1)
12 Infinite-state Markov Chains and Matrix Analytic Methods (MAM)
285(66)
12.1 Properties Specific to Infinite-state Markov Chains
286(7)
12.1.1 Diverging and Converging Markov Chains
287(2)
12.1.2 Stochastic and Substochastic Solutions of Infinite-state Markov Chains
289(2)
12.1.3 Convergence to the Desired Solution
291(2)
12.2 Markov Chains with Repeating Rows, Scalar Case
293(17)
12.2.1 Recurrent and Transient Markov Chains
294(1)
12.2.2 The Extrapolating Crout Method
295(5)
12.2.3 Using Generating Functions for Norming the Probabilities
300(3)
12.2.4 The Waiting-time Distribution of the GI/G/1 Queue
303(1)
12.2.5 The Line Length Distribution in a GI/G/1 Queue Obtained from its Waiting-Time Distribution
304(2)
12.2.6 The M/D/c Queue
306(2)
12.2.7 Increase of X limited to 1, and Decrease of X limited to 1
308(2)
12.3 Matrices with Repeating Rows of Matrix Blocks
310(19)
12.3.1 Recurrent and Transient GI/G/1 Type processes
312(1)
12.3.2 The GI/G/1 Paradigm
313(3)
12.3.3 Generating Functions
316(3)
12.3.4 The QBD Process
319(7)
12.3.5 The Classical MAM Paradigms
326(3)
12.4 Solutions using Characteristic Roots and Eigenvalues
329(18)
12.4.1 Solutions based on Characteristic Roots
330(4)
12.4.2 Using Eigenvalues for Block-Structured Matrices with Repeating Rows
334(3)
12.4.3 Application of the Generalized Eigenvalue Problem for Finding Equilibrium Solutions
337(2)
12.4.4 Eigenvalue Solutions Requiring only one Eigenvalue
339(8)
12.5 Conclusions
347(4)
Problems
348(3)
Appendix A Language Conventions for Algorithms 351(2)
References 353(6)
Index 359
Winfried Grassmann completed his Ph.D. at the University of Zurich, Switzerland, in 1967 with summa cum laude. After four years working as an operations research analyst at Swissair, the Swiss flag carrier, He joined the University of Saskatchewan, Canada, to teach operations research and computer science. Author of three books and numerous articles, Grassmann introduced the randomization method as a numerical tool and invented the Grassmann-Taksar-Heyman (GTH) method. Javad Tavakoli holds a PhD in Categorical Algebra from Dalhousie University, NS, Canada. In 1996 he proudly had the opportunity to meet with Winfried Grassmann at the University of Saskatchewan, Canada, where he started his new research area in Applied Probability and Stochastic Processes. Javad Tavakoli has been a researcher and educator at the University of British Columbia Okanagan, Canada since 2003. He published a number of papers in Queuing Theory, mostly with Winfried Grassmann. Javad Tavakoli also has received several awards for teaching excellence and published a pre-calculus book from the indigenous perspective.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97830311008262e.html
Märksõnad: