Mathematical Methods for Construction of Queueing Models

to the English edition Many processes that describe the operation of engineering, economic, organiza­ tional, and other systems are represented as sequences of operations performed on material, information, or other types of flows. Typical examples are processes of connection of telephone users, data transmission and processing, calculation at multi user computer centers, and queueing at service centers. The models studied by the theory of service systems, or queueing theory, are used to describe such processes. The more pessimistic term "queueing theory" is used more often in the non-Soviet literature. Random arrivals (requests for service), probability distributions defining queueing processes (distributions of service times and acceptable waiting times), and structure parameters (customer priorities, parameters that delimit acceptable queues, parameters that define paths of customers, etc.) are characteristic com­ ponents of queueing models. Typical output characteristics of queueing models are the probability distributions of queue lengths, waiting times, lengths of busy periods, and so forth.

1 Substantive Formulation of the Problem of Queueing Model Construction.- 1.1 Construction of a Model as an Object of Study.- 1.2 The Problem of Identification of Classes and Values of Model Parameters.- 1.3 The Problem of Model Simplification. Approximation of Models.- 1.4 The Stability Problem.- 1.5 A General Schema of Model Construction.- 1.6 Discussion and Review of Literature.- 2 The Concept of Characterization as a General Mathematical Schema for Constructing Queueing Models.- 2.1 Queueing Models. Formalization of Queueing Models.- 2.1.1 General Concepts and Notation.- 2.1.2 Single-Channel Models.- 2.1.3 Multichannel Models.- 2.1.4 The Multiphase Model.- 2.1.5 The Multiphase-Multichannel Model.- 2.2 The Problem of Pure Characterization of a Queueing Model.- 2.3 The Direct Characterization Problem and Its Stability.- 2.4 The Inverse Characterization Problem and Its Stability.- 2.5 Discussion and Review of the Literature 44.- 3 Probability Metrics.- 3.1 Introductory Remarks.- 3.1.1 The Concept of the Metric in Probability Theory.- 3.1.2 Problems of the Theory of Probability Metrics.- 3.2 The Concept of Probability Metric.- 3.2.1 Basic Notation and Definitions.- 3.2.2 Definition of Probability Metric. The Berkes-Philipp Lemma.- 3.2.3 Compound and Simple Metrics.- 3.3 Examples of Probability Metrics.- 3.3.1 Auxiliary Notation.- 3.3.2 Compound Metrics.- 3.3.3 Simple Metrics.- 3.4 Classification of Probability Metrics.- 3.4.1 The Hausdorff Structure (the A-Structure).- 3.4.2 The A-Structure.- 3.4.3 Representation of the Hausdorff Structure in the Form of the A-Structure.- 3.4.4 The ?-Structure of Probability Metrics.- 3.4.5 The ? -Structure of Simple Metrics.- 3.5 The Concept of Minimality of Probability Metrics.- 3.5.1 Definition of Minimal Metric.- 3.5.2 Invariant Relations.- 3.6 Dual Relations for Compound and Related Minimal Metrics.- 3.6.1 Generalized Kantorovich Theorem.- 3.6.2 Strassen Theorem.- 3.7 Explicit Representations for Minimal Metrics.- 3.7.1 Minimal Metrics with the ?-Structure.- 3.7.2 Minimal Metrics with the Hausdorff Structure.- 3.8 The Concept of Ideality of Probability Metrics.- 3.8.1 Definition and Basic Properties of Ideal Metrics.- 3.8.2 Ideal Metrics with the ?-Structure.- 3.9 Topological Properties of Probability Metrics. The Concept of Compactness.- 3.9.1 Definitions. General Criterion of Topological Comparability of Metrics.- 3.9.2 The General Compactness Criterion.- 3.9.3 The Compactness Criterion for Weak Metrics.- 3.9.4 The Compactness Criterion for Strong Metrics.- 3.10 Relations Between Metrics.- 3.10.1 Bounds of the Metrics $$\mu _{n,p}^{\left( 7 \right)} \mu _{n,p}^{(7)}$$.- 3.10.2 Relations Between Minimal Metrics.- 3.10.3 Bounds for ?-Metrics.- 3.10.4 Relations Between Ideal Metrics.- 3.11 Discussion of Results and Review of Literature.- 4 Characterization of the Components of Queueing Models.- 4.1 Formulation of the Problem.- 4.2 Characterization of a Poisson Flow in Terms of the Aging Property. Evaluation of Stability.- 4.2.1 Ag-Classes of Random Variables.- 4.2.2 Characterization of an Exponential Distribution in Terms of the Aging Property.- 4.2.3 Estimates of the Degree of Closeness of a Perturbed Flow to a Poisson Flow.- 4.3 Characterization of an Erlang Flow in Terms of the Aging Property.- 4.4 Characterization of a Renewal Flow in Terms of the Aging Property.- 4.4.1 The Order Relation Based on the Aging Property.- 4.4.2 Estimate of the Closeness of Flows Based on Weak Comparability of Their Components.- 4.5 Characterization of a Poisson Flow in Terms of the Lack-of-Memory Property.- 4.5.1 The LM-Property of Multivariate Distributions.- 4.5.2 Characterization of an Exponential Distribution in Terms of the LM-Property.- 4.5.3 Estimates of the Stability of Characterization of a Poisson Input Flow in Terms of the LM-Property.- 4.6 Stability of the Characterization of a Poisson Flow as a Stationary, Ordinary Flow Without Memory.- 4.6.1 Notation and Auxiliary Estimates.- 4.6.2 Stability of Characterization.- 4.7 Chaxacterization of an Erlang Flow in Terms of the LM-Property.- 4.8 Characterization of Random Flows in Terms of Sample Characteristics.- 4.9 Auxiliary Results from a Comparison of Metrics.- 4.10 Discussion of Results and Review of Literature.- 5 Methods of Analysis of the Continuity of Queueing Models.- 5.1 Formulation of the Problem and Its Practical Import.- 5.2 Continuity on Finite Time Intervals (Output Data as a Random Sequence).- 5.2.1 Basic Notation.- 5.2.2 General Evaluations of Continuity.- 5.3 Evaluations for Sequences Generated by Piecewise-Linear Transforms.- 5.3.1 Definitions.- 5.3.2 Properties of Piecewise-Linear Transforms.- 5.4 Examples.- 5.4.1 Duplication with Renewal.- 5.4.2 The Single-Channel Queueing Model.- 5.4.3 The Multichannel Queueing Model.- 5.4.4 The Multiphase Queueing Model.- 5.4.5 The Multiphase-Multichannel Queueing Model.- 5.5 Continuity on Finite Time Intervals (Output Data as a Stochastic Process).- 5.6 Continuity Uniform in Time.- 5.6.1 Coupling of Random Sequences.- 5.6.2 Evaluations of Continuity in Terms of Coupling.- 5.6.3 Regenerative Processes.- 5.6.4 Renewal Processes.- 5.6.5 Estimates of the First-Passage Time.- 5.7 Examples.- 5.7.1 The Single-Channel Queueing Model.- 5.7.2 The Multichannel Queueing Model.- 5.7.3 The Multiphase-Multichannel Queueing Model.- 5.7.4 The Doubling-with-Renewal Model.- 5.8 Discussion of Results and Review of Literature.- 6 Construction of Queueing Models from Observations of Their Inputs - Direct Problems of Characterization.- 6.1 Introductory Remarks.- 6.2 Characterization of Queueing Models in Terms of the Aging Property.Evaluations of Stability.- 6.2.1 Characterization of a Model of the Type MI ? | MI µ | 1 | ?.- 6.2.2 Characterization of Models with Erlang Input and Service Flows.- 6.2.3 Characterization of a Model of the Type GI | GI | 1 | ?.- 6.3 Characterization of Queueing Models in Terms of the Lack-of-Memory Property.- 6.3.1 Characterization of Models of the Type MI ? | MI µ | 1 | ? and MI | MI | 1 |?.- 6.3.2 Characterization of Models of the Type GI | GI | 1 | ?.- 6.4 Characterization of Queueing Models in Terms of Empirical Distributions of the Input Flow and Service Flow.- 6.5 Evaluations Uniform in Time of the Stability of Characterization.- 6.6 Characterization of the Multiphase-Multichannel Model.- 6.7 Unsolved Problems.- 7 Identification of Individual Queueing Models from Observations of Output Data - Inverse Characterization Problems.- 7.1 Introductory Remarks.- 7.2 Identification of Queueing Models.- 7.2.1 The Model MI | GI | 1 | ?.- 7.2.2 The Model G | G | 1 | ?.- 7.2.3 The Model M | GI | 1 | ?.- 7.2.4 The Model MI? | GI i | 1 | ?.- 7.2.5 The Model MI? | GI | 1 | 0.- 7.2.6 The Model GI | GI | ?.- 7.3 Identification of a Class of Queueing Models.- 7.3.1 The Model GI | GI | 1 | ?.- 7.3.2 The Model GI | GI | ?.- 7.4 Remarks and Comments.- 8 Simplification and Approximation of Probability Models.- 8.1 Formulation of the Problem, and an Approach to the Solution.- 8.2 Hyper-Erlang Approximation of Distribution Functions and Estimates of Its Accuracy.- 8.2.1 Formulation of the Problem.- 8.2.2 Erlang Approximation of a Degenerate Distribution.- 8.2.3 Hyper-Erlang Approximation of Arbitrary Distributions.- 8.3 Finite Approximation of Countable Markov Chains.- 8.3.1 Approximation of Stationary Distributions.- 8.3.2 Uniform Approximation of Prestationary Distributions.- 8.4 Finite Approximation of Noncountable Markov Chains.- 8.5 Approximation of Output Flows.- 8.6 The Problem of Asymptotic Consolidation of States.- 8.7 Discussion and Review of Literature.- Appendix 1 The Prokhorov Criterion and Skorokhod’s Theorem of the Weak Convergence of Measures.- Appendix 2 The Duality Theorem of Linear Programming.- Appendix 3 Uniformly Integrable Random Variables.- Appendix 4 The Space D)[0, ?).- Appendix 5 Ancillary Information from the Theory of Markov Processes.- Appendix 6 Estimates of the Coupling Times for Discrete Renewal Processes.- References.- Index of Notation.