Waiting time analysis of the multiple priority dual queue with a preemptive priority service discipline

The dual queue consists of two queues, called the primary queue and the secondary queue. There is a single server in the primary queue but the secondary queue has no service facility and only serves as a holding queue for the overloaded primary queue. The dual queue has the additional feature of a priority scheme to help reduce congestion. Two classes of customers, class 1 and 2, arrive to the dual queue as two independent Poisson processes and the single server in the primary queue dispenses an exponentially distributed service time at the rate which is dependent on the customer’s class. The service discipline is preemptive priority with priority given to class 1 over class 2 customers. In this paper, we use matrix-analytic method to construct the infinitesimal generator of the system and also to provide a detailed analysis of the expected waiting time of each class of customers in both queues.     

The waiting time distribution for a correlated queue with exponential interarrival and service times

We are concerned with the analysis of the waiting time distribution in an $M∕M∕1$ queue in which the interarrival time between the $n$th and the $(n+1)$th customers and the service time of the $n$th customer are correlated random variables with Downton’s bivariate exponential distribution. In this paper we show that the conditional waiting time distribution, given that the waiting time is positive, is exponential.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Waiting time and queue length analysis of Markov-modulated fluid priority queues

Queueing Systems - This paper considers a multi-type fluid queue with priority service. The input fluid rates are modulated by a Markov chain, which is common for all fluid types. The service rate...     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, Kleinrock suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.     

Heavy traffic limit for the workload plateau process in a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue has renewal arrivals with generally distributed service times, and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. The reuse of service times creates strong dependence at the second queue, making its workload difficult to analyze. To investigate the evolution of workload in the second queue, we introduce and study a process $M$, called the plateau process, which encodes most of the information in the workload process. We focus on the case of infinite-variance service times and show that under appropriate scaling, workload in the first queue converges, and although the workload in the second queue does not converge, the plateau process does converge to a limit $M^1$ that is a certain function of two independent Lévy processes. Using excursion theory, we derive some useful properties of $M^1$ and compare a time changed version of it to a limit process derived in previous work.     

An analytical solution for a tandem queue with blocking

The model considered in this paper involves a tandem queue with two waiting lines, and as soon as the second waiting line reaches a certain upper limit, the first line is blocked. Both lines have exponential servers, and arrivals are Poisson. The objective is to determine the joint distribution of both lines in equilibrium. This joint distribution is found by using generalized eigenvalues. Specifically, a simple formula involving the cotangent is derived. The periodicity of the cotangent is then used to determine the location of the majority of the eigenvalues. Once all eigenvalues are found, the eigenvectors can be obtained recursively. The method proposed has a lower computational complexity than all other known methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Discrete time analysis of MAP/PH/1 vacation queue with gated time‐limited service

We analyse a single‐server queue in which the server goes through alternating periods of vacation and work. In each work period, the server attends to the queue for no more than a fixed length of time, T. The system is a gated one in which the server, during any visit, does not attend to customers which were not in the system before its visit. As soon as all the customers within the gate have been served or the time limit has been reached (whichever occurs first) the server goes on a vacation. The server does not wait in the queue if the system is empty at its arrival for a visit. For this system the resulting Markov chain, of the queue length and some auxiliary variables, is level‐dependent. We use special techniques to carry out the steady state analysis of the system and show that when the information regarding the number of customers in the gate is not critical we are able to reduce this problem to a level‐independent Markov chain problem with large number of boundary states. For this modified system we use a hybrid method which combines matrix‐geometric method for the level‐independent part of the system with special solution method for the large complex boundary which is level‐dependent. This revised version was published online in June 2006 with corrections to the Cover Date.     

Response time in a tandem queue with blocking, Markovian arrivals and phase-type services

A novel approach for obtaining the response time in a discrete-time tandem-queue with blocking is presented. The approach constructs a Markov chain based on the age of the leading customer in the first queue. We also provide a stability condition and carry out several numerical examples.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Stationary remaining service time conditional on queue length

In Mandelbaum and Yechiali [The conditional residual service time in the M/G/1 queue, http://www.math.tau.ac.il/∼uriy/publications (No. 30a), 1979] and in Fakinos [The expected remaining service time in a single-server queue, Oper. Res. 30 (1982) 1014-1018] a simple formula is derived for the (stationary) expected remaining service time in a M/G/1 queue, conditional on the number of customers in the system. We give a short new proof of the formula using Rate Conservation Law, and generalize to handle higher moments.     

State-dependent importance sampling for a slowdown tandem queue

In this paper we investigate an advanced variant of the classical (Jackson) tandem queue, viz. a two-node system with server slowdown. By this mechanism, the service speed of the upstream queue is reduced as soon as the number of jobs in the downstream queue reaches some pre-specified threshold. We focus on the estimation of the probability of overflow in the downstream queue before the system becomes empty, starting from any given state in the state space.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

Batch arrival single-server queue with variable service speed and setup time

In this paper, we consider an M\({}^X\)/M/1/SET-VARI queue which has batch arrivals, variable service speed and setup time. Our model is motivated by power-aware servers in data centers where dynamic scaling techniques are used. The service speed of the server is proportional to the number of jobs in the system. The contribution of our paper is threefold. First, we obtain the necessary and sufficient condition for the stability of the system. Second, we derive an expression for the probability generating function of the number of jobs in the system. Third, our main contribution is the derivation of the Laplace–Stieltjes transform (LST) of the sojourn time distribution, which is obtained in series form involving infinite-dimensional matrices. In this model, since the service speed varies upon arrivals and departures of jobs, the sojourn time of a tagged job is affected by the batches that arrive after it. This makes the derivation of the LST of the sojourn time complex and challenging. In addition, we present some numerical examples to show the trade-off between the mean sojourn time (response time) and the energy consumption. Using the numerical inverse Laplace–Stieltjes transform, we also obtain the sojourn time distribution, which can be used for setting the service-level agreement in data centers.     

Optimal dispatching in a tandem queue

Motivated by a capacity allocation problem within a finite planning period, we conduct a transient analysis of a single-server queue with Lévy input. From a cost minimization perspective, we investigate the error induced by using stationary congestion measures as opposed to time-dependent measures. Invoking recent results from fluctuation theory of Lévy processes, we derive a refined cost function, that accounts for transient effects. This leads to a corrected capacity allocation rule for the transient single-server queue. Extensive numerical experiments indicate that the cost reductions achieved by this correction can be significant.     

Three stage tandem queue with blocking

An analysis is given of the state and first-come, first-served waiting time processes for a three stage queueing system with no waiting space between stages, but with limited space before the first. Although the basic processes are exponential, no detailed analysis in this generality appears to have been made before; the nearest analyses entail the simplifying assumption that the first stage is never empty. A sufficient condition is derived easily for equilibrium to exist and it can be asserted with virtual certainty that it is also necessary; the complexity of calculation has so far excluded a proper proof, though this is in principle a possibility.The objective is to provide a theoretical framework easily adaptable for a numerical assessment of system performance to be made. Some typical tables with comments are given.     

Strategic behaviour in a tandem queue with alternating server

Queueing Systems - This paper considers an unobservable two-site tandem queueing system attended by an alternating server. We study the strategic customer behaviour under two threshold-based...     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.