System for regulating arrivals of customers to servers

• US 4,858,120 A
• Filed: 03/18/1987
• Issued: 08/15/1989
• Est. Priority Date: 03/18/1987
• Status: Expired due to Term

• Current Assignee: SER Solutions Incorporated (Atos SE)
• Original Assignee: International Telesystems Corp (Electronic Information Systems, Inc.)
• Inventors: Samuelson, Douglas A.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/027,359
• Time in Patent Office: 881 Days
• Field of Search: 340/286 R, 379/113, 379/266, 379/309, 379/92, 379/69, 364/401, 364/436
• US Class Current: 705/7.25
• 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/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/109 Time management, e.g. calendars, reminders, meetings or time accounting
• CPC Class Codes: G06Q 10/1091 Recording time for administrative or management purposes
• CPC Class Codes: G07C 11/00 Arrangements, systems or apparatus for checking, e.g. the occurrence of a condition, not provided for elsewhere
• CPC Class Codes: G07C 2011/04 related to queuing systems
• CPC Class Codes: H04M 3/36 Statistical metering, e.g. recording occasions when traffic exceeds capacity of trunks
• CPC Class Codes: H04M 3/523 with call distribution or queueing
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor
• CPC Class Codes: Y10S 379/904 Auto-calling

Abstract

A method for controlling arrivals to servers, comprising: regulating arrivals, by initiating a processor generating arrivals or by re-routing or turning away arrivals; measuring durations of service; computing and updating time statistics, including mean, minimum, maximum expected and standard deviation of duration of service thereby estimating expected duration of service; measuring transit times from the point of regulating arrivals to start of service and thereby estimating expected transit times; measuring a ratio of numbers of service initiations to numbers of arrivals at the point of regulating arrivals; recording starting time of each current service; noting present time; comparing present time to starting time, and thereby determining time in progress for each service; comparing time in progress to expected duration of service, and estimating time remaining in service for each customer currently in service; comparing estimated time remaining in service to estimated transit time from the point of regulating arrivals to the start of service, determining a number of currently busy servers expected to be available by the time another arrival could reach them; measuring the number of available servers not currently serving; adding the number of currently available servers and the number of currently busy servers expected to be available and thereby computing total number of servers expected to be available; subtracting the number of arrivals currently queued awaiting service thereby producing a resultant number of servers expected to be available; and controlling a means for regulating arrivals to correspond to the resultant number of servers expected to be available.

Claims

1. A method for controlling arrivals of customers to servers wherein customers are queued to await service by said servers, comprising the steps of:

measuring durations of customer service;

computing and updating time statistics of services to customers, thereby estimating expected duration of customer service;

recording starting time of each current customer service and noting present time;

comparing present time to starting time, and thereby determining time in progress for each customer service;

comparing time in progress to expected duration of service, and estimating time remaining in service for each customer currently in service;

determining a number of currently busy servers expected to be available by the time another customer arrival could reach the currently busy servers;

measuring the number of available servers not currently serving a customer;

adding the number of currently available servers and the number of currently busy servers expected to be available, thereby computing total number of servers expected to be available;

subtracting the number of customer arrivals currently queued awaiting service thereby producing a resultant number of servers expected to be available; and

controlling a processor which regulates customer arrivals to correspond to the resultant number of servers expected to be available.

2. The method of claim 1, further comprising the steps of:

measuring a ratio of number of service initiations to numbers of customer arrivals;

calculating the number of service initiations by dividing the total number of servers expected to be available by said ratio during a selected time interval of recent operation.

3. The method of claim 2, wherein the step of calculating comprises the steps of:

computing a weighted average of the total number of servers expected to be available; and

calculating with that weighted average the number of arrivals being initiated by the processor which regulates customer arrivals.

4. The method of claim 1, wherein the step of computing and updating time statistics comprises the steps of:

classifying service times as short or long;

measuring mean, minimum, and maximum of short service times; and

measuring mean, minimum, and maximum of long service times.

5. The method of claim 4, wherein the comparing of time in progress to the expected duration of service comprises comparing the time in progress to a measured minimum time of service during a selected recent time interval of operation.

