On the distributions of infinite server queues with batch arrivals

Queues that feature multiple entities arriving simultaneously are among the oldest models in queueing theory, and are often referred to as “batch” (or, in some cases, “bulk”) arrival queueing systems. In this work, we study the effect of batch arrivals on infinite server queues. We assume that the arrival epochs occur according to a Poisson process, with treatment of both stationary and non-stationary arrival rates. We consider both exponentially and generally distributed service durations, and we analyze both fixed and random arrival batch sizes. In addition to deriving the transient mean, variance, and moment-generating function for time-varying arrival rates, we also find that the steady-state distribution of the queue is equivalent to the sum of scaled Poisson random variables with rates proportional to the order statistics of its service distribution. We do so through viewing the batch arrival system as a collection of correlated sub-queues. Furthermore, we investigate the limiting behavior of the process through a batch scaling of the queue and through fluid and diffusion limits of the arrival rate. In the course of our analysis, we make important connections between our model and the harmonic numbers, generalized Hermite distributions, and truncated polylogarithms.

     

Autocorrelations in infinite server batch arrival queues

This paper studies an important aspect of queueing theory, autocorrelation properties of system processes. A general infinite server queue with batch arrivals is considered. There areM different types of customers and their arrivals are regulated by a Markov renewal input process. Batch sizes and service times depend on the relevant customer types. With a conditional approach, closed form expressions are obtained for the autocovariance of the continuous time and prearrival system sizes. Some special models are also discussed, giving insights into steady state system behaviour. Autocorrelation functions have a wide range of applications. We highlight one area of application by using autocovariances to derive variances of sample means for a number of special models.This work has been supported by the Natural Sciences and Engineering Council of Canada through Grant A5639 and by the National Natural Science Foundation of China through Grant 19001015.     

Analysis of a single server queue with semi-Markovian service interruption

In this paper we analyze a discrete-time single server queue where the service time equals one slot. The numbers of arrivals in each slot are assumed to be independent and identically distributed random variables. The service process is interrupted by a semi-Markov process, namely in certain states the server is available for service while the server is not available in other states. We analyze both the transient and steady-state models. We study the generating function of the joint probability of queue length, the state and the residual sojourn time of the semi-Markov process. We derive a system of Hilbert boundary value problems for the generating functions. The system of Hilbert boundary value problems is converted to a system of Fredholm integral equations. We show that the system of Fredholm integral equations has a unique solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

On dams with continuous semi-Markovian inputs

An infinite capacity dam subject to semi-Markovian inputs and a content dependent release rule will be discussed. The content process will be constructed, the distributions of the content at time t and time to first emptiness will be computed, and the limiting distribution of the content process will be obtained in a special case. Our methods rely heavily on Markov renewal theory with continuous state spaces.     

On a multivariate renewal-reward process involving time delays and discounting: applications to IBNR processes and infinite server queues

This paper considers a particular renewal-reward process with multivariate discounted rewards (inputs) where the arrival epochs are adjusted by adding some random delays. Then, this accumulated reward can be regarded as multivariate discounted Incurred But Not Reported claims in actuarial science and some important quantities studied in queueing theory such as the number of customers in \(G/G/\infty \) queues with correlated batch arrivals. We study the long-term behaviour of this process as well as its moments. Asymptotic expressions and bounds for quantities of interest, and also convergence for the distribution of this process after renormalization, are studied, when interarrival times and time delays are light tailed. Next, assuming exponentially distributed delays, we derive some explicit and numerically feasible expressions for the limiting joint moments. In such a case, for an infinite server queue with a renewal arrival process, we obtain limiting results on the expectation of the workload, and the covariance of queue size and workload. Finally, some queueing theoretic applications are provided.     

Analysis of multi-server queues with station and server vacations

In this paper, we consider GI/M/c queues with two classes of vacation mechanisms: Station vacation and server vacation. In the first one, all the servers take vacation simultaneously whenever the system becomes empty, and they also return to the system at the same time, i.e., station vacation is a group vacation for all servers. This phenomenon occurs in practice, for example, when the system consists of a set of machines monitored by a single operator, or the system consists of inseparable interconnected parallel machines. In such situations the whole station has to be treated as a single entity for vacation when the system is utilized for a secondary task. For the second class of vacation mechanisms, each server takes its own vacation whenever it complexes a service and finds no customers waiting in the queue, which occurs, for instance in the post office, when each server is a relatively independent working unit, and can itself be used for other purposes. For both models, we derive steady state probabilities that have matrix geometric form, and develop computational algorithms to obtain numerical solutions. We also analyze and make comparisons of these models based on numerical observations.     

