Method and apparatus for predicting queuing delays

• US 6,023,681 A
• Filed: 08/11/1997
• Issued: 02/08/2000
• Est. Priority Date: 08/11/1997
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Whitt, Ward
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US08/908,042
• Time in Patent Office: 911 Days
• Field of Search: 705/8, 705/9, 395/200.32, 395/200.57
• US Class Current: 705/7.29
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: H04M 3/523 with call distribution or queueing
• CPC Class Codes: H04M 3/5238 with waiting time or load prediction arrangements

Abstract

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.

Claims

1. A method of predicting a waiting time for a customer in a queue, comprising the steps of:

for each of a number of customers in service and ahead of the customer;

classifying the customer in service according to an attribute known for the customer in service, and generating, based on the attribute of the customer in service, an estimate for the customer representing a time that the customer will terminate service;

for each of a number of customers ahead of the customer in queue;

classifying the customer ahead in queue according to an attribute known for the customer ahead in queue, and

generating, based on the attribute of the customer ahead in queue, an estimate for the customer ahead in queue representing a time that the customer ahead in queue will terminate service; and

predicting, based on the estimates generated for the customer in service and ahead in queue, an estimated waiting time for the customer in queue representing a time that the customer in queue will wait before service.

2. The method of claim 1, wherein the estimate of the first generating step for at least one customer in service is a probability over time that the customer will terminate service by that time.

3. The method of claim 1, wherein an estimate of the second generating step for at least one customer ahead in queue is a probability over time that the customer ahead in queue will terminate service by that time.

4. The method of claim 1, wherein the estimate generated for at least one customer in service is a probability distribution function.

5. The method of claim 4, wherein the probability distribution function of the at least one customer in service is based on an estimated mean time of service for the customer.

6. The method of claim 1, wherein the estimate generated for at least one customer ahead in queue is a probability distribution function.

7. The method of claim 6, wherein the probability distribution function of the at least one customer ahead in queue is based on an estimated mean time of service for the customer.

8. The method of claim 1, wherein the customer in queue is new to the queue.

9. The method of claim 1, wherein the attribute known for at least one customer in service is the time elapsed for the one customer since the one customer first began to receive service.

10. The method of claim 7, wherein the estimate generated for the one customer is a conditional probability distribution function representing a probability over time when the one customer will terminate service given the elapsed time for the one customer.

11. The method of claim 1, wherein the attribute known for at least one customer in service is the identity of an agent serving the one customer.

12. The method of claim 1, wherein the attribute known for at least one customer in service is an upper limit service time for the one customer.

13. The method of claim 1, wherein the attribute known for at least one customer in queue is an upper limit service time for the one customer.

14. The method of claim 1, wherein the attribute known for at least one customer in service is an identifier of the one customer.

15. The method of claim 1, wherein the attribute known for at least one customer in queue is an identifier of the one customer.

16. The method of claim 1, wherein the attribute known for at least one customer in service is conduct of the one customer.

17. The method of claim 1, wherein the estimated waiting time is the time before beginning service.

18. The method of claim 1, wherein the estimated waiting time is a time before concluding service.

19. The method of claim 1, wherein the generating step includes a step of predicting a time when the customer in queue will begin to receive service.

20. The method of claim 1, wherein the estimate generated for at least one customer in queue is based on the predicted time when the one customer will begin to receive service.

21. The method of claim 1, wherein the predicted waiting time is an estimated probability distribution function.

22. The method claim 21, further comprising a step of communicating the estimated probability distribution function to the new customer.

23. The method of claim 21, further comprising a step of communicating a predetermined approximation of the estimated probability distribution function to the new customer.

24. The method of claim 21, further comprising a step of communicating the estimated probability distribution function to a system administrator.

25. The method of claim 21, further comprising a step of budgeting resources based on the estimated probability distribution function.

26. The method of claim 1, further comprising a step of communicating the estimated waiting time to the customer in queue.

27. A method of predicting a wait time for a customer in queue to receive service from a system, comprising the steps of:

classifying each of a plurality of customers in service according to an attribute known for the customer in service,

generating for each customer in service, based on the attribute known for the customer in service, a probability distribution function for the customer representing a probability over time that the customer will terminate service;