6. The method of claim 4, wherein the comparing of time in progress to the expected duration of service comprises comparing the time in progress to a measured maximum time of service during a selected recent time interval of operation.

7. The method of claim 4 wherein the comparing of time in progress to the expected duration of service comprises comparing the time in progress to a measured mean (average) of times of service during a selected recent time interval of operation.

8. The method of claim 4 wherein the step of comparing time in progress to expected duration of service comprises the steps of:

computing an estimated boundary between long and short services;

classifying services which have been in progress longer than said estimated boundary as long services, and classifying other services in progress as short services; and

using the estimated duration of long services as the expected duration of service for services currently in progress which are classified as long services, and using the estimated duration of short services as the expected duration of service for services currently in progress which are classified as short services.

9. The method of claim 8 wherein the step of computing an estimated boundary further comprises calculating a weighted average of the means of the short and long service times and using the weighted average as the estimated boundary between long and short service times.

10. The method of claim 8 wherein the step of computing the estimated boundary further comprises calculating a weighted average of the maximum duration of short services and the minimum duration of long services and using said weighted average as the estimated boundary between long and short services.

11. The method of claim 8 wherein the step of computing the estimated boundary further comprises using the mean duration of short services plus s standard deviations of the durations of short services as the estimated boundary between long and short service times, where s is any positive number.

12. The method of claim 8 wherein the step of computing the estimated boundary further comprises using the mean duration of long services minus t standard deviations of the durations of long services as the estimated boundary between long and short service times, where t is any positive number.

13. The method of claim 4 wherein the step of classifying comprises the steps of:

using the measured mean of the short service times as an estimated duration of short services; and

using the measured mean of the long service times as an estimated duration of long services.

14. The method of claim 4 wherein the step of classifying comprises using the minimum duration of short services as the estimated duration of short services.

15. The method of claim 4 wherein the step of classifying comprises using the maximum duration of short services as the estimated duration of short services.

16. The method of claim 1, wherein customers may return to servers for subsequent stages of service, further comprising counting the number of customers having completed service but available (still within the system) to return to a subsequent stage of service, and subtracting the number of customers having completed service but expected to return to a subsequent stage of service from the total number of servers expected to be available, to regulate arrivals so as to ensure availability of servers for customers returning to service.

17. The method of claim 16, further comprising computing the estimated proportion of customers having completed one stage of service who are expected to return for subsequent service, and subtracting said estimated proportion, rather than the total number of customers having completed service and available to return to a subsequent stage of service, from the total number of servers expected to be available, to regulate arrivals.

18. The method of claim 1, further adjusting automatically to provide a specified proportion, q, of arrivals for which no server is available, comprising the steps of:

computing a quantile such that the proportion qn of service times less than said quantile is equal to the pre-selected proportion q; and

using the said quantile as the estimate of duration of service.

19. The method of claim 18, further iteratively adjusting expected duration of service, d, to maintain a pre-selected proportion q of arrivals for which no server is available, comprising the steps of:

using a statistic of service times as an initial estimate, d=d₁, of the duration of service;

decreasing d to d₂ =0.9d₁ if the resulting proportion q₁ of arrivals for which no server is available is higher than q;

increasing d to d₂ =1.1d₁ if the resulting proportion of arrivals q₁ for which no server is available is lower than q, and

computing d_n p₁ =d_n +(q-q_n)(d_n -d_n m₁)/(q_n -q_n m₁) at each step where d_n p₁ is the new calculated d, d_n is the most recently used estimate of d, d_n m₁ is the next most recently used estimate of d, q_n is the proportion of arrivals for which no server was available when d_n was used as the estimate of d, and q_n m₁ is the proportion of arrivals for which no server was available when d_n m₁ was used as the estimate of d.

20. The method of claim 1 wherein the step of determining a number of currently busy servers expected to be available comprises the steps of:

measuring times from the point of initiating arrivals to start of service and thereby estimating expected transit times; and

comparing said transit times to estimated time remaining in service for the currently busy servers.