Resource assignment and scheduling system

• US 5,943,652 A
• Filed: 04/18/1997
• Issued: 08/24/1999
• Est. Priority Date: 02/25/1994
• Status: Expired due to Fees

• Current Assignee: 3M Innovative Properties Company (3M Company)
• Original Assignee: 3M Innovative Properties Company (3M Company)
• Inventors: Collins, John E., Sisley, Elizabeth M.
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/844,087
• Time in Patent Office: 858 Days
• Field of Search: 364/468.05, 364/468.06, 395/670, 395/672, 395/674, 705/8, 705/9
• 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/063116 Schedule adjustment for a person or group
• 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: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/1097 Task assignment

Abstract

A system and method for assigning and scheduling resource requests to resource providers use a modified "best-first" search technique that combines optimization, artificial intelligence, and constraint-processing to arrive at near-optimal assignment and scheduling solutions. In response to changes in a dynamic resource environment, potential changes to an existing assignment set are evaluated in a search for a better solution. New calls are assigned and scheduled as they are received, and the assignment set is readjusted as the field service environment changes, resulting in global optimization. Each search operation is in response to either an incremental change to the assignment set such as adding a new resource request, removing a pending resource request, reassigning a pending resource request, or to a request for further evaluation. Thus, the search technique assumes that the existing assignment set is already optimized, and limits the task only to evaluating the effects of the incremental change. In addition, each search operation produces a complete assignment and scheduling solution. Consequently, the search can be terminated to accept the best solution generated so far, making the technique an "anytime" search.

Claims

1. A computer-implemented system for assigning a plurality of resource requests among a plurality of resource providers, the plurality of resource requests including a plurality of pending resource requests assigned among the resource providers according to an existing assignment set, wherein the existing assignment set defines a root node of a search tree, the computer-implemented system being programmed to execute a plurality of steps including the steps of:

(a) expanding the root node by forming one or more next-level nodes, each of the next-level nodes corresponding to the root node but being further defined by a reassignment of one of the pending resource requests between one of the resource providers and another of the resource providers;

(b) estimating, for each of the next-level nodes, a stress value representing a degree of undesirability of the respective reassignment; and

(c) generating a new assignment set corresponding to one of the next-level nodes having a minimum stress value.

2. The computer-implemented system of claim 1, wherein each of the pending resource requests is a field service call, and each of the resource providers is a field service technician.

3. The computer-implemented system of claim 1, wherein the plurality of resource requests includes an unassigned new resource request, and the step (a) includes the steps of:

(a)(i) expanding the root node by forming one or more first-level nodes, each of the first-level nodes corresponding to the root node but being further defined by an assignment of the new resource request to a selected one of the resource providers;

(a)(ii) estimating, for each of the first-level nodes, a stress value representing a degree of undesirability of the respective assignment; and

(a)(iii) expanding one or more of the first-level nodes by forming, for each of the first-level nodes, one or more of the next-level nodes, wherein each of the next-level nodes corresponds to the respective first-level node but is further defined by a reassignment of one of the pending resource requests between the selected one of the resource providers and another of the resource providers,

wherein the new assignment set corresponds to one of the first-level nodes and the next-level nodes having a minimum stress value.

4. The computer-implemented system of claim 3, wherein the step (a)(iii) comprises the steps of:

selecting one of the first-level nodes having a minimum stress value; and

expanding the selected one of the first-level nodes by forming one or more of the next-level nodes.

5. The computer-implemented system of claim 4, wherein the computer-implemented system is further programmed to execute the steps of:

(d) selecting one of the unexpanded first-level nodes and the unexpanded next-level nodes having a minimum stress value;

(e) expanding the selected one of the unexpanded first-level nodes and the unexpanded next-level nodes as a preceding-level node by forming one or more next-level nodes, each of the next-level nodes corresponding to the preceding-level node but being further defined by a reassignment of one of the pending resource requests between one of the resource providers and another of the resource providers; and

(f) estimating, for each of the next-level nodes formed by step (e), a stress value representing a degree of undesirability of the respective reassignment; and

(g) repeating the steps (d), (e), and (f) to expand one of the unexpanded first-level nodes and the unexpanded next-level nodes as a preceding-level node, thereby forming a succession of the next-level nodes,

wherein the new assignment set corresponds to one of the first-level nodes and the succession of the next-level nodes having a minimum stress value.

