Method and apparatus for predicting queuing delays

Apparatus and method for predicting wait times for queuing customers. Upon arrival of a new customer to the queue, or at any other desired time, a system classifies each customer in service according to one or more attributes. The system generates a probability distribution of the remaining service time for each customer based on the attributes. Preferably, the system classifies each customer in queue according to one or more attributes and generates a probability distribution of service time based on the attributes. From the probability distributions of the customers in service and the customers in queue, the system estimates a wait time for the new customer. The estimated wait time may be communicated to the customers or to a system administrator and may include information on the full waiting time distribution or a summary of the distribution.

BACKGROUND OF THE INVENTION 
The present invention is directed to a method and apparatus that estimates 
delays to be endured by customers to a queue. 
In service systems having a limited capacity, it is known to place 
customers who cannot be served immediately into a queue until system 
resources become available to the customer. Often, customers are not given 
an estimate of the time when the customer can begin to receive service. If 
the customers are forced to wait "on hold" for a long period of time 
without such information, the customer may become dissatisfied with the 
service provider. 
To provide customers with information regarding a time in which the 
customer can expect to wait in queue, some service providers may identify 
the customer's position in queue. However, position information may not 
enable the customer to determine how long the customer will have to wait 
before obtaining service. The customer cannot determine how many agents 
are fielding service requests or the rate at which the agents are 
completing service requests. 
Other service providers may generate an estimate of the rate at which its 
agents complete service requests from its customers. A system having s 
agents each of whom, on average, complete service requests in r minutes, 
may predict that a customer placed in queue at the kth position will be 
served in k*r/s minutes. However, prediction based on such long-run 
averages may be subject to gross inaccuracies in specific instances. If 
long-term averages are not met in specific instances, customers may wait 
for a much longer time than is predicted. Such customers, too, may become 
dissatisfied with the service provider. 
Accurate prediction could also serve other purposes. For instance, a 
service provider might provide additional service at some other facility 
after the first service is complete. The predicted delay at the first 
facility might enable the service provider to better plan for the 
subsequent service. The service provider also might use the delay 
predictions to budget its available service capacity, e.g., by adding 
agents when large delays are predicted. 
For the reasons set forth above, there is a need in the art for a system 
that accurately predicts anticipated wait times that customers will incur 
upon entering a queue. 
SUMMARY OF THE INVENTION 
The disadvantages of the prior art are alleviated to a great extent by an 
apparatus and method that classifies each waiting customer and each 
customer being serviced based upon known attributes of the customers and 
possibly upon the agents that are providing the service. Based upon the 
classifications, the system estimates the probability distribution 
function of each customer's remaining service time. The system calculates, 
from the estimated probability distribution functions of the service 
times, an estimated number of departures that are expected over time and 
further calculates a full probability distribution function of the 
expected waiting time before a new customer can begin service. The system 
may also calculate a full probability distribution of the waiting time 
before beginning service for other customers that already have been 
waiting (those in queue). 
The present invention may use one of four different methods to predict a 
distribution of the estimated waiting time for a new customer. First, the 
estimated waiting time distribution may be based on the probability 
distribution functions of the service times for the customers in service 
and the customers in queue. Second, an added refinement may be used to 
estimate starting times for the customers in queue ahead of the new 
customers. Third, when the number of agents is greater than the number of 
customers, the estimated waiting time may be estimated based on the rate 
of service of the agents. Fourth, when the number of agents is less than 
the number of customers in queue, the estimated waiting time may be 
estimated based on the service-time distributions of the customers in 
queue.

