126,99 €
Matrix-analytic methods (MAM) were introduced by Professor Marcel Neuts and have been applied to a variety of stochastic models since. In order to provide a clear and deep understanding of MAM while showing their power, this book presents MAM concepts and explains the results using a number of worked-out examples. This book's approach will inform and kindle the interest of researchers attracted to this fertile field. To allow readers to practice and gain experience in the algorithmic and computational procedures of MAM, Introduction to Matrix-Analytic Methods in Queues 2 provides a number of computational exercises. It also incorporates simulation as another tool for studying complex stochastic models, especially when the state space of the underlying stochastic models under analytic study grows exponentially. This book's detailed approach will make it more accessible for readers interested in learning about MAM in stochastic models.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 516
Veröffentlichungsjahr: 2022
Cover
Dedication
Title Page
Copyright
List of Notations
Preface
Chapter 1. Single-Server Queues Embedded at Departure Epochs
1.1.
BMAP/G/
1 queue
1.2.
MAP/G/
1 queue
1.3.
PH/G/
1 queue
1.4.
M/G/
1 queue
1.5.
PH/M/
1 queue
1.6.
M/M/
1 queue
1.7. Exercises
Chapter 2. Single-Server Queues Embedded at Arrival Epochs
2.1.
GI/PH/
1 queue
2.2.
GI/M/
1 queue
2.3.
M/PH/
1 queue
2.4.
M/M/
1 queue
2.5. Exercises
Chapter 3. Single-Server Queues Based on Arbitrary Epochs
3.1.
BMAP/PH/
1 queue
3.2.
MAP/PH/
1 queueing model
3.3.
PH/PH/
1 queue
3.4.
PH/M/
1 queue
3.5.
M/PH/
1 queue
3.6.
M/M/
1 queue
3.7. Exercises
Chapter 4. Busy Period in Queues
4.1. Busy period in
M/G/
1-type queues (scalar case)
4.2. Busy period in
M/G/
1-type queues (matrix case)
4.3. Busy period in
GI/M/
1-type queues (scalar case)
4.4. Busy period in
GI/PH/
1-type queues
4.5.
BMAP/PH/
1 queue
4.6. Busy period in QBD-type queues
4.7. When the fundamental period is not the busy period
4.8.
GI/G/
1 queues
4.9. Exercises
Chapter 5. Multi-Server Queues
5.1.
BMAP/PH/c
queue
5.2.
MAP/PH/
3 queue
5.3.
BMAP/M/c
queue
5.4.
GI/PH/c
queue
5.5. Exercises
Chapter 6. Finite-Capacity Queues
6.1. Finite-capacity queues with single server
6.2. Finite-capacity queues with multiple servers
6.3. Exercises
Chapter 7. Simulation
7.1. Introduction to ARENA
7.2. Model building using ARENA
7.3.
GI/G/c
queues
7.4.
BMAP/G/c
queues
7.5. Exercises
References
Index
Summary of Volume 1
Wiley End User License Agreement
Cover
Table of Contents
Title Page
i
ii
iii
iv
ix
x
xi
xii
xiii
xiv
xv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
405
406
407
408
409
411
412
413
414
415
417
418
419
420
421
422
423
This book is dedicated to my parents:Mrs. P.S. Rajalakshmi and Mr. P.S.S. Raghavan;to my professors:Dr. Marcel F. Neuts and Dr. K.N. Venkataraman;to my wife, son, and daughter-in-law:Jayanthi, Arvind, and Vina;and to His Holiness Sri Maha Periyava (Sri Chandrasekharendra Saraswati Mahaswamigal)of Kanchi Kamakoti Peetham
Series EditorNikolaos Limnios
Srinivas R. Chakravarthy
First published 2022 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2022The rights of Srinivas R. Chakravarthy to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.
Library of Congress Control Number: 2022935181
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-78630-823-8
e
column vector, with all elements equal to 1, of appropriate dimension
e
T
row vector, with all elements equal to 1, of appropriate dimension
e
i
column vector with 1 in the
i
th position and 0 elsewhere
I
identity matrix
⊗
Kronecker product
⊕
Kronecker sum
∆(.)
diagonal matrix with entries given in the parentheses
BMAP
batch Markovian arrival process
BP
busy period
CDF
(cumulative) distribution function
CPH
continuous phase type
CTMC
continuous-time Markov chain
D-BMAP
discrete-time BMAP
DPH
discrete phase type
DRI
directly Riemann integrable
DTMC
discrete-time Markov chain
EMC
embedded Markov chain
LST
Laplace-Stieltjes transform
LT
Laplace transform
MAM
matrix-analytic method(s)
MAP
Markovian arrival process
MC
Markov chain
MRP
Markov renewal process
probability density function
PGF
probability generating function
PH
phase type
PMF
probability mass function
TPM
transition probability matrix
VMPP
versatile Markovian point process
The introduction of the phase type (PH) distributions in the early 1970s by Marcel Neuts opened up a wide range of possibilities in Applied Probability modeling and ushered in the idea that finding computable, numerical solutions was an acceptable and desirable goal in analyzing stochastic models. Furthermore, he popularized incorporating the computational aspects in the study of stochastic models. It gave researchers a powerful new tool that enabled them to move beyond the traditional models limited to exponential processes for analytical convenience to studying more realistic stochastic models with algorithmic solutions and simple, elegant probabilistic interpretations. The goal of building models with computationally tractable solutions rather than the abstract transform-based solutions took root. This rapidly led to an entirely new area of research on the study of stochastic models in queues, inventory, reliability, and communication networks using matrix-analytic methods (MAM). The versatile Markovian point process (VMPP) was introduced by Neuts in the late 1970s. This process was used in the study of a single-server queueing system with general services by one of Neuts’s students, V. Ramaswami, for his PhD dissertation. In 1990, this VMPP was studied differently as a batch Markovian arrival process (BMAP) by Neuts and his students David Lucantoni and Kathy Meier-Hellstern. At that time it was thought that VMPP was a special case of BMAP, but it was proved that BMAP and VMPP are the same. However, the compact and transparent notations with which BMAP is described allowed the readers to understand this versatile point process with relative ease, and since then VMPP is referred to as BMAP in the literature. In the case of single arrivals, the process is referred to as a Markovian arrival process (MAP).
The study of stochastic models possessing matrix-geometric solutions (thus extending the geometric solution result for the scalar case for Poisson arrivals and exponential services in a single server queue) by Neuts in the late 1970s and the introduction of PH distributions, BMAP, and an emphasis on the algorithmic approach, paved the way for Neuts to the introduction of MAM. Ever since, these methods have been extensively studied both theoretically and computationally in the context of a variety of stochastic models useful in many applied areas. A handful of books starting with Neuts’s two classical books, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, originally published in 1981, and Structured Stochastic Matrices of M/G/1 Type and Their Applications in 1989, to the latest one, The Theory of Queuing Systems with Correlated Flows by Dudin, Klimenok and Vishnevsky in 2020, have appeared in the literature that deal with MAM. The other books published from 1989 to 2020 include Introduction to Matrix Analytic Methods in Stochastic Modeling by Latouche and Ramaswami (1999); Numerical Methods for Structured Markov Chains by Bini et al. (2005); Queueing Theory for Telecommunications by Alfa (2010); Fundamentals of Matrix-Analytic Methods by He (2014); and Matrix-Exponential Distributions in Applied Probability by Bladt and Nielsen (2017).
All the texts mentioned above provide an excellent foundation of a variety of stochastic models in general and of theoretical properties and applications of MAM to those models. The present work takes a different approach by covering the basics of MAM but focusing on clearly illustrating its use in analyzing many stochastic models. It is also my strong belief that the art of model building and analysis is better learned by studying carefully constructed examples and by practicing those skills on other models. A text that incorporates the mathematical ideas of MAM along with clearly illustrated examples on the use of these methods in analyzing interesting stochastic models makes MAM more accessible to current researchers. I believe this juxtaposition reinforces the power of MAM, enables one to appreciate and get better in the art of model building, and helps in improving “probabilistic thinking” of models and solutions. It is also for these reasons that I have included a large collection of exercises, most of which are computational in nature, for the reader to practice, experiment and get the experience in the algorithmic and computational procedures. It should be pointed out that the illustrative examples and the exercises are deliberately made more generic so as to let the readers modify them for their areas of applications. This approach was motivated by the feedback that I have had from numerous graduate students and fellow researchers in the past.
Furthermore, the text also contains exploration of simulation as an integral tool in studying stochastic models, which don’t admit analytical or numerical solutions. Finally, the text provides detailed explanations on the mathematics and the applications of MAM to enable graduate students with a strong background in probability and mathematics.
Thus, the text is a useful source of reference for researchers established in this field and, more importantly, a valuable, inviting guide for those venturing into this rich research area.
This two-volume book is organized as follows: Volume 1 has nine chapters. Chapter 1 reviews basic concepts in probability and matrix theory. Chapter 2 has a brief review of discrete-state-discrete-time and discrete-state-continuous-time Markov chains. These two chapters are not meant to be an exhaustive and thorough review of those topics but hopefully sufficient enough to understand the rest of the materials in the two-volume book. In Chapter 3, discrete-time phase type distribution is presented. Chapter 4 focuses on the continuous-time phase type distributions. Chapters 5 and 6, respectively, cover discrete and continuous time BMAP. The basics of MAM from both discrete time (through embedded epochs) and continuous time points of view along with many examples and exercises are, respectively, presented in Chapters 7 and 8. A brief summary of the applications of queueing (and in turn MAM) is given in Chapter 9. The presence of numerous detailed solutions and exercises benefit students by piquing their interest in MAM, helping them learn and understand basic concepts, and succeed in constructing and solving models of their own in their research. The solutions to these exercises can be found at the following link: www.iste.co.uk/chakravarthy/queues2.zip.
Volume 2 contains seven chapters. In Chapters 1, 2, and 3, respectively, single-server queues are studied by looking at departure, arrivals, and at arbitrary epochs. Chapter 4 focuses on the busy periods in queues. Selected multi-server queues are studied in Chapter 5, and finite capacity queues are the focus in Chapter 6. Finally in Chapter 7, we present analysis of queues via simulation using ARENA, a powerful simulation software. In this chapter we also provide a very brief introduction to ARENA. All these chapters have exercises.
This two-volume book can be used in a number of settings. Senior undergraduate students (with sufficient background in probability) and Master’s level graduate students could use Volume 1 to get an understanding of the fundamentals of MAM. Research scholars pursuing MPhil and PhD degrees can start with Volume 1 and, after going through the basics covered there, move on to finishing Volume 2. For research scholars pursuing MPhil and PhD degrees, the two volumes would constitute a two- to three-semester course.
Writing this book has been lot of fun but also a challenge. However, my family, friends, and mentors helped me to meet that challenge. I take a great pleasure in acknowledging them. This book project would not have been possible without the educational foundation, moral support, encouragement, and critical analysis of teachers, friends, and families.
Specifically, I want to acknowledge the following people who made a positive difference.
– My (late) father, P.S.S. Raghavan, for being a role model. My mother, P.S.S. Rajalakshmi, for her encouragement. Both my parents made many sacrifices that enabled me to first go to college and, later on, to leave for the United States to pursue higher studies.
– My sister, Vasumathi Parthasarathy, for exposing me to mathematics at a very young age.
– My (late) Professors Marcel F. Neuts and K.N. Venkataraman. While K.N.V. gave me an opportunity to learn probability theory under him while in India, M.F.N. showed me the path to MAM. I owe a debt of gratitude to him for what I am now and for his important role in shaping my career as a teacher and a researcher.
– My college teachers, Prof. D. Ratnasabapathi (Presidency College in Madras) and Prof. K. Suresh Chandra (University of Madras), who not only taught me statistics but also were a source of encouragement to pursue higher studies.
– I benefited a lot through interacting with my friends and colleagues V. Ramaswami, D.M. Lucantoni, Kathy Meier-Hellstern and S. Kumar, during my days at Delaware.
– R. Parthasarathy (Kent State University), whom I knew from my college days in India and who has always been there to give moral support since those days.
– My research colleagues who played key roles in my career, notably A.S. Alfa, A.N. Dudin, A. Krishnamoorthy, and A. Rumyantsev.
– My students: Serife Ozkar, who visited from Turkey to finish up her doctoral thesis with me at Kettering, and Shruti Goel, who attended the workshops I conducted in India. The questions these students, along with a countless others, including Alka Choudhry, a doctoral student at the Central University of Rajasthan, India, raised provided the impetus for this book. Furthermore, I am thankful to both Serife and Shruti for helping me put the bibliography in the format required by the publishers.
– Several of my colleagues at Kettering, notably (the late) Duane McKeachie, Petros Gheresus, and T.R. Chandrupatla (who retired from Rowan University recently after serving nearly two decades at Kettering) for their friendship and encouragement throughout my career at Kettering.
– Kettering University for its support of my sabbatical which was instrumental in completing this book project.
– The ISTE team for their continued and timely help during the production process of this two-volume book.
– Finally, the most important people in my life, my wife, Jayanthi Chakravarthy, son Arvind Chakravarthy and his beloved wife, Vina Harji Chakravarthy. Since Jayanthi and Arvind came into my life, their understanding, love and support have helped me to focus on my research and career without any distraction. They along with Vina have been a source of constant inspiration to finish the book. No words are adequate to express my sincere appreciation to them.
Srinivas CHAKRAVARTHYApril 2022