|
Article Excerpt
1. Introduction
We investigate alternative ways to estimate, in real time, the delay (before entering service) of an arriving customer in a service system with customer abandonment. We do this primarily so that delay announcements can be made to arriving customers. Delay announcements can be helpful when queues are invisible to customers, as in call centers; see Gans et al. (2003) and Aksin et al. (2007) for background on call centers.
Comparing alternative delay estimators is complicated. Naturally, we would like to have a delay estimator that is effective. We quantify the effectiveness of a delay estimator by the mean squared error (MSE). Because the estimator typically depends on state information, we use the expected MSE, considering the steady-state distribution of the state information, which we estimate via simulation by computing the average squared error (ASE), averaging over a large number of customers in steady state. A lower expected MSE (or ASE) corresponds to a more effective delay estimator.
But, we would also like to have a simple delay estimator, which can be easily implemented in a real-life system, i.e., one that uses information that is readily available. Alternative delay estimators differ in the type and amount of information that their implementation requires. For example, this information may involve the model, the system state upon arrival, or the history of delays in the system. An important insight, which applies broadly, is that simplicity and ease of implementation are often obtained at the expense of statistical precision.
Our main contributions are (i) to propose new, effective, and simple ways to do better delay estimation in overloaded, many-server queues with customer abandonment; (ii) to establish heavy-traffic limits that generate approximations for the expected MSE of some delay estimators; and (iii) to describe results of simulation experiments evaluating alternative delay estimators. We obtain more effective delay estimators by exploiting approximations for performance measures in many-server queues with a nonexponential abandonment-time distribution, from Whitt (2005, 2006).
1.1. Queueing Model
We study the performance of alternative real-time delay estimators by considering the steady-state behavior of an overloaded GI/GI/s + GI queueing model, allowing customer abandonment. This model has independent and identically distributed (i.i.d.) interarrival times with mean [[lambda].sup.-1] and a general distribution. We only use the i.i.d. assumption for the interarrival times when simulating the model; it is not required for the implementation of our delay estimators. Service times are i.i.d. with mean [[mu].sup.-1] and a general distribution. Each arriving customer will abandon if he is unable to start service before a random time with mean [[alpha].sup.-1] and a general distribution. Abandonments times are i.i.d.; the arrival, service, and abandonment processes are all mutually independent. There is unlimited waiting space and arriving customers are served in order of arrival; i.e., we use the first-come-first-served service discipline. The traffic intensity is [rho] [equivalent to] [lambda]/s[mu].
We focus on overloaded scenarios, in which the arrival rate exceeds the maximum possible total service rate. Customer abandonment makes the system stable in this case. (That can be proved by bounding the model above by the GI/GI/[infinity] model obtained by removing all servers; then the abandonment times can be thought of as service times. For more on the stability of the GI/GI/[infinity] model, see p. 178 of Whitt 1982.) We consider overloaded systems because we are primarily interested in estimating delays when they are large. Many call centers are overloaded some of the time, especially service-oriented ones in which emphasis is placed on efficiency rather than on quality of service.
1.2. Queue-Length-Based and Delay-History-Based Delay Estimators
We consider both queue-length-based and delay-history-based delay estimators. Queue-length-based delay estimators exploit system-state information including the queue length (number of waiting customers) seen upon arrival. In contrast, delay-history-based estimators only exploit information about recent customer delay history in the system. These delay estimators are appealing because they are easy to interpret, and because they are simple and robust, applying to a broad range of models, without requiring knowledge of the model or its parameters; e.g., number of servers, mean service time, and arrival rate.
1.3. Customer Response to Delay Announcements
We envision our delay estimates being used to make delay announcements to arriving customers: Each delayed customer, upon arrival, is given a single-number delay estimate of that customer's delay until he can start service. Customers typically respond to delay announcements, and their response alters system performance. For example, some customers may elect to balk, upon arrival, in response to a delay announcement. As a result, the arrival rate to the system would become state dependent. Moreover, customers who decide to stay may have different abandonment behavior in response to the announcement. They may become increasingly impatient if they have to wait more than their announced delay. As a result, the abandonment distribution of customers in queue would depend on their elapsed waiting time. Changes in system performance alter, in turn, the delay estimates given. As discussed by Armony et al. (2009), studying customer responses to delay announcements requires an equilibrium analysis. However, it is not clear whether an equilibrium exists, or how to fully characterize it. There may even be multiple equilibria.
Here, we do not directly consider customer response. We think of our delay estimates being based on model information obtained after equilibrium has been reached (with the announcements being used). More generally, we regard our work as an essential first step toward studying the performance impact of delay announcements in the GI/GI/s + GI model. It is not hard to see how the delay estimation methods of this paper can be applied to the more complicated setting involving customer response. Indeed, the delay-history-based estimators directly account for customer response because they depend on the history of delays in the system, which in turn is affected by customer response.
The queue-length-based estimators can also be extended to account for changes in customer behavior. For example, we could use an iterative simulation-based algorithm to develop approximations of the equilibrium steady-state performance of the GI/GI/s + GI model with delay announcements. During each iteration, we would give real-time delay estimates to arriving customers, and model their response. We would then reestimate model parameters that are affected by customer response, and feed these new estimates into the subsequent iteration. The algorithm would continue until the observed difference between successive estimates of model parameters is negligible. It is significant that our proposed queue-length-based estimators apply directly to the successive iterations of this algorithm, because the queueing model in each iteration is a GI/GI/s + GI model with a different set of parameters. There remains, however, to determine appropriate regularity conditions under which this algorithm terminates, i.e., under which there exists a unique equilibrium in the system.
1.4. Actual and Potential Waiting Times
As in Baccelli et al. (1984) and Garnett et al. (2002), we need to distinguish between the actual and potential waiting times of a given delayed customer in a queueing model with customer abandonment. A customer's actual waiting time is the amount of time that this customer spends in queue, until he either abandons or joins service, whichever comes first. A customer's potential waiting time is the delay he would experience, if he had infinite patience (quantified by his abandon time). For example, the potential waiting time of a delayed customer who finds n other customers waiting ahead in queue upon arrival, is the amount of time needed to have n + 1 consecutive departures from the system (either service completions or abandonments from the queue). In this study, we estimate the potential waiting times of delayed customers.
1.5. Quantifying Performance: Average Squared Error (ASE)
In our simulation experiments, we quantify the performance of a delay estimator by computing the ASE, defined by
ASE [equivalent to] [1/k] [k.summation over (i = 1)] [([p.sub.i] - [e.sub.i]).sup.2], (1)
where [p.sub.i] > is the potential waiting time of delayed customer i, [e.sub.i] is the delay estimate given to customer i, and k is the number of customers in our sample. In our simulation experiments, we measure [p.sub.i] for both served and abandoning customers. For abandoning customers, we compute the delay experienced, had the customer not abandoned, by keeping him "virtually" in queue until he would have begun service. Such a customer does not affect the waiting time of any other customer. The ASE should approximate the expected MSE in steady state.
1.6. Mean Squared Error (MSE)
Let [W.sub.Q] (n) represent a random variable with the conditional distribution of the potential delay of an arriving customer, given that this customer must wait before starting service, and given that the queue length at the time of his arrival, t, not counting himself, is Q(t) = n. (In this framework, the event "Q(t) = 0" corresponds to all servers being busy and our arriving customer being the first in queue.) Let [[theta].sub.QL](n) be some given single-number delay estimate that is based on the queue length, n. Then, the MSE of the corresponding delay estimator is given by
MSE [equivalent to] MSE([[theta].sub.QL](n)) [equivalent to] E[[([W.sub.Q](n) - [[theta].sub.QL](n)).sup.2]].
The MSE of a queue-length-based delay estimator is a function of...
|
