Algorithmic analysis of the Geo/Geo/c retrial queue

In this paper, we consider a discrete-time queue of Geo/Geo/c type with geometric repeated attempts. It is known that its continuous counterpart, namely the M/M/c queue with exponential retrials, is analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused from the retrial feature. In discrete-time, the occurrence of multiple events at each slot increases the complexity of the model and raises further computational difficulties. We propose several algorithmic procedures for the efficient computation of the main performance measures of this system. More specifically, we investigate the stationary distribution of the system state, the busy period and the waiting time. Several numerical examples illustrate the analysis.     

Approximation of multiserver retrial queues by means of generalized truncated models

It is well-known that an analytical solution of multiserver retrial queues is difficult and does not lead to numerical implementation. Thus, many papers approximate the original intractable system by the so-called generalized truncated systems which are simpler and converge to the original model. Most papers assume heuristically the convergence but do not provide a rigorous mathematical proof. In this paper, we present a proof based on a synchronization procedure. To this end, we concentrate on theM/M/c retrial queue and the approximation developed by Neuts and Rao (1990). However, the methodology can be employed to establish the convergence of several generalized truncated systems and a variety of Markovian multiserver retrial queues. J.R. Artalejo thanks the support received from DGES 98-0837.     

The N threshold policy for the GI/M/1 queue

We study a GI/M/1 queue with an N threshold policy. In this system, the server stops attending the queue when the system becomes empty and resumes serving the queue when the number of customers reaches a threshold value N. Using the embeded Markov chain method, we obtain the stationary distributions of queue length and waiting time and prove the stochastic decomposition properties.     

On the GI/M/1/N queue with multiple working vacations—analytic analysis and computation

We consider finite buffer single server GI/M/1 queue with exhaustive service discipline and multiple working vacations. Service times during a service period, service times during a vacation period and vacation times are exponentially distributed random variables. System size distributions at pre-arrival and arbitrary epoch with some important performance measures such as, probability of blocking, mean waiting time in the system etc. have been obtained. The model has potential application in the area of communication network, computer systems etc. where a single channel is allotted for more than one source.     

Analysis of an M/G/∞ queue with batch arrivals and batch-dedicated servers

We analyze an M/G/∞ queue with batch arrivals, where jobs belonging to a batch have to be processed by the same server. The number of jobs in the system is characterized as a compound Poisson random variable through a scaling of the original arrival and batch size processes.     

Fluid model driven by an M/G/1 queue with multiple exponential vacations

This paper studies a fluid model driven by an M/G/1 queue with multiple exponential vacations. By introducing various vacation strategies to the fluid model, we can provide greater flexibility for the design and control of input rate and output rate. The Laplace transform of the steady-state distribution of the buffer content is expressed through the minimal positive solution to a crucial equation. Then the performance measure-mean buffer content, which is independent of the vacation parameter, is obtained. Finally, with some numerical examples, the parameter effect on the mean buffer content is presented.     

Numerical Calculation of the Stationary Distribution of the Main Multiserver Retrial Queue

We are concerned with the main multiserver retrial queue of M/M/c type with exponential repeated attempts. It is known that an analytical solution of this queueing model is difficult and does not lead to numerical implementation. Based on appropriate understanding of the physical behavior, an efficient and numerically stable algorithm for computing the stationary distribution of the system state is developed. Numerical calculations are done to compare our approach with the existing approximations.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

Steady state analysis of an M/G/1 queue with linear retrial policy and two phase service under Bernoulli vacation schedule

We consider a single server queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under the so called linear retrial policy. This model extends both the classical M/G/1 retrial queue with linear retrial policy as well as the M/G/1 queue with two phases of service and Bernoulli vacation model. We carry out an extensive analysis of the model.     

Busy period analysis for <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 queues with workload dependent balking

We consider an M/PH/1 queue with workload-dependent balking. An arriving customer joins the queue and stays until served if and only if the system workload is no more than a fixed level at the time of his arrival. We begin by considering a fluid model where the buffer content changes at a rate determined by an external stochastic process with finite state space. We derive systems of first-order linear differential equations for the mean and LST (Laplace-Stieltjes Transform) of the busy period in this model and solve them explicitly. We obtain the mean and LST of the busy period in the M/PH/1 queue with workload-dependent balking as a special limiting case of this fluid model. We illustrate the results with numerical examples.      

