System and method for scheduling service providers to perform customer service requests

• US 5,615,121 A
• Filed: 01/31/1995
• Issued: 03/25/1997
• Est. Priority Date: 01/31/1995
• Status: Expired due to Term

• Current Assignee: Qwest Communications International Incorporated (Lumen Technologies, Inc.)
• Original Assignee: US West Technologies, Inc.
• Inventors: Berger, Richard M., Dean, Vincil C., Parrish, Scott H., Hansen, Ronald L., Babayev, Djangir A.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): BROWN, THOMAS
• Application Number:
  US08/381,657
• Time in Patent Office: 784 Days
• Field of Search: 364/401-403, 364/468, 364/406, 395/912, 395/925, 395/926
• US Class Current: 705/7.22
• 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/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

A scheduling system is disclosed for scheduling tasks for fulfilling a series of service requests. When each service request is received, a determination is made as to the amount of resources a task requires to provide the requested service. Further, a preferred time within which to perform the task is obtained from the requestor of the service request. For each service request, data for the estimated amount of resources and the preferred time are supplied, on a first-come-first-serve basis, to a scheduling component for solving a combinatorial optimization model which efficiently allocates a predetermined amount of resources for each time slot in a scheduling period by rearranging tasks for service requests previously received. The scheduling component provides for a service requestor, without regard to subsequently received service requests, a service time in which to perform the task for the requested service substantially immediately after the service request is made. Whenever possible, the service time coincides with the preferred time. Each previously received service request will have its related task performed within the service time provided to the requestor of the service request. The scheduling system is particularly useful in scheduling technician time for service calls received by customer representatives in the telecommunication and utility industries.

Claims

1. A method for scheduling a predetermined plurality of resources, comprising the steps of:

receiving a plurality of requests for services requiring at least some of said predetermined plurality of resources, said plurality of requests including a first request and a second request;

establishing a schedule for said plurality of requests, comprising the step of performing steps (A1)-(A4) for at least one of the first and second request;

(A1) obtaining information related to the request, said information including (a) a preferred time interval for performing a task related to the request for providing a requested service and (b) an estimate related to an amount of said predetermined plurality of resources for performing the task related to the request, wherein said preferred time interval is longer than a time estimated to perform said task associated with the revest;

(A2) determining an actual time interval within which to allocate said estimated amount of resources for performing the task, said actual time interval being determined using said preferred time interval as input for solving a combinatorial optimization model, wherein said actual time interval is longer than said time estimated to perform said task associated with the request;

(A3) outputting a message indicating the actual time interval determined in step (A2), wherein said message is output substantially immediately after receiving the request; and

(A4) retaining said actual time interval for the request as part of said schedule, said actual time interval providing scheduling flexibility in that said task associated with the request may be commenced at more than one time within said actual time interval and yet still be completed within said actual time interval.

2. A method as claimed in claim 1, wherein said predetermined plurality of resources includes an amount of time for each of a plurality of service providers.

3. A method as claimed in claim 2, wherein said estimate related to an amount of said predetermined resources to perform a task includes an amount of time for a service provider of said plurality of service providers to perform the task.

4. A method as claimed in claim 1, wherein said step of obtaining includes soliciting said preferred time interval from a customer supplying the request.

5. A method as claimed in claim 1, wherein for each said request of said plurality of requests, each said actual time interval includes an integral number of time slots in a discrete series of predetermined time slots.

6. A method as claimed in claim 1, further including a step of providing a first starting time for commencing a first task related to the first request and a second starting time for commencing a second task related to the second request wherein said first and second tasks are to be performed within their respective actual time intervals;

and

wherein, when said time intervals for the first and second tasks overlap, said first and second tasks are to be performed without an overlap when the actual time interval overlap requires more of said predetermined plurality of resources than are available.

7. A method as claimed in claim 6, wherein said step of providing includes using a predetermined function to be optimized and a predetermined set of constraints to be satisfied when said function is optimized.

8. A method as claimed in claim 7, wherein said predetermined function relates to a work load measurement for a plurality of service providers.

9. A method as claimed in claim 7, wherein said set of constraints provides for a single starting time for a task related to a request.

