Resource allocation - Patent Review 5963911

What is claimed is:

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.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to a method for optimising the allocation of a plurality of resources to a plurality of jobs and to a apparatus for performing such a method. It is particularly suited for use in situations where the availability of resources and the jobs to be performed both change dynamically. An example of such a situation is the allocation of jobs to a field force of operatives, for example ambulance or taxi drivers, a vehicle repair call out field force, or a maintenance field force for a distributed system such as a power or water supply or telecommunications network.

2. Related Art

An article entitled `Work Management System`, by G J Garwood and A C Robinson (British Telecommunications Engineering Journal, Vol 10 No 3 October 1991, pages 204-210) describes a system for allocating jobs to individual field technicians. One element of this system handles unplanned work (as distinct from scheduled or "appointment" work) to handle repairs to faults.

In such situations the workload is highly variable and volatile, and jobs have to be allocated in real time since the necessary response times are of the order of the lengths of the jobs themselves, and very much shorter than an operative's working day. The durations of the individual jobs are themselves highly variable which affects resource availability for those jobs awaiting allocation.

The reference cited above describes in general terms a real-time algorithm which takes into account various attributes of the individual members of the field force (such as their current location, skills forecast time to availability etc.) and jobs required, (such as the skills required to perform them, and their "time to jeopardy": i.e. the time by which the job is to be performed).

Various cost analysis algorithms are known for allocating jobs to resources, such as the so called "Hungarian algorithm" described in a 1955 paper by H W Kuhn "The Hungarian Method for the Assignment Problem" (Naval Research Logistics Quarterly, Vol 2, pages 83-97) and developed further by M B Wright "Speeding up the Hungarian Algorithm", Computer Operations Research Vol 17 No 1 pages 95-96 (1990). However the use of these algorithms in real situations is not easy.

SUMMARY OF THE INVENTION

According to a first aspect of the invention there is provided 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 cost.

The method may be operated such that when a resource becomes available the steps described above are performed, the available resource then being assigned to the job which is associated with it in the smallest cost combination identified by the above procedure.

New jobs may be added to the plurality of jobs, the method described above being performed when such additions take place.

If a second resource becomes available at or near to its forecast time and no other changes have occurred since the optimisation determination was last performed, the second resource may be assigned the job already allocated to it in the lowest-cost combination previously calculated.

The method may be arranged such that combinations of resources and jobs which are incompatible are ascribed substantially infinite cost values. If it is desired to allocate a specific resource to a job, it may be arranged that combinations of that job with other resources are treated as incompatible.

The jobs may be prioritised on the basis of the times at which they to be performed, and the resources may be prioritised on the basis of which are forecast to become available first. The cost evaluation may be performed for a predetermined number of the jobs, being those having the highest priority.

The method may allow low priority jobs to be interrupted to allow a high priority job to be done instead.

If more jobs are available than resources, dummy resources may be included in the analysis. High values are allotted to the cost functions of jobs allocated to such resources.

A group of jobs which are closely related may be represented by a single job in the calculation of cost scores, other jobs of the group being assigned to the same resource if they are compatible.

According to a second aspect of the invention there is provided 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 cost.

According to a further aspect, there is provided 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 possibile 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; and

to determine the combination which produces the smallest total projected cost.

By assigning a time-dependent cost function to each job, the fact that different resources would perform it at different times, and the consequences of this, such as failure to meet an agreed time, can be taken into account.

Means may be provided for adding new jobs to the plurality of jobs. Means may also be provided for identifying incompatible combinations of jobs with resources and ascribing infinite cost values to such combinations.

There may also be means for selectively allocating a specified resource to a given job, arranged so that combinations of such a job with other resources are identified as incompatible.

Means may also be provided for prioritising jobs and/or resources, and for selecting the jobs and resources with the highest priority on which to perform the cost evaluation.

Allocation equipment as described above may be provided in combination with a plurality of communications terminals for use by the resources, and with a communications network for communicating between the terminals and the control apparatus.

Advantageously, these terminals may store details of a second job provisionally allocated to the resource by the allocation equipment, but only reveal these details if an attempt to report completion of a first job fails to communicate with the allocation apparatus.

The terminals are preferably portable, and may communicate with the allocation equipment either by a radio network or by a fixed telecommunications network to which the terminals may be connected. They send information to the allocation equipment, as well as receiving instructions from it.

In this invention, the performance of the job and the availability of the resource are calculated as time-dependent functions, with a greater cost weighting being applied to resource-job combinations with a greater likelihood of failing to achieve a target time.

In a preferred arrangement only resources which have completed their current job are informed of the next job allocated to them. Other allocations are provisional and may be changed in response to changed circumstances, e.g. new jobs being requested, or a resource reporting a job completion earlier or later than the estimated time. In a particularly preferred arrangement the job allocation procedure is normally performed whenever a resource reports its current job completed, but if there have been no changes such as new job requests since the last run of the allocation procedure, and if the resource has reported job completion close to the projected completion time, the results of the last run of one procedure are used instead.

The allocation procedure may also be performed when significant changes take place such as the addition of new jobs. This allows the current allocation to keep up with such developments, so that when a resource requests a job the system can respond with an assigned job immediately without having to run the allocation procedure. However, if a resource reports job completion earlier than predicted, this is itself a significant change which would require re-running of the allocation procedure.

