Queueing Theory 2

Vladimir Anisimov is Full Professor in Applied Statistics. He works in the Center for Design & Analysis at Amgen Inc. in London, UK. His research interests include probability models and stochastic processes, clinical trials modeling, applied statistics, queueing models and asymptotic techniques. Nikolaos Limnios is Full Professor in Applied Mathematics at the University of Technology of Compiègne, part of the Sorbonne University Group, in France. His research interests include stochastic processes and statistics, Markov and semi-Markov processes, random evolutions with applications in reliability, queueing systems, earthquakes and biology.

Preface xi

Chapter 1. Stability Analysis of Queueing Systems based on Synchronization of the Input and Majorizing Output Flows 1
Larisa AFANASEVA

1.1. Introduction 1

1.2. Model description 4

1.3. Auxiliary service process 6

1.4. Instability result for the case ρ ≥ 1 9

1.5. Stochastic boundedness for the case ρ < 1 10

1.6. Queueing system with unreliable servers and preemptive resume service discipline 11

1.7. Discrete-time queueing system with interruptions and preemptive repeat different service discipline 15

1.8. Queueing system with a preemptive priority discipline 18

1.9. Queueing system with simultaneous service of a customer by a random number of servers 20

1.10. Applications to transport systems analysis 23

1.11. Conclusion 28

1.12. Acknowledgment 29

1.13. References 29

Chapter 2. Queueing Models in Services – Analytical and Simulation Approach 33
Srinivas R. CHAKRAVARTHY

2.1. Introduction 33

2.2. Phase-type distributions and the batch Markovian arrival process 34

2.2.1. Phase-type distributions 35

2.2.2. Some useful results related to continuous PH distributions 36

2.2.3. The batch Markovian arrival process 40

2.3. Generation of MAP processes for numerical purposes 42

2.4. Analysis of selected queueing models of BMAP/G/c type 44

2.4.1. MAP/PH/1 queueing model 44

2.4.2. The system performance measures 48

2.4.3. Illustrative numerical examples for MAP/PH/1 49

2.4.4. MAP/M/c queueing model 55

2.4.5. The system performance measures 57

2.4.6. Illustrative numerical examples for MAP/M/c 57

2.5. Simulated models of BMAP/G/c type queues 58

2.5.1. Simulated model validation using MAP/M/c type queues 59

2.5.2. Simulated model validation using MAP/PH/1 type queues 59

2.5.3. Selected simulated models of BMAP/G/c type queues 59

2.6. Analysis of selected queueing models of BMAP/G/c type with a vacation 66

2.6.1. MAP/PH/1 queueing model with a vacation 66

2.6.2. The system performance measures 69

2.6.3. Illustrative numerical examples for MAP/PH/1 with a vacation 69

2.6.4. Validation of the simulated model for vacation type queues 74

2.6.5. Selected simulated models of BMAP/G/c type queues with a vacation 75

2.7. Acknowledgment 78

2.8. References 78

Chapter 3. Distributions and Random Processes Related to Queueing and Reliability Models 81
Boyan DIMITROV

3.1. Some useful notations, relationships and interpretations 81

3.2. Unreliable service model and reliability maintenance 85

3.3. Characterizations of exponential and geometric distributions via properties of service times 88

3.3.1. Instant repairs: characterization of geometric distribution 89

3.3.2. Instant repairs: characterizations of the exponential distribution 94

3.3.3. Various simplifying conditions 101

3.3.4. Unreliable service, repair times included 111

3.4. Probability distributions almost having lack of memory property 115

3.4.1. Service time on an unreliable server: instantaneous repairs 116

3.4.2. Properties of ALM distributions, and equivalent presentations 119

3.4.3. Periodicity in natural phenomena 126

3.5. Random processes with a periodic nature 126

3.5.1. Counting processes 127

3.5.2. Characterization of an NPP 128

3.5.3. Applications in risk modeling 131

3.6. Conclusions 132

3.7. References 133

Chapter 4. The Impact of Information Structure on Strategic Behavior in Queueing Systems 137
Antonis ECONOMOU

4.1. Introduction 138

4.2. Game-theoretical framework in queueing 139

