Introduction to Queuing Theory

Book by GNEDENKO

to the Second Edition.- to the First Edition.- 1. Problems of Queueing Theory under the Simplest Assumptions.- 1.1. Simple Streams.- 1.1.1. Historical Remarks.- 1.1.2. The Notion of a Stream of Homogeneous Events.- 1.1.3. Qualitative Assumptions and Their Analysis.- 1.1.4. Derivation of Equations for Simple Streams.- 1.1.5. Solution of the Equations.- 1.1.6. Derivation of the Additional Assumption from the Other Three Assumptions.- 1.1.7. Distribution of Times of Events of a Stream.- 1.1.8. The Intensity and Parameter of a Stream.- 1.2. Service with Waiting.- 1.2.1. Statement of the Problem.- 1.2.2. The Servicing Process as a Markov Process.- 1.2.3. Construction of Equations.- 1.2.4. Determination of the Stationary Solution.- 1.2.5. Some Preliminary Results.- 1.2.6. The Distribution Function of the Waiting Time.- 1.2.7. The Mean Waiting Time.- 1.2.8. Example.- 1.3. Birth and Death Processes.- 1.3.1. Definition.- 1.3.2. Differential Equations for the Process.- 1.3.3. Proof of Feller’s Theorem.- 1.3.4. Passive Redundancy without Renewal.- 1.3.5. Active Redundancy without Renewal.- 1.3.6. Existence of Solutions for Birth and Death Equations.- 1.3.7. Backward Equations.- 1.4. Applications of Birth and Death Processes in Queueing Theory.- 1.4.1. Systems with Losses.- 1.4.2. Systems with Limited Waiting Facilities.- 1.4.3. Distribution of the Waiting Time until the Commencement of Service.- 1.4.4. Team Servicing of Machines.- 1.4.5. A Numerical Example.- 1.4.6. Duplicated Systems with Renewal (Passive Redundancy).- 1.4.7. Duplicated Systems with Renewal (Active Redundancy).- 1.4.8. Duplicated Systems with Renewal (Partially Active Redundancy).- 1.5. Priority Service.- 1.5.1. Statement of the Problem.- 1.5.2. Problems with Losses.- 1.5.3. Equations for pij(t).- 1.5.4. A Particular Case.- 1.5.5. The Possibility of Failure of the Servers.- 1.6. General Principles of Constructing Markov Models of Systems.- 1.6.1. Homogeneous Markov Processes.- 1.6.2. Characteristics of Functionals.- 1.6.3. A General Scheme for Constructing Markov Models of Service Systems.- 1.6.4. The HyperErlang Approximation.- 1.7. Systems with Limited Waiting Time.- 1.7.1. Statement of the Problem.- 1.7.2. The Stochastic Process Describing the State of a System for ? = const.- 1.7.3. System of Integro-differential Equations for the Problem..- 1.7.4. Various Characteristics of Service.- 1.7.5. Distribution of the Queue Length.- 1.7.6. Waiting Time Bounded by a Random Variable.- 1.8. Systems with Bounded Holding Times.- 1.8.1. Statement of the Problem and Assumptions.- 1.8.2. A Stochastic Process Describing the Service.- 1.8.3. Stationary Distributions.- 1.8.4. Holding Time in a System Bounded by a Random Variable.- 2. The Study of the Incoming Customer Stream.- 2.1. Some Examples.- 2.1.1. The Notion of the Incoming Stream.- 2.1.2. Feed of Components from a Hopper.- 2.1.3. A Regular Stream of Customers.- 2.1.4. Streams of Customers Served by Successively Positioned Servers.- 2.1.5. A Wider Approach to the Notion of the Incoming Stream.- 2.1.6. Marked Streams.- 2.2. A Simple Nonstationary Stream.- 2.2.1. Definition of a Simple Nonstationary Stream.- 2.2.2. Equations for the Probabilities pk(t0, t).- 2.2.3. Solution of the System (7).- 2.2.4. Instantaneous Intensity of a Stream.- 2.2.5. Examples.- 2.2.6. The General Form of Poisson Streams without Aftereffects.- 2.2.7. A System with Infinitely Many Servers.- 2.3. A Property of Stationary Streams.- 2.3.1. Existence of the Parameter.- 2.3.2. A Lemma.- 2.3.3. Proof of Khinchin’s Theorem.- 2.3.4. An Example of a Stationary Stream with Aftereffects.- 2.4. General Form of Stationary Streams without Aftereffects.- 2.4.1. Statement of the Problem.- 2.4.2. The Existence of the Limits $$\mathop {\lim }\limits_{t \to 0} \frac{{{\pi _k}(t)}}{t}$$.- 2.4.3. Equations for the General Stationary Stream without Aftereffects.- 2.4.4. Solution of Systems (3) and (4).- 2.4.5. A Special Case.- 2.4.6. The Generating Function of the Stream.- 2.4.7. Concluding Remarks.- 2.5. The Palm-Khinchin Functions.- 2.5.1. Definition of the Palm-Khinchin Functions.- 2.5.2. Proof of the Existence of the Palm-Khinchin Functions.- 2.5.3. The Palm-Khinchin Formulas.- 2.5.4. Intensity of a Stationary Stream.- 2.5.5. Korolyuk’s Theorem.- 2.5.6. The Case of Nonorderly Streams.- 2.6. Characteristics of Stationary Streams and the Lebesgue Integral.- 2.6.1. A General Definition of Mathematical Expectation.- 2.6.2. A Refinement of the Notion of Orderliness.- 2.6.3. Existence of the Parameter of a Stream.- 2.6.4. Dobrushin’s Theorem.- 2.6.5. The Existence of the Palm-Khinchin Function.- 2.6.6. The k-Intensity of a Stream.- 2.7. Basic Renewal Theory.- 2.7.1. Definition of Renewal Processes (Renewal Streams).- 2.7.2. A Property of Renewal Streams.- 2.7.3. Relation to the Palm-Khinchin Functions.- 2.7.4. Definition of the Palm-Khinchin Functions for Stationary Renewal Streams.- 2.7.5. Basic Formulas for Renewal Processes.- 2.7.6. Statements of Some Theorems on Stationary Renewal Processes.- 2.8. Limit Theorems for Compound Streams.- 2.8.1. Statement of the Problem.- 2.8.2. Definitions and Notation.- 2.8.3. Statement of the Basic Result and a Proof of Necessity.- 2.8.4. Proof of Sufficiency.- 2.8.5. The Case of Stationary and Orderly Component Streams.- 2.8.6. Additional Remarks.- 2.9. Direct Probabilistic Methods.- 2.10. Limit Theorem for Thinning Streams.- 2.10.1. Statement of the Problem.- 2.10.2. Laplace Transform of Transformed Streams.- 2.10.3. Some Properties of the T-Operation.- 2.10.4. The Tq-Transformation for a Simple Stream.- 2.10.5. Rényi’s Limit Theorem.- 2.11. Additional Limit Theorems for Thinning Streams.- 2.11.1. Belyaev’s Theorem and its Generalizations.- 2.11.2. Rare Events in the Scheme of a Regenerative Process.- 3. Some Classes of Stochastic Processes.- 3.1. Kendall’s Method: Semi-Markov Processes.- 3.1.1. Semi-Markov Processes and Embedded Markov Chains.- 3.1.2. Some Results from the Theory of Markov Chains.- 3.1.3. Basic Relations for Semi-Markov Processes.- 3.1.4. Ergodic Properties of a Semi-Markov Process.- 3.1.5. Method of “Catastrophes”.- 3.2. Linear-Type Markov Processes.- 3.2.1. Definition.- 3.2.2. Basic Equations.- 3.2.3. The Ergodic Theorem for Lined Processes.- 3.2.4. The Method of Integrodifferential Equations.- 3.2.5. Lined Processes with a Fixed Remainder.- 3.2.6. Differential Equations.- 3.3. Piecewise-Linear Markov Processes.- 3.3.1. Method of Additional Variables.- 3.3.2. Piecewise-Linear Markov Process.- 3.3.3. Regularity Conditions.- 3.3.4. Two Reductions.- 3.3.5. Embedded Markov Chain.- 3.4. Other Important Classes of Random Processes.- 4. Semi-Markov Models of Queueing Systems.- 4.1. Classification of Queueing Systems.- 4.2. M?G?1 System.- 4.2.1. Statement of the Problem, Notation.- 4.2.2. Embedded Markov Chain.- 4.2.3. Pollaczek-Khinchin Formula.- 4.2.4. Mathematical Law of a Stationary Queue.- 4.2.5. Virtual Waiting Time.- 4.2.6. The Limiting Distribution of the Waiting Time.- 4.2.7. The Case p ? 1.- 4.3. Nonstationary Characteristics of an M|G|1 System.- 4.3.1. The Busy Period.- 4.3.2. An Integral Equation.- 4.3.3. Functional Equation.- 4.3.4. Distribution of the Number of Customers Served During the Busy Period.- 4.3.5. Distribution of Time until the First Disengagement of the Server.- 4.3.6. Nonstationary Distribution of the Virtual Waiting Time..- 4.3.7. Nonstationary Conditions of the Queueing System for a Simple Incoming Stream.- 4.4. A System of the GI?M?m Type.- 4.4.1. Construction of an Embedded Markov Chain.- 4.4.2. Example.- 4.5. M|G|1 System with an Unreliable and “Renewable” Server.- 4.5.1. Possible Statements of the Problem.- 4.5.2. Failure During Idle Time.- 4.5.3. The General Case.- 4.5.4. The Influence of Partial Failure.- 4.6. Mixed Service Systems.- 4.6.1. Mixed System with Constant Service Rate.- 4.6.2. Condition for Ergodicity.- 4.6.3. Mixed System with Variable Service Rate.- 4.6.4. Example.- 4.6.5. M?G?1?m System.- 4.7. Systems with Restrictions.- 4.7.1. Various Forms of Restrictions.- 4.7.2. Formulation of Restrictions.- 4.7.3. Existence of the Ergodic Distribution.- 4.7.4. Equation for the Stationary Distribution.- 4.7.5. Embedded Markov Chain.- 4.8. Priority Service.- 4.8.1. Assumptions and Notation.- 4.8.2. Service of Customers of the First Type.- 4.8.3. The Method of Investigation.- 4.8.4. Determination of the Function ??(s).- 4.8.5. Determination of the Function ?*2 (s).- 4.8.6. The Ergodicity Condition.- 4.9. The Generalized Scheme of Priority Service with a Limited Queue.- 4.9.1. Statement of the Problem.- 4.9.2. The Structure of the Process.- 4.9.3. Basic Equations.- 4.9.4. Remarks.- 5. Application of More General Methods.- 5.1. The GI?G?1 System.- 5.1.1. Basic Recurrence Relations.- 5.1.2. The Integral Equation; The Existence of the Limiting Distribution.- 5.1.3. Analytic Methods.- 5.2. GI?G?m Systems.- 5.2.1. Multidimensional Random Walk.- 5.2.2. Kiefer and Wolfowitz’s Ergodic Theorem.- 5.3. The M?G?m?0 System.- 5.3.1. The Ergodic Theorem.- 5.3.2. Proof of Sevast’yanov’s Formula.- 5.4. More Complex Systems with Losses.- 5.4.1. Reliability of a Renewable System.- 5.4.2. A Renewable System with a Variable Renewal Rate.- 5.4.3. Incompletely Accessible Service System.- 5.4.4. A Necessary and Sufficient Condition for Solvability of the State Equations of a System in Constants.- 5.4.5. Further Generalizations.- 5.4.6. The Problem of Redundancy with a Redistributed Load.- 5.5. Ergodic Theorems.- 5.5.1. Sevast’yanov’s Theorem.- 5.5.2. Construction of Innovation Times.- 5.5.3. Stability of Queueing Systems.- 5.6. Heavily Loaded Queueing Systems.- 5.6.1. Limit Theorem for Distribution of Waiting Time in a GI?G?1 System.- 5.6.2. Utilization of the Invariance Principle.- 5.6.3. Borovkov’s Theorem.- 5.6.4. Asymptotic Invariance.- 5.7. Underloaded Queueing Systems.- 5.7.1. Introductory Remarks.- 5.7.2. Statement of the Problem.- 5.7.3. Investigation of the Process ?x(t).- 5.8. Little’s Theory and its Corollaries.- 5.8.1. General Statements.- 5.8.2. Little’s Theorem.- 5.8.3. Notes.- 6. Statistical Simulation of Systems.- 6.1. Principles of the Monte Carlo Method.- 6.1.1. Foundation of the Methodology.- 6.1.2. Weighted Simulation.- 6.2. Simulation of Some Classes of Random Processes.- 6.2.1. Preliminary Remarks.- 6.2.2. Simulation of Random Trials and Variables.- 6.2.3. Simulation of a Homogeneous Markov Chain.- 6.2.4. Simulation of a Markov Process with a Finite Set of States.- 6.2.5. Simulation of a Semi-Markov Process with a Finite Set of States.- 6.2.6. Simulation of a Piecewise-Linear Markov Process.- 6.3. Statistical Problems Associated with Simulation.- 6.4. Simulation of Queueing Systems.- 6.4.1. General Principles of Simulation of Systems.- 6.4.2. Block Principle of Simulation.- 6.4.3. Piecewise-Linear Aggregates.- 6.4.4. A Typical Element of the Model.- 6.4.5. Interpretation of Elements of Queueing Systems.- 6.5. Calculation of Corrections to Characteristics of Systems.- 6.5.1. Introductory Remarks.- 6.5.2. Statement of the Problem.- 6.5.3. Remark.- 6.5.4. Notes.