Introduction to Matrix-Analytic Methods in Queues 2 E-Book

Srinivas R. Chakravarthy

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

Seitenzahl: 516

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

Leseprobe

Contents

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

Guide

Cover

Table of Contents

Title Page

Pages

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

Introduction to Matrix-Analytic Methods in Queues 2

Analytical and Simulation Approach – Queues and Simulation

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

List of Notations

Symbols

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

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

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

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