In certain circumstances there may be resources which are unable to perform certain jobs. This would apply for example where a job requires a specific skill, or where an item of equipment is needed which is only held by some of the available operatives. Other situations may occur where only a limited group of operatives have authority to work at a particular site, e.g. because of a customer's security procedures. In yet other cases a specific individual operative may be requested for a particular job, for example because it is a follow-up to an earlier job performed by that individual, or as part of the individual's training. In order to accommodate this the cost values for all incompatible resource/job combinations may be arranged to be reset to infinity. However, if the operating system on which the system is being run has difficulty in handling infinities, a finite number may be used which is nevertheless sufficiently large that no such incompatible allocation will be made. This will nevertheless ensure that the allocation will be made to a compatible resource. In this specification, the phrase `substantially infinite` is used to mean any number whose value is large enough to achieve this.

In order to reduce processing time, the system may operate on combinations only of those resources projected to become available in the near future (including any currently available) and those jobs having the highest priority.

In a further development of the invention, there is provided an 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 cost;

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.

Where the network is a telecommunications network, said fault detecting means may be a fault management system forming part of the network. The means for supplying parameters to the jobs may be simply an interface between the fault management system and said apparatus.

The parameters may 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. In particular, if there is no spare capacity, such that service is interrupted, the job is allocated the highest priority.

BRIEF DESCRIPTION OF THE DRAWINGS

An embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

FIG. 1 shows a general arrangement of a system including a computer configured to operate according to the invention;

FIG. 2 is a flow chart showing diagrammatically the operation of a minimum cost calculation routine (the "Hungarian algorithm"--Wright variant) forming part of the main program of the computer of the system of FIG. 1;

FIG. 3 is a general flow chart showing an over-view of the various routines which together form the main program of the computer, the individual routine being shown in greater detail in FIGS. 2 and 4 to 12;

FIG. 4 is a flow chart showing the routine performed when a operative reports job completion;

FIG. 5 shows the routine for updating the operatives' parameters in the system

FIG. 6 is a flow chart showing the job allocation routine itself;

FIG. 7 shows the routine for updating job parameters when a new job is requested;

FIG. 8 shows a continuation of the job parameter update;

FIG. 9 shows a pre-allocation routine for those jobs which are identified as being required by a specific individual operative;

FIG. 10 shows a flow chart for the initialisation routine to be performed at the beginning of the working day;

FIG. 11 shows a flow chart showing a periodical updating procedure; and

FIG. 12 shows a sub routine for allocating a second job to an operative which forms an optional part of the routine of FIG. 6.

FIG. 13 shows a flow chart for the end-of-day procedure.

FIG. 14 shows a flow chart for a `job-interrupt` procedure.

FIG. 15a shows a flow chart for a job-selection procedure. FIG. 15b shows a flow chart for a job-grouping procedure.

FIGS. 16 and 17 are representations of cost score matrixes for the situation illustrated in FIG. 1.

FIG. 18 is a functional block diagram of the resource allocation system shown in FIG. 1.

FIG. 19 shows the components of the computer of FIG. 1.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

Referring to FIG. 1, there is shown a resource allocation system comprising an apparatus in the form of a computer X for allocating resources to jobs and three hand held terminals H1, H2, H3. Each of the hand held terminals may be a Husky model FS/2 produced by Husky Computers Ltd of Coventry, England. Each of the hand held terminals may be connected to the computer X by a fixed or mobile telecommunications network. FIG. 1 shows a link C made by such a network between terminal H1 and the computer X.

In the present example, the resources take the form of three technicians T1, T2, T3 who are provided, respectively, with the terminals H1, H2, H3. The three technicians are presently engaged on jobs J1, J2, J3 and there are four further jobs J4, J5, J6, J7 awaiting attention. In a real situation there will be many more technicians and jobs. The technicians T1, T2, T3 can use their terminals H1, H2, H3 for reporting completion of a job and for certain special purpose to be described later. They also use the terminals to receive instructions for the next job from the computer X.

In the present example, the three technicians T1, T2, T3 are part of a field force for performing jobs on a telecommunications work.

The components of computer X are shown in FIG. 19. These comprise a keyboard 191, a central processing unit (CPU) 192, a visual display unit (VDU) 193, a memory 194 and an input/output port 195. The data and the programs for controlling the computer X are stored in memory 194. The input/output port 195 connects the computer to the telecommunications system which provides the communication links between the computer X and the hand held terminals H1, H2, H3. The computer X can also review alarms from a fault monitoring system associated with the telecommunications network.

The computer X is provided with a main program for allocating the technicians to the jobs. The main program is divided into a set of routines. The general structures of the program the individual routine and the method used by the program for allocating the technicians to the jobs are discussed in detail below.

In FIG. 1, technician T1 has completed job J1 and contacts the computer X with the aid of his terminal H1 and the communication link c for instructions for his next job.

The problem is to determine which of jobs J4, J5, J6, J7 technician T1 should be instructed to perform next. The method used by the main program of computer X takes into account.

whether the technician can perform each individual job;

the time the technician would take to travel to the location of each job;

the time the technician would take to perform each job.

the relevant importance of each job, determined for example by the number of