Operations Research

An influence diagram is a graphical structure for modeling uncertain variables and decisions and explicitly revealing probabilistic dependence and the flow of information. It is an intuitive framework in which to formulate problems as perceived by decision makers and to incorporate the knowledge of experts. At the same time, it is a precise description of information that can be stored and manipulated by a computer. We develop an algorithm that can evaluate any well-formed influence diagram and determine the optimal policy for its decisions. Since the diagram can be analyzed directly, there is no need to construct other representations such as a decision tree. As a result, the analysis can be performed using the decision maker's perspective on the problem. Questions of sensitivity and the value of information are natural and easily posed. Modifications to the model suggested by such analyses can be made directly to the problem formulation, and then evaluated directly.

Two types of customer behavior are considered: (1) if a customer is acquired for service before he has waited a time τ₀, he remains in the queue until served irrespective of whether or not his total waiting time exceeds τ₀. Only those customers who wait for a time τ₀ without being acquired for service become “lost” customers, and (2) a customer whose total waiting time is τ₀ becomes a lost customer irrespective of whether he is acquired for service or not.

We consider a Markovian model of a multiclass queueing system in which a single large pool of servers attends to the various customer classes. Customers waiting to be served may abandon the queue, and there is a cost penalty associated with such abandonments. Service rates, abandonment rates, and abandonment penalties are generally different for the different classes. The problem studied is that of dynamically scheduling the various classes. We consider the Halfin-Whitt heavy traffic regime, where the total arrival rate and the number of servers both become large in such a way that the system's traffic intensity parameter approaches one. An approximating diffusion control problem is described and justified as a purely formal (that is, nonrigorous) heavy traffic limit. The Hamilton-Jacobi-Bellman equation associated with the limiting diffusion control problem is shown to have a smooth (classical) solution, and optimal controls are shown to have an extremal or “bang-bang” character. Several useful qualitative insights are derived from the mathematical analysis, including a “square-root rule” for sizing large systems and a sharp contrast between system behavior in the Halfin-Whitt regime versus that observed in the “conventional” heavy traffic regime. The latter phenomenon is illustrated by means of a numerical example having two customer classes.

We consider queueing systems in which customers arrive according to a Poisson process and have exponentially distributed service requirements. The customers are impatient and may abandon the system while waiting for service after a generally distributed amount of time. The system incurs customer-related costs that consist of waiting and abandonment penalty costs. We study capacity sizing in such systems to minimize the sum of the long-term average customer-related costs and capacity costs. We use fluid models to derive prescriptions that are asymptotically optimal for large customer arrival rates. Although these prescriptions are easy to characterize, they depend intricately upon the distribution of the customers' time to abandon and may prescribe operating in a regime with offered load (the ratio of the arrival rate to the capacity) greater than 1. In such cases, we demonstrate that the fluid prescription is optimal up to O(1). That is, as the customer arrival rate increases, the optimality gap of the prescription remains bounded.

Deterministic fluid models are developed to provide simple first-order performance descriptions for multiserver queues with abandonment under heavy loads. Motivated by telephone call centers, the focus is on multiserver queues with a large number of servers and nonexponential service-time and time-to-abandon distributions. The first fluid model serves as an approximation for the G/GI/s+GI queueing model, which has a general stationary arrival process with arrival rate λ, independent and identically distributed (IID) service times with a general distribution, s servers and IID abandon times with a general distribution. The fluid model is useful in the overloaded regime, where λ > s, which is often realistic because only a small amount of abandonment can keep the system stable. Numerical experiments, using simulation for M/GI/s+GI models and exact numerical algorithms for M/M/s+M models, show that the fluid model provides useful approximations for steady-state performance measures when the system is heavily loaded. The fluid model accurately shows that steady-state performance depends strongly upon the time-to-abandon distribution beyond its mean, but not upon the service-time distribution beyond its mean. The second fluid model is a discrete-time fluid model, which serves as an approximation for the G_t (n)/GI/s+GI queueing model, having a state-dependent and time-dependent arrival process. The discrete-time framework is exploited to prove that properly scaled queueing processes in the queueing model converge to fluid functions as s → ∞. The discrete-time framework is also convenient for calculating the time-dependent fluid performance descriptions.

