Tail asymptotics for the queue size distribution in a discrete-time Geo/G/1 retrial queue

We consider a discrete-time Geo/G/1 retrial queue where the service time distribution has a finite exponential moment. We show that the tail of the queue size distribution is asymptotically geometric. Remarkably, the result is inconsistent with the corresponding result in the continuous-time counterpart, the M/G/1 retrial queue, where the tail of the queue size distribution is asymptotically given by a geometric function multiplied by a power function.     

Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

Global and local asymptotics for the busy period of an M/G/1 queue

We consider an M/G/1 queue with subexponential service times. We give a simple derivation of the global and local asymptotics for the busy period. Our analysis relies on the explicit formula for the joint distribution for the number of customers and the length of the busy period of an M/G/1 queue.     

Unreliable M/G/1 retrial queue: monotonicity and comparability

In this paper we investigate the monotonicity properties of an unreliable M/G/1 retrial queue using the general theory of stochastic ordering. We show the monotonicity of the transition operator of the embedded Markov chain relative to the strong stochastic ordering and increasing convex ordering. We obtain conditions of comparability of two transition operators and we obtain comparability conditions of the number of customers in the system. Inequalities are derived for the mean characteristics of the busy period, number of customers served during a busy period, number of orbit busy periods and waiting times. Inequalities are also obtained for some probabilities of the steady-state distribution of the server state. An illustrative numerical example is presented.     

An infinite-server queue influenced by a semi-Markovian environment

We consider an infinite-server queue, where the arrival and service rates are both governed by a semi-Markov process that is independent of all other aspects of the queue. In particular, we derive a system of equations that are satisfied by various “parts” of the generating function of the steady-state queue-length, while assuming that all arrivals bring an amount of work to the system that is either Erlang or hyperexponentially distributed. These equations are then used to show how to derive all moments of the steady-state queue-length. We then conclude by showing how these results can be slightly extended, and used, along with a transient version of Little’s law, to generate rigorous approximations of the steady-state queue-length in the case that the amount of work brought by a given arrival is of an arbitrary distribution.      

A note on the event horizon for a processor sharing queue

In this note we identify a phenomenon for processor sharing queues that is unique to ones with time-varying rates. This property was discovered while correcting a proof in Hampshire, Harchol-Balter and Massey (Queueing Syst. 53(1–2), 19–30, 2006). If the arrival rate for a processor sharing queue has unbounded growth over time, then it is possible for the number of customers in a processor sharing queue to grow so quickly that a newly entering job never finishes. We define the minimum size for such a job to be the event horizon for a processor sharing queue. We discuss the use of such a concept and develop some of its properties. This short article serves both as errata for Hampshire, Harchol-Balter and Massey (Queueing Syst. 53(1–2), 19–30, 2006) and as documentation of a characteristic feature for some processor sharing queues with time varying rates.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

Admission control for a multi-server queue with abandonment

In a M/M/N+M queue, when there are many customers waiting, it may be preferable to reject a new arrival rather than risk that arrival later abandoning without receiving service. On the other hand, rejecting new arrivals increases the percentage of time servers are idle, which also may not be desirable. We address these trade-offs by considering an admission control problem for a M/M/N+M queue when there are costs associated with customer abandonment, server idleness, and turning away customers. First, we formulate the relevant Markov decision process (MDP), show that the optimal policy is of threshold form, and provide a simple and efficient iterative algorithm that does not presuppose a bounded state space to compute the minimum infinite horizon expected average cost and associated threshold level. Under certain conditions we can guarantee that the algorithm provides an exact optimal solution when it stops; otherwise, the algorithm stops when a provided bound on the optimality gap is reached. Next, we solve the approximating diffusion control problem (DCP) that arises in the Halfin–Whitt many-server limit regime. This allows us to establish that the parameter space has a sharp division. Specifically, there is an optimal solution with a finite threshold level when the cost of an abandonment exceeds the cost of rejecting a customer; otherwise, there is an optimal solution that exercises no control. This analysis also yields a convenient analytic expression for the infinite horizon expected average cost as a function of the threshold level. Finally, we propose a policy for the original system that is based on the DCP solution, and show that this policy is asymptotically optimal. Our extensive numerical study shows that the control that arises from solving the DCP achieves a very similar cost to the control that arises from solving the MDP, even when the number of servers is small.     

Asymptotic behavior of the loss rate for Markov-modulated fluid queue with a finite buffer

We consider a Markov-modulated fluid queue with a finite buffer. It is assumed that the fluid flow is modulated by a background Markov chain which may have different transitions when the buffer content is empty or full. In Sakuma and Miyazawa (Asymptotic Behavior of Loss Rate for Feedback Finite Fluid Queue with Downward Jumps. Advances in Queueing Theory and Network Applications, pp. 195–211, Springer, Cambridge, 2009), we have studied asymptotic loss rate for this type of fluid queue when the mean drift of the fluid flow is negative. However, the null drift case is not studied. Our major interest is in asymptotic loss rate of the fluid queue with a finite buffer including the null drift case. We consider the density of the stationary buffer content distribution and derive it in matrix exponential forms from an occupation measure. This result is not only useful to get the asymptotic loss rate especially for the null drift case, but also it is interesting in its own light.     

Determining an adequate probe separation for estimating the arrival rate in an M/D/1 queue using single-packet probing

We present a technique to estimate the arrival rate from delay measurements, acquired using single-packet probing. With practical applications in mind, we investigate a lower bound on the value of probe separation, to obtain a satisfactory estimate in a fixed amount of time. This leads to a problem: how long does it take for an M/D/1 queue to converge to its steady state as a function of the load? We examine this problem using three independent approaches: the time until the autocovariance of the transient workload process becomes negligible; the time it takes for the first transient moment of the workload process to get close to its stationary limit; and the convergence rate of the transient workload distribution to stationarity. These approaches yield different, yet strikingly similar results. We conclude with a recommendation for the probe separation threshold, and a practical approach to obtaining an arrival rate estimate using single-packet probing.     

