An enhanced algorithm to solve multiserver retrial queueing systems with impatient customers

The homogenization of the state space for solving retrial queues refers to an approach, where the performance of the M/M/c retrial queue with impatient customers and c servers is approximated with a retrial queue with a maximum retrial rate restricted beyond a given number of users in the orbit. As a consequence, the stationary distribution can be obtained by the matrix-geometric method, which requires the computation of the rate matrix. In this paper, we revisit an approach based on the homogenization of the state space. We provide the exact expression for the conditional mean number of customers based on the computation of the rate matrix R with the time complexity of O(c). We develop simplified equations for the memory-efficient implementation of the computation of the performance measures. We construct an efficient algorithm for the stationary distribution with the determination of a threshold that allows the computation of performance measures with a specific accuracy.     

An M/PH/k retrial queue with finite number of sources

We study retrial queues with a finite source of customers and identical multiple servers in parallel. Service time requirements in such systems are not of exponential type, yet most of the models assume this service distribution. In this paper, we allow the service times to assume phase type distribution and present two different types of Markov chains based on state space arrangements, for modelling the system. We discuss the special features of the two formulations, show how to obtain some key performance measures and present numerical examples.     

Retrial queuing system with Markovian arrival flow and phase-type service time distribution

We consider a multi-server queuing system with retrial customers to model a call center. The flow of customers is described by a Markovian arrival process (MAP). The servers are identical and independent of each other. A customer’s service time has a phase-type distribution (PH). If all servers are busy during the customer arrival epoch, the customer moves to the buffer with a probability that depends on the number of customers in the system, leaves the system forever, or goes into an orbit of infinite size. A customer in the orbit tries his (her) luck in an exponentially distributed arbitrary time. During a waiting period in the buffer, customers can be impatient and may leave the system forever or go into orbit. A special method for reducing the dimension of the system state space is used. The ergodicity condition is derived in an analytically tractable form. The stationary distribution of the system states and the main performance measures are calculated. The problem of optimal design is solved numerically. The numerical results show the importance of considering the MAP arrival process and PH service process in the performance evaluation and capacity planning of call centers.     

A M/D/1 vacation queue model for a signalized intersection

We consider a queueing system that arises in the modeling of isolated signalized intersections in a urban transportation network. In this system, the server alternates in two states, attended or removed, in respect to the queue, while in each state, the server will spend a constant time period with different value. It is assumed that the server is able to disperse up to r(r≥1) customers during a constant service cycle. The evolution of this queueing system can be characterized by a Markov chain embedded at equally spaced time epochs along the time axis. Transition matrix of this Markov chain is of the M/G/1 type introduced by Neuts so that matrix analytical method can be applied to obtain the necessary and sufficient criterion for ergodicity of this Markov chain as well as to compute its stationary distribution. Furthermore, the queue length and waiting time distributions with other performance measures are also given in this paper.     

A discrete-time retrial queueing system with starting failures,Bernoulli feedback and general retrial times

It is well known that discrete-time queues are more appropriate than their continuous-time counterparts for modelling computer and telecommunication systems. This paper is concerned with a discrete-time Geo/G/1 retrial queue with general retrial times, Bernoulli feedback and the server subjected to starting failures. In this paper, we generalize the previous works in discrete-time retrial queue with unreliable server due to starting failures in the sense that we consider general service with Bernoulli feedback and general retrial times. We analyse the Markov chain underlying the considered queueing system and present some performance measures of the system in steady-state. We provide two stochastic decomposition laws and as application we give bounds for the distance between the system size distribution of our model and the corresponding model without retrials. Besides, some numerical results are given to illustrate the impact of the unreliability and the feedback on the performance of the system. We also investigate the relation between our discrete-time system and its continuous counterpart.     

MMAP|M|N queueing system with impatient heterogeneous customers as a model of a contact center

A multi-server queueing system with infinite buffer and impatient heterogeneous customers as a model of a contact center that processes incoming calls (priority customers) and e-mail requests (non-priority customers) is investigated. The arrival flow is described by a Marked Markovian Arrival Process (MMAP). The service time of priority and non-priority customers by a server has an exponential distribution with different parameters. The steady state distribution of the system is analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transforms of the sojourn and waiting time distribution are derived. The problem of optimal choice of the number of contact center agents under the constraint that the average waiting time of e-mail requests does not exceed a predefined value is numerically solved.     

The BMAP/PH/N retrial queueing system operating in Markovian random environment

We consider the BMAP/PH/N retrial queueing system operating in a finite state space Markovian random environment. The stationary distribution of the system states is computed. The main performance measures of the system are derived. Presented numerical examples illustrate a poor quality of the approximation of the main performance measures of the system by means of the simpler queueing models. An effect of smoothing the traffic and an impact of intensity of retrials are shown.     

A finite source multi-server inventory system with service facility