Two different kinds of heavy-traffic limit theorems have been proved for s-server queues. The first kind involves a sequence of queueing systems having a fixed number of servers with an associated sequence of traffic intensities that converges to the critical value of one from below. The second kind, which is often not thought of as heavy traffic, involves a sequence of queueing systems in which the associated sequences of arrival rates and numbers of servers go to infinity while the service time distributions and the traffic intensities remain fixed, with the traffic intensities being less than the critical value of one. In each case the sequence of random variables depicting the steady-state number of customers waiting or being served diverges to infinity but converges to a nondegenerate limit after appropriate normalization. However, in an important respect neither procedure adequately represents a typical queueing system in practice because in the (heavy-traffic) limit an arriving customer is either almost certain to be delayed (first procedure) or almost certain not to be delayed (second procedure). Hence, we consider a sequence of (GI/M/S) systems in which the traffic intensities converge to one from below, the arrival rates and the numbers of servers go to infinity, but the steady-state probabilities that all servers are busy are held fixed. The limits in this case are hybrids of the limits in the other two cases. Numerical comparisons indicate that the resulting approximation is better than the earlier ones for many-server systems operating at typically encountered loads.

We consider a class of parallel server systems that are known as N-systems. In an N-system, there are two customer classes that are catered by servers in two pools. Servers in one of the pools are cross-trained and can serve customers from both classes, whereas all of the servers in the other pool can serve only one of the customer classes. A customer reneges from his queue if his waiting time in the queue exceeds his patience. Our objective is to minimize the total cost that includes a linear holding cost and a reneging cost. We prove that, when the service speed is pool dependent, but not class dependent, a cμ-type greedy policy is asymptotically optimal in many-server heavy traffic.

This paper reviews the relevant literature on the problem of determining suitable ordering policies for both fixed life perishable inventory, and inventory subject to continuous exponential decay. We consider both deterministic and stochastic demand for single and multiple products. Both optimal and sub-optimal order policies are discussed. In addition, a brief review of the application of these models to blood bank management is included. The review concludes with a discussion of some of the interesting open research questions in the area.

Motivated by telephone call centers, we study large-scale service systems with multiple customer classes and multiple agent pools, each with many agents. To minimize staffing costs subject to service-level constraints, where we delicately balance the service levels (SLs) of the different classes, we propose a family of routing rules called fixed-queue-ratio (FQR) rules. With FQR, a newly available agent next serves the customer from the head of the queue of the class (from among those he is eligible to serve) whose queue length most exceeds a specified proportion of the total queue length. The proportions can be set to achieve desired SL targets. The FQR rule achieves an important state-space collapse (SSC) as the total arrival rate increases, in which the individual queue lengths evolve as fixed proportions of the total queue length. In the current paper we consider a variety of service-level types and exploit SSC to construct asymptotically optimal solutions for the staffing-and-routing problem. The key assumption in the current paper is that the service rates depend only on the agent pool.

We investigate how performance scales in the standard M/M/n queue in the presence of growing congestion-dependent customer demand. We scale the queue by letting the potential (congestion-free) arrival rate be proportional to the number of servers, n, and letting n increase. We let the actual arrival rate with n servers be of the form λ_n=f(ξ_n)n, where f is a strictly-decreasing continuous function and ξ_n is a steady-state congestion measure. We consider several alternative congestion measures, such as the mean waiting time and the probability of delay. We show, under minor regularity conditions, that for each n there is a unique equilibrium pair (λ*_n, ξ*_n) such that ξ*_n is the steady-state congestion associated with arrival rate λ*n and λ*n=f(ξ*_n)n. Moreover, we show that, as n increases, the queue with the equilibrium arrival rate λ*n is brought into heavy traffic, but the three different heavy-traffic regimes for multiserver queues identified by Halfin and Whitt (1981) each can arise depending on the congestion measure used. In considerable generality, there is asymptotic service efficiency: the server utilization approaches one as n increases. Under the assumption of growing congestion-dependent demand, the service efficiency can be achieved even if there is significant uncertainty about the potential demand, because the actual arrival rate adjusts to the congestion.