Introduction to Matrix Analytic Methods in Queues 1 E-Book

Srinivas R. Chakravarthy

• Herausgeber: John Wiley & Sons
• Kategorie: Bildung
• Sprache: Englisch

Seitenzahl: 472

Veröffentlichungsjahr: 2022

Beschreibung

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 1 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. The book's detailed approach will make it more accessible for readers interested in learning about MAM in stochastic models.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

List of Notations

Preface

1 Introduction

1.1. Probability concepts

1.2. Renewal process

1.3. Matrix analysis

2 Markov Chains

2.1. Discrete-time Markov chains (DTMC)

2.2. Continuous-time Markov chain (CTMC)

2.3. Semi-Markov and Markov renewal processes

3 Discrete Phase Type Distributions

3.1. Discrete phase type (DPH) distribution

3.2. DPH renewal processes

3.3. Exercises

4 Continuous Phase Type Distributions

4.1. Continuous phase type (CPH) distribution

4.2. CPH renewal process

4.3. Exercises

5 Discrete-Batch Markovian Arrival Process

5.1. Discrete-batch Markovian arrival process

5.2. Counting process associated with the D-BMAP

5.3. Generation of D-MAP processes for numerical purposes

5.4. Exercises

6 Continuous-Batch Markovian Arrival Process

6.1. Continuous-time batch Markovian arrival process (BMAP)

6.2. Counting processes associated with BMAP

6.3. Generation of MAP processes for numerical purposes

6.4. Exercises

7 Matrix-Analytic Methods (Discrete-Time)

7.1. M/G/1-paradigm (scalar case)

7.2. M/G/1-paradigm (matrix case)

7.3. GI/M/1-paradigm (scalar case)

7.4. GI/M/1-paradigm (matrix case)

7.5. QBD process (scalar case)

7.6. QBD process (matrix case)

7.7. Exercises

8 Matrix-Analytic Methods (Continuous-time)

8.1. M/G/1-type (scalar case)

8.2. M/G/1-type (matrix case)

8.3. GI/M/1-type (scalar case)

8.4. GI/M/1-type (matrix case)

8.5. QBD process (scalar case)

8.6. QBD process (matrix case)

8.7. Exercises

9 Applications

9.1. Production and manufacturing

9.2. Service sectors

References

Index

Summary of Volume 2

Wiley End User License Agreement

List of Tables

Chapter 3

Table 3.1. PMF of X

Table 3.2. PMF of X

Chapter 6

Table 6.1. Palm and variance functions for example 6.7

Table 6.2. Palm and variance functions for example 6.8

Table 6.3. Palm and variance functions for example 6.9

Table 6.4. Palm and variance functions for example 6.10

Chapter 7

Table 7.1. Probability mass functions {ak} and {bk}

Table 7.2. Probabilities for Exercise 7.60

Guide

Cover

Contents

Title Page

Copyright

List of Notations

Preface

1 Introduction

References

Index

Summary of Volume 2

Wiley End User License Agreement

Pages

v

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

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

130

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

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

192

190

191

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

292

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

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

339

340

341

343

344

345

346

347

348

349

350

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; and to His Holiness

Sri Maha Periyava (Sri Chandrasekharendra Saraswati Mahaswamigal) of Kanchi Kamakoti Peetham

Series Editor

Nikolaos Limnios

Introduction to Matrix-Analytic Methods in Queues 1

Analytical and Simulation Approach – Basics

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, Inc111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2022

The 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: 2022935180

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-78630-732-3

List of Notations

Symbols

e column vector, with all elements equal to 1, of appropriate dimension

eT row vector, with all elements equal to 1, of appropriate dimension

ei column vector with 1 in the ith position and 0 elsewhere

I identity matrix

⊗ Kronecker product

⊕ Kronecker sum

Δ(.) diagonal matrix with entries given in the parentheses

Abbreviations

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 (batch Markovian arrival process)

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 methods

MAP Markovian arrival process

MC Markov chain

MRP Markov renewal process

PDF probability density function

PGF probability generating function

PH phase type

PMF probability mass function

TPM transition probability matrix

VMPP versatile Markovian point process

Preface

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/queues1.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