6. The computer-implemented system of claim 5, wherein the existing assignment set includes an existing schedule set, the existing schedule set including, for each of the resource providers, an existing schedule of the pending resource requests assigned to the respective resource provider, the computer-implemented system being further programmed to execute the steps of:

generating, for each of the first-level nodes, a schedule set corresponding to the existing schedule set but including a schedule of the new resource request and the pending resource requests assigned to the selected one of the resource providers; and

generating, for each of the next-level nodes, a schedule set corresponding to the schedule set for the respective preceding-level node but including schedules of the resource requests assigned and reassigned to the one and the another of the resource providers,

wherein the new assignment set includes the schedule set for the respective one of the first-level nodes and the next-level nodes having the minimum stress value.

7. The computer-implemented system of claim 6, wherein the step of generating a schedule set for each of the first-level nodes includes the steps of:

generating one or more potential schedules of the new resource request and the pending resource requests assigned to the selected one of the resource providers;

estimating, for each of the potential schedules, a schedule stress value representing a degree of undesirability of the respective potential schedule; and

selecting one of the potential schedules having a minimum schedule stress value as the schedule for the selected one of the resource providers.

8. The computer-implemented system of claim 7, wherein the step of generating a schedule set for each of the next-level nodes includes the steps of:

generating one or more potential schedules, the potential schedules including one or more first potential schedules of the resource requests assigned to the one of the resource providers, and one or more second potential schedules of the resource requests assigned to the another of the resource providers;

estimating, for each of the potential schedules, a schedule stress value representing a degree of undesirability of the respective potential schedule; and

selecting one of the first potential schedules having a first minimum schedule stress value as the schedule for the one of the resource providers, and one of the second potential schedules having a second minimum schedule stress value as the schedule for the another of the resource providers.

9. The computer-implemented system of claim 8, wherein, in the step (a)(ii), the stress value estimated for each of the first-level nodes includes a representation of the minimum schedule stress value for the respective first-level node, and, in the steps (b) and (f), the stress value estimated for each of the next-level nodes includes a representation of the first minimum schedule stress value and the second minimum schedule stress value for the respective next-level node.

10. The computer-implemented system of claim 9, the computer-implemented system being further programmed to execute the step of storing the schedule sets previously generated for the first-level nodes and the next-level nodes, wherein each of the steps of generating a schedule set for one of the first-level nodes and the next-level nodes includes the steps of:

before the step of generating the one or more potential schedules for a respective one of the resource providers, searching the stored schedule sets to locate a previous schedule for the resource requests to be schedule for the respective resource provider; and

if a previous schedule for the resource requests to be scheduled for the respective resource provider is located, selecting the previous schedule as the schedule for the respective resource provider.

11. The computer-implemented system of claim 7, wherein the step of generating the one or more potential schedules for each of the first-level nodes includes, before generating the potential schedules, the steps of:

estimating a worst acceptable schedule stress value;

estimating, for each of the first-level nodes, a minimum stress of insertion of the new resource request among the pending resource requests on the existing schedule for the selected technician; and

discarding each of the first-level nodes having a minimum stress of insertion that exceeds the worst acceptable schedule stress value.

12. The computer-implemented system of claim 8, wherein the step of generating the one or more first and second potential schedules for each of the next-level nodes includes, before generating the potential schedules, the steps of:

estimating a worst acceptable schedule stress value;

estimating, for each of the next-level nodes, a minimum stress of insertion of the pending resource request reassigned to one of the one and the another of the resource providers among the pending resource requests on the existing schedules for the respective one of the one and the another of the resource providers; and

discarding each of the next-level nodes having a minimum stress of insertion that exceeds the worst acceptable schedule stress value.

13. The computer-implemented system of claim 8, wherein each of the steps of generating one or more potential schedules for each of the first-level nodes and the next-level nodes includes the steps of:

designating, for each of the potential schedules, a critical set of the resource requests assigned to the respective resource provider;

scheduling one of the resource requests in the critical set earlier than the resource requests not in the critical set;

designating, after the scheduling of one of the resource requests in the critical set, a different critical set of the resources requests; and

scheduling one of the resource requests in the different critical set earlier than the resource requests not in the different critical set.

