Convergence to equilibrium states for fluid models of many-server queues with abandonment

Fluid models, in particular their equilibrium states, have become an important tool for the study of many-server queues with general service and patience time distributions. However, it remains an open question whether the solution to a fluid model converges to the equilibrium state and under what condition. We show in this paper that the convergence holds under some conditions. Our method builds on the framework of measure-valued processes, which keeps track of the remaining patience and service times.     

Validity of heavy-traffic steady-state approximations in many-server queues with abandonment

We consider \(GI/Ph/n+M\) parallel-server systems with a renewal arrival process, a phase-type service time distribution, \(n\) homogenous servers, and an exponential patience time distribution with positive rate. We show that in the Halfin–Whitt regime, the sequence of stationary distributions corresponding to the normalized state processes is tight. As a consequence, we establish an interchange of heavy-traffic and steady-state limits for \(GI/Ph/n+M\) queues.     

Fluid models for many-server Markovian queues in a changing environment

Motivated by service systems with time-varying customer arrivals, we consider a fluid model as a macroscopic approximation for many-server Markovian queues alternating between underloaded and overloaded intervals. Our main result is a refinement of the piecewise stationary approximation (PSA) for the stationary distribution of the fluid model. The form of the refined approximation suggests simple metrics for assessing the accuracy of PSA for underloaded and overloaded intervals respectively.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

A note on a limit interchange for many-server queues

A connection between open and closed many-server queueing systems is examined. Two limits are considered: (i) the number and reliability of machines (customers) increase simultaneously while the offered load remains constant (Poisson limit), and (ii) the number of machines (customers) and repairmen (servers) increase while the utilization remains close to unity (QED limit). It is argued that the two limits are interchangeable.     

Fluid queues with synchronized output

We present a model of parallel Lévy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.     

Gaussian skewness approximation for dynamic rate multi-server queues with abandonment

The multi-server queue with non-homogeneous Poisson arrivals and customer abandonment is a fundamental dynamic rate queueing model for large scale service systems such as call centers and hospitals. Scaling the arrival rates and number of servers arises naturally when a manager updates a staffing schedule in response to a forecast of increased customer demand. Mathematically, this type of scaling ultimately gives us the fluid and diffusion limits as found in Mandelbaum et al., Queueing Syst 30:149–201 (1998) for Markovian service networks. The asymptotics used here reduce to the Halfin and Whitt, Oper Res 29:567–588 (1981) scaling for multi-server queues. The diffusion limit suggests a Gaussian approximation to the stochastic behavior of this queueing process. The mean and variance are easily computed from a two-dimensional dynamical system for the fluid and diffusion limiting processes. Recent work by Ko and Gautam, INFORMS J Comput, to appear (2012) found that a modified version of these differential equations yield better Gaussian estimates of the original queueing system distribution. In this paper, we introduce a new three-dimensional dynamical system that is based on estimating the mean, variance, and third cumulant moment. This improves on the previous approaches by fitting the distribution from a quadratic function of a Gaussian random variable.     

Many-server Gaussian limits for overloaded non-Markovian queues with customer abandonment

Extending Ward Whitt’s pioneering work “Fluid Models for Multiserver Queues with Abandonments, Operations Research, 54(1) 37–54, 2006,” this paper establishes a many-server heavy-traffic functional central limit theorem for the overloaded \(G{/}GI{/}n+GI\) queue with stationary arrivals, nonexponential service times, n identical servers, and nonexponential patience times. Process-level convergence to non-Markovian Gaussian limits is established as the number of servers goes to infinity for key performance processes such as the waiting times, queue length, abandonment and departure processes. Analytic formulas are developed to characterize the distributions of these Gaussian limits.     

Fluid queues with level dependent evolution

A fluid queue is a two-dimensional Markov process, of which the first component, or level, varies linearly according to the second component, the phase, which is the state of a finite state space Markov process evolving in the background.     

Abandonment versus blocking in many-server queues: asymptotic optimality in the QED regime

We consider a controlled queueing system of the $G/M/n/B+GI$ G / M / n / B + G I type, with many servers and impatient customers. The queue-capacity $B$ B is the control process. Customers who arrive at a full queue are blocked and customers who wait too long in the queue abandon. We study the tradeoff between blocking and abandonment, with cost accumulated over a random, finite time-horizon, which yields a queueing control problem (QCP). In the many-server quality and efficiency-driven (QED) regime, we formulate and solve a diffusion control problem (DCP) that is associated with our QCP. The DCP solution is then used to construct asymptotically optimal controls (of the threshold type) for QCP. A natural motivation for our QCP is telephone call centers, hence the QED regime is natural as well. QCP then captures the tradeoff between busy signals and customer abandonment, and our solution specifies an asymptotically optimal number of trunk-lines.     

On the probability of abandonment in queues with limited sojourn and waiting times

Consider the Geo/Geo/1 queue with impatient customers and let X reflect the patience distribution. We show that systems with a smaller patience distribution X in the convex-ordering sense give rise to fewer abandonments (due to impatience), irrespective of whether customers become patient when entering the service facility.     

Time-varying many-server finite-queues in tandem: Comparing blocking mechanisms via fluid models

This paper focuses on the mechanism of Blocking Before Service (BBS), in time-varying many-server queues in tandem. BBS arises in telecommunication networks, production lines and healthcare systems. We model a stochastic tandem network under BBS and develop its corresponding fluid limit, which includes reflection due to jobs lost. Comparing our fluid model against simulation shows that the model is accurate and effective. This gives rise to design/operational insights regarding network throughput, under both BBS and BAS (Blocking After Service).     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Switching stochastic models and applications in retrial queues

Some special classes of Switching Processes such as Recurrent Processes of a Semi-Markov type and Processes with Semi-Markov Switches are introduced. Limit theorems of Averaging Principle and Diffusion Approximation types are given. Applications to the asymptotic analysis of overloading state-dependent Markov and semi-Markov queueing modelsM _SM,Q /M _SM,Q /1/∞ and retrial queueing systemsM/G/1/w.r in transient conditions are studied. The paper was supported by INTAS Project 96-0828     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

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.     

A survey of Markov decision models for control of networks of queues

We review models for the optimal control of networks of queues. Our main emphasis is on models based on Markov decision theory and the characterization of the structure of optimal control policies.This research was partially supported by the National Science Foundation under Grant No. DDM-8719825. The Government has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research was also partially supported by the C.I.E.S. (France), while the author was on leave at INRIA, Sophia-Antipolis, 1991–92.     

Asymptotic expansions of defective renewal equations with applications to perturbed risk models and processor sharing queues

We consider asymptotic expansions for defective and excessive renewal equations that are close to being proper. These expansions are applied to the analysis of processor sharing queues and perturbed risk models, and yield approximations that can be useful in applications where moments are computable, but the distribution is not.