10. A method as claimed in claim 8, wherein said set of constraints includes, for a predetermined time slot, a constraint relating a number of said service providers available for task assignment in said predetermined time slot to a sum of:

(a) a number of allocated service providers for said predetermined time slot and (b) a number of unallocated service providers for said predetermined time slot.

11. A method as claimed in claim 7, wherein said step of providing includes solving a combinatorial optimization model for a feasible allocation of said predetermined plurality of resources, said predetermined function and said predetermined set of constraints included in said combinatorial optimization model.

12. A method as claimed in claim 6, wherein said step of providing includes shifting a current or proposed starting time for said first task when:

(a) said actual time interval for the first request is longer than a time to perform said first task;

(b) there is a time slot where said first and second tasks overlap if said first task commences at said current starting time for said first task and said second task commences at said second starting time; and

(c) there are insufficient resources in said time slot to allocate resources to both said first and second tasks.

13. A method as claimed in claim 6, wherein said step of providing includes shifting a current or proposed starting time for said second task when:

(a) said actual time interval for the second request is longer than a time to perform said second task;

(b) there is a time slot where said first and second tasks overlap if said first task commences at said first starting time for said first task and said second task commences at said current starting time for said second task; and

(c) there are insufficient resources for said time slot to allocate resources to both said first and second tasks.

14. A method as claimed in claim 6, wherein each of said first and second tasks are performed in a same predetermined scheduling period.

15. A method as claimed in claim 1, wherein said actual time interval is one or more days in length.

16. A method as claimed in claim 1, wherein said step of determining includes solving a combinatorial optimization model for determining said time actual interval.

17. A method as claimed in claim 1, wherein said step of determining includes determining a current starting time for the task such that the task is performed in said preferred time interval for the request when commenced at said current starting time.

18. An apparatus for scheduling a plurality of tasks, comprising:

input means for inputting, for each service request of a series of service requests, request data related to the service request, said request data including a preferred time for commencing a task related to the service request, said task requiring a predetermined amount of resources from a predetermined plurality of resources;

means for determining, for each service request of the series of service requests, a service time to perform the related task, said means for determining including a means for solving a combinatorial optimization model for said service time when said input means supplies said request data related to the service request, wherein said service time determined for each of the service requests is determined before said request data related to a next service request of the series of service requests is supplied, wherein said means for solving includes means for determining an extreme value for a predetermined objective function of said combinatorial optimization model, wherein said extreme value satisfies a predetermined plurality of constraints of said combinatorial optimization model;

output means for outputting, for each service request of the series of service requests, information indicating said service time for the service request;

wherein, for each of the service requests, said service time for the service request is substantially identical to said preferred time for commencing the task related to the service request when said predetermined amount of resources required by the task is determined to be available for a consistent solution of said combinatorial optimization model.

19. An apparatus as claimed in claim 18, wherein each said service request is a request for a telecommunication service.

20. An apparatus as claimed in claim 18, wherein said request data for substantially all of the service requests includes an estimated amount of resources of said predetermined plurality of resources to perform the task related to the service request.

21. An apparatus as claimed in claim 18, wherein said input means includes a data entry device used by a customer service representative to input said request data for a service request from the series of service requests.

22. An apparatus as claimed in claim 18, wherein said predetermined plurality of resources includes resources forecasted for each of a predetermined number of time slots for a scheduling period.

23. An apparatus as claimed in claim 22, wherein said plurality of constraints includes constraints providing:

(a) for each of the service requests whose service time has been determined, there is exactly one starting time for the task related to the service request, and (b) for each time slot having forecasted resources, a maximal number of said resources allocated to tasks related to the service requests in the time slot does not exceed the forecasted resources for the time slot.

24. An apparatus as claimed in claim 22, wherein said predetermined objective function is a function of a number of unallocated resources for the predetermined number of time slots in the scheduling period.

25. An apparatus as claimed in claim 18, wherein said predetermined objective function is a function of a weighted sum of a plurality of parameter values, each parameter value related to a time for performing a task for a service request of said series of service requests.

26. An apparatus as claimed in claim 18, wherein said means for determining includes storage means for storing first data related to said predetermined amount of said resources for performing the task related to a first service request of the series of service requests wherein said service time has been determined for said first service request, wherein said first data is used by said means for determining in determining a service time for a second service request later in said series of said service requests than said first service request.