In this article, we study a continuous review retrial inventory system with a finite source of customers and identical multiple servers in parallel. The customers arrive according a quasi-random process. The customers demand unit item and the demanded items are delivered after performing some service the duration of which is distributed as exponential. The ordering policy is according to (s, S) policy. The lead times for the orders are assumed to have independent and identical exponential distributions. The arriving customer who finds all servers are busy or all items are in service, joins an orbit. These orbiting customer competes for service by sending out signals at random times until she finds a free server and at least one item is not in the service. The inter-retrial times are exponentially distributed with parameter depending on the number of customers in the orbit. The joint probability distribution of the number of customer in the orbit, the number of busy servers and the inventory level is obtained in the steady state case. The Laplace–Stieltjes transform of the waiting time distribution and the moments of the waiting time distribution are calculated. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

Priority tandem queueing model with admission control

A two-stage multi-server tandem queue with two types of processed customers is analyzed. The input is described by the Marked Markovian Arrival Process (MMAP). The first stage has an infinite number of servers while the second stage has a finite number of servers. The service time at the both stages has an exponential distribution. Priority customers are always admitted to the system. Non-priority customers are admitted to the system only if the number of busy servers at the second stage does not exceed some pre-assigned threshold. Queueing system’s behavior is described in terms of the multi-dimensional asymptotically quasi-Toeplitz continuous time Markov chain. It allows to exploit a numerically stable algorithm for calculation of the stationary distribution of the queueing system. The loss probability at the both stages of the tandem is computed. An economic criterion of the system operation is optimized with respect to the threshold. The effect of control on the main performance measures of the system is numerically demonstrated.     

A finite source multi-server inventory system with service facility

In this article, we study a continuous review retrial inventory system with a finite source of customers and identical multiple servers in parallel. The customers arrive according a quasi-random process. The customers demand unit item and the demanded items are delivered after performing some service the duration of which is distributed as exponential. The ordering policy is according to (s, S) policy. The lead times for the orders are assumed to have independent and identical exponential distributions. The arriving customer who finds all servers are busy or all items are in service, joins an orbit. These orbiting customer competes for service by sending out signals at random times until she finds a free server and at least one item is not in the service. The inter-retrial times are exponentially distributed with parameter depending on the number of customers in the orbit. The joint probability distribution of the number of customer in the orbit, the number of busy servers and the inventory level is obtained in the steady state case. The Laplace–Stieltjes transform of the waiting time distribution and the moments of the waiting time distribution are calculated. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

Finite-source M/M/S retrial queue with search for balking and impatient customers from the orbit

The present paper deals with a generalization of the homogeneous multi-server finite-source retrial queue with search for customers in the orbit. The novelty of the investigation is the introduction of balking and impatience for requests who arrive at the service facility with a limited capacity and FIFO queue. Arriving customers may balk, i.e., they either join the queue or go to the orbit. Moreover, the requests are impatient and abandon the buffer after a random time and enter the orbit, too. In case of an empty buffer, each server searches for a customer in the orbit after finishing service. All random variables involved in the model construction are supposed to be exponentially distributed and independent of each other. The primary aim of this analysis is to show the effect of balking, impatience, and buffer size on the steady-state performance measures. Concentrating on the mean response time, several numerical examples are investigated by the help of the MOSEL-2 tool used for creating the model and calculating the stationary characteristics.     

A discrete-time retrial queue with negative customers and unreliable server

This paper treats a discrete-time single-server retrial queue with geometrical arrivals of both positive and negative customers in which the server is subject to breakdowns and repairs. Positive customers who find sever busy or down are obliged to leave the service area and join the retrial orbit. They request service again after some random time. If the server is found idle or busy, the arrival of a negative customer will break the server down and simultaneously kill the positive customer under service if any. But the negative customer has no effect on the system if the server is down. The failed server is sent to repair immediately and after repair it is assumed as good as new. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating functions of the number of customers in the orbit and in the system are also obtained along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, some numerical examples show the influence of the parameters on some crucial performance characteristics of the system.     

Analysis and optimization of Guard Channel Policy in cellular mobile networks with account of retrials

A multi-server retrial queue with two types of calls (handover and new calls) is analyzed. This queue models the operation of a cell of a mobile communication network. Calls of two types arrive at the system according to the Marked Markovian Arrival Process. Service times of both types of the calls are exponentially distributed with different service rates. Handover calls have priority over new calls. Priority is provided by means of reservation of several servers of the system exclusively for service of handover calls. A handover call is dropped and leaves the system if all servers are busy at the arrival epoch. A new call is blocked if all servers available to new calls are busy. Such a call has options to balk (to leave the system without getting the service) or to retry later on. The behavior of the system is described by the four-dimensional Markov chain belonging to the class of the asymptotically quasi-Toeplitz Markov chains (AQTMC). In the paper, a constructive ergodicity condition for this chain is derived and the effective algorithm for computing the stationary distribution is presented. Based on this distribution, formulas for various performance measures of the system are obtained. Results of numerical experiments illustrating the behavior of key performance measures of the system depending on the number of the reserved servers under the different shares of the handover and the new calls are presented. An optimization problem is considered and high positive effect of server's reservation is demonstrated.     