4.3. The unobservable model 142

4.4. The observable model 146

4.5. Comparison of the unobservable and the observable models 151

4.6. Partially observable models 153

4.7. Heterogeneously observable models 158

4.8. Observable-with-delay models 162

4.9. Conclusions and literature review for further study 167

4.10. Acknowledgments 167

4.11. References 168

Chapter 5. Non-extensive Maximum Entropy Formalisms and Inductive Inference of a Stable M/G/1 Queue with Heavy Tails 171
Demetres D. KOUVATSOS and Ismail A. MAGEED

5.1. Introduction 172

5.2. General systems and inductive ME formalisms 175

5.2.1. “Classical” Shannon’s EME formalism with short-range interactions 175

5.2.2. Rényi’s and Tsallis’s NME formalisms with long-range interactions 176

5.3. NME formalisms and EME consistency axioms 177

5.4. A stable M/G/1 queue with long-range interactions 179

5.4.1. Background: Shannon’s EME state probability of a stable M/G/1 queue 179

5.4.2. Tsallis’ and Rényi’s NME state probabilities of a stable M/G/1 queue 180

5.4.3. Exact Rényi’s and Tsallis’ NME state probabilities with distinct GEq-type service time distributions 183

5.5. Numerical experiments and interpretations 188

5.6. Conclusions 195

5.7. Acknowledgments 196

5.8. Appendix: Rényi’s NME formalisms versus EME consistency axioms 196

5.8.1. Uniqueness 196

5.8.2. Invariance 197

5.8.3. System independence 197

5.8.4. Subset independence 198

5.9. References 199

Chapter 6. Inventory with Positive Service Time: a Survey 201
Achyutha KRISHNAMOORTHY, Dhanya SHAJIN and Viswanath C. NARAYANAN

6.1. Introduction 201

6.2. Queueing inventory models 203

6.2.1. Single-commodity queueing-inventory systems 206

6.2.2. Production inventory systems 215

6.2.3. Multicommodity queueing-inventory system 217

6.2.4. Retrial queues with inventory 219

6.2.5. Queues requiring additional items for service 222

6.2.6. Queueing-inventory: some work in progress and suggestions for future studies 225

6.3. Acknowledgment 227

6.4. References 227

Chapter 7. A Stability Analysis Method of Regenerative Queueing Systems 239
Evsey MOROZOV and Bart STEYAERT

7.1. Introduction 239

7.2. Preliminaries 241

7.3. The single-server system 244

7.4. The zero-delayed multiserver system 248

7.5. The delayed multiserver system: finiteness of the first regeneration period 252

7.6. Instability 256

7.6.1. Some comments on the method 260

7.7. Related research 262

7.8. Acknowledgments 266

7.9. References 266

Chapter 8. Transient Analysis of Markovian Queueing Systems: a Survey with Focus on Closed-forms and Uniformization 269
Gerardo RUBINO

8.1. Introduction 270

8.2. Basics on Markovian queues 272

8.2.1. Markov models 272

8.2.2. Uniformization 273

8.3. First examples 275

8.3.1. The Ehrenfest model in continuous-time 275

8.3.2. The M/M/∞ model 276

8.3.3. A queue with no server and catastrophes 277

8.3.4. The fundamental M/M/1 model 278

8.3.5. M/M/1 with bounded waiting room: the M/M/1/H model 282

8.3.6. Comments 284

8.4. An uniformization-based path for the M/M/1 with matrix generating functions 284

8.4.1. General case 286

8.4.2. Mean number of customers at time t in the M/M/1 287

8.5. An uniformization-based path using duality 290

8.5.1. Duality 290

8.5.2. The path toward the transient state distributions using duality 293

8.5.3. Application to the M/M/1 queueing system 294

8.5.4. Application to the M/M/1/H queueing system 295

8.5.5. Application to an M/M/1/H model with catastrophes 297

8.6. Other transient results 299

8.6.1. Busy period of the M/M/1 299

8.6.2. Max backlog of the M/M/1 over a finite time interval 299

8.6.3. M/E/1 300

8.7. Conclusions 302

8.8. References 302

List of Authors 307

Index 309