Stochastic Processes in Queueing Theory

The object of queueing theory (or the theory of mass service) is the investigation of stochastic processes of a special form which are called queueing (or service) processes in this book. Two approaches to the definition of these processes are possible depending on the direction of investigation. In accordance with this fact, the exposition of the subject can be broken up into two self-contained parts. The first of these forms the content of this monograph. . The definition of the queueing processes (systems) to be used here is dose to the traditional one and is connected with the introduction of so-called governing random sequences. We will introduce algorithms which describe the governing of a system with the aid of such sequences. Such a definition inevitably becomes rather qualitative since under these conditions a completely formal construction of a stochastic process uniquely describing the evolution of the system would require introduction of a complicated phase space not to mention the difficulties of giving the distribution of such a process on this phase space.

§ 1. Classifications. Some Notation.- 1. Systems with Queues and Service of Type One.- § 2. Cases in Which the Systems ‹G› Can be Described by Means of Recursion Equations. Equivalence to the System ‹G, G, G, 1›.- § 3. The Basic Equation. Properties of the Solution as a Process. Ergodic Theorems.- § 4. Interrupted Governing Sequences.- § 5. On Systems Governed by Sequences of Independent Random Variables.- § 6. The Virtual Waiting Time. A Continuous Analogue of the System Equation. Properties of the Solution.- § 7. Further Properties of the Process w(t). Beneš’ Equation.- § 8. The Stationary Solution of Beneš’ Equation. Approximation Formulae for Heavy and Light Traffic.- § 9. The Processes X(t) and Y(t) with Stationary Increments Corresponding to Governing Sequences with Independent Terms. The Connection between the Distributions of wc(t) and wk.- § 10. Estimates of the Rate of Convergence of the Distributions of wn and w(t) to Stationarity. Connection with the Queue Length.- § 11. Theorems on the Stability of the Stationary Waiting Time under a Change of the Governing Sequences.- 2.Some Boundary Problems for Processes Continuous from below with Independent Increments. Their Connection with the Distribution of w(t).- § 12. Boundary Problems for Processes Continuous from below with Independent Increments.- § 13. Properties of the Distribution of w(t). The Busy Period.- § 14. Discrete Time.- 3. Boundary Problems for Sequences with Independent Increments and Factorization Identities.- § 15. Preliminary Remarks.- § 16. The First Factorization Identity and Its Consequences.- § 17. The Second Factorization Identity and Its Consequences.- 4. Properties of the Supremum of Sums of Independent Random Variables and Related Problems of Queueing Theory.- § 18. Uniqueness Theorems.- § 19. Methods of Finding the Distribution of $$\bar{Y}$$.- § 20. Explicit Formulae for the Distribution of $$\bar{Y}$$ under the Conditions of Queueing Theory.- § 21. Stability Theorems. The Rate of Convergence.- § 22. Asymptotic Properties of the Distributions of $$\bar{Y}$$ and ?.- § 23. Inequalities for the Distributions of $$\bar{Y}_n$$ and $$\bar{Y}$$. The Rate of Approach of the Distributions of wn and w1.- § 24. Comparison Theorems.- § 25. Conditions for Heavy Traffic. Transitional Phenomena.- § 26. The Relation between the Waiting Time and Queue Length Distributions.- 5. Multi-Channel Queueing Systems.- § 27. Classes of Systems Which Can Be Described by Recursion Equations. Existence Theorems for a Stationary Solution in the Systems ‹G, G,G/m, 1›. The Relation between the Waiting Time and the Queue Length.- § 28. The Systems ‹GI, GIGI/m, 1›. Stability Theorems. Connection between the Waiting Time and Queue Length. Estimates of Rates of Convergence.- § 29. The Systems ‹GI 1, E/m, 1› and ‹E, GI, GI/m, 1›.- 6. The Systems ‹G, G, G/?, 1) with an Infinite Number of Service Channels.- § 30. Theorems on Convergence to Stationary Processes.- § 31. Stability Theorems.- § 32. The Systems ‹ GI, G, GI/?, 1›.- § 33. The Systems ‹E, 1, GI/?, 1›.- § 34. The Systems ‹G„ 1, EI/?, 1›.- 7. Systems with Refusals.- § 35. The Systems ‹G, G, G/m, 1›R. General Theorems.- § 36. Stability Theorems.- § 37. The Systems ‹GI, 1, GI/m, 1›R.- § 38. The Systems ‹GI GI, E/m, GI›R.- § 39. The Systems ‹G›R.- § 40. Asymptotic Analysis of Multi-Channel Systems.- 8. Systems with Autonomous Service.- § 41. General Properties.- § 42. Methods of Calculating the Stationary Distributions.- Appendices.- Appendix 1. Some Theorems from Renewal Theory.- Appendix 3. The Wiener-Lévy Theorems and the Asymptotic Behavior of the Coefficients of Absolutely Convergent Series.- Appendix 4. Estimates for the Distributions of Sums of Independent Random Variables.- List of Basic Notation.- Bibliographical Notes.- Author Index.