Introduction to Queuing Theory

Prof. Dr. B.W. Gnedenko galt als einer der führenden russischen Spezialisten auf dem Gebiet der Wahrscheinlichkeitstheorie. Seine Arbeiten zur Wahrscheinlichkeitstheorie, zur mathematischen Statistik und zur Mathematikgeschichte leisteten einen wichtigen Beitrag zur Entwicklung dieser Gebiete.
Während einer Gastprofessur des Autors an der Humboldt-Universität Berlin entstand der Kontakt zu Prof. Dr. H.-J. Roßberg, der für die Herausgabe der deutschen Ausgabe des bewährten Standardwerkes verantwortlich ist.

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 o 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¿i¿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 MG1 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. MG1 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.

to the Second Edition.- to the First Edition.- 1. Problems of Queueing Theory under the Simplest Assumptions.- 1.1. Simple Streams.- 1.2. Service with Waiting.- 1.3. Birth and Death Processes.- 1.4. Applications of Birth and Death Processes in Queueing Theory.- 1.5. Priority Service.- 1.6. General Principles of Constructing Markov Models of Systems.- 1.7. Systems with Limited Waiting Time.- 1.8. Systems with Bounded Holding Times.- 2. The Study of the Incoming Customer Stream.- 2.1. Some Examples.- 2.2. A Simple Nonstationary Stream.- 2.3. A Property of Stationary Streams.- 2.4. General Form of Stationary Streams without Aftereffects.- 2.5. The Palm-Khinchin Functions.- 2.6. Characteristics of Stationary Streams and the Lebesgue Integral.- 2.7. Basic Renewal Theory.- 2.8. Limit Theorems for Compound Streams.- 2.9. Direct Probabilistic Methods.- 2.10. Limit Theorem for Thinning Streams.- 2.11. Additional Limit Theorems for Thinning Streams.- 3. Some Classes of Stochastic Processes.- 3.1. Kendall's Method: Semi-Markov Processes.- 3.2. Linear-Type Markov Processes.- 3.3. Piecewise-Linear Markov Processes.- 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.3. Nonstationary Characteristics of an M|G|1 System.- 4.4. A System of the GI?M?m Type.- 4.5. M|G|1 System with an Unreliable and "Renewable" Server.- 4.6. Mixed Service Systems.- 4.7. Systems with Restrictions.- 4.8. Priority Service.- 4.9. The Generalized Scheme of Priority Service with a Limited Queue.- 5. Application of More General Methods.- 5.1. The GI?G?1 System.- 5.2. GI?G?m Systems.- 5.3. The M?G?m?0 System.- 5.4. More Complex Systems with Losses.- 5.5. Ergodic Theorems.- 5.6.Heavily Loaded Queueing Systems.- 5.7. Underloaded Queueing Systems.- 5.8. Little's Theory and its Corollaries.- 6. Statistical Simulation of Systems.- 6.1. Principles of the Monte Carlo Method.- 6.2. Simulation of Some Classes of Random Processes.- 6.3. Statistical Problems Associated with Simulation.- 6.4. Simulation of Queueing Systems.- 6.5. Calculation of Corrections to Characteristics of Systems.