Analysis and Computation of the Joint Queue Length Distribution in a FIFO Single-Server Queue with Multiple Batch Markovian Arrival Streams

This paper considers a work-conserving FIFO single-server queue with multiple batch Markovian arrival streams governed by a continuous-time finite-state Markov chain. A particular feature of this queue is that service time distributions of customers may be different for different arrival streams. After briefly discussing the actual waiting time distributions of customers from respective arrival streams, we derive a formula for the vector generating function of the time-average joint queue length distribution in terms of the virtual waiting time distribution. Further assuming the discrete phase-type batch size distributions, we develop a numerically feasible procedure to compute the joint queue length distribution. Some numerical examples are provided also.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Matrix Product-Form Solutions for LCFs Preemptive Service Single-Server Queues with Batch Markovian Arrival Streams

ABSTRACT

This paper considers three variants of last-come first-served (LCFS) preemptive service single-server queues, where customers are served under the LCFS preemptive resume (LCFS-PR), preemptive repeat-different (LCFS-PD), and preemptive repeat-identical (LCFS-PI) disciplines, respectively. These LCFS queues are fed by multiple batch Markovian arrival streams. Service times of customers from each arrival stream are generally distributed and their distributions may differ among different streams. For each of LCFS-PR, LCFS-PD, and LCFS-PI queues, we show that the stationary distribution of the queue string representing enough information to keep track of queueing dynamics has a matrix product-form solution. Further, this paper discusses the stability of LCFS-PD and LCFS-PI queues based on the busy cycle. Finally, by numerical experiment, we examine the impact of the variation of the service time distribution on the mean queue lengths for the three variants of LCFS queues.     

Limit theorems for single server queues with mixed renewal and poisson inputs

The following queuing system is considered:Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that these customers have priority:head-of-the-line, preemptive-resume, and preemptive-repeat discipline. Formulas derived for the limiting distribution functions of the actual and the virtual waiting time of low priority customers and of the number of these customers in the system, by using of independences of certain random processes when the time tends to infinity.     

Stationary distributions of the R[X]/R/1 cross-correlated queue

We consider an infinite buffer single server queue wherein batch interarrival and service times are correlated having a bivariate mixture of rational (R) distributions, where R denotes the class of distributions with rational Laplace–Stieltjes transform (LST), i.e., ratio of a polynomial of degree at most n to a polynomial of degree n. The LST of actual waiting time distribution has been obtained using Wiener–Hopf factorization of the characteristic equation. The virtual waiting time, idle period (actual and virtual) distributions, as well as inter-departure time distribution between two successive customers have been presented. We derive an approximate stationary queue-length distribution at different time epochs using the Markovian assumption of the service time distribution. We also derive the exact steady-state queue-length distribution at an arbitrary epoch using distributional form of Little’s law. Finally, some numerical results have been presented in the form of tables and figures.     

Multi-class M/PH/1 queues with deterministic impatience times

This article considers computational procedures for the waiting time and queue length distributions in stationary multi-class first-come, first-served single-server queues with deterministic impatience times. There are several classes of customers, which are distinguished by deterministic impatience times (i.e., maximum allowable waiting times). We assume that customers in each class arrive according to an independent Poisson process and a single server serves customers on a first-come, first-served basis. Service times of customers in each class are independent and identically distributed according to a phase-type distribution that may differ for different classes. We first consider the stationary distribution of the virtual waiting time and then derive numerically feasible formulas for the actual waiting time distribution and loss probability. We also analyze the joint queue length distribution and provide an algorithmic procedure for computing the probability mass function of the stationary joint queue length.     

Large deviations of multiclass M/G/1 queues

Consider a multiclass M/G/1 queue where queued customers are served in their order of arrival at a rate which depends on the customer class. We model this system using a chain with states represented by a tree. Since the service time distribution depends on the customer class, the stationary distribution is not of product form so there is no simple expression for the stationary distribution. Nevertheless, we can find a harmonic function on this chain which provides information about the asymptotics of this stationary distribution. The associated h‐transformation produces a change of measure that increases the arrival rate of customers and decreases the departure rate thus making large deviations common. The Canadian Journal of Statistics 37: 327–346; 2009 © 2009 Statistical Society of Canada     