Tail asymptotics for a Lévy-driven tandem queue with an intermediate input

We consider a Lévy-driven tandem queue with an intermediate input assuming that its buffer content process obtained by a reflection mapping has the stationary distribution. For this queue, no closed form formula is known, not only for its distribution but also for the corresponding transform. In this paper, we consider only light-tailed inputs. For the Brownian input case, we derive exact tail asymptotics for the marginal stationary distribution of the second buffer content, while weaker asymptotic results are obtained for the general Lévy input case. The results generalize those of Lieshout and Mandjes from the recent papers (Lieshout and Mandjes in Math. Methods Oper. Res. 66:275–298, 2007 and Queueing Syst. 60:203–226, 2008) for the corresponding tandem queue without an intermediate input.     

On the GI/M/∞ queue with batch arrivals of constant size

In this note, the GI/M/ queue with batch arrivals of constant sizek is investigated. It is shown that the stationary probabilities that an arriving batch findsi customers in the system can be computed in terms of the corresponding binomial moments (Jordan's formula), which are determined by a recursive relation. This generalizes well-known results by Takács [12] for GI/M/. Furthermore, relations between batch arrival- and time-stationary probabilities are given.     

Transient analysis of a queue with system disasters and customer impatience

A single server queue with Poisson arrivals and exponential service times is studied. The system suffers disastrous breakdowns at an exponential rate, resulting in the loss of all running and waiting customers. When the system is down, it undergoes a repair mechanism where the repair time follows an exponential distribution. During the repair time any new arrival is allowed to join the system, but the customers become impatient when the server is not available for a long time. In essence, each customer, upon arrival, activates an individual timer, which again follows an exponential distribution with parameter ξ. If the system is not repaired before the customer’s timer expires, the customer abandons the queue and never returns. The time-dependent system size probabilities are presented using generating functions and continued fractions.     

Waiting and sojourn times in a multi-server queue with mixed priorities

We consider a multi-server queue with K priority classes. In this system, customers of the P highest priorities (P<K) can preempt customers with lower priorities, ejecting them from service and sending them back into the queue. Service times are assumed exponential with the same mean for all classes. The Laplace–Stieltjes transforms of waiting times are calculated explicitly and the Laplace–Stieltjes transforms of sojourn times are provided in an implicit form via a system of functional equations. In both cases, moments of any order can be easily calculated. Specifically, we provide formulae for the steady state means and the second moments of waiting times for all priority classes. We also study some approximations of sojourn-time distributions via their moments. In a practical part of our paper, we discuss the use of mixed priorities for different types of Service Level Agreements, including an example based on a real scheduling problem of IT support teams.      

On the Wave Equation Associated to the Hermite and the Twisted Laplacian

The dispersive properties of the wave equation u _tt +Au=0 are considered, where A is either the Hermite operator −Δ+|x|² or the twisted Laplacian −(∇ _x −iy)²/2−(∇ _y +ix)²/2. In both cases we prove optimal L ¹−L ^∞ dispersive estimates. More generally, we give some partial results concerning the flows exp (itL ^ν ) associated to fractional powers of the twisted Laplacian for 0<ν<1.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

The Poincaré series of divisorial valuations in the plane defines the topology of the set of divisors

With a plane curve singularity one associates a multi-index filtration on the ring of germs of functions of two variables defined by the orders of a function on irreducible components of the curve. The Poincaré series of this filtration turns out to coincide with the Alexander polynomial of the curve germ. For a finite set of divisorial valuations on the ring corresponding to some components of the exceptional divisor of a modification of the plane, in a previous paper there was obtained a formula for the Poincaré series of the corresponding multi-index filtration similar to the one associated with plane germs. Here we show that the Poincaré series of a set of divisorial valuations on the ring of germs of functions of two variables defines “the topology of the set of the divisors” in the sense that it defines the minimal resolution of this set up to combinatorial equivalence. For the plane curve singularity case, we also give a somewhat simpler proof of the statement by Yamamoto which shows that the Alexander polynomial is equivalent to the embedded topology.     

Analysis of the M/G/1 queue with exponentially working vacations—a matrix analytic approach

In this paper, an M/G/1 queue with exponentially working vacations is analyzed. This queueing system is modeled as a two-dimensional embedded Markov chain which has an M/G/1-type transition probability matrix. Using the matrix analytic method, we obtain the distribution for the stationary queue length at departure epochs. Then, based on the classical vacation decomposition in the M/G/1 queue, we derive a conditional stochastic decomposition result. The joint distribution for the stationary queue length and service status at the arbitrary epoch is also obtained by analyzing the semi-Markov process. Furthermore, we provide the stationary waiting time and busy period analysis. Finally, several special cases and numerical examples are presented.     

Control the Fibre Orientation Distribution at the Outlet of Contraction

A two dimensional model of the orientation distribution of fibres in a paper machine headbox is studied. The goal is to control the fibre orientation distribution at the outlet of contraction by changing its shape. The mathematical formulation leads to an optimization problem with control in coefficients of a linear convection-diffusion equation as the state problem. Then, the problem is expressed as an optimal control problem governed by variational forms. By using an embedding method, the class of admissible shapes is replaced by a class of positive Radon measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this linear programming problem. In this paper, we have shown that the embedding method (embedding the admissible set into a subset of measures), successfully can be applied to shape variation design to a one dimensional headbox. The usefulness of this idea is that the method is not iterative and it does not need any initial guess of the solution.