14. The computer-implemented system of claim 7, wherein each of the steps of estimating a schedule stress value includes estimating the degree of undesirability of the respective potential schedule based on at least one of a plurality of component schedule stress values associated with each of the resource requests on the respective potential schedule, the component stress values including a priority value of the respective resource request, an urgency value of the respective resource request, a queue time value representing a time interval elapsed between receipt of the respective resource request and a completion time of a preceding one of the resource requests on the respective potential schedule, a tardiness value representing a time interval between a promised start time for the respective resource request and an expected start time for the respective resource request, and a travel time value representing a time required by the resource provider to whom the respective resource request is assigned to travel to a location associated with the respective resource request.

15. The computer-implemented system of claim 5, the computer-implemented system being further programmed to execute the step of generating, for each of the resource requests, a list of the resource providers qualified to accept assignment of the respective resource request, the resource providers on the list being designated as candidate resource providers for the respective resource request, wherein, in the step (a)(i), the selected one of the resource providers is a selected one of the candidate resource providers for the new resource request, and, in the step (e), each of the one and the another of the resource providers is one of the candidate resource providers for the respective reassigned pending resource request.

16. The computer-implemented system of claim 15, wherein each of the candidate resource providers qualified to accept assignment of a respective one of the new and pending resource requests is associated with a resource level appropriate for the respective resource request.

17. The computer-implemented system of claim 16, wherein the new resource request and each of the pending resource requests is a field service call, and each of the resource providers is a field service technician.

18. The computer-implemented system of claim 15, wherein each of the candidate resource providers qualified to accept assignment of a respective one of the new and pending resource requests is associated with a territory appropriate for the respective resource request.

19. The computer-implemented system of claim 15, wherein the step (a)(i) of forming one or more of the next-level nodes further comprises the steps of:

(A) forming one or more out-expanded next-level nodes corresponding to the respective first-level node but being further defined by a reassignment of one of the pending resource requests from the selected one of the resource providers to another of the resource providers; and

(B) forming one or more in-expanded next-level nodes corresponding to the respective first-level node but being further defined by a reassignment of one of the pending resource requests to the selected one of the resource providers from another of the resource providers.

20. The computer-implemented system of claim 5, the computer-implemented system being further programmed to execute the step of terminating the repetition of the steps (d), (e), and (f) when none of the unexpanded first-level nodes and the unexpanded next-level nodes has a stress value less than a stress threshold.

21. The computer-implemented system of claim 20, wherein the stress threshold is a sum of a minimum stress value of the stress values for the first-level nodes and the next-level nodes and a stress margin, the stress threshold being recalculated with each repetition of the step (f).

22. The computer-implemented system of claim 21, wherein the new resource request and each of the pending resource requests is a field service call, and each of the resource providers is a field service technician.

23. The computer-implemented system of claim 5, the computer-implemented system being further programmed to execute the step of terminating the repetition of the steps (d), (e), and (f) when a number of levels formed of the next-level nodes exceeds a depth limit.

24. The computer-implemented system of claim 5, the computer-implemented system being further programmed to execute the step of terminating the repetition of the steps (d), (e), and (f) when a number of the first-level nodes and the next-level nodes exceeds a node-count limit.

25. The computer-implemented system of claim 5, the computer-implemented system being further programmed to execute the step of terminating the repetition of the steps (d), (e), and (f) when elapsed time during formation of the first-level nodes and the next-level nodes exceeds a time limit.

26. The computer-implemented system of claim 5, wherein the step (a)(ii) of estimating a stress value includes estimating the degree of undesirability of the respective assignment based on at least one of a plurality of component stress values associated with the respective assignment.

27. The computer-implemented system of claim 26, wherein the plurality of component stress values includes:

a commitment stress value, the commitment stress value being a low value if assignment of the respective new resource request is not committed to one of the resource providers or if assignment of the respective new resource request is committed to the resource provider to whom the respective new resource request is assigned, and the commitment stress value otherwise being higher than the low value;

a primary resource provider stress value, the primary resource provider stress value being a low value if none of the resource providers is designated as a primary resource provider for the respective new resource request or if the respective new resource request is assigned to one of the resource providers designated as the primary resource provider for the respective new resource request, and the primary resource provider stress value otherwise being higher than the low value; and

a territory stress value, the territory stress value being a low value if a location associated with the respective new resource request is within an acceptable travel time of a territory of the resource provider to whom the respective new resource request is assigned, and the territory stress value otherwise being higher than the low value.

