(s; S); (r; Q), random reorder quantity, etc. is presented. Stochastic decomposition results are also discussed. A brief description of the work done in queues with the requirement of additional items for service, is also provided.
Chapter 8 examines a transient analysis of Markovian queueing systems focussing on the derivation of closed-form solutions for the main transient state distributions and the development of numerical techniques with the aim to position and underline the role of the uniformization technique.
The two volumes of Queueing Theory will be useful for graduate and PhD students, lecturers, and also the researchers and developers working in mathematical and stochastic modelling and various applications in computer and communication networks, science and engineering in the departments of Mathematics & Applied Mathematics, Statistics, or Operations Research at universities and in various research and applied centres.
1
Stability Analysis of Queueing Systems based on Synchronization of the Input and Majorizing Output Flows
Larisa AFANASEVA
Department of Probability, Faculty of Mathematics and Mechanics, Lomonosov Moscow State University, Russia
This chapter is focused on the stability conditions for a multiserver queueing system with heterogeneous servers and a regenerative input flow X. The main idea is constructing an auxiliary service process Y, which is also a regenerative flow and determination of the common points of regeneration for both processes X and Y. Then the traffic rate is defined in terms of the mean of the increments of these processes on a common regeneration period. It allows us to use well-known results from the renewal theory to find the instability and stability conditions. The possibilities of the proposed approach are demonstrated by examples. We also present the applications to transport system capacity analysis.
1.1. Introduction
This chapter deals with the study of stability conditions for a heterogeneous multiserver queueing system with regenerative input flow (Afanaseva 2019).
We consider queueing systems with regenerative input flow for three reasons. First, a process describing the performance of the system under some natural conditions turns out to be a classical regenerative process (Asmussen 2003; Thorisson 2000) and the renewal theory gives very effective tools for asymptotic analysis of the system. Second, the class of regenerative flows is rather wide and includes fundamental flows from queueing theory. Finally, regenerative flow has some useful properties that allow us to investigate various applied models (Afanasyeva and Bashtova 2014).
The main objective of our study is to determine conditions under which the process describing the performance of the system is stochastically bounded and therefore, under some additional assumptions, a stable process.
Let us note that stability results for the classical homogeneous multiserver queue are very well known. We refer to the works of (Kiefer and Wolfowitz 1955) for the GI|GI|m system and the general ergodicity results of (Loynes 1962). As it was shown in Sadowsky (1995), the proposed approach could not be applied for heterogeneous systems. Instead, in the work of (Sadowsky 1995), the stability is examined from the point of view of Harris recurrent Markov chain theory. Based on the works of (Malyshev and Menshikov 1982; Meyn and Tweedie 2009; Georgiadis and Szpankowski 1992; Szpankowski 1994), the author obtained two results concerning the irreducibility and positive Harris recurrence of the corresponding process.
The heterogeneous multiserver queueing system with regenerative flow was investigated in the papers of (Afanasyeva and Tkachenko 2014, 2016, 2018). Under some assumptions, the necessary and sufficient stability condition was obtained there.
We consider m-server queueing system S with regenerative input flow X with intensity λX. The main assumption is that the process X does not depend on the stochastic sequences and processes determining the work of the servers, such as service time, the moments of breakdowns and recovery of the servers, and the random numbers of the servers required for the service of the customers.
We construct an auxiliary system S0 with input flow X0. The latter does not depend on X and is determined by the stochastic sequence describing the work of the servers. The flow X0 is constructed in such a way that there are always customers for service. We introduce an auxiliary flow Y, which is the number of customers served in the system S0 up to time t. Then we establish the conditions of Y being the regenerative flow with the intensity λγ.
The basic idea is constructing the common points of regeneration for both processes X and Y. Then we define the traffic rate of the system in terms of the first moments of increments of these processes on the common regeneration period. Under some conditions, we estimate the increments of the service process ỹ(t) in the original system S (that is the number of customers served in the system up to time t) with the help of increments of an auxiliary process Y (t). It allows us to prove instability results and to find conditions of stochastic boundedness of the number of customers Q(t) at the system at time t as t → ∞.
One more traditional approach to the analysis of stability of the queueing systems is based on the regenerative structure of the processes describing the states of the system, such as the number of customers in the system or workload process. We make assumptions providing the presence of the points of the regeneration for the processes. Then, it is required to establish the finiteness of the mean of the times between the regenerations in accordance with the theorem of (Smith 1955). It is quite a complex problem for non-Markovian processes. Exactly this approach is employed in several works of Morozov and colleagues (Morozov et al. 2011; Morozov 2004, 2007; Morozov and Dimitriou 2017; Morozov and Rumyantsev 2016) for establishing the conditions for stability of a wide circle of models. Although our approach is also based on the notions of regeneration and synchronization, it significantly differs from the approach employed in the works mentioned earlier. Our main objective is to establish necessary and sufficient conditions of the stochastic boundedness of the process, describing the system. Thus, this process does not have to be regenerative. Let us point out that a similar situation emerges in the classic models (Borovkov 1976). The analysis of the stochastic boundedness of the process is important for the applications, since precisely the existence of the stochastic boundaries manifests that the system successfully deals with the task. Our conditions may seem too restrictive to be useful in applications. Therefore, we consider four models with service interruptions as examples. In particular, in section 1.7, a discrete-time heterogeneous multiserver queueing system with a regenerative input flow and service interruptions, which are described by independent renewal processes for various servers, is discussed. It is shown that the traffic rate ρ is not expressed in terms of the first moments of the random variables defining the model for the preemptive repeat different service discipline (Gaver 1962). We also prove that Q(t) → ∞ as t → ∞ when ρ ≥ 1 and Q(t) is a stochastically bounded process when ρ < 1.
We should consider that models with service interruptions occur in numerous applications including manufacturing processes, multiprocessor computer networks, telecommunicating networks and various types of service counters.
White and Christie (1958) were the first to study queueing systems with interruptions. Those authors investigated the M|M|1 model