27. An apparatus as claimed in claim 18, wherein said means for determining includes storage means for storing current data related to said service time for a first service request of the series of service requests wherein said service time for said first service request has been determined, said current data used by said means for determining in determining a service time for a second service request later in said series of service requests than said first service request.

28. An apparatus as claimed in claim 27, wherein said means for determining includes means for changing said current data when:

(a) said preferred time for said first service request includes a first time interval larger than an amount of time to perform the task related to said first service request, and (b) said preferred time for said second service request includes a second time interval overlapping said first time interval.

29. An apparatus as claimed in claim 27, wherein said means for determining includes means for reallocating resources of said predetermined plurality of resources so that resources allocated to the task related to said first service request are reallocated to the task related to said second service request when:

(a) said preferred time for said first service request is longer than an estimated amount of time to perform the related task, and (b) said preferred times for said first and second service requests overlap in a time slot having insufficient unallocated resources to perform the tasks for said first and second service requests concurrently.

30. A method for scheduling customer service requests for a predetermined time period, comprising the steps of:

receiving a service request from a customer;

identifying a first time interval within said predetermined time period for performing said service request, wherein said first time interval is longer than an estimated service time to perform said service request;

generating a schedule for said predetermined time period utilizing said first time interval, said schedule comprising a second time interval for performing said service request, wherein said second time interval is longer than said estimated service time required to perform said service request;

storing said second time interval;

communicating said second time interval to said customer, wherein said storing step maintains said second time interval in a fixed condition for said service request such that said service request will be performed during said second time interval and further to alleviate a need to recontact said customer based upon one or more subsequent receiving steps;

determining a current starting time within said second time interval to commence performing said service request and which will allow for completion of said service request within said second time interval; and

repeating said identifying, generating, storing, communicating and determining steps for one or more subsequent executions of said receiving step associated with said predetermined time period;

wherein for each execution of said repeating step, said generating step regenerates said schedule for said predetermined time period by modifying said current starting time for at least one previously received service request, wherein said current starting time will still be within said second time interval for the previously received service request and will still allow for completion of said service request within the associated second time interval.

31. A method, as claimed in claim 30, wherein said first time interval and an associated said second time interval are the same.

32. A method, as claimed in claim 30, wherein said first time interval and an associated said second time interval are overlapping.

33. A method, as claimed in claim 30, wherein said first time interval and an associated said second time interval are different.

34. A method, as claimed in claim 30, wherein a service time required to perform said service request is less than said first time interval.

35. A method, as claimed in claim 30, wherein a service time required to perform said service request is equal to said first time interval, and wherein an associated said second time interval from said generating step is the same as said first time interval.

36. A method for scheduling a predetermined plurality of resources, comprising:

receiving a plurality of requests for services requiring some of said predetermined plurality of resources, said plurality of requests including a first request and a second request;

performing steps (A1)-(A3) for each of the first and second request, said performing for the first request completed before commencing said performing for the second request;

(A1) obtaining information related to the request, said information including (a) a preferred time interval for performing a task related to the request for providing a requested service and (b) an estimate related to an amount of said predetermined plurality of resources for performing the task related to the request;

(A2) determining a time interval within which to allocate said estimated amount of resources for performing the task, said time interval being determined using said preferred time interval as input for solving a combinatorial optimization model;

(A3) outputting a message indicating the time interval determined in step (A2), said message is output substantially immediately after receiving the request;

providing a first starting time for commencing a first task related to the first request and a second starting time for commencing a second task related to the second request wherein said first and second tasks are to be performed within their respective time intervals; and

wherein, when said time intervals for the first and second tasks overlap, said first and second tasks are to be performed without an overlap when the time interval overlap requires more of said predetermined plurality of resources than are available.

37. A method as claimed in claim 36, wherein said step of providing includes using a predetermined function to be optimized and a predetermined set of constraints to be satisfied when said function is optimized.

38. A method as claimed in claim 37, wherein said predetermined function relates to a work load measurement for a plurality of service providers.

39. A method as claimed in claim 37, wherein said set of constraints provides for a single starting time for a task related to a request.

