EP0669586A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
System and method for resource assignment and scheduling
Assignee: 3M Co
•
Filing: 1995-02-23
•
Granted: —
•
Expires: 2015-02-23
Abstract
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.
Inventors
- 👤 Elizabeth M. C/O Minnesota Mining And Sisley
- 👤 John E. C/O Minnesota Mining And Collins
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 02:01
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/063; G06Q10/0631; G06Q10/06311; G06Q10/063116; G06Q10/06312; G06Q10/06314; G06Q10/06315; G06Q10/06316; G06Q10/10; G06Q10/109; G06Q10/1097
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
145 words
A computer-implemented method for assigning a plurality of resource requests among a plurality of resource providers, said plurality of resource requests including a plurality of pending resource requests assigned among said resource providers according to an existing assignment set, wherein said existing assignment set defines a root node of a search tree, said method comprising the steps of: (a) expanding said root node by forming one or more next-level nodes, each of said next-level nodes corresponding to said root node but being further defined by a reassignment of one of said pending resource requests between one of said resource providers and another of said resource providers, (b) estimating, for each of said 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 said next-level nodes having a minimum stress value.
Claim 2
Dependent Claim
145 words
A computer-implemented method for assigning a plurality of resource requests among a plurality of resource providers, said plurality of resource requests including a plurality of pending resource requests assigned among said resource providers according to an existing assignment set, wherein said existing assignment set defines a root node of a search tree, said method comprising the steps of: (a) expanding said root node by forming one or more next-level nodes, each of said next-level nodes corresponding to said root node but being further defined by a reassignment of one of said pending resource requests between one of said resource providers and another of said resource providers, (b) estimating, for each of said 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 said next-level nodes having a minimum stress value.
Claim 3
Dependent Claim
176 words
The method according to claim 1, characterized in that said plurality of resource requests includes an unassigned new resource request, and said step (a) includes the steps of: (a)(i) expanding said root node by forming one or more first-level nodes, each of said first-level nodes corresponding to said root node but being further defined by an assignment of said new resource request to a selected one of said resource providers, (a)(ii) estimating, for each of said first-level nodes, a stress value representing a degree of undesirability of the respective assignment, and (a)(iii) expanding one or more of said first-level nodes by forming, for each of said first-level nodes, one or more of said next-level nodes, wherein each of said next-level nodes corresponds to the respective first-level node but is further defined by a reassignment of one of said pending resource requests between said selected one of said resource providers and another of said resource providers, wherein said new assignment set corresponds to one of said first-level nodes and said next-level nodes having a minimum stress value.
Claim 4
Dependent Claim
215 words
The method according to claim 2, characterized in that said step (a)(iii) comprises the steps of: selecting one of said first-level nodes having a minimum stress value, and expanding the selected one of said first-level nodes by forming one or more of said next-level nodes, said method further comprising 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 said unexpanded first-level nodes and said unexpanded next-level nodes as a preceding-level node by forming one or more next-level nodes, each of said next-level nodes corresponding to the preceding-level node but being further defined by a reassignment of one of said pending resource requests between one of said resource providers and another of said resource providers, and (f) estimating, for each of said next-level nodes formed by step (e), a stress value representing a degree of undesirability of the respective reassignment, and (g) repeating said steps (d), (e), and (f) to expand one of said unexpanded first-level nodes and said unexpanded next-level nodes as a preceding-level node, thereby forming a succession of said next-level nodes, wherein said new assignment set corresponds to one of said first-level nodes and said succession of said next-level nodes having a minimum stress value.
Claim 5
Dependent Claim
156 words
The method according to claim 3, characterized in that said existing assignment set includes an existing schedule set, said existing schedule set including, for each of said resource providers, an existing schedule of the pending resource requests assigned to the respective resource provider, said method further comprising the steps of: generating, for each of said first-level nodes, a schedule set corresponding to said existing schedule set but including a schedule of said new resource request and the pending resource requests assigned to said selected one of said resource providers, and generating, for each of said 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 said one and said another of said resource providers, wherein said new assignment set includes the schedule set for the respective one of said first-level nodes and said next-level nodes having said minimum stress value.
Claim 6
Dependent Claim
96 words
The method according to claim 4, characterized in that said step of generating a schedule set for each of said first-level nodes includes the steps of: generating one or more potential schedules of said new resource request and the pending resource requests assigned to said selected one of said resource providers, estimating, for each of said potential schedules, a schedule stress value representing a degree of undesirability of the respective potential schedule, and selecting one of said potential schedules having a minimum schedule stress value as said schedule for said selected one of said resource providers.
Claim 7
Dependent Claim
143 words
The method according to claim 5, characterized in that said step of generating a schedule set for each of said next-level nodes includes the steps of: generating one or more potential schedules, said potential schedules including one or more first potential schedules of the resource requests assigned to said one of said resource providers, and one or more second potential schedules of the resource requests assigned to said another of said resource providers, estimating, for each of said potential schedules, a schedule stress value representing a degree of undesirability of the respective potential schedule, and selecting one of said first potential schedules having a first minimum schedule stress value as said schedule for said one of said resource providers, and one of said second potential schedules having a second minimum schedule stress value as said schedule for said another of said resource providers.
Claim 8
Dependent Claim
76 words
The method according to claim 6, characterized in that, in said step (a)(ii), the stress value estimated for each of said first-level nodes includes a representation of said minimum schedule stress value for the respective first-level node, and, in said steps (b) and (f), the stress value estimated for each of said next-level nodes includes a representation of said first minimum schedule stress value and said second minimum schedule stress value for the respective next-level node.
Claim 9
Independent Claim
97 words
The method according to any one of claims 5 to 7, characterized in that said step of generating said one or more potential schedules for each of said first-level nodes includes, before generating said potential schedules, the steps of: estimating a worst acceptable schedule stress value, estimating, for each of said first-level nodes, a minimum stress of insertion of said new resource request among the pending resource requests on the existing schedule for said selected technician, and discarding each of said first-level nodes having a minimum stress of insertion that exceeds said worst acceptable schedule stress value.
Claim 10
Dependent Claim
120 words
The method according to claim 6 or 7, characterized in that said step of generating said one or more first and second potential schedules for each of said next-level nodes includes, before generating said potential schedules, the steps of: estimating a worst acceptable schedule stress value, estimating, for each of said next-level nodes, a minimum stress of insertion of the pending resource request reassigned to one of said one and said another of said resource providers among the pending resource requests on the existing schedules for the respective one of said one and said another of said resource providers, and discarding each of said next-level nodes having a minimum stress of insertion that exceeds said worst acceptable schedule stress value.
Claim 11
Independent Claim
111 words
The method according to any one of claims 3 to 9, characterized by the step of generating, for each of said resource requests, a list of said resource providers qualified to accept assignment of the respective resource request, the resource providers on said list being designated as candidate resource providers for the respective resource request, wherein, in said step (a)(i), said selected one of said resource providers is a selected one of the candidate resource providers for said new resource request, and, in said step (e), each of said one and said another of said resource providers is one of the candidate resource providers for the respective reassigned pending resource request.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.