predicting, based on the probability distribution functions of the customers in service, a rate of service for the system, and

predicting a wait time for the customer in queue based on the rate of service.

28. The method of claim 27, wherein a number of customers in service exceeds a number of customers in queue.

29. The method of claim 27, wherein the customer in queue is first in queue.

30. The method of claim 27, wherein the probability distribution function of at least one customer in service is based upon a mean of a remaining service time of the respective customer.

31. A method of predicting a wait time for a customer new to a queue, comprising the steps of:

classifying each of a plurality of customers in queue according to an attribute known for the customer in queue,

generating, based on the attribute of the customer in queue, a mean approximating a probability distribution over time that the customer will terminate service, and

predicting, based on the means for each customer in queue, an estimated waiting time for the new customer.

32. The method of claim 31, wherein each customer in queue will not receive service until one of a plurality of customers in service terminate service, and

a number of customers in queue is much greater than a number of customers in service.

33. In a system comprising a plurality of agents and a queue, an apparatus for predicting a wait time for a customer in the queue, comprising:

a processor in communication with each of the agents for monitoring activity of customers in communication with the agents, said processor also in communication with the queue, wherein for each of the agents, the processor generates a probability function representing a probability over time when the customer in communication with the agent will conclude service, wherein the processor further estimates a wait time based on the probability functions, and

communication means for communicating the estimated wait time to the new customers.

34. The system of claim 33, wherein the processor generates the probability function based on monitored activity of the customer in service.

35. The system of claim 33, wherein the processor estimates a probability distribution of the wait time.

36. The system of claim 35, wherein the processor estimates a mean wait time.

37. The system of claim 35, wherein the processor estimates a predetermined percentile of the wait time.

38. In a system comprising a plurality of agents and a queue, an apparatus for predicting a wait time for a certain customer in queue, comprising:

a processor in communication with each of the agents for monitoring activity of customers in communication with the agents, said processor also in communication with the queue,

wherein, for each of the agents, the processor generates a first probability function representing a probability over time when the agent will conclude service,

wherein, for each of a plurality of customers in queue, the processor generates a second probability function representing a probability over time when the queuing customer will conclude service;

wherein the processor estimates a wait time based on the probability functions, and

a communicator that communicates the estimated wait time to the certain customer in queue.

39. The apparatus of claim 38, wherein upon arrival of the certain customer, the processor estimates a wait time for each customer ahead in queue and the communication means communicates the wait times to the respective customer ahead in queue.

40. A method of predicting a wait time for a certain customer in a queue, comprising steps of:

for each of a plurality of customers in service and in queue;

classifying the customer based on at least one attribute of the customer, and

based upon the at least one attribute, generating a probability distribution function representing a probability over time when the customer will conclude service; and

estimating a wait time for the certain customer based on the probability distribution functions for the customers in service and in queue.

41. A method of predicting a wait time for a first customer in queue, comprising steps of:

for each of a plurality of customers in service;

classifying the customer based on at least one attribute, and

based on the attributes, generating an estimated service time when the customer in service will conclude service; and

estimating a wait time for the first customer based on the estimated service time.

42. A method of predicting a wait time for a customer in a queue when a number of customers in queue greatly exceeds a number of customers in service, the method comprising steps of:

classifying each customer in queue ahead of the customer in queue based on at least one attribute,

for each customer ahead in queue, generating an estimated time before the respective customer will complete service, based on the attribute of classification, and, complete service, based on the attribute of classification, and,

predicting a wait time for the customer in queue based on the estimates generated for the customers ahead in queue.

43. A method of allocating a number of agents in a service system, the system including a plurality of agents and a queue comprising the method steps of:

monitoring the agents, each agent serving a customer, to estimate a time when the agent will conclude service of its customer,

for each of a plurality of customers in the queue,

classify the customer in queue based on at least one attribute,

generating an estimated service time for the customer in queue based on the classification,

predicting an estimated wait time before the last customer in queue will wait before receiving service based on the estimated service times,

determining when the estimated wait time exceeds a predetermined wait time, and

when the estimated wait time exceeds the predetermined wait time, increasing the number of agents.