ANALYSIS OF A GI/G Y /1 SYSTEM IN DISCRETE-TIME

ABSTRACT

We consider a class of single server queueing systems in which customers arrive singly and service is provided in batches, depending on the number of customers waiting when the server becomes free. Service is independent of the batch size. This system could also be considered as a batch service queue in which a server visits the queue at arbitrary times and collects a batch of waiting customers for service, or waits for a customer to arrive if there are no waiting customers. A waiting server immediately collects and processes the first arriving customer. The system is considered in discrete time. The interarrival times of customers and the inter-visit times of the server, which we call the service time, have general distributions and are represented as remaining time Markov chains. We analyze this system using the matrix-geometric method and show that the resulting R matrix can be determined explicitly in some special cases and the stationary distributions are known semi-explicitly in some other special cases.     

The existence of waiting time moments for single server queues with mixed renewal and poisson inputs

The following queuing system is considered: Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that customers of type 1 have priority: head-of-the-line, preemptive-resume, and preemptive-repeat discipline. For all three cases, the limiting distribution function of actual waiting times of low-priority customers is considered, and conditions are given for the existence of moments related to these limiting distributions.     

Performance analysis of the retrial queues with finite number of sources and service interruptions

This paper aims at presenting an analytic approach for investigating a single-server retrial queue with finite population of customers where the server is subject to interruptions. A free source may generate a primary call to request service. If the server is free upon arrival, the call starts to be served and the service times are independent, generally distributed random variables. During the service time the source cannot generate a new primary call. After service the source moves into the free state and can generate a new primary call. There is no waiting space in front of the server, and a call who finds the server unavailable upon arrival joins an orbit of unsatisfied customers. The server is subject to interruptions during the service processes. When the server is interrupted, the call being served just before server interruption goes to the retrial orbit and will retry its luck after a random amount of time until it finds the server available. The recovery times of the interrupted server are assumed to be generally distributed. Our analysis extends previous work on this topic and includes the analysis of the arriving customer’s distribution, the busy period, and the waiting time process.     

Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple working vacation policy. The service time during a working vacation is generally distributed random variable which is independent of the service times during a normal busy period as well as the arrival process. Duration of service times during a normal busy period and duration of working vacation times follow the class of distributions whose Laplace-Stieltjes transforms are rational functions (R-type distributions). The service time during a normal busy period, working vacation time, and the service time during a working vacation are independent of each other as well as of the arrival process. If a working vacation terminates while service is going on for a customer at head of the queue in vacation mode then, the server switches to normal mode and the customer at head of the queue is entitled to receive a full service time in the normal busy period irrespective of the amount of service received by the customer at head of the queue during the previous working vacation period. We obtain system-length distributions at various epoch, such as post-departure, pre-arrival, arbitrary, and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain system-length distribution at post-departure epoch. Later, we use supplementary variable technique and simple algebraic manipulations to obtain system-length distribution at arbitrary epoch using the system-length distribution at post-departure epoch. Some important performance measures, such as mean system lengths and mean waiting time have been obtained. Finally, some numerical results have been presented in the form of tables and graphs to show the applicability of the results obtained in this article. The model has potential application in areas of computer and communication networks, such as ethernet passive optical network (EPON).     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

Bayesian estimation for the M/G/1 queue using a phase-type approximation

This article deals with Bayesian inference and prediction for M/G/1 queueing systems. The general service time density is approximated with a class of Erlang mixtures which are phase-type distributions. Given this phase-type approximation, an explicit evaluation of measures such as the stationary queue size, waiting time and busy period distributions can be obtained. Given arrival and service data, a Bayesian procedure based on reversible jump Markov Chain Monte Carlo methods is proposed to estimate system parameters and predictive distributions.     

