Queueing Theory 2. Nikolaos Limnios
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 with preemptive resume priority discipline. Their results were later extended by (Avi-Itzhak and Naor 1963) and (Thiruvengadam 1963) who study queues with general service times. Gaver (1962) studied single-server queues with batch Poisson arrivals and generally distributed service times. So far there is extensive literature concerning queueing systems with interruptions. There are some review papers that cover most of the literature in this sphere. Some of the important papers on the single-server case are presented in Fiems and Bruneel (2013).
The most extensive literature survey on systems with interruptions both for single-server and multiserver cases is given by (Krishnamoorthy et al. 2012). This paper also covers some non-Markovian multichannel systems with homogeneous servers. There are some other articles with extensive literature survey as well (Pechinkin et al. 2009; Morozov et al. 2011). Nevertheless, to the best of our knowledge, there are no papers that study the stability problem for multichannel queueing systems with heterogeneous servers in non-Markovian case with general input flow and service times. Synchronization method combined with the regenerative theory is one of the powerful approaches to obtain stability conditions for such systems.
Let us also mention the fluid approximation approach as an alternative to the synchronization approach followed here. Such an approach has lent to significant progress in stability analysis of multiclass queueing networks (Dai 1995; Chen 1995; Chen and Yao 2001). See also Foss and Konstantopoulos (2004) for a survey of various approaches to stability of queueing systems with a focus on the fluid approach. Nevertheless, our analysis does not rely on a fluid approach because to the best of our knowledge, the synchronization method with regard to regenerative structure of the processes turns out to be suitable for obtaining complete and transparent proofs as well as natural stability conditions for the model at hand.
We also note that stability analysis is an essential and challenging stage of investigation of a stochastic model, however, stability conditions may be of independent interest. In particular, the stability criterion of the multiserver model can be used for the capacity planning of the model at the design stage to obtain the lower bound of the capacity that keeps system stable. As an example of applications of our results, we estimate the carrying capacity of the automobile road, intersected by a crosswalk. Under capacity we mean the upper bound of the intensity of the flow of cars when the queue of cars does not tend to infinity. This means that the analysis can be based on the results obtained in this chapter.
1.2. Model description
We begin from the definition of the regenerative flow (Afanasyeva and Bashtova 2014)). Assume a stochastic process {X(t), t ≥ 0} (X(0) = 0) taking values 0, 1, 2... to be defined in a probability space
DEFINITION 1.1.– The stochastic flow X is called regenerative if there is an increasing sequence of Markov moments with respect to such that the sequence
consists of independent identically distributed (iid) random elements on
The random variable
We consider discrete-time queueing systems as well as continuous-time queueing systems (Avi-Itzhak and Naor 1963). In the first case, time is divided into fixed length intervals or slots and all arrivals and departures are synchronized with respect to slot boundaries. Moreover, in the case of some events being synchronized at one slot these events are ordered as follows: arrival and departure. The system is observed at the end of the slot.
We consider a queueing system S with m servers, FCFS discipline and regenerative input flow X . We assume that a server may simultaneously serve only one customer so that at any time the number of customers on the servers is not more than m. A customer leaves a system only after completion the service. The system is defined by the sequence
[1.1]
takes place for some function Φ(∙) on the corresponding space. For example, for the system Reg|G|1|∞ we consider the process
The main goal of this chapter is the determination of the conditions of the stochastic boundedness of the number of customers Q(t) in the system as t → ∞. Our analysis is based on the construction of the auxiliary service process.
1.3. Auxiliary service