An SM2/MSP/n/r System with Random-Service Discipline and a Common Buffer

A multi-server queueing system with a semi-Markov input flow of two types of customers, Markov service, a common buffer of finite capacity, and random-service discipline is investigated. The method of Markov imbedded chain is applied to find the stationary distribution of the main service characteristics of this system. By way of example, a system with phase-type service time distribution is given.     

Markov Models of Queueing–Inventory Systems with Variable Order Size

Markov models of queueing–inventory systems with variable order size are investigated. Two classes of models are considered: with instant service and with nonzero service time. The model with nonzero service time assumes that impatient customers can form a queue of either finite or infinite length. The exact and approximate methods are developed to calculate the characteristics of the systems under proposed restocking policy.     

The M/G/1 retrial queue with Bernoulli schedules and general retrial times

This paper is concerned with the analysis of a single-server queue with Bernoulli vacation schedules and general retrial times. We assume that the customers who find the server busy are queued in the orbit in accordance with an FCFS (first-come-first-served) discipline and only the customer at the head of the queue is allowed access to the server. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution, as well as some performance measures of the system under steady-state condition. We show that the general stochastic decomposition law for M/G/1 vacation models holds for the present system also. Some special cases are also studied.     

On the number of customers served in the M/G/1 retrial queue: first moments and maximum entropy approach

In this paper we present general results on the number of customers, I, served during the busy period in an M/G/1 retrial system. Its analysis in terms of Laplace transforms has been previously discussed in the literature. However, this solution presents important limitations in practice; in particular, the moments of I cannot be obtained by direct differentiation. We propose a direct method of computation for the second moment of I and also for the probability of k,k⩽4, customers being served in a busy period. Then, the maximum entropy principle approach is used to estimate the true distribution of I according to the available information.Scope and purposeWe consider an M/G/1 queue with retrials. Retrial queueing systems are characterized by the fact that, an arriving customer who finds the server busy is obliged to leave the service area and return later to repeat his request after some random time. We deal with I, the number of customers served during the busy period of a retrial queue, and obtain closed expressions for its main characteristics, which will be employed in order to estimate the true distribution of this random variable.     

An M/G/1 retrial G-queue with non-exhaustive random vacations and an unreliable server

This paper deals with an M/G/1 retrial queue with negative customers and non-exhaustive random vacations subject to the server breakdowns and repairs. Arrivals of both positive customers and negative customers are two independent Poisson processes. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The server takes a vacation of random length after an exponential time when the server is up. We develop a new method to discuss the stable condition by finding absorb distribution and using the stable condition of a classical M/G/1 queue. By applying the supplementary variable method, we obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law. We also analyse the busy period of the system. Some special cases of interest are discussed and some known results have been derived. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analysed numerically.     

Single server retrial queue with group admission of customers

We consider a retrial queueing system with a single server and novel customer׳s admission discipline. The input flow is described by a Markov Arrival Process. If an arriving customer meets the server providing the service, it goes to the orbit and repeats attempts to get service in random time intervals whose duration has exponential distribution with parameter dependent on the customers number in orbit. Server operates as follows. After a service completion epoch, customers admission interval starts. Duration of this interval has phase type distribution. During this interval, primary customers and customers from the orbit are accepted to the pool of customers which will get service after the admission interval. Capacity of this pool is limited and after the moment when the pool becomes full before completion of admission interval all arriving customers move to the orbit. After completion of an admission interval, all customers in the pool are served simultaneously by the server during the time having phase type distribution depending on the customers number in the pool. Using results known for Asymptotically Quasi-Toeplitz Markov Chains, we derive stability condition of the system, compute the stationary distribution of the system states, derive formulas for the main performance measures and numerically show advantages of the considered customer׳s admission discipline (higher throughput, smaller average number of customers in the system, higher probability to get a service without visiting the orbit) in case of proper choice of the capacity of the pool and the admission period duration.     

The <Emphasis Type="Italic">MAP/M/N</Emphasis> retrial queueing system with time-phased batch arrivals

We consider a retrial queueing system with batch arrival of customers. Unlike standard batch arrival, where a whole batch enters the system simultaneously, we assume that customers of a batch (session) arrive one by one in exponentially distributed time intervals. Service time is exponentially distributed. The batch arrival flow is MAP. The number of customers in a session is geometrically distributed. The number of sessions that can enter the system simultaneously is a control parameter. We analyze the joint probability distribution of the number of sessions and customers in the system using the techniques of multidimensional asymptotically quasi-Toeplitz Markov chains.