28. The computer-implemented system of claim 27, wherein the new resource request and each of the pending resource requests is a field service call, and each of the resource providers is a field service technician.

29. The computer-implemented system of claim 26, wherein the plurality of component stress values includes:

a resource stress value representing a number of resources for which the resource provider, to whom the respective new resource request is assigned, is qualified to provide.

30. The computer-implemented system of claim 5, wherein each of the steps (b) and (f) of estimating a stress value includes estimating the degree of undesirability of the respective reassignment based on at least one of a plurality of component stress values associated with the respective reassignment.

31. The computer-implemented system of claim 30, wherein the plurality of component stress values includes:

a commitment stress value, the commitment stress value being a low value if assignment of the respective pending resource request is not committed to one of the resource providers or if assignment of the respective pending resource request is committed to the resource provider to whom the respective pending resource request is reassigned, and the commitment stress value otherwise being higher than the low value;

a primary resource provider stress value, the primary resource provider stress value being a low value if none of the resource providers is designated as a primary resource provider for the respective pending resource request or if the respective pending resource request is reassigned to one of the resource providers designated as the primary resource provider for the respective pending resource request, and the primary resource provider stress value otherwise being higher than the low value; and

a territory stress value, the territory stress value being a low value if a location associated with the respective pending resource request is within an acceptable travel time of a territory of the resource provider to whom the respective pending resource request is reassigned, and the territory stress value otherwise being higher than the low value.

32. The computer-implemented system of claim 30, wherein the plurality of component stress values includes:

a resource stress value representing a number of resources for which the resource provider, to whom the respective pending resource request is reassigned, is qualified to provide.

33. The computer-implemented system of claim 5, further comprising the step of displaying a representation of the new assignment set to a user for approval.

34. A computer-implemented method for assigning a plurality of field service calls among a plurality of field service technicians comprising the steps of:

(a) defining a search tree having a root node, wherein the root node defines an existing assignment set representing a pending assignment of a plurality of pending field service calls among a plurality of field service technicians, and

(b) expanding the root node by forming one or more next-level nodes, wherein each of the next-level nodes corresponds to the root node but is further defmed by a reassignment of one of the pending field service calls between one of the field service technicians and another of the field service technicians;

(b) estimating, for each of the next-level nodes, a stress value representing a degree of undesirability of the respective reassignment; and

(c) generating a new assignment set corresponding to one of the next-level nodes having a minimum stress value.

35. The computer-implemented method of claim 34, wherein the plurality of field service calls includes an unassigned new field service call, and the step (a) includes the steps of:

(a)(i) expanding the root node by forming one or more first-level nodes, each of the first-level nodes corresponding to the root node but being further defined by an assignment of the new field service call to a selected one of the field service technicians;

(a)(ii) estimating, for each of the first-level nodes, a stress value representing a degree of undesirability of the respective assignment; and

(a)(iii) expanding one or more of the first-level nodes by forming, for each of the first-level nodes, one or more of the next-level nodes, wherein each of the next-level nodes corresponds to the respective first-level node but is further defined by a reassignment of one of the pending field service calls between the selected one of the field service technicians and another of the field service technicians,

wherein the new assignment set corresponds to one of the first-level nodes and the next-level nodes having a minimum stress value.

36. The computer-implemented method of claim 35, wherein the step (a)(iii) comprises the steps of:

selecting one of the first-level nodes having a minimum stress value; and

expanding the selected one of the first-level nodes by forming one or more of the next-level nodes.

37. The computer-implemented method of claim 36, wherein the method further comprises the steps of:

(d) selecting one of the unexpanded first-level nodes and the unexpanded next-level nodes having a minimum stress value;

(e) expanding the selected one of the unexpanded first-level nodes and the unexpanded next-level nodes as a preceding-level node by forming one or more next-level nodes, each of the next-level nodes corresponding to the preceding-level node but being further defined by a reassignment of one of the pending field service calls between one of the field service technicians and another of the field service technicians; and

(f) estimating, for each of the next-level nodes formed by step (e), a stress value representing a degree of undesirability of the respective reassignment; and

(g) repeating the steps (d), (e), and (f) to expand one of the unexpanded first-level nodes and the unexpanded next-level nodes as a preceding-level node, thereby forming a succession of the next-level nodes,

wherein the new assignment set corresponds to one of the first-level nodes and the succession of the next-level nodes having a minimum stress value.