40. A method as claimed in claim 38, wherein said set of constraints includes, for a predetermined time slot, a constraint relating a number of said service providers available for task assignment in said predetermined time slot to a sum of:

(a) a number of allocated service providers for said predetermined time slot and (b) a number of unallocated service providers for said predetermined time slot.

41. A method as claimed in claim 37, wherein said step of providing includes solving a combinatorial optimization model for a feasible allocation of said predetermined plurality of resources, said predetermined function and said predetermined set of constraints included in said combinatorial optimization model.

42. A method as claimed in claim 36, wherein said step of providing includes shifting a current or proposed starting time for said first task when:

(a) said time interval for the first request is longer than a time to perform said first task;

(b) there is a time slot where said first and second tasks overlap if said first task commences at said current starting time for said first task and said second task commences at said second starting time; and

(c) there are insufficient resources in said time slot to allocate resources to both said first and second tasks.

43. A method as claimed in claim 36, wherein said step of providing includes shifting a current or proposed starting time for said second task when:

(a) said time interval for the second request is longer than a time to perform said second task;

(b) there is a time slot where said first and second tasks overlap if said first task commences at said first starting time for said first task and said second task commences at said current starting time for said second task; and

(c) there are insufficient resources for said time slot to allocate resources to both said first and second tasks.

44. A method as claimed in claim 36, wherein each of said first and second tasks are performed in a same predetermined scheduling period.

45. An apparatus for scheduling a plurality of tasks, comprising:

input means for inputting, for each service request of a series of service requests, request data related to the service request, said request data including a preferred time for commencing a task related to the service request, said task requiring a predetermined amount of resources from a predetermined plurality of resources;

means for determining, for each service request of the series of service requests, a service time to perform the related task, said means for determining including a means for solving a combinatorial optimization model for said service time when said input means supplies said request data related to the service request, wherein said service time determined for each of the service requests is determined before said request data related to a next service request of the series of service requests is supplied, wherein said means for determining includes storage means for storing first data related to said predetermined amount of said resources for performing the task related to a first service request of the series of service requests wherein said service time has been determined for said first service request, wherein said first data is used by said means for determining in determining a service time for a second service request later in said series of said service requests than said first service request;

output means for outputting, for each service request of the series of service requests, information indicating said service time for the service request;

wherein, for each of the service requests, said service time for the service request is substantially identical to said preferred time for commencing the task related to the service request when said predetermined amount of resources required by the task is determined to be available for a consistent solution of said combinatorial optimization model.

46. An apparatus for scheduling a plurality of tasks, comprising:

input means for inputting, for each service request of a series of service requests, request data related to the service request, said request data including a preferred time for commencing a task related to the service request, said task requiring a predetermined amount of resources from a predetermined plurality of resources;

means for determining, for each service request of the series of service requests, a service time to perform the related task, said means for determining including a means for solving a combinatorial optimization model for said service time when said input means supplies said request data related to the service request, wherein said service time determined for each of the service requests is determined before said request data related to a next service request of the series of service requests is supplied, wherein said means for determining includes storage means for storing current data related to said service time for a first service request of the series of service requests wherein said service time for said first service request has been determined, said current data used by said means for determining in determining a service time for a second service request later in said series of service requests than said first service request;

output means for outputting, for each service request of the series of service requests, information indicating said service time for the service request;

wherein, for each of the service requests, said service time for the service request is substantially identical to said preferred time for commencing the task related to the service request when said predetermined amount of resources required by the task is determined to be available for a consistent solution of said combinatorial optimization model.

47. An apparatus as claimed in claim 46, wherein said means for determining includes means for changing said current data when:

(a) said preferred time for said first service request includes a first time interval larger than an amount of time to perform the task related to said first service request, and (b) said preferred time for said second service request includes a second time interval overlapping said first time interval.

48. An apparatus as claimed in claim 46, wherein said means for determining includes means for reallocating resources of said predetermined plurality of resources so that resources allocated to the task related to said first service request are reallocated to the task related to said second service request when:

(a) said preferred time for said first service request is longer than an estimated amount of time to perform the related task, and (b) said preferred times for said first and second service requests overlap in a time slot having insufficient unallocated resources to perform the tasks for said first and second service requests concurrently.