Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1998-03-19
2003-06-10
Hafiz, Tariq R. (Department: 3623)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C705S002000, C705S007380
Reexamination Certificate
active
06578005
ABSTRACT:
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 tasks, and to an apparatus for performing such a method. It is particularly suited for use in situations where the availability of resources, and the tasks to be performed, both change dynamically. An example of such a situation is the allocation of tasks to a field force of personnel, for example ambulance or taxi drivers, a vehicle repair call-out field force, or a maintenance field force for a distributed system such as an electricity or water supply system or a telecommunications network.
2. Related Art
In such situations the workload is highly variable and volatile, and tasks have to be allocated in real-time since the necessary response times are of the order of the duration of the tasks themselves, and very much shorter than a technician's working day. The durations of the individual tasks are themselves very variable and often unpredictable, which affects resource availability for those tasks awaiting allocation.
A prior art system, described in International patent application no. WO 95/26535, describes a system in which, for each resource, the time at which it will become available is estimated. Each task is assigned a time-dependent function, referred to hereinafter as a “cost function”. This cost function is a measure of the consequences of a resource being allocated to the task at a given time. For example, if a resource fails to be allocated within a deadline which has been guaranteed to a customer, compensation may be payable to the customer. Travelling time to, from, and between tasks, and idle time (incurred if a resource cannot perform the next allocated task immediately the resource becomes available to perform it, for example before access to premises can be gained, or before a preceding task in a sequence has been done) are other factors. For each combination of tasks with resources a predicted cost can be determined. This cost is the sum of the values of the time-dependent functions for each task at the time that the resource allocated to it becomes available to perform it. The combination giving the lowest overall cost is then determined.
Additional features are disclosed in the above-mentioned patent which ensure incompatible task/resource combinations are not allocated, and which reduce the complexity of the calculation by prioritising the tasks and resources. The allocation schedule can be kept up to date by running the program periodically, (for example every five minutes) or on demand (for example when a technician requires a new task, or when a new task request is added to the system).
This system requires a large amount of processing power because the entire allocation schedule is constructed from scratch every time the program is run. Such an arrangement is possible when the allocation criteria are themselves relatively simple, even though many individual elements (tasks and resources) may be involved. The problem becomes more intractable when there are complex inter-relationships between the tasks or the personnel involved. For example some tasks may require two or more people to be simultaneously at different places in order to determine the integrity of a connection between the two locations. In other circumstances, tasks may have to be performed in a specified sequence, and different personnel may be required for their performance.
Because the prior art system runs in real time, time available to run the program is limited, so it can only schedule one task, or at most a very few tasks, ahead. This is likely to result in a schedule which is sub-optimal in the longer term, particularly if tasks which will take a large proportion of the day, or even several days, are involved, since the availability of resources in the longer term cannot easily be taken into account in such a system.
Another problem with this real-time process is that when there is a task with a high priority, and several of the technicians could do it, the prior-art real-time process described above schedules it as the next task for a specific individual technician. This would normally be selected according to which technicians are closest to the geographical location of the task, and which are predicted to finish their present task first. However, if the selected technician is delayed on his current task, such that the target time for this next task is jeopardised, other technicians who become available cannot be allocated it instead, unless the whole scheduling process is re-run. Until this happens, the task remains scheduled for the first technician.
An alternative approach, which deals readily with complex inter-relationships and long-term tasks, is to build up a schedule for a complete day (or even longer). This can be done very rigorously, by allocating a lot of computer time to it (for example overnight). However, the result is not readily adaptable to changing circumstances, simply because of the large amount of computer time devoted to preparing it in the first place.
A proposal has been made by G J Garwovod and A C Robinson: “Work Management System” in British Telecommunications Engineering Journal: Vol 10 October 1991 to run two different systems, one according to each of the above two approaches: a “real time” system, for dealing with relatively straightforward but urgent cases which are suitable for real time scheduling, and a “schedule building” system for more complex but less urgent cases, which are more suited to a complex but much slower scheduling process. However, this has a number of drawacks. Firstly, an initial decision has to be made as to which resources and tasks to allocate to each system. Resources cannot switch back and forth between systems (for example to perform a short-term task in one system to fill-in between two larger tasks in the other). A link may be provided between the two systems so that if one of the complex schedules fails for an unforseen reason, the resources and tasks which can no longer perform, or be performed in, the original complex schedule are transferred to the real-time scheduling system. However, the real-time scheduling system is not configured to readily deal with such tasks. In particular, the real time scheduler is constrained to only consider tasks whose target time is imminent, as the need to respond quickly precludes inspecting any more tasks.
SUMMARY OF THE INVENTION
According to the invention there is provided a task-allocation apparatus comprising:
input means for providing information relating to the tasks to be allocated and the resources available to perform the tasks,
schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial schedule,
storage means for storing the initial schedules,
updating means for receiving, from the input means, updated information relating to the tasks and resources, and
modifying means for modifying the initial schedule of at least a first resource in response to such updated information,
whereby changes to the initial schedules may be made in response to such updated information, independently of the schedule generation means.
According to another aspect there is provided a method of allocating a plurality of resources to a plurality of tasks, the method comprising the use of a computer to perform the following functions:
providing initial information relating to the tasks to be allocated and the resources available to perform the tasks,
generating, for each resource, an initial schedule to allocate the resources to the tasks,
storing the initial schedules,
providing updated information relating to the tasks and resources, and
modifying the initial schedule of at least a first resource in response to such updated information,
whereby changes to individual schedules may be made in response to such updated information independently of the process of generating the initial schedules.
In this arrangement, there is a closer co-operation between the two basic proces
Alletson Ian S
Azarmi Nader
Laithwaite Robert N. W.
Lesaint David
Noble Andrew P
British Telecommunications public limited company
Hafiz Tariq R.
Robinson-Boyce Akiba
LandOfFree
Method and apparatus for resource allocation when schedule... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for resource allocation when schedule..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for resource allocation when schedule... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158000