Comparisons between observable and unobservable M/M/1 queues with respect to optimal customer behavior

We consider an M/M/1 queueing system in which the queue length may or may not be observable by a customer upon entering the system. The “observable” and “unobservable” models are compared with respect to system properties and performance measures under two different types of optimal customer behavior, which we refer to as “selfishly optimal” and “socially optimal”. We consider average customer throughput rates and show that, under both types of optimal customer behavior, the equality of effective queue-joining rates between the observable and unobservable systems results in differences with respect to other performance measures such as mean busy periods and waiting times. We also show that the equality of selfishly optimal queue-joining rates between the two types of system precludes the equality of socially optimal joining rates, and vice versa.     

The Virtual Waiting Time of the M/G/1 Queue with Impatient Customers

The M/G/1 queue with impatient customers is studied. The complete formula of the limiting distribution of the virtual waiting time is derived explicitly. The expected busy period of the queue is also obtained by using a martingale argument.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

On M-hyponormal weighted shifts

Let α≡{α_n}_n=0^∞ be a weight sequence and let W_α denote the associated unilateral weighted shift on . In this paper we prove that if α is eventually increasing, then W_α is M-hyponormal and that if α has exactly two subsequential limits such that the larger one is different from the spectral radius of W_α then W_α is not M-hyponormal.     

A G/M/1 retrial queue with constant retrial rate

In this paper, we are concerned with the analytical treatment of an GI/M/1 retrial queue with constant retrial rate. Constant retrial rate is typical for some real world systems where the intensity of individual retrials is inversely proportional to the number of customers in the orbit or only one customer from the orbit is allowed to make the retrials. In our model, a customer who finds the server busy joins the queue in the orbit in accordance with the FCFS (first-come-first-out) discipline and only the oldest customer in the queue is allowed to make the repeated attempts to reach the server. A distinguishing feature of the considered system is an arbitrary distribution of inter-arrival times, while the overwhelming majority of the papers is devoted to the retrial systems with the stationary Poisson arrival process. We carry out an extensive analytical analysis of the queue in steady state using the well-known matrix analytic technique. The ergodicity condition and simple expressions for the stationary distributions of the system states at pre-arrival, post-arrival and arbitrary times are derived. The important and difficult problem of finding the stationary distribution of the sojourn time is solved in terms of the Laplace–Stieltjes transform. Little’s formula is proved. Numerical illustrations are presented.     

Diffusion-equation model of slightly loaded M/M/1 queue

Another derivation of the diffusion approximation of the M/M/1 queue is presented, which results in a new boundary condition. The model proposed approximates the time-dependent behavior of the M/M/1 system for all values of channel utilization.     

Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Analysis of Queueing Systems with Synchronous Single Vacation for Some Servers

We study a multi-server M/M/c type queue with a single vacation policy for some idle servers. In this queueing system, if at a service completion instant, any d (d c) servers become idle, these d servers will take one and only one vacation together. During the vacation of d servers, the other c–d servers do not take vacation even if they are idle. Using a quasi-birth-and-death process and the matrix analytic method, we obtain the stationary distribution of the system. Conditional stochastic decomposition properties have been established for the waiting time and the queue length given that all servers are busy.     

The Busy Period and the Waiting Time Analysis of a MAP/M/c Queue with Finite Retrial Group

Abstract

We concentrate on the analysis of the busy period and the waiting time distribution of a multi-server retrial queue in which primary arrivals occur according to a Markovian arrival process (MAP). Since the study of a model with an infinite retrial group seems intractable, we deal with a system having a finite buffer for the retrial group. The system is analyzed in steady state by deriving expressions for (a) the Laplace–Stieltjes transforms of the busy period and the waiting time; (b) the probabiliy generating functions for the number of customers served during a busy period and the number of retrials made by a customer; and (c) various moments of quantites of interest. Some illustrative numerical examples are discussed.