Search

Join the Shortest Queue (JSQ) is a popular routing policy for server farms. However, until now all analysis of JSQ has been limited to First-Come-First-Serve (FCFS) server farms, whereas it is known that web server farms are better modeled as Processor Sharing (PS) server farms. We provide the first approximate analysis of JSQ in the PS server farm model for general job-size distributions, obtaining the distribution of queue length at each queue. To do this, we approximate the queue length of each queue in the server farm by a one-dimensional Markov chain, in a novel fashion. We also discover some interesting insensitivity properties of PS server farms with JSQ routing, and discuss the near-optimality of JSQ.

We review queueing-theory methods for setting staffing requirements in service systems where customer demand varies in a predictable pattern over the day. Analyzing these systems is not straightforward, because standard queueing theory focuses on the long-run steady-state behavior of stationary models. We show how to adapt stationary queueing models for use in nonstationary environments so that time-dependent performance is captured and staffing requirements can be set. Relatively little modification of straightforward stationary analysis applies in systems where service times are short and the targeted quality of service is high. When service times are moderate and the targeted quality of service is still high, time-lag refinements can improve traditional stationary independent period-by-period and peak-hour approximations. Time-varying infinite-server models help develop refinements, because closed-form expressions exist for their time-dependent behavior. More difficult cases with very long service times and other complicated features, such as end-of-day effects, can often be treated by a modified-offered-load approximation, which is based on an associated infinite-server model. Numerical algorithms and deterministic fluid models are useful when the system is overloaded for an extensive period of time. Our discussion focuses on telephone call centers, but applications to police patrol, banking, and hospital emergency rooms are also mentioned.

One traditional application of queueing models is to help set staffing requirements in service systems, but the way to do so is not entirely straightforward, largely because demand in service systems typically varies greatly by the time of day. This article discusses ways—old and new—to cope with that time-varying demand. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007

This paper proposes simple methods for staffing a single‐class call center with uncertain arrival rate and uncertain staffing due to employee absenteeism. The arrival rate and the proportion of servers present are treated as random variables. The basic model is a multi‐server queue with customer abandonment, allowing non‐exponential service‐time and time‐to‐abandon distributions. The goal is to maximize the expected net return, given throughput benefit and server, customer‐abandonment and customer‐waiting costs, but attention is also given to the standard deviation of the return. The approach is to approximate the performance and the net return, conditional on the random model‐parameter vector, and then uncondition to get the desired results. Two recently‐developed approximations are used for the conditional performance measures: first, a deterministic fluid approximation and, second, a numerical algorithm based on a purely Markovian birth‐and‐death model, having state‐dependent death rates.

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.

In this paper we establish upper and lower bounds on the steady-state per-class workload distributions in a single-server queue with multiple priority classes. Motivated by communication network applications, the model has constant processing rate and general input processes with stationary increments. The bounds involve corresponding quantities in related models with the first-come first-served discipline. We apply the bounds to support a new notion of effective bandwidths for multi-class systems with priorities. We also apply the lower bound to obtain sufficient conditions for the workload distributions to have heavy tails.

Many service systems have demand that varies significantly by time of day, making it costly to provide sufficient capacity to be able to respond very quickly to each service re- quest. Fortunately, however, different service requests often have very different response-time requirements. Some service requests may need immediate response, while others can tolerate substantial delays. Thus it is often possible to smooth demand by partitioning the service requests into separate priority classes according to their response-time requirements. Classes with more stringent performance requirements are given higher priority for service. Lower capacity may be required if lower-priority-class demand can be met during off-peak periods. We show how the priority classes can be defined and the resulting required fixed capacity can be determined, directly accounting for the time-dependent behavior. For this purpose, we ex- ploit relatively simple analytical models, in particular, Mt/G/∞ and deterministic offered-load models. The analysis also provides an estimate of the capacity savings that can be obtained from partitioning time-varying demand into priority classes.

We establish stability, monotonicity, concavity and subadditivity properties for open stochastic storage networks in which the driving process has stationary increments. A principal example is a stochastic fluid network in which the external inputs are random but all internal flows are deterministic. For the general model, the multi-dimensional content process is tight under the natural stability condition. The multi-dimensional content process is also stochastically increasing when the process starts at the origin, implying convergence to a proper limit under the natural stability condition. In addition, the content process is monotone in its initial conditions. Hence, when any content process with non-zero initial conditions hits the origin, it couples with the content process starting at the origin. However, in general, a tight content process need not hit the origin.