Switching Processes in Queueing Models

Vladimir V. Anisimov is currently Director of the Research Statistics Unit at GlaxoSmithKline, UK. He has written about 200 papers, nine books and manuals in this area.

• Preface 13Definitions 17Chapter 1. Switching Stochastic Models 191.1. Random processes with discrete component 191.1.1.Markov and semi-Markov processes 211.1.2. Processes with independent increments and Markov switching 211.1.3. Processes with independent increments and semi-Markov switching 231.2. Switching processes 241.2.1. Definition of switching processes 241.2.2. Recurrent processes of semi-Markov type (simple case) 261.2.3.RPSMwithMarkov switching 261.2.4. General case of RPSM 271.2.5. Processes with Markov or semi-Markov switching 271.3. Switching stochastic models 281.3.1. Sums of random variables 291.3.2. Random movements 291.3.3. Dynamic systems in a random environment 301.3.4. Stochastic differential equations in a random environment 301.3.5. Branching processes 311.3.6. State-dependent flows 321.3.7. Two-level Markov systems with feedback 321.4. Bibliography 33Chapter 2. Switching Queueing Models 372.1. Introduction 372.2. Queueing systems 382.2.1. Markov queueing models 382.2.1.1. A state-dependent system MQ/MQ/1/∞ 392.2.1.2. Queueing system MM,Q/MM,Q/1/m 402.2.1.3. System MQ,B/MQ,B/1/∞ 412.2.2.Non-Markov systems 422.2.2.1. Semi-Markov system SM/MSM,Q/1 422.2.2.2. System MSM,Q/MSM,Q/1/∞ 432.2.2.3. System MSM,Q/MSM,Q/1/V 442.2.3. Models with dependent arrival flows 452.2.4. Polling systems 462.2.5. Retrial queueing systems 472.3. Queueing networks 482.3.1. Markov state-dependent networks 492.3.1.1. Markov network (MQ/MQ/m/∞)r  492.3.1.2. Markov networks (MQ,B/MQ,B/m/∞)r with batches 502.3.2.Non-Markov networks 502.3.2.1. State-dependent semi-Markov networks 502.3.2.2. Semi-Markov networks with random batches 522.3.2.3. Networks with state-dependent input 532.4.Bibliography 54Chapter 3. Processes of Sums of Weakly-dependent Variables 573.1. Limit theorems for processes of sums of conditionally independent random variables 573.2. Limit theorems for sums with Markov switching 653.2.1. Flows of rare events 673.2.1.1. Discrete time 673.2.1.2. Continuous time 693.3. Quasi-ergodic Markov processes 703.4. Limit theorems for non-homogenous Markov processes 733.4.1. Convergence to Gaussian processes 743.4.2. Convergence to processes with independent increments 783.5. Bibliography 81Chapter 4. Averaging Principle and Diffusion Approximation for Switching Processes 834.1. Introduction 834.2. Averaging principle for switching recurrent sequences 844.3. Averaging principle and diffusion approximation for RPSMs 884.4. Averaging principle and diffusion approximation for recurrent processes of semi-Markov type (Markov case) 954.4.1. Averaging principle and diffusion approximation for SMP 1054.5. Averaging principle for RPSM with feedback 1064.6. Averaging principle and diffusion approximation for switching processes 1084.6.1. Averaging principle and diffusion approximation for processes with semi-Markov switching 1124.7. Bibliography 113Chapter 5. Averaging and Diffusion Approximation in Overloaded Switching Queueing Systems and Networks 1175.1. Introduction 1175.2. Markov queueing models 1205.2.1. System MQ,B/MQ,B/1/∞ 1215.2.2. System MQ/MQ/1/∞ 1245.2.3. Analysis of the waiting time 1295.2.4. An output process 1315.2.5. Time-dependent system MQ,t/MQ,t/1/∞ 1325.2.6. Asystemwith impatient calls 1345.3. Non-Markov queueing models 1355.3.1. System GI/MQ/1/∞ 1355.3.2. Semi-Markov system SM/MSM,Q/1/∞ 1365.3.3. System MSM,Q/MSM,Q/1/∞ 1385.3.4. System SMQ/MSM,Q/1/∞ 1395.3.5. System GQ/MQ/1/∞ 1425.3.6. A system with unreliable servers 1435.3.7. Polling systems 1455.4. Retrial queueing systems 1465.4.1. Retrial system MQ/G/1/w.r 1475.4.2. System M¯ /G¯/1/w.r 1505.4.3. Retrial system M/M/m/w.r 1545.5. Queueing networks 1595.5.1. State-dependent Markov network (MQ/MQ/1/∞)r 1595.5.2. Markov state-dependent networks with batches 1615.6. Non-Markov queueing networks 1645.6.1. A network (MSM,Q/MSM,Q/1/∞)r with semi-Markov switching 1645.6.2. State-dependent network with recurrent input 1695.7. Bibliography 172Chapter 6. Systems in Low Traffic Conditions 1756.1. Introduction 1756.2. Analysis of the first exit time from the subset of states 1766.2.1. Definition of S-set 1766.2.2. An asymptotic behavior of the first exit time 1776.2.3. State space forming a monotone structure 1806.2.4. Exit time as the time of first jump of the process of sums with Markov switching 1826.3. Markov queueing systems with fast service 1836.3.1. M/M/s/m systems 1836.3.1.1. System MM/M/l/m in a Markov environment 1856.3.2. Semi-Markov queueing systems with fast service 1886.4. Single-server retrial queueing model 1906.4.1. Case 1: fast service 1916.4.1.1. State-dependent case 1946.4.2. Case 2: fast service and large retrial rate 1956.4.3. State-dependent model in a Markov environment 1976.5. Multiserver retrial queueing models 2016.6. Bibliography 204Chapter 7. Flows of Rare Events in Low and Heavy Traffic Conditions 2077.1. Introduction 2077.2. Flows of rare events in systems with mixing 2087.3. Asymptotically connected sets (Vn-S-sets) 2117.3.1. Homogenous case 2117.3.2. Non-homogenous case 2147.4. Heavy traffic conditions 2157.5. Flows of rare events in queueing models 2167.5.1. Light traffic analysis in models with finite capacity 2167.5.2. Heavy traffic analysis 2187.6. Bibliography 219Chapter 8. Asymptotic Aggregation of State Space 2218.1. Introduction 2218.2. Aggregation of finite Markov processes (stationary behavior) 2238.2.1. Discrete time 2238.2.2. Hierarchic asymptotic aggregation 2258.2.3. Continuous time 2278.3. Convergence of switching processes 2288.4. Aggregation of states in Markov models 2318.4.1. Convergence of the aggregated process to a Markov process (finite state space) 2328.4.2. Convergence of the aggregated process with a general state space 2368.4.3. Accumulating processes in aggregation scheme 2378.4.4. MP aggregation in continuous time 2388.5. Asymptotic behavior of the first exit time from the subset of states (non-homogenous in time case) 2408.6. Aggregation of states of non-homogenous Markov processes 2438.7. Averaging principle for RPSM in the asymptotically aggregated Markov environment 2468.7.1. Switching MP with a finite state space 2478.7.2. Switching MP with a general state space 2508.7.3. Averaging principle for accumulating processes in the asymptotically aggregated semi-Markov environment 2518.8. Diffusion approximation for RPSM in the asymptotically aggregated Markov environment 2528.9. Aggregation of states in Markov queueing models 2558.9.1. System MQ/MQ/r/∞ with unreliable servers in heavy traffic 2558.9.2. System MM,Q/MM,Q/1/∞ in heavy traffic 2568.10. Aggregation of states in semi-Markov queueing models 2588.10.1. System SM/MSM,Q/1/∞ 2588.10.2. System MSM,Q/MSM,Q/1/∞ 2598.11. Analysis of flows of lost calls 2608.12. Bibliography 263Chapter 9. Aggregation in Markov Models with Fast Markov Switching 2679.1. Introduction 2679.2. Markov models with fast Markov switching 2699.2.1.Markov processes with Markov switching 2699.2.2. Markov queueing systems with Markov type switching 2719.2.3. Averaging in the fast Markov type environment 2729.2.4. Approximation of a stationary distribution 2749.3. Proofs of theorems 2759.3.1. Proof of Theorem 9.1 2759.3.2. Proof of Theorem 9.2 2779.3.3. Proof of Theorem 9.3 2799.4. Queueing systems with fast Markov type switching 2799.4.1. System MM,Q/MM,Q/1/N 2799.4.1.1. Averaging of states of the environment 2799.4.1.2. The approximation of a stationary distribution 2809.4.2. Batch system BMM,Q/BMM,Q/1/N 2819.4.3. System M/M/s/mwith unreliable servers 2829.4.4. Priority model MQ/MQ/m/s,N 2839.5. Non-homogenous in time queueing models 2859.5.1. SystemMM,Q,t/MM,Q,t/s/m with fast switching – averaging of states 2869.5.2. System MM,Q/MM,Q/s/m with fast switching – aggregation of states 2879.6. Numerical examples 2889.7. Bibliography 289Chapter 10. Aggregation in Markov Models with Fast Semi-Markov Switching 29110.1. Markov processes with fast semi-Markov switches 29210.1.1.Averaging of a semi-Markov environment 29210.1.2. Asymptotic aggregation of a semi-Markov environment 30010.1.3. Approximation of a stationary distribution 30510.2. Averaging and aggregation in Markov queueing systems with semi-Markov switching 30910.2.1.Averaging of states of the environment 30910.2.2. Asymptotic aggregation of states of the environment 31010.2.3. The approximation of a stationary distribution 31110.3. Bibliography 313Chapter 11. Other Applications of Switching Processes 31511.1. Self-organization in multicomponent interacting Markov systems 31511.2. Averaging principle and diffusion approximation for dynamic systems with stochastic perturbations 31911.2.1. Recurrent perturbations 31911.2.2. Semi-Markov perturbations 32111.3. Random movements 32411.3.1. Ergodic case 32411.3.2. Case of the asymptotic aggregation of state space 32511.4. Bibliography 326Chapter 12. Simulation Examples 32912.1. Simulation of recurrent sequences 32912.2. Simulation of recurrent point processes 33112.3. Simulation ofRPSM 33212.4. Simulation of state-dependent queueing models 33412.5. Simulation of the exit time from a subset of states of a Markov chain 33712.6. Aggregation of states in Markov models 340Index 343