DETAILED DESCRIPTION 
The present invention provides improved service in a service system having 
a limited capacity by estimating a probability distribution function of 
the waiting time before a new customer (or a customer already in queue) 
will begin to receive service. This probability distribution can be used 
by the service provider to provide approximate wait time estimates to 
customers. The service provider could communicate to the customers the 
full estimated probability distribution function of the wait time or, 
alternatively, communicate only summary descriptions of the probability 
distribution function, such as the expected value or the 90th percentile. 
The service provider could also give some idea of the uncertainty of an 
expected estimate value, e.g. by giving the variance. Finally, the service 
provider may use the estimate to reconfigure the system and add or remove 
agents to change the wait time estimates. 
All customers, those receiving service and those waiting in queue, are 
categorized by one or more customer attributes. From those customer 
attributes, a probability distribution function ("PDF") of the remaining 
service time is generated for each customer. These service-time PDFs 
permit a system administrator to predict a waiting time PDF for a new 
customer being added to the queue. It also permits a system administrator 
to predict the waiting time PDF of any customer already in the queue. 
The "probability distribution function" of a random quantity is a 
description of the probability that the quantity is less than or equal to 
any specified value, for all possible values. If X is a random time, then 
its probability distribution function can be denoted by 
G(x)=P(X.ltoreq.x), 0.ltoreq.x&lt;.infin., i.e., the probability that X is 
less than or equal to x for each possible x. 
FIG. 1(a) shows an embodiment of a system 100 constructed in accordance 
with the present invention. The system 100 includes a plurality of agents 
A.sub.1 -A.sub.s having capacity s and a queue 110 having capacity q. The 
agents A.sub.1 -A.sub.s, and the queue 110 are in communication with a 
plurality of customers (not shown) via a network 200. In a preferred 
embodiment, the system 100 includes a processor 120 in communication with 
each of the agents A.sub.1-A.sub.s and with the queue. The processor 120 
monitors the activity of the agents A.sub.1 -A.sub.s, and, accordingly, 
monitors the service requirements of the customers for whom each agent is 
providing service. The processor also monitors the queue 110 and, 
accordingly, monitors all activity between the queue 110 and the customers 
placed therein. 
When all agents are serving customers, any new customers are placed in the 
queue 110. New customers are dropped when the queue 110 is full. If the 
system 100 is serving s customers and k customers are in queue, the new 
customer is placed in queue 110 at position k+1. Upon arrival, the system 
100 provides new customers with an estimate of the wait time that the 
customer will endure. At any other desired time, the system also can 
provide customers already in queue with estimates of remaining wait-times 
they will endure. 
The prediction method of the present invention is shown in FIG. 2. Upon 
arrival of a new customer or at any desired time, the system 100 examines 
attributes of each customer in service (Step 1000). The system generates 
probability distribution functions, labeled G.sub.i (t), for the remaining 
service-time of each customer i based on the attributes found (Step 1010). 
The system also considers the customers in queue ahead of the new 
customer. As with the customers in service, the system examines attributes 
of the customers in queue (Step 1010). Based on the customer attributes, 
the system generates service-time PDFs G.sub.i (t) for each queuing 
customer i representing the probability that the customer's service will 
be less than or equal to any specified time (Step 1030). Finally, the 
system estimates a PDF of the waiting time before beginning service based 
upon the estimated number of departures (Step 1100). 
To establish service-time PDFs for the customers, the system 100 examines a 
number of attributes for each customer As an illustrative example, the 
system 100 may be one for providing internet connection services. Each of 
the s customers in service might be classified according to the activity 
that the customer initiates upon connection. FIG. 3 illustrates a variety 
of probability distribution functions that may be appropriate to the 
classifications. Customers that connect to retrieve electronic mail, for 
example, may disconnect very soon after connection; PDF1 may be 
appropriate for these customers, shown in FIG. 3 (a). Other customers may 
exhibit behavior that demonstrates a longer connection time, in which case 
PDF2 would be appropriate, shown in FIG. 3(b) Still other PDFs may be 
assigned to other customers or based on other attributes. As another 
attribute, the relative efficiency of one agent A.sub.1 may be considered 
when generating PDFs. Further, policies of the service providers may 
affect distributions. For example, a help desk may choose to limit service 
requests to a set amount of time, say 10 minutes; if a customer's problem 
is not solved before the limit expires, the customer may be referred to 
some other service provider. Such a policy could be represented by PDF3 in 
FIG. 3(c). Each customer i in service is assigned a service-time PDF 
G.sub.i (t) representing the probability that the customer will disconnect 
on or before time t. 
One attribute that is particularly useful when generating PDFs of the 
remaining service time of customers in service is the elapsed time of 
service. Given that the customer has been in service an amount of time x, 
the system estimates probabilities that the customer will terminate 
service before time t, for all t values. The estimate is called a 
"conditional PDF." FIGS. 4(a) and 4(b) illustrate a relationship between 
the PDF and probability density functions. If g(t) is the probability 
density function associated with probability distribution function G(t), 
they are related by: 
##EQU1## 
i.e., G(t) is the integral of g from 0 to t and g(t) is the derivative of 
G(t) at t. FIG. 4(b) displays a hypothetical probability density function 
g.sub.i (t). A conditional probability distribution function G.sub.i 
(t.vertline.x) is represented by the g1 area divided by the total area (g1 
and g2). 
The total area under the curve g.sub.i (t) is assumed to be 1. Because it 
represents a probability, the system 100 calculates a conditional PDF, 
G.sub.i (t.vertline.x.sub.i), representing the probability that, given 
that the customer service has lasted a time x.sub.i, the customer service 
will conclude within an additional time t: 
##EQU2## 
Even if the elapsed times of the customers in service are not available, 
the knowledge that a customer already is in service may be exploited. 
Then, instead of the original service-time PDF, an alternative 
service-time stationary-excess conditional PDF 
##EQU3## 
can be used; where m.sub.i is the mean (expected value) of the PDF 
G.sub.i. 
In addition to the customers in service, the system 100 generates PDFs for 
the k customers in queue by classifying the customers by whatever 
attributes are known about them. Using the internet connection example 
above, because the queuing customers have not received internet services, 
the system cannot classify them based upon their conduct. However, the 
system 100 may possess other information, such as the customers' IDs or 
telephone numbers, that permit limited classifications to be made. If the 
customer's IDs are known, the system may assign PDFs based on the 
customers' prior behavior. As noted, the system 100 may have established 
policies, independent of any customer attribute, that governs the PDF. A 
PDF G.sub.j (t) is assigned to each customer in queue (1&lt;j&lt;k) representing 
a probability over time when the customer will conclude service. 
For certain customers, either those in service or those in queue, only 
partial information may be available regarding the customer's estimated 
service time. For example, a mean service time, m.sub.i, may be available. 
When only partial information is available, the system fits a service time 
PDF G.sub.i (t) to the partial information, For example, given the mean 
m.sub.i, the system can fit an exponential PDF G.sub.i 
(t)=1-e.sup.-t/m.sbsp.i. For some customers, the mean m.sub.i may have to 
be a long-run average. 
Once service-time PDF's are generated for the customers in service and the 
customers in queue, the system 100 sums across all customers in service to 
estimate the expected number of departures in the time interval [0, t] 
from the customers initially in service, ED.sub.s (t): 
##EQU4## 
Assuming, as a practical approximation, that the customers in queue can 
start service immediately, the expected number of departures over time for 
the first k customers in queue, ED.sub.q (t), can be approximately 
expressed as: 
##EQU5## 
An associated estimate of the total expected number of departures can be 
obtained by adding Eqs. (4) and (5), i.e: 
EQU ED(t)=ED.sub.s (t)+ED.sub.q (t). (6) 
Armed with an estimated number of departures over time, the system may 
estimate the time before the system will service k+1 customers, which is 
the time when the new customer can begin to receive service. The same 
formula applies to a customer already in queue if he is the (k+1).sup.th 
customer. The actual random waiting time W is: 
EQU W=min{t.gtoreq.0:ED(t)=k+1} (7) 
The next step is to develop an approximate expression for the PDF of the 
waiting time W, i.e., for P(W.ltoreq.w) as a function of w. Because the 
random number D(t) is a sum of independent random variables, its 
distribution is assumed to be approximately normally distributed. Let 
w.sub.x be defined to represent a waiting time based on the mean ED(t) and 
the standard deviation SD(D(t)): 
EQU w.sub.x =min{t.gtoreq.0:ED(t)+xSD(D(t))=k+1} (8) 
where x is a constant. Then the system may obtain an approximate expression 
for the distribution of W by: 
EQU P(W&gt;w.sub.x).apprxeq.P(D(t).ltoreq.ED(t)+xSD(D(t)).apprxeq.P(N(0,1).ltoreq. 
x).apprxeq..PHI.(x), (9) 
where N(0,1) is a standard normal random variable having mean 0 and 
variance 1 and .PHI. is its PDF. As x is allowed to vary, Eqs. (8) and (9) 
give an expression for the complementary PDF of W, i.e., for 1-P(W&lt;w) as a 
function of w. 
In many applications, it is useful to obtain the full distribution of W. In 
such applications, the system calculates the distribution according to Eq. 
(9) above. However, in other applications, only a single value of a wait 
time is necessary. In this circumstance, the system progresses as follows. 
For 0&lt;.alpha.&lt;1, a relationship is defined x.sub..alpha. =.PHI..sup.-1 
(.alpha.) (or, equivalently, .PHI.(x.sub..varies.)=.alpha.). Then 
W.sub.x.sbsb..alpha. is the approximate .alpha..sup.th percentile of the 
distribution of w. 
The system can also generate a single value summary estimate of the PDF of 
the waiting time W. The relationship between .alpha. and w allows a system 
operator to choose how aggressive or conservative his estimate will be. 
For example, setting .alpha.=0.90, the system operator obtains an estimate 
of w that has a 90% probability [.alpha.*100%] of being less than or equal 
to the estimates. Alternatively, setting .alpha.=0.5 obtains an estimate 
that has a 50% chance of being less than or equal to the estimates (i.e., 
the median). 
In a second embodiment of the present invention, a better estimate of wait 
times is obtained by estimating the times at which each customer in queue 
ahead of the new customers will be able to begin service. The system 100 
estimates times of departure of the customers now in service based on 
their PDFs. The system 100 then uses each estimated departure time as a 
starting point of the PDFs of the customers in queue. The system 100 
estimates a time, t.sub.j, in which the j.sup.th customer in queue will 
begin service: 
EQU t.sub.j =min{t.gtoreq.0:ED.sub.s (t)=j} (10) 
where ED.sub.s (t) is given in Eq. (4) From the t.sub.j 's, the system 100 
obtains an estimate of the expected number of departures over time: 
##EQU6## 
Having obtained a more precise estimate of the number of departures over 
time, the system may estimate the waiting time of the new customers 
according to W in the first embodiment (Eq. (7)-(9)) but using ED(t) in 
Eq. (11) above as the basis of the estimate. 
In a third embodiment, the system calculates waiting times for the first 
few customers in queue. The third embodiment is particularly useful when 
the number of customers in queue is small relative to the number of agents 
(i.e., k&lt;&lt;s). The system estimates the instantaneous rate of departure of 
customers in service and extends that rate over the first few customers in 
queue. The waiting time of the first customer in the queue has the 
complementary PDF: 
##EQU7## 
which may be calculated via: 
##EQU8## 
The service-time PDF G.sub.i (t) in Eqs. (12) and (13) is assumed to be 
based on the customer and agent attributes, just as before. Furthermore, 
W.sub.1 may be approximated by an exponential distribution: 
##EQU9## 
Then, the departure process can be approximated by a Poisson process with 
rate .mu..sub.1 so that W.sub.k has approximately a gamma distribution 
with mean and variance: 
##EQU10## 
This approximation is natural to use when only the mean remaining service 
times of the customers in service is known (m.sub.i, 1.ltoreq.i 
.ltoreq.s). Then the rate .mu..sub.1 may be approximately expressed as 
##EQU11## 
In a fourth embodiment, the system 100 tends to de-emphasize the role of 
the customers in service. Such a prediction scheme finds application where 
the number of customers in queue is large compared with the number of 
agents (i.e. k&gt;&gt;s). In this embodiment, the estimated. waiting time 
resembles the k/s*r estimate described in the background of the invention 
above. However, the present invention advantageously considers the 
nonidentically distributed PDFs G.sub.i (t) of the customers, and the 
means m.sub.i and variances .sigma..sub.i.sup.2 of the PDFs: 
##EQU12## 
The s customers in service are indexed first, followed by the first 
customers in queue. 
The present invention has been characterized as a method for predicting a 
wait time that a customer, either in queue or new to a queue, will endure 
before being able to begin receiving service The present invention also 
finds application as a method and apparatus for predicting an estimated 
waiting-time before the customer will end service. In this embodiment, the 
system considers the service-time PDF of the customer himself, in addition 
to those customers already in service and those in queue ahead of the 
customer. If T.sub.i is the total time for customer i to complete service, 
then its PDF can be obtained from the two component PDF's by a convolution 
integral: 
##EQU13## 
The expected values are related simply by: 
EQU ET.sub.i =EW.sub.i +m.sub.i, (19) 
where m.sub.i is the expected value of the service-time PDF G.sub.i. 
The present invention described above generates a more precise and reliable 
estimate of queuing delays to be experienced by customers in a queue by 
estimating service times of customers in service and perhaps customers in 
queue based upon attributes known for each customer. From the estimated 
service times, a prediction of a waiting time for a certain customer may 
be made. The prediction also provides benefits to queue administrators who 
may allocate additional or fewer agents to meet changing demand.