Resource allocation

• US 5,963,911 A
• Filed: 09/25/1996
• Issued: 10/05/1999
• Est. Priority Date: 03/25/1994
• Status: Expired due to Term

• Current Assignee: Trimble MRM Ltd. (Trimble Inc.)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Taylor, Alan, Morton, David, Laithwaite, Robert N. W., Denman, John, Williams, Gerwyn L., Jubb, Mike, Walker, Paul
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Patel, Jagdish
• Application Number:
  US08/720,199
• Time in Patent Office: 1,105 Days
• Field of Search: 705/7, 705/8, 705/9
• US Class Current: 705/7.12
• 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/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. A method as claimed in claim 1 wherein combinations of resources and jobs which are incompatible are ascribed substantially infinite cost values.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. Apparatus according to claim 11, further comprising means for adding new jobs to the plurality of jobs.

13. 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.

14. 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.

15. 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.

16. 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.

17. A system as claimed in claim 15, wherein the terminals are portable.

18. A system as claimed in claim 15, wherein the communications network is a radio network.

19. A system as claimed in claim 15, wherein the terminals are connectable to a fixed telecommunications network.

20. A system as claimed in claim 15, wherein the terminals are arranged to receive said output from the allocation apparatus.

21. A system as claimed in claim 20, wherein the terminals include memory means to store said output.

22. A system as claimed in claim 15, wherein the terminals are arranged to send information to the allocation apparatus.

23. A system as claimed in claim 15, wherein the terminals are arranged to allow paging of the resources by the allocation apparatus.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. Apparatus according to claim 28, further arranged to add new jobs to the plurality of jobs.

30. Apparatus according to claim 28, arranged to identify incompatible combinations of jobs with resources and to ascribe infinite cost values to such combinations.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.