US6578005B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for resource allocation when schedule changes are incorporated in real time
Assignee: Apsolve Ltd
•
Filing: 1997-11-12
•
Granted: 2003-06-10
•
Expires: 2017-11-12
Abstract
Abstract A plurality of resources, typically service operatives, are allocated to a plurality of tasks by a method in which initial information relating to the tasks to be allocated and the resources available to perform the tasks is provided. An initial series of schedules is first generated allocating resources to the tasks, and then modifying the individual schedule of at least one resource in response to updated information. Changes to individual schedules may be made in response to such updated information independently of the schedule generation. The initial, series of schedules may be generated in a two-stage process in which a rule-based system allocates tasks selected as being difficult to allocate (e.g., because they are linked to other tasks). then a stochastic (non-systematic) search system compiles the rest of the schedule. Periodically, the stochastic system may be interrupted to allow a further rule-based system to analyze the schedules created thus far, and fix the best ones in the schedule, so that the stochastic system can then concentrate on improving the remaining schedules. In order to allow the system to handle rapid changes in the requirements for tasks and the resources, on a scale faster than the time required to generate the schedules, a schedule modification system is arranged to make changes in the short term in between schedule updates delivered by the schedule generation system.
Inventors
- 👤 David Lesaint
- 👤 Christos Voudouris
- 👤 Nader Azarmi
- 👤 Robert N. W. Laithwaite
- 👤 John J O'Donoghue
- 👤 Andrew P Noble
- 👤 Paul Walker
- 👤 Ian S Alletson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:59
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/063; G06Q10/0631; G06Q10/06311; G06Q10/063112; G06Q10/063116; G06Q10/06312
Claims Analysis
Total Claims: 119
Claim 1
Independent Claim
214 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks during a given period; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storage means for storing the initial complete schedule, updating means for receiving, from the input means, updated information relating to the tasks and resources for said given period, the updated information being received by the input means during said given period from a source external to the apparatus, and on-line modifying means for modifying the initial complete schedule of at least a first a resource in response to such updated information to generate at least one modified complete schedule, wherein changes to the initial complete schedule may be made in response to such updated information in real time, independently of the schedule generation means; and the initial complete schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified complete schedule generated by the on-line modifying means reacts to said updated information.
Claim 2
Dependent Claim
214 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks during a given period; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storage means for storing the initial complete schedule, updating means for receiving, from the input means, updated information relating to the tasks and resources for said given period, the updated information being received by the input means during said given period from a source external to the apparatus, and on-line modifying means for modifying the initial complete schedule of at least a first a resource in response to such updated information to generate at least one modified complete schedule, wherein changes to the initial complete schedule may be made in response to such updated information in real time, independently of the schedule generation means; and the initial complete schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified complete schedule generated by the on-line modifying means reacts to said updated information.
Claim 3
Dependent Claim
58 words
Apparatus as in claim 1 , wherein: the schedule generation means is arranged to periodically generate an initial complete schedule according to data received by the input means, and the modifying means is arranged to make changes to the initial complete schedule in response to the receipt of data between such periodic generation of the initial complete schedule.
Claim 4
Dependent Claim
56 words
Apparatus as in claim 1 , wherein the schedule generation means comprises: a first, deterministic, stage; means for selecting tasks which are to be scheduled by the first stage; and a second, optimization, stage for scheduling the remaining tasks, wherein the second stage includes means to treat the tasks scheduled by the first stage as fixed.
Claim 5
Dependent Claim
39 words
Apparatus as in claim 3 , wherein the means for selecting tasks for scheduling by the first stage is arranged to select groups of linked tasks involving more than one of the resources, or forming a sequence of tasks.
Claim 6
Dependent Claim
15 words
Apparatus as in claim 3 wherein the second stage operates according to a stochastic process.
Claim 7
Dependent Claim
15 words
Apparatus as in claim 5 , wherein the stochastic process is a Simulated Annealing process.
Claim 8
Dependent Claim
68 words
Apparatus as in claim 3 wherein the schedule generation means comprises a third, post-optimization stage, comprising: means for analyzing the schedules created by the second stage, means for identifying schedules requiring further optimization, and means for inputting such schedules into a further iteration of the second stage for further optimization, the further iteration of the second stage having means to treat the schedules not so identified as fixed.
Claim 9
Dependent Claim
91 words
Apparatus as in claim 1 wherein the schedule modifying means comprises: a plurality of selection means, each for assessing in turn the plurality of tasks waiting to be performed to determine if a task of a given priority suitable for performance by the first resource is available, and allocating such a task to the first resource, the selection means being arranged to identify tasks of successively descending priority, such that tasks of high priority are allocated in preference to lower priority tasks in the initial optimized schedule for the first resource.
Claim 10
Dependent Claim
79 words
Apparatus as in claim 8 , wherein at least one of the selection means comprises: first assessment means for determining if the initial optimized schedule of the first resource includes a task of the given priority, and selecting said task if present, and second assessment means, operable if the initial optimized schedule of the first resource does not contain such a task, for determining if a task exists which has not been scheduled, and selecting said task if present.
Claim 11
Dependent Claim
230 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial schedule to instruct a user; storage means for storing the initial schedules; updating means for receiving, from the input means, updated information relating to the tasks and resources, the updated information being received by the input means from a source external to the apparatus during a period of time in which tasks allocated in the initial schedule are performed; on-line modifying means for modifying the initial schedule of at least a first resource in response to such updated information to generate at least one modified schedule; whereby changes to the initial schedules may be made in response to such updated information in real time, independently of the schedule generation means; wherein the schedule modifying means comprises means to identify resources having characteristics related to those of the first resource, and arranged to modify the schedules of only those resources having such characteristics in response to the updated information; and the initial schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified schedule generated by the on-line modifying means reacts to said updated information.
Claim 12
Dependent Claim
230 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial schedule to instruct a user; storage means for storing the initial schedules; updating means for receiving, from the input means, updated information relating to the tasks and resources, the updated information being received by the input means from a source external to the apparatus during a period of time in which tasks allocated in the initial schedule are performed; on-line modifying means for modifying the initial schedule of at least a first resource in response to such updated information to generate at least one modified schedule; whereby changes to the initial schedules may be made in response to such updated information in real time, independently of the schedule generation means; wherein the schedule modifying means comprises means to identify resources having characteristics related to those of the first resource, and arranged to modify the schedules of only those resources having such characteristics in response to the updated information; and the initial schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified schedule generated by the on-line modifying means reacts to said updated information.
Claim 13
Dependent Claim
244 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks during a given period; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storage means for storing the initial complete schedule, updating means for receiving, from the input means, updated information relating to the tasks and resources for said given period, the updated information being received by the input means during said given period from a source external to the apparatus, on-line modifying means for modifying the initial complete schedule of at least a first resource in response to such updated information to generate at least one modified complete schedule, whereby changes to the initial complete schedule may be made in response to such updated information in real time, independently of the schedule generation means; means for adding in real time, after generation of the initial schedule and during said given period, further tasks and/or resources to the plurality of tasks and/or resources to be scheduled; and wherein the initial complete schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified complete schedule generated by the on-line modifying means reacts to said updated information.
Claim 14
Dependent Claim
244 words
A task-allocation apparatus comprising: input means for providing information relating to tasks to be allocated and resources available to perform the tasks during a given period; off-line schedule generation means to allocate the resources to the tasks, thereby generating, for each resource, an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storage means for storing the initial complete schedule, updating means for receiving, from the input means, updated information relating to the tasks and resources for said given period, the updated information being received by the input means during said given period from a source external to the apparatus, on-line modifying means for modifying the initial complete schedule of at least a first resource in response to such updated information to generate at least one modified complete schedule, whereby changes to the initial complete schedule may be made in response to such updated information in real time, independently of the schedule generation means; means for adding in real time, after generation of the initial schedule and during said given period, further tasks and/or resources to the plurality of tasks and/or resources to be scheduled; and wherein the initial complete schedule is generated by the off-line schedule generation means without reacting to any change in input information provided to the off-line schedule generation means, whereas the modified complete schedule generated by the on-line modifying means reacts to said updated information.
Claim 15
Independent Claim
202 words
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 during a given period, generating, off-line, for each resource an initial complete schedule to allocate the resources to the tasks covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storing the initial complete schedule, providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer, and modifying, on-line, the initial complete schedule of at least a first resource in response to such updated information to generate a modified complete schedule, whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial complete schedule; and the initial complete schedule is generated without reacting to any change in the initial information used to generate the initial complete schedule, whereas the modified complete schedule is generated by reacting to said updated information.
Claim 16
Independent Claim
202 words
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 during a given period, generating, off-line, for each resource an initial complete schedule to allocate the resources to the tasks covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storing the initial complete schedule, providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer, and modifying, on-line, the initial complete schedule of at least a first resource in response to such updated information to generate a modified complete schedule, whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial complete schedule; and the initial complete schedule is generated without reacting to any change in the initial information used to generate the initial complete schedule, whereas the modified complete schedule is generated by reacting to said updated information.
Claim 17
Dependent Claim
38 words
Method as in claim 12 , wherein initial complete schedules are generated periodically, and the initial complete schedules so generated are modified in response to the receipt of data between such periodic generation of the initial complete schedules.
Claim 18
Independent Claim
244 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules; during the periodic generation of the initial schedules the modification process is suspended, the updated information being retained until the new initial schedules are generated, and then used to modify the initial schedules when their generation is complete; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 19
Independent Claim
244 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules; during the periodic generation of the initial schedules the modification process is suspended, the updated information being retained until the new initial schedules are generated, and then used to modify the initial schedules when their generation is complete; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 20
Independent Claim
235 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules; wherein during the generation of the initial schedules the modification process continues, the schedules so modified being input as modifications to the initial schedules when their generation is complete; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 21
Independent Claim
235 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules; wherein during the generation of the initial schedules the modification process continues, the schedules so modified being input as modifications to the initial schedules when their generation is complete; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 22
Dependent Claim
20 words
Method as in claim 12 wherein the schedule generation process is initiated if a substantial update data item is received.
Claim 23
Dependent Claim
43 words
Method as in claim 12 wherein the schedule generation function comprises: a first deterministic stage for scheduling selected tasks, and a second optimization stage for scheduling the remaining tasks, wherein the second stage treats the tasks scheduled by the first stage as fixed.
Claim 24
Dependent Claim
33 words
Method as in claim 17 in which groups of linked tasks involving more than one of the resources, or forming a sequence of tasks are selected for scheduling by the first, deterministic, stage.
Claim 25
Dependent Claim
15 words
Method as in claim 17 wherein the second stage operates according to a stochastic process.
Claim 26
Dependent Claim
15 words
Method as in claim 19 , wherein the stochastic process is a Simulated Annealing process.
Claim 27
Dependent Claim
63 words
Method as in claim 17 wherein the schedule generation function comprises a third, post-optimization stage, in which the schedules created by the second stage are analyzed to identify schedules requiring further optimization, and such schedules are input into a further iteration of the second stage for further optimization, the further iteration of the second stage treating as fixed the schedules not so identified.
Claim 28
Dependent Claim
106 words
Method as in claim 12 wherein the schedule modifying process comprises a plurality of selection steps, in each of which: the plurality of tasks waiting to be performed is assessed to determine if a task of a given priority suitable for performance by the first resource is available, and such a task is allocated to the first resource if identified, the selection steps each being arranged to identify tasks of successively descending priority, such that a task of high priority is allocated in preference to one of lower priority, whether or not the high priority task is in the initial optimized schedule for the first resource.
Claim 29
Dependent Claim
69 words
Method as in claim 22 , wherein at least one of the selection steps: first determines whether the initial optimized schedule of the resource includes a task of the given priority, and selects said task if present or, if the initial optimized schedule of the resource does not contain such a task, determines if a task exists which has not been scheduled, and selects such a task if present.
Claim 30
Independent Claim
204 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein the schedule modification function identifies resources having characteristics related to those of the first resource, and modifies the schedules of only those resources having such characteristics; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 31
Independent Claim
204 words
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 during a given period; generating, off-line, for each resource, an initial schedule to allocate the resources to the tasks to instruct a user; storing the initial schedules; providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer; modifying, on-line, the initial schedule of at least a first resource in response to such updated information to generate a modified schedule; whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial schedules; wherein the schedule modification function identifies resources having characteristics related to those of the first resource, and modifies the schedules of only those resources having such characteristics; and the initial schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified schedule is generated by reacting to said updated information.
Claim 32
Independent Claim
221 words
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 during a given period, generating, off-line, for each resource an initial complete schedule to allocate the resources to the tasks covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storing the initial complete schedule, providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer, modifying, on-line, the initial complete schedule of at least a first resource in response to such updated information to generate a modified complete schedule, whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial complete schedule; wherein further tasks may be added to the plurality of tasks to be performed after generation of the initial optimized schedule; and the initial complete schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified complete schedule is generated by reacting to said updated information.
Claim 33
Independent Claim
221 words
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 during a given period, generating, off-line, for each resource an initial complete schedule to allocate the resources to the tasks covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, storing the initial complete schedule, providing updated information relating to the tasks and resources received by the computer during said given period from a source external to the computer, modifying, on-line, the initial complete schedule of at least a first resource in response to such updated information to generate a modified complete schedule, whereby changes to individual schedules may be made in response to such updated information in real time and independently of the process of generating the initial complete schedule; wherein further tasks may be added to the plurality of tasks to be performed after generation of the initial optimized schedule; and the initial complete schedule is generated without reacting to any change in the initial information used to generate the initial schedule, whereas the modified complete schedule is generated by reacting to said updated information.
Claim 34
Dependent Claim
222 words
A computer apparatus for allocating a plurality of tasks to a plurality of resources during a given period, 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 generate, off-line, and store an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, based on predicted availability of resources, task priorities, and suitability of tasks to resources, the initial complete schedule being generated without reacting to any change in input information used to generate the initial complete schedule and performing the following steps: when a resource becomes available, assessing, on-line, the plurality of tasks waiting to be performed in real time, to determine if a high priority task suitable for performance by the resource is available, and, if so, allocating it to the resource; if no such task is available for the resource to perform, assessing the next task on the resource's initial complete schedule to determine if it can be performed, and allocating it to the resource if it can be performed; if said next task is not available for the resource to perform, allocating to the resource a lower priority task from the plurality of tasks.
Claim 35
Dependent Claim
222 words
A computer apparatus for allocating a plurality of tasks to a plurality of resources during a given period, 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 generate, off-line, and store an initial complete schedule covering substantially all the then known tasks to be carried out during the period under consideration to instruct a user, based on predicted availability of resources, task priorities, and suitability of tasks to resources, the initial complete schedule being generated without reacting to any change in input information used to generate the initial complete schedule and performing the following steps: when a resource becomes available, assessing, on-line, the plurality of tasks waiting to be performed in real time, to determine if a high priority task suitable for performance by the resource is available, and, if so, allocating it to the resource; if no such task is available for the resource to perform, assessing the next task on the resource's initial complete schedule to determine if it can be performed, and allocating it to the resource if it can be performed; if said next task is not available for the resource to perform, allocating to the resource a lower priority task from the plurality of tasks.
Claim 36
Dependent Claim
54 words
Apparatus as in claim 10 wherein the schedule generation means is arranged to periodically generate initial schedules according to the data received by the input means, and the modifying means is arranged to make changes to the initial schedules in response to the receipt of data between such periodic generation of the initial schedules.
Claim 37
Dependent Claim
55 words
Apparatus as in claim 10 wherein the schedule generation means comprises: a first, deterministic, stage; means for selecting tasks which are to be scheduled by the first stage; and a second, optimization, stage for scheduling the remaining tasks; wherein the second stage includes means to treat the tasks scheduled by the first stage as fixed.
Claim 38
Dependent Claim
38 words
Apparatus as in claim 28 wherein the means for selecting tasks for scheduling by the first stage is arranged to select groups of linked tasks involving more than one of the resources, or forming a sequence of tasks.
Claim 39
Dependent Claim
15 words
Apparatus as in claim 28 wherein the second stage operates according to a stochastic process.
Claim 40
Dependent Claim
14 words
Apparatus as in claim 30 wherein the stochastic process is a Simulated Annealing process.
Claim 41
Dependent Claim
68 words
Apparatus as in claim 28 wherein the schedule generation means comprises a third, post-optimization stage, comprising means for analyzing the schedules created by the second stage, means for identifying schedules requiring further optimization, and means for inputting such schedules into a further iteration of the second stage for further optimization, the further iteration of the second stage having means to treat the schedules not so identified as fixed.
Claim 42
Dependent Claim
91 words
Apparatus as in claim 10 wherein the schedule modifying means comprises a plurality of selection means, each for assessing in turn the plurality of tasks waiting to be performed to determine if a task of a given priority suitable for performance by the first resource is available, and allocating such a task to the first resource, the selection means being arranged to identify tasks of successively descending priority, such that tasks of high priority are allocated in preference to lower priority tasks in the initial optimized schedule for the first resource.
Claim 43
Dependent Claim
78 words
Apparatus as in claim 33 wherein at least one of the selection means comprises first assessment means for determining if the initial optimized schedule of the first resource includes a task of the given priority, and selecting said task if present, and second assessment means, operable if the initial optimized schedule of the first resource does not contain such a task, for determining if a task exists which has not been scheduled, and selecting said task if present.
Claim 44
Dependent Claim
31 words
Apparatus as in claim 10 further comprising means for adding, after generation of the initial optimized schedule, further tasks and/or resources to the plurality of tasks and/or resources to be scheduled.
Claim 45
Dependent Claim
34 words
Method as in claim 14 wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules.
Claim 46
Dependent Claim
20 words
Method as in claim 14 wherein the schedule generation process is initiated if a substantial update data item is received.
Claim 47
Dependent Claim
43 words
Method as in claim 14 wherein the schedule generation function comprises a first deterministic stage for scheduling selected tasks, and a second optimization stage for scheduling the remaining tasks, wherein the second stage treats the tasks scheduled by the first stage as fixed.
Claim 48
Dependent Claim
33 words
Method as in claim 38 in which groups of linked tasks involving more than one of the resources, or forming a sequence of tasks are selected for scheduling by the first, deterministic, stage.
Claim 49
Dependent Claim
15 words
Method as in claim 38 wherein the second stage operates according to a stochastic process.
Claim 50
Dependent Claim
14 words
Method as in claim 40 wherein the stochastic process is a Simulated Annealing process.
Claim 51
Dependent Claim
63 words
Method as in claim 38 wherein the schedule generation function comprises a third, post-optimization stage, in which the schedules created by the second stage are analyzed to identify schedules requiring further optimization, and such schedules are input into a further iteration of the second stage for further optimization, the further iteration of the second stage treating as fixed the schedules not so identified.
Claim 52
Dependent Claim
106 words
Method as in claim 14 wherein the schedule modifying process comprises a plurality of selection steps, in each of which the plurality of tasks waiting to be performed is assessed to determine if a task of a given priority suitable for performance by the first resource is available, and such a task is allocated to the first resource if identified, the selection steps each being arranged to identify tasks of successively descending priority, such that a task of high priority is allocated in preference to one of lower priority, whether or not the high priority task is in the initial optimized schedule for the first resource.
Claim 53
Dependent Claim
68 words
Method as in claim 43 wherein at least one of the selection steps first determines whether the initial optimized schedule of the resource includes a task of the given priority, and selects said task if present or, if the initial optimized schedule of the resource does not contain such a task, determines if a task exists which has not been scheduled, and selects such a task if present.
Claim 54
Dependent Claim
26 words
Method as in claim 14 wherein further tasks may be added to the plurality of tasks to be performed after generation of the initial optimized schedule.
Claim 55
Dependent Claim
34 words
Method as in claim 15 wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules.
Claim 56
Dependent Claim
20 words
Method as in claim 15 wherein the schedule generation process is initiated if a substantial update data item is received.
Claim 57
Dependent Claim
43 words
Method as in claim 15 wherein the schedule generation function comprises a first deterministic stage for scheduling selected tasks, and a second optimization stage for scheduling the remaining tasks, wherein the second stage treats the tasks scheduled by the first stage as fixed.
Claim 58
Dependent Claim
33 words
Method as in claim 48 in which groups of linked tasks involving more than one of the resources, or forming a sequence of tasks are selected for scheduling by the first, deterministic, stage.
Claim 59
Dependent Claim
15 words
Method as in claim 48 wherein the second stage operates according to a stochastic process.
Claim 60
Dependent Claim
14 words
Method as in claim 50 wherein the stochastic process is a Simulated Annealing process.
Claim 61
Dependent Claim
63 words
Method as in claim 48 wherein the schedule generation function comprises a third, post-optimization stage, in which the schedules created by the second stage are analyzed to identify schedules requiring further optimization, and such schedules are input into a further iteration of the second stage for further optimization, the further iteration of the second stage treating as fixed the schedules not so identified.
Claim 62
Dependent Claim
106 words
Method as in claim 15 wherein the schedule modifying process comprises a plurality of selection steps, in each of which the plurality of tasks waiting to be performed is assessed to determine if a task of a given priority suitable for performance by the first resource is available, and such a task is allocated to the first resource if identified, the selection steps each being arranged to identify tasks of successively descending priority, such that a task of high priority is allocated in preference to one of lower priority, whether or not the high priority task is in the initial optimized schedule for the first resource.
Claim 63
Dependent Claim
68 words
Method as in claim 53 wherein at least one of the selection steps first determines whether the initial optimized schedule of the resource includes a task of the given priority, and selects said task if present or, if the initial optimized schedule of the resource does not contain such a task, determines if a task exists which has not been scheduled, and selects such a task if present.
Claim 64
Dependent Claim
26 words
Method as in claim 15 wherein further tasks may be added to the plurality of tasks to be performed after generation of the initial optimized schedule.
Claim 65
Dependent Claim
34 words
Method as in claim 24 wherein initial schedules are generated periodically, and the initial schedules so generated are modified in response to the receipt of data between such periodic generation of the initial schedules.
Claim 66
Dependent Claim
20 words
Method as in claim 24 wherein the schedule generation process is initiated if a substantial update data item is received.
Claim 67
Dependent Claim
43 words
Method as in claim 24 wherein the schedule generation function comprises a first deterministic stage for scheduling selected tasks, and a second optimization stage for scheduling the remaining tasks, wherein the second stage treats the tasks scheduled by the first stage as fixed.
Claim 68
Dependent Claim
33 words
Method as in claim 58 in which groups of linked tasks involving more than one of the resources, or forming a sequence of tasks are selected for scheduling by the first, deterministic, stage.
Claim 69
Dependent Claim
15 words
Method as in claim 58 wherein the second stage operates according to a stochastic process.
Claim 70
Dependent Claim
14 words
Method as in claim 60 wherein the stochastic process is a Simulated Annealing process.
Claim 71
Dependent Claim
63 words
Method as in claim 58 wherein the schedule generation function comprises a third, post-optimization stage, in which the schedules created by the second stage are analyzed to identify schedules requiring further optimization, and such schedules are input into a further iteration of the second stage for further optimization, the further iteration of the second stage treating as fixed the schedules not so identified.
Claim 72
Dependent Claim
106 words
Method as in claim 24 wherein the schedule modifying process comprises a plurality of selection steps, in each of which the plurality of tasks waiting to be performed is assessed to determine if a task of a given priority suitable for performance by the first resource is available, and such a task is allocated to the first resource if identified, the selection steps each being arranged to identify tasks of successively descending priority, such that a task of high priority is allocated in preference to one of lower priority, whether or not the high priority task is in the initial optimized schedule for the first resource.
Claim 73
Dependent Claim
68 words
Method as in claim 63 wherein at least one of the selection steps first determines whether the initial optimized schedule of the resource includes a task of the given priority, and selects said task if present or, if the initial optimized schedule of the resource does not contain such as task, determines if a task exists which has not been scheduled, and selects such a task if present.
Claim 74
Dependent Claim
26 words
Method as in claim 24 wherein further tasks may be added to the plurality of tasks to be performed after generation of the initial optimized schedule.
Claim 75
Dependent Claim
57 words
Apparatus as in claim 11 wherein: the schedule generation means is arranged to periodically generate an initial complete schedule according to data received by the input means, and the modifying means is arranged to make changes to the initial complete schedule in response to the receipt of data between such periodic generation of the initial complete schedule.
Claim 76
Dependent Claim
55 words
Apparatus as in claim 11 wherein the schedule generation means comprises: a first, deterministic, stage; means for selecting tasks which are to be scheduled by the first stage; and a second, optimization, stage for scheduling the remaining tasks, wherein the second stage includes means to treat the tasks scheduled by the first stage as fixed.
Claim 77
Dependent Claim
38 words
Apparatus as in claim 67 wherein the means for selecting tasks for scheduling by the first stage is arranged to select groups of linked tasks involving more than one of the resources, or forming a sequence of tasks.
Claim 78
Dependent Claim
15 words
Apparatus as in claim 67 wherein the second stage operates according to a stochastic process.
Claim 79
Dependent Claim
14 words
Apparatus as in claim 69 wherein the stochastic process is a Simulated Annealing process.
Claim 80
Dependent Claim
68 words
Apparatus as in claim 67 wherein the schedule generation means comprises a third, post-optimization stage, comprising: means for analyzing the schedules created by the second stage, means for identifying schedules requiring further optimization, and means for inputting such schedules into a further iteration of the second stage for further optimization, the further iteration of the second stage having means to treat the schedules not so identified as fixed.
Claim 81
Dependent Claim
91 words
Apparatus as in claim 11 wherein the schedule modifying means comprises: a plurality of selection means, each for assessing in turn the plurality of tasks waiting to be performed to determine if a task of a given priority suitable for performance by the first resource is available, and allocating such a task to the first resource, the selection means being arranged to identify tasks of successively descending priority, such that tasks of high priority are allocated in preference to lower priority tasks in the initial optimized schedule for the first resource.
Claim 82
Dependent Claim
78 words
Apparatus as in claim 72 wherein at least one of the selection means comprises: first assessment means for determining if the initial optimized schedule of the first resource includes a task of the given priority, and selecting said task if present, and second assessment means, operable if the initial optimized schedule of the first resource does not contain such a task, for determining if a task exists which has not been schedule, and selecting said task if present.
Claim 83
Dependent Claim
43 words
Apparatus as in claim 11 wherein the schedule modifying means comprises means to identify resources having characteristics related to those of the first resource, and arranged to modify the schedules of only those resources having such characteristics in response to the updated information.
Claim 84
Dependent Claim
37 words
Method as in claim 25 wherein initial complete schedules are generated periodically, and the initial complete schedules so generated are modified in response to the receipt of data between such periodic generation of the initial complete schedules.
Claim 85
Dependent Claim
44 words
Method as in claim 25 wherein during the periodic generation of the initial schedules the modification process is suspended, the updated information being retained until the new initial schedules are generated, and then used to modify the initial schedules when their generation is complete.
Claim 86
Dependent Claim
33 words
Method as in claim 25 wherein during generation of the initial schedules the modification process continues, the schedules so modified being input as modifications to the initial schedules when their generation is complete.
Claim 87
Dependent Claim
20 words
Method as in claim 25 wherein the schedule generation process is initiated if a substantial update data item is received.
Claim 88
Dependent Claim
43 words
Method as in claim 25 wherein the schedule generation function comprises: a first deterministic stage for scheduling selected tasks, and a second optimization stage for scheduling the remaining tasks, wherein the second stage treats the tasks scheduled by the first stage as fixed.
Claim 89
Dependent Claim
33 words
Method as in claim 79 in which groups of linked tasks involving more than one of the resources, or forming a sequence of tasks are selected for scheduling by the first, deterministic, stage.
Claim 90
Dependent Claim
15 words
Method as in claim 79 wherein the second stage operates according to a stochastic process.
Claim 91
Dependent Claim
14 words
Method as in claim 81 wherein the stochastic process is a Simulated Annealing process.
Claim 92
Dependent Claim
63 words
Method as in claim 79 wherein the schedule generation function comprises a third, post-optimization stage, in which the schedules created by the second stage are analyzed to identify schedules requiring further optimization, and such schedules are input into a further iteration of the second stage for further optimization, the further iteration of the second stage treating as fixed the schedules not so identified.
Claim 93
Dependent Claim
106 words
Method as in claim 25 wherein the schedule modifying process comprises a plurality of selection steps, in each of which: the plurality of tasks waiting to be performed is assessed to determine if a task of a given priority suitable for performance by the first resource is available, and such a task is allocated to the first resource if identified, the selection steps each being arranged to identify tasks of successively descending priority, such that a task of high priority is allocated in preference to one of lower priority, whether or not the high priority task is in the initial optimized schedule for the first resource.
Claim 94
Dependent Claim
68 words
Method as in claim 84 wherein at least one of the selection steps: first determines whether the initial optimized schedule of the resource includes a task of the given priority, and selects said task if present or, if the initial optimized schedule of the resource does not contain such a task, determines if a task exists which has not been schedule, and selects such a task if present.
Claim 95
Independent Claim
179 words
A method of using a computer system to assign resources to perform tasks, the method comprising: receiving first data relating to tasks and resources to perform the tasks; generating, off-line, a first schedule based on the first data, the first schedule initially assigning the resources to perform the tasks during a given time period; outputting the first schedule to a user before said given time period begins; receiving second data relating at least to a task from a source external to the computer system and after the first schedule has been generated; generating, on-line, a second schedule based on at least the second data in real time, the second schedule assigning the resources to perform the tasks during the given time period in a manner at least partially different than the first schedule; outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to any change to the first data, whereas the second schedule is generated by reacting to changes to the second data in real time.
Claim 96
Independent Claim
179 words
A method of using a computer system to assign resources to perform tasks, the method comprising: receiving first data relating to tasks and resources to perform the tasks; generating, off-line, a first schedule based on the first data, the first schedule initially assigning the resources to perform the tasks during a given time period; outputting the first schedule to a user before said given time period begins; receiving second data relating at least to a task from a source external to the computer system and after the first schedule has been generated; generating, on-line, a second schedule based on at least the second data in real time, the second schedule assigning the resources to perform the tasks during the given time period in a manner at least partially different than the first schedule; outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to any change to the first data, whereas the second schedule is generated by reacting to changes to the second data in real time.
Claim 97
Dependent Claim
24 words
A method as in claim 86 , wherein the second schedule is generated by modifying the first schedule and without re-generating the first schedule.
Claim 98
Dependent Claim
21 words
A method as in claim 86 , wherein the second data is received by the computer system through a manual interface.
Claim 99
Dependent Claim
23 words
A method as in claim 86 , wherein the second data is received by the computer system through input from an electronic device.
Claim 100
Dependent Claim
28 words
A method as in claim 86 , wherein the task represented by the second data is not represented by any of the tasks represented by the first data.
Claim 101
Dependent Claim
22 words
A method as in claim 86 , wherein the second data is received during said given time period that tasks are performed.
Claim 102
Independent Claim
173 words
A method of using a computer system to instruct a user, the method comprising: generating, off-line, a first schedule assigning a user to perform a plurality of tasks during a given period; outputting the first schedule to instruct the user to perform the plurality of tasks; receiving data in real time relating to another task, the another task not previously included in the plurality of tasks, from a source external to the computer system after the first schedule has been generated; generating, on-line and in real time, a second schedule based on at least the data relating to the another task, the second schedule assigning the tasks to be performed by the user in a manner at least partially different than the first schedule; outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to changes in data used to generate the first schedule whereas the second schedule is generated by reacting to changes in the data received in real time.
Claim 103
Independent Claim
173 words
A method of using a computer system to instruct a user, the method comprising: generating, off-line, a first schedule assigning a user to perform a plurality of tasks during a given period; outputting the first schedule to instruct the user to perform the plurality of tasks; receiving data in real time relating to another task, the another task not previously included in the plurality of tasks, from a source external to the computer system after the first schedule has been generated; generating, on-line and in real time, a second schedule based on at least the data relating to the another task, the second schedule assigning the tasks to be performed by the user in a manner at least partially different than the first schedule; outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to changes in data used to generate the first schedule whereas the second schedule is generated by reacting to changes in the data received in real time.
Claim 104
Dependent Claim
25 words
A method as in claim 92 , wherein the second schedule is output to the user upon receipt of an on-line request from the user.
Claim 105
Dependent Claim
21 words
A method as in claim 92 , wherein the received data is received during said given period that tasks are performed.
Claim 106
Independent Claim
195 words
A method of using a computer system to assign resources to perform tasks, the method comprising: receiving first data relating to tasks and resources to perform the tasks; generating, off-line, a first schedule based on the first data, the first schedule initially assigning the resources to perform the tasks during a given time period; outputting the first schedule to a user before said given time period has begun; receiving second data relating at least to a task from a source external to the computer system and after said given time period has begun, the second data reflecting real time circumstances; generating, on-line, a second schedule based on at least the second data in real time, the second schedule assigning the resources to perform the tasks represented by the first and second data during the given time period in a manner at least partially, different than the first schedule; and outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to any change to the first data, whereas the second schedule is generated by reacting to changes to the second data in real time.
Claim 107
Independent Claim
195 words
A method of using a computer system to assign resources to perform tasks, the method comprising: receiving first data relating to tasks and resources to perform the tasks; generating, off-line, a first schedule based on the first data, the first schedule initially assigning the resources to perform the tasks during a given time period; outputting the first schedule to a user before said given time period has begun; receiving second data relating at least to a task from a source external to the computer system and after said given time period has begun, the second data reflecting real time circumstances; generating, on-line, a second schedule based on at least the second data in real time, the second schedule assigning the resources to perform the tasks represented by the first and second data during the given time period in a manner at least partially, different than the first schedule; and outputting the second schedule to the user after said given period has begun; and wherein the first schedule is generated without reacting to any change to the first data, whereas the second schedule is generated by reacting to changes to the second data in real time.
Claim 108
Dependent Claim
32 words
An apparatus as in claim 1 , wherein the initial complete schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified complete schedule.
Claim 109
Dependent Claim
30 words
An apparatus as in claim 10 , wherein the initial schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified schedule.
Claim 110
Dependent Claim
32 words
An apparatus as in claim 11 , wherein the initial complete schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified complete schedule.
Claim 111
Dependent Claim
31 words
The method as in claim 12 wherein the initial complete schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified complete schedule.
Claim 112
Dependent Claim
29 words
The method as in claim 14 wherein the initial schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified schedule.
Claim 113
Dependent Claim
29 words
The method as in claim 15 wherein the initial schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified schedule.
Claim 114
Dependent Claim
29 words
The method as in claim 24 wherein the initial schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified schedule.
Claim 115
Dependent Claim
31 words
The method as in claim 25 wherein the initial complete schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the modified complete schedule.
Claim 116
Dependent Claim
40 words
An apparatus as in claim 26 , wherein the initial complete schedule is generated with a comparatively more rigorous computer process than a computer process used to assess, on-line, the plurality of tasks waiting to be performed in real time.
Claim 117
Dependent Claim
29 words
The method as in claim 86 wherein the first schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the second schedule.
Claim 118
Dependent Claim
29 words
The method as in claim 92 wherein the first schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the second schedule.
Claim 119
Dependent Claim
29 words
The method as in claim 95 wherein the first schedule is generated with a comparatively more rigorous computer process than a computer process used to generate the second schedule.
References Cited (Backward Citations)
US5260868A
Cited
US5524077A
Cited
US5111391A
Cited
US5343388A
Cited
US5467268A
Cited
US5943652A
Cited
WO1995026535A1
Cited
EP0678818A1
Cited
US5799286A
Cited
EP0938714A1
Cited
US5923552A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-09 | 2006-12-09 | 2007-06-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-09 | 2010-12-09 | 2011-06-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-09 | 2014-12-09 | 2015-06-10 | $7700.00 | Window Closed / Lapsed |