On the relationship between work load and waiting time in single server queues with batch inputs

The relationship between work load and waiting time in single server queues with batch inputs is discussed under a work-conserving service discipline. Based on a result of Brumelle, the relationship is newly presented especially under the preemptive-resume discipline. This relationship is applied to analyze batch Poisson input models.     

Analysis of customers’ impatience in queues with server vacations

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absentee of servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/c queue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline. This work was supported by the Euro-Ngi network of excellence.     

Stationary queues with one autonomous server

Given a stationary stochastic continuous demand of service σ(θ_tω) dt with ∫ σ(ω)P(dω) < 1, we construct real stationary point processes $\text{(T}{}_{\mathrm{n}}\text{, n ∈}\text{Z}\text{)[T}{}_{\mathrm{n}}\text{< T}{}_{\mathrm{n}}\text{+1, lim}{}_{\mathrm{\pm \infty }}\text{T}{}_{\mathrm{n}}\text{= ±∞]}$ such that

for a given constant D \2>0. These point processes correspond to a service discipline for which a single server services during the time intervals [T_n, T_n+1[ the demand of service accumulated during the proceding intervals [T_n?1, T_n[ and take a rest of fixed duration D.     

System with priority queues and unreliable server

A single server queueing system with an unreliable server and priority customers is considered. The limit distribution of the number of ordinary customers in the system is obtained.     

Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues

A fluid queue with ON periods arriving according to a Poisson process and having a long-tailed distribution has long range dependence. As a result, its performance deteriorates. The extent of this performance deterioration depends on a quantity determined by the average values of the system parameters. In the case when the the performance deterioration is the most extreme, we quantify it by studying the time until the amount of work in the system causes an overflow of a large buffer. This turns out to be strongly related to the tail behavior of the increase in the buffer content during a busy period of the M/G/∞ queue feeding the buffer. A large deviation approach provides a powerful method of studying such tail behavior. This revised version was published online in June 2006 with corrections to the Cover Date.     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the system.     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

An analytical solution for the discrete time single server system with semi-Markovian arrivals

In this paper we derive an analytical solution for the stationary distribution of the number of customers and the idle time in a single server system with semi-Markovian arrival processes in discrete time domain (SM/G/1). This kind of arrival process enables us to take autocorrelations into account, with various applications for the modeling of communication and manufacturing systems. It will be shown that the distribution of the customer number can be represented as a linear combination of geometric distributions. Thus a simple calculation of higher moments of the customer number is possible.     

Retrial queues with server subject to breakdowns and repairs

In this paper we consider a single server retrial queue where the server is subject to breakdowns and repairs. New customers arrive at the service station according to a Poisson process and demand i.i.d. service times. If the server is idle, the incoming customer starts getting served immediately. If the server is busy, the incoming customer conducts a retrial after an exponential amount of time. The retrial customers behave independently of each other. The server stays up for an exponential time and then fails. Repair times have a general distribution. The failure/repair behavior when the server is idle is different from when it is busy. Two different models are considered. In model I, the failed server cannot be occupied and the customer whose service is interrupted has to either leave the system or rejoin the retrial group. In model II, the customer whose service is interrupted by a failure stays at the server and restarts the service when repair is completed. Model II can be handled as a special case of model I. For model I, we derive the stability condition and study the limiting behavior of the system by using the tools of Markov regenerative processes.Visiting from Department of Applied Mathematics, Korea Advanced Institute of Science and Technology, Cheongryang, Seoul, Korea.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Stability of multi-class queueing networks with infinite virtual queues

We generalize the standard multi-class queueing network model by allowing both standard queues and infinite virtual queues which have an infinite supply of work. We pose the general problem of finding policies which allow some of the nodes of the network to work with full utilization, and yet keep all the standard queues in the system stable. Toward this end we show that re-entrant lines, systems of two re-entrant lines through two service stations, and rings of service stations can be stabilized with priority policies under certain parameter restrictions. The analysis throughout the paper depends on model and policy and illustrates the difficulty in solving the general problem.