Fundamentals of Queueing Theory

Title Page\r......Page 3
Copyright\r......Page 4
Contents\r......Page 6
Preface\r......Page 9
Acknowledgements\r......Page 11
CHAPTER 1: INTRODUCTION\r......Page 12
1.1 Description of the Queueing Problem......Page 13
1.2.1 Arrival Pattern of Customers......Page 14
1.2.3 Queue Discipline......Page 15
1.2.5 Number of Service Channels......Page 16
1.2.6 Stages of Service......Page 17
1.3 Notation......Page 18
1.4 Measuring System Performance......Page 19
1.5 Some General Results......Page 20
1.5.1 Little\'s Formulas......Page 21
1.6 Simple Data Bookkeeping for Queues......Page 23
1.7 Poisson Process and the Exponential Distribution......Page 27
1.8 Markovian Property of the Exponential Distribution......Page 31
1.9.1 Markov Process......Page 35
1.9.2 Discrete-Parameter Markov Chains......Page 37
1.9.3 Continuous-Parameter Markov Chains......Page 38
1.9.4 Imbedded Markov Chains......Page 41
1.9.5 Long-Run Behavior of Markov Processes......Page 42
Example 1.1......Page 43
Example 1.2......Page 44
1.9.6 Ergodicity......Page 45
Theorem 1.1.......Page 49
Theorem 1.3.\r......Page 50
1.10 Introduction to the QtsPlus Software......Page 51
Problems......Page 52
2.1 Birth-Death Processes......Page 59
2.2 Single-Server Queues M/M/1......Page 63
2.2.1 Solving for {pn} Using an Iterative Method......Page 64
2.2.2 Solving for {pn} Using Generating Functions......Page 66
2.2.3 Solving for {pn} Using Operators......Page 67
2.2.4 Measures of Effectiveness......Page 69
Example 2.1......Page 73
2.2.5 Waiting- Time Distribution......Page 74
2.3 Multiserver Queues M/M/c......Page 76
Example 2.3......Page 80
Example 2.4......Page 82
2.4 Choosing the Number of Servers......Page 83
2.5 Queues with Truncation M/M/c/K......Page 86
Example 2.6......Page 90
2.6 Erlang\'s Loss Formula M/M/c/c......Page 91
2.6.1 Computational Issues......Page 92
Example 2.7......Page 93
Example 2.8......Page 94
2.8 Finite-Source Queues......Page 95
Example 2.9......Page 97
2.9 State-Dependent Service......Page 101
Example 2.10......Page 102
2.10.1 M/M/1 Balking......Page 105
2.10.2 M/M/1 Reneging......Page 106
2.11.1 Transient Behavior of M/M/1/1......Page 107
2.11.2 Transient Behavior of M/M/1/∞......Page 108
2.11.3 Transient Behavior of M/M/∞......Page 111
2.12 Busy-Period Analysis......Page 112
Problems......Page 113
3.1 Bulk Input M[x]/M/1......Page 126
Example 3.2......Page 129
Example 3.3......Page 130
3.2 Bulk Service M/M[y]/1......Page 132
Example 3.4......Page 134
3.3.1 The Erlang Distribution......Page 137
3.3.2 Generalization to Phase-Type Distributions......Page 139
Example 3.5......Page 141
3.3.3 Erlang Service Model M/Ek/1......Page 142
Example 3.7......Page 144
Example 3.9......Page 145
3.3.4 Erlang Arrival Model Ek/M/1......Page 146
Example 3.10......Page 148
3.3.5 Ej/Ek/1 Models......Page 149
3.4 Priority Queue Disciplines......Page 150
3.4.1 Nonpreemptive Systems with Two Classes......Page 152
3.4.2 Nonpreemptive Systems with Many Classes......Page 159
3.4.3 Preemptive priorities......Page 165
3.5 Retrial Queues......Page 166
3.5.1 M/M/1 Retrial Queue......Page 168
3.5.2 M/M/1 Retrial Queue with Impatience......Page 171
3.5.3 An Approximation for the M/M/c Retrial Queue......Page 177
Example 3.12......Page 179
Problems......Page 180
CHAPTER 4: NETWORKS, SERIES, AND CYCLIC QUEUES\r......Page 187
4.1.1 Queue Output......Page 189
Example 4.1......Page 192
4.1.2 Series Queues with Blocking......Page 193
4.2 Open Jackson Networks......Page 195
Example 4.2......Page 201
4.2.1 Open Jacksin Networks with Multiple Customer Classes......Page 202
4.3 Closed Jackson Networks......Page 203
Example 4.4......Page 205
4.3.1 Mean-Value Analysis......Page 209
Example 4.5......Page 211
4.4 Cyclic Queues......Page 217
4.5 Extensions of Jackson Networks......Page 218
4.6 Non-Jackson Networks......Page 220
Problems......Page 222
5.1 General Service, Single Server M/G/1......Page 227
5.1.1 Expected-Value Measures of Effectiveness The Pollaczek-Khintchine Formula......Page 228
Example 5.2......Page 230
5.1.2 Departure-Point System-Size Probabilities......Page 233
Example 5.3......Page 236
Example 5.4......Page 239
5.1.3 Proof That  πn = pn......Page 240
5.1.4 Ergodic Theory......Page 241
5.1.5 Waiting Times......Page 243
Example 5.5......Page 246
5.1.6 Busy-Period Analysis......Page 247
5.1.7 Finite M/G/1 Queues......Page 249
5.1.8 Some Additional Results......Page 250
5.1.9 The Bulk-Input Queue M[x]/G/1......Page 252
5.1.10 Departure-Point State Dependence,Decomposition, and Server Vacations......Page 254
5.1.11 Level-Crossing Methods......Page 258
Example 5.7......Page 260
5.2 General Service, Multiserver \0䴀⼀䜀⼀挀⼀⸀Ⰰ䴀⼀䜀⼢Ḁ......Page 262
5.2.2 The M/G/∞ Queue and M/G/c/c Loss System......Page 263
5.3.1 Single-Server G/M/1 Queue......Page 267
Example 5.9......Page 271
5.3.2 Multiserver G/M/c Queue......Page 273
Problems......Page 278
6.1 G/Ek/1,G[k]/M/1, and G/PHk/1......Page 284
Example 6.1......Page 286
6.1.1 Matrix Geometric Solutions......Page 288
6.1.2 Quasi-Birth-Death Processes......Page 290
6.2 General Input, General Service G/G/1......Page 291
Example 6.2......Page 295
6.2.1 GEj/GEk/1......Page 297
6.2.2 Discrete G/G/1......Page 300
6.3 Poisson Input, Constant Service, Multiserver M/D/c......Page 301
6.4 Semi-Markov Renewal Processes in Queueing......Page 303
Example 6.5......Page 304
6.5 Other Queue Disciplines......Page 308
6.5.1 Conservation......Page 311
6.6 Design and Control of Queues......Page 313
6.6.1 Queueing Design Problems......Page 315
Example 6.6......Page 318
6.6.2 Queueing Control Problems......Page 320
6.7 Statistical Inference in Queueing......Page 324
Example 6.7......Page 328
Example 6.8......Page 329
Problems......Page 332
CHAPTER 7: BOUNDS AND APPROXIMATIONS......Page 336
7.1.1 Basic Relationships for Single-Server Queues......Page 337
7.1.2 Bounds for Single-Server Queues......Page 339
Example 7.1......Page 344
7.1.3 Bounds for Multiserver Queues......Page 348
7.2.1 Using Bounds to Approximate......Page 350
7.2.2 System Approximations......Page 352
7.2.3 Process Approximations......Page 353
Example 7.3......Page 357
Example 7.4......Page 358
7.3 Network Approximations......Page 363
7.3.1 Preliminaries and Notation......Page 364
7.3.2 Parametric Decomposition......Page 365
Example 7.5......Page 371
Example 7.6......Page 373
Problems......Page 374
8.1 Numerical Techniques......Page 376
8.1.1 Steady-State Solutions......Page 377
8.1.2 Transient Solutions......Page 385
8.2 Numerical Inversion of Transforms......Page 392
Example 8.1......Page 393
8.2.1 The Fourier-Series Method......Page 394
Example 8.2......Page 395
8.2.2 Error Analysis......Page 398
8.2.3 Examples......Page 399
Example 8.3......Page 400
Example 8.5......Page 402
Example 8.6......Page 403
8.2.4 Other Numerical Inversion Methods......Page 404
8.3 Discrete-Event Stochastic Simulation......Page 405
8.3.1 Elements of a Simulation Model......Page 406
Example 8.7......Page 407
8.3.2 Input Modeling and Random-Variate Generation......Page 409
8.3.3 Bookkeeping Aspects of Simulation Analysis......Page 422
8.3.4 Output Analysis......Page 423
8.3.5 Model Validation......Page 427
Problems......Page 428
REFERENCES......Page 433
APPENDIX A: SYMBOLS AND ABBREVIATIONS......Page 444
APPENDIX B: TABLES......Page 451
C.1 Laplace Transforms......Page 459
C.1.1 Moment Generating Functions......Page 464
C.2 Generating Functions......Page 466
C.2.1 Probability Generating Functions......Page 468
D.1 Ordinary Differential Equations......Page 471
D.1.2 Solutions......Page 472
D.1.3 Separation of Variables......Page 474
D.1.4 Linear Differential Equations of First Order......Page 475
D.1.5 Linear Differential Equations with Constant Coefficients......Page 476
Example D.2......Page 478
D.1.6 Undertermined Coefficients......Page 479
Example D.4......Page 480
D.1.7 Differential Operators......Page 481
D.1.8 Reduction of Order......Page 483
D.1.9 Systems of Linear Differential Equations......Page 484
Example D.6......Page 485
D.2 Difference Equations......Page 487
D.2.1 Linear Difference Equations with Constant Coefficients......Page 488
Example D.7......Page 489
Example D.8......Page 490
APPENDIX E: QTSPLUS SOFTWARE......Page 492
INDEX......Page 496
Wiley Series in Probability and Statistics......Page 504