Patent US2269150A successfully refreshed from Google Patents.
Patent US5963911A successfully refreshed from Google Patents.
US5963911A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Resource allocation
Assignee: Apsolve Ltd
•
Filing: 1996-09-25
•
Granted: 1999-10-05
•
Expires: 2016-09-25
Abstract
Abstract In order to optimize the utilization of resources (e.g., technicians) in performing a number of jobs, each job is assigned a cost time-dependent function and each resource is assessed for the time at which it will be available. For each combination of jobs with resources, an actual can be determined. The combination giving the lowest overall cost is then determined. Additional features are disclosed to ensure incompatible job/resource combinations are not allocated, and to reduce the complexity of the calculation by prioritizing the jobs and resources.
Inventors
- 👤 Paul Walker
- 👤 Robert N. W. Laithwaite
- 👤 John Denman
- 👤 David Morton
- 👤 Gerwyn L. Williams
- 👤 Mike Jubb
- 👤 Alan Taylor
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 12:03
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/063; G06Q10/0631
Claims Analysis
Total Claims: 49
Claim 1
Independent Claim
137 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to perform the following steps: determining the time at which each resource is forecast to become available; determining the time at which each job is required to be performed; assigning to each job a time-dependent cost function calculated as a function of the time at which the job will be performed; for each possible combination of jobs with resources, determining the total projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; determining the combination which produces the smallest total projected costs; allocating the resources based on the determined combination; and generating an output based on the allocating of the resources.
Claim 2
Independent Claim
137 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to perform the following steps: determining the time at which each resource is forecast to become available; determining the time at which each job is required to be performed; assigning to each job a time-dependent cost function calculated as a function of the time at which the job will be performed; for each possible combination of jobs with resources, determining the total projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; determining the combination which produces the smallest total projected costs; allocating the resources based on the determined combination; and generating an output based on the allocating of the resources.
Claim 3
Dependent Claim
44 words
A resource allocation method using a method according to claim 1, wherein when a resource becomes available the steps of claim 1 are performed, the available resource being assigned to the job which is associated with it in the combination having the smallest cost.
Claim 4
Dependent Claim
50 words
A method as claimed in claim 2, wherein if a second resource becomes available at or near to its forecast time and no other changes have occurred since the allocation determination was last performed, the second resource is assigned the job allocated to it in the lowest-cost combination previously determined.
Claim 5
Dependent Claim
35 words
A method according to claim 2, wherein when a first job is assigned to a resource, other jobs closely related to the first job and compatible with the resource are also assigned to the resource.
Claim 6
Dependent Claim
32 words
A resource allocation method as claimed in claim 2, wherein new jobs may be added to the plurality of jobs, the steps of claim 1 being performed when such additions take place.
Claim 7
Dependent Claim
22 words
A method as claimed in claim 1 wherein combinations of resources and jobs which are incompatible are ascribed substantially infinite cost values.
Claim 8
Dependent Claim
29 words
A method according to claim 6, wherein a resource may be allocated to a specific job, such that combinations of that job with other resources are treated as incompatible.
Claim 9
Dependent Claim
40 words
A method according to claim 1, wherein if the cost value of a first job exceeds a threshold value, a resource is instructed to interrupt a second job which it is currently engaged on and perform the first job instead.
Claim 10
Independent Claim
196 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to perform the following steps: determining the time at which each resource is forecast to become available; determining the time at which each job is required to be performed; assigning to each job a time-dependent cost function calculated as a function of the time at which the job will be performed; determining the total projected cost for combinations of jobs with resources, dependent on the time at which the resource is forecast to be available and the value of the cost function for the respective job at that time; determining the combination which produces the smallest total projected cost; allocating the resources based on the determined combination; and generating an output based on the allocating of the resources, wherein the jobs are prioritized on the basis of the times at which they are to be performed, and the resources are prioritized on the basis of those which are forecast to become available first, the jobs and resources having the highest priority are selected, and the cost evaluation is performed for each possible combination of the selected jobs and resources.
Claim 11
Independent Claim
196 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to perform the following steps: determining the time at which each resource is forecast to become available; determining the time at which each job is required to be performed; assigning to each job a time-dependent cost function calculated as a function of the time at which the job will be performed; determining the total projected cost for combinations of jobs with resources, dependent on the time at which the resource is forecast to be available and the value of the cost function for the respective job at that time; determining the combination which produces the smallest total projected cost; allocating the resources based on the determined combination; and generating an output based on the allocating of the resources, wherein the jobs are prioritized on the basis of the times at which they are to be performed, and the resources are prioritized on the basis of those which are forecast to become available first, the jobs and resources having the highest priority are selected, and the cost evaluation is performed for each possible combination of the selected jobs and resources.
Claim 12
Dependent Claim
36 words
A method according to claim 9, wherein the predetermined number of resources is less than the predetermined number of jobs, the cost values of jobs not being allocated to resources being included in the cost evaluation.
Claim 13
Dependent Claim
164 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: means for storing parameters relating to the resources; means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for determining, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected costs; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources.
Claim 14
Dependent Claim
164 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: means for storing parameters relating to the resources; means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for determining, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected costs; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources.
Claim 15
Dependent Claim
17 words
Apparatus according to claim 11, further comprising means for adding new jobs to the plurality of jobs.
Claim 16
Dependent Claim
26 words
Apparatus according to claim 11, further comprising means for identifying incompatible combinations for jobs with resources and means for ascribing infinite cost values to such combinations.
Claim 17
Dependent Claim
30 words
Apparatus according to claim 13, comprising means for selectively allocating a specific resource to a given job, wherein combinations of such a job with other resources are identified as incompatible.
Claim 18
Dependent Claim
37 words
A resource allocation system comprising allocation apparatus according to claim 11, in combination with a plurality of communications terminals for use by the resources, and a communications network for communicating between the terminals and the allocation apparatus.
Claim 19
Dependent Claim
61 words
A resource allocation system according to claim 15, the allocation apparatus further comprising means for allocating a provisional second job to each resource, the terminals comprising means for storing said second job details, means for attempting to report job completion to the allocation apparatus, and means for displaying the stored details of the second job only if such an attempt fails.
Claim 20
Dependent Claim
12 words
A system as claimed in claim 15, wherein the terminals are portable.
Claim 21
Dependent Claim
15 words
A system as claimed in claim 15, wherein the communications network is a radio network.
Claim 22
Dependent Claim
17 words
A system as claimed in claim 15, wherein the terminals are connectable to a fixed telecommunications network.
Claim 23
Dependent Claim
20 words
A system as claimed in claim 15, wherein the terminals are arranged to receive said output from the allocation apparatus.
Claim 24
Dependent Claim
17 words
A system as claimed in claim 20, wherein the terminals include memory means to store said output.
Claim 25
Dependent Claim
19 words
A system as claimed in claim 15, wherein the terminals are arranged to send information to the allocation apparatus.
Claim 26
Dependent Claim
22 words
A system as claimed in claim 15, wherein the terminals are arranged to allow paging of the resources by the allocation apparatus.
Claim 27
Dependent Claim
54 words
Apparatus according to claim 11, in combination with a network on which the jobs are to be performed, said network including means for detecting faults in the network, and means for supplying, to said means for storing parameters relating to the jobs, parameters of jobs to be performed to rectify the faults so detected.
Claim 28
Dependent Claim
40 words
Apparatus according to claims 24, arranged such that the parameters supplied include an assessment of the priority of the job to the performed, made wholly or in part on the basis of the availability of spare capacity in the network.
Claim 29
Dependent Claim
26 words
Apparatus according to claim 25, arranged such that if there is no spare capacity, such that service is interrupted, the job is allocated the highest priority.
Claim 30
Dependent Claim
185 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: means for storing parameters relating to the resources; means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for prioritizing jobs and/or resources; means for selecting the jobs and resources with the highest priority; means for determining, for each possible combination of the selected jobs with the selected resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected costs; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources.
Claim 31
Dependent Claim
185 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: means for storing parameters relating to the resources; means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for prioritizing jobs and/or resources; means for selecting the jobs and resources with the highest priority; means for determining, for each possible combination of the selected jobs with the selected resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected costs; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources.
Claim 32
Dependent Claim
186 words
A computer apparatus for allocating a plurality of jobs to a plurality of resources, said computer apparatus comprising a central processing unit, a memory, an input device and an output device, said memory containing a program for controlling the computer and which is arranged: to store parameters relating to the resources; to store parameters relating to the jobs; to determine from the parameters the time at which each resource is forecast to become available; to determine from the parameters the time at which each job is required to be performed; to assign to each job a cost function which is calculated as a function of the time at which the job will be performed; to determine, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; to determine the combination which produces the smallest total projected cost; to allocate the resources based on the determined combination; and to generate an output based on the allocating of the resources.
Claim 33
Dependent Claim
186 words
A computer apparatus for allocating a plurality of jobs to a plurality of resources, said computer apparatus comprising a central processing unit, a memory, an input device and an output device, said memory containing a program for controlling the computer and which is arranged: to store parameters relating to the resources; to store parameters relating to the jobs; to determine from the parameters the time at which each resource is forecast to become available; to determine from the parameters the time at which each job is required to be performed; to assign to each job a cost function which is calculated as a function of the time at which the job will be performed; to determine, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; to determine the combination which produces the smallest total projected cost; to allocate the resources based on the determined combination; and to generate an output based on the allocating of the resources.
Claim 34
Dependent Claim
16 words
Apparatus according to claim 28, further arranged to add new jobs to the plurality of jobs.
Claim 35
Dependent Claim
23 words
Apparatus according to claim 28, arranged to identify incompatible combinations of jobs with resources and to ascribe infinite cost values to such combinations.
Claim 36
Dependent Claim
30 words
Apparatus according to claim 30, further arranged to selectively allocate a specific resource to a given job, wherein combinations of such a job with other resources are identified as incompatible.
Claim 37
Dependent Claim
204 words
A computer apparatus for allocating a plurality of jobs to a plurality of resources, said computer apparatus comprising a central processing unit, a memory, an input device and an output device, said memory containing a program for controlling the computer and which is arranged to: to store parameters relating to the resources; to store parameters relating to the jobs; to determine from the parameters the time at which each resource is forecast to become available; to determine from the parameters the time at which each job is required to be performed; to assign to each job a cost function which is calculated as a function of the time at which the job will be performed; to prioritise jobs and/or resources; to select the jobs and resources with the highest priority; to determine, for each possible combination of selected jobs with selected resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; to determine the combination which produces the smallest total projected cost; to allocate the resources based on the determined combination; and to generate an output based on the allocating of the resources.
Claim 38
Dependent Claim
204 words
A computer apparatus for allocating a plurality of jobs to a plurality of resources, said computer apparatus comprising a central processing unit, a memory, an input device and an output device, said memory containing a program for controlling the computer and which is arranged to: to store parameters relating to the resources; to store parameters relating to the jobs; to determine from the parameters the time at which each resource is forecast to become available; to determine from the parameters the time at which each job is required to be performed; to assign to each job a cost function which is calculated as a function of the time at which the job will be performed; to prioritise jobs and/or resources; to select the jobs and resources with the highest priority; to determine, for each possible combination of selected jobs with selected resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; to determine the combination which produces the smallest total projected cost; to allocate the resources based on the determined combination; and to generate an output based on the allocating of the resources.
Claim 39
Independent Claim
92 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein more jobs than resources are used for the calculation, un-assigned jobs being assigned to dummy resources with a cost value for such assignments being determined as a function of the cost of the job not being done.
Claim 40
Independent Claim
92 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein more jobs than resources are used for the calculation, un-assigned jobs being assigned to dummy resources with a cost value for such assignments being determined as a function of the cost of the job not being done.
Claim 41
Dependent Claim
31 words
A method according to claim 33, in which jobs are selected for calculation of cost combinations such that jobs having different characteristics are selected in preference to jobs having similar characteristics.
Claim 42
Independent Claim
84 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein when the lowest-cost combination is calculated, a first job is assigned to a resource, and any jobs closely related to the first job are also assigned to the resource.
Claim 43
Independent Claim
84 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein when the lowest-cost combination is calculated, a first job is assigned to a resource, and any jobs closely related to the first job are also assigned to the resource.
Claim 44
Independent Claim
103 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for possible combinations of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein, of a group of closely related jobs, having different priorities, the highest priority job is selected for combination calculations and, when the lowest-cost combination is calculated, a first job is assigned to a resource, and any jobs closely related to the first job are also assigned to the resource.
Claim 45
Independent Claim
103 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for possible combinations of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein, of a group of closely related jobs, having different priorities, the highest priority job is selected for combination calculations and, when the lowest-cost combination is calculated, a first job is assigned to a resource, and any jobs closely related to the first job are also assigned to the resource.
Claim 46
Independent Claim
101 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein jobs are assigned priority values and target times, and wherein high priority jobs are monitored such that if a high priority job approaches its target time, a resource working on a lower-priority job is instructed to interrupt the lower-priority job and perform the high priority job.
Claim 47
Independent Claim
101 words
A method of allocating a plurality of resources to a plurality of jobs, by using a computer to assign a projected cost for each possible combination of resources with jobs, calculate the lowest-cost combination, allocate the resources based on the calculated lowest-cost combination and generate an output based on the allocating of the resources, wherein jobs are assigned priority values and target times, and wherein high priority jobs are monitored such that if a high priority job approaches its target time, a resource working on a lower-priority job is instructed to interrupt the lower-priority job and perform the high priority job.
Claim 48
Dependent Claim
215 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: first means for storing parameters relating to the resources; second means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for determining, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected cost; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources, said apparatus being used in combination with a network on which the jobs are to be performed, said network including means for detecting faults in the network, and means for supplying, to said second means for storing, parameters of jobs to be performed to rectify the faults so detected.
Claim 49
Dependent Claim
215 words
Apparatus for allocating a plurality of resources to a plurality of jobs comprising: first means for storing parameters relating to the resources; second means for storing parameters relating to the jobs; means for determining from the parameters the time at which each resource is forecast to become available; means for determining from the parameters the time at which each job is required to be performed; means for assigning to each job a cost function which is calculated as a function of the time at which the job will be performed; means for determining, for each possible combination of jobs with resources, the projected cost, dependent on the time at which each resource is forecast to be available and the value of the cost function for the respective job at that time; means for determining the combination which produces the smallest total projected cost; means for allocating the resources based on the determined combination; and means for generating an output based on the allocating of the resources, said apparatus being used in combination with a network on which the jobs are to be performed, said network including means for detecting faults in the network, and means for supplying, to said second means for storing, parameters of jobs to be performed to rectify the faults so detected.
References Cited (Backward Citations)
US4852001A
Cited
US4866628A
Cited
US5077661A
Cited
US5006983A
Cited
US5111391A
Cited
US5155679A
Cited
US5295065A
Cited
US5291394A
Cited
US5216593A
Cited
US5392429A
Cited
US5291397A
Cited
US5442730A
Cited
US5467268A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-04 | 2003-04-05 | 2003-10-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-04 | 2007-04-05 | 2007-10-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-04 | 2011-04-05 | 2011-10-05 | $7700.00 | Window Closed / Lapsed |