A Retrial Queue with a Constant Retrial Rate,Server Downs and Impatient Customers

ABSTRACT

In this paper, we consider a retrial queueing system consisting of a waiting line of infinite capacity in front of a single server subject to breakdowns. A customer upon arrival may join the queue (waiting line) or go to the retrial orbit (another queue) to retry for service after a random time. Only the customer at the head of the retrial orbit is allowed to retry for service. Upon retrial, the customer enters the service if the server is idle; otherwise, it may go back to the retrial orbit or leave the system (become impatient). All the interarrival times, service times, server up times, server down times and retrial times are exponential, and all the necessary independence conditions in these variables are assumed. For this system, we provide sufficient conditions under which, for any given number of customers in the orbit, the stationary probability of the number of customers in the waiting line decays geometrically. We also provide explicitly an expression for the decay parameter.     

Explicit formulae and convergence rate for the system M α /G/1/N as N→∞

The paper deals with the system M ^α /G/1/N with a finite number of waiting places in which arrivals can occur in a group. The number of customers in the line and the virtual waiting time are studied both in the transient and in the stationary regime. Special attention is paid to the stationary distributions of these functionals as N→∞. The number of customers lost during a busy period is considered as well.     

Approximating M/G/1 Waiting Time Tail Probabilities

Abstract

We propose a new approximation formula for the waiting time tail probability of the M/G/1 queue with FIFO discipline and unlimited waiting space. The aim is to address the difficulty of obtaining good estimates when the tail probability has non-exponential asymptotics. We show that the waiting time tail probability can be expressed in terms of the waiting time tail probability of a notional M/G/1 queue with truncated service time distribution plus the tail probability of an extreme order statistic. The Cramér–Lundberg approximation is applied to approximate the tail probability of the notional queue. In essence, our technique extends the applicability of the Cramér–Lundberg approximation to cases where the standard Lundberg condition does not hold. We propose a simple moment-based technique for estimating the parameters of the approximation; numerical results demonstrate that our approximation can yield very good estimates over the whole range of the argument.     

On some probability distributions associated with random walks

The probability distribution of the total number of games to ruin in a gambler's ruin random walk with initial position n, the probability distribution of the total size of an epidemic starting with n cases and the probability distribution of the number of customers served during a busy period M/M/1 when the service starts with n waiting customers are identical. All these can be easily obtained by using Lagrangian expansions instead of long combinatorial methods. The binomial, trinomial, quadrinomial and polynomial random walks of a particle have been considered with an absorbing barrier at 0 when the particle starts its walks from a point n, and the pgfs. and the probability distributions of the total number of jumps (trials) before absorption at 0 have been obtained. The values for the mean and variance of such walks have also been given.     

A two phases queueing system with Bernoulli vacation schedule under multiple vacation policy

This paper deals with a single server Poisson arrival queue with two phases of heterogeneous service along with a Bernoulli schedule vacation model, where after two successive phases service the server either goes for a vacation with probability p (0≤p≤1) or may continue to serve the next unit, if any, with probability q(=1−p). Further the concept of multiple vacation policy is also introduced here. We obtained the queue size distributions at a departure epoch and at a random epoch, Laplace Stieltjes Transform of the waiting time distribution and busy period distribution along with some mean performance measures. Finally we discuss some statistical inference related issues.     

THE EFFECT OF POSTPONABLE INTERRUPTIONS ON A M/G/1 SYSTEM WITH IMPATIENT CUSTOMERS

This paper considers a waiting line system where units become impatient after having waited for certain time and leave the queue (renege) without being serviced. The servicing of the units is subject to interruption by the arrival of an "interruption " possessing a priority for service over the ordinary units, head-of-the-line priority discipline being prevalent. The busy period process is investigated first, making use of the supplementary variable method. Later, the general process is studied in terms of the busy period process and renewal distributions. Lastly, the ergodic properties of the general process are examined by appealing to some results of renewal theory.