Method and apparatus for resource allocation when schedule changes are incorporated in real time

• US 6,578,005 B1
• Filed: 03/19/1998
• Issued: 06/10/2003
• Est. Priority Date: 11/22/1996
• Status: Expired due to Term

• Current Assignee: Trimble MRM Ltd. (Trimble Inc.)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Walker, Paul, OʼDonoghue, John J, Noble, Andrew P, Laithwaite, Robert N. W., Lesaint, David, Azarmi, Nader, Alletson, Ian S, Voudouris, Christos
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): ALLEN, AKIBA KANELLE
• Application Number:
  US09/043,423
• Time in Patent Office: 1,909 Days
• Field of Search: 705/8, 705/7, 705/9
• US Class Current: 705/7.14
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/063112 Skill-based matching of a person or a group to a task
• CPC Class Codes: G06Q 10/063116 Schedule adjustment for a person or group
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling

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.

Claims

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

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

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

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

5. Apparatus as in claim 3 wherein the second stage operates according to a stochastic process.

6. Apparatus as in claim 5, wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

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

30. Apparatus as in claim 28 wherein the second stage operates according to a stochastic process.

31. Apparatus as in claim 30 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

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

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

69. Apparatus as in claim 67 wherein the second stage operates according to a stochastic process.

70. Apparatus as in claim 69 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

16. Method as in claim 12 wherein the schedule generation process is initiated if a substantial update data item is received.

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

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

19. Method as in claim 17 wherein the second stage operates according to a stochastic process.

20. Method as in claim 19, wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

37. Method as in claim 14 wherein the schedule generation process is initiated if a substantial update data item is received.

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

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

40. Method as in claim 38 wherein the second stage operates according to a stochastic process.

41. Method as in claim 40 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

47. Method as in claim 15 wherein the schedule generation process is initiated if a substantial update data item is received.

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

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

50. Method as in claim 48 wherein the second stage operates according to a stochastic process.

51. Method as in claim 50 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

57. Method as in claim 24 wherein the schedule generation process is initiated if a substantial update data item is received.

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

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

60. Method as in claim 58 wherein the second stage operates according to a stochastic process.

61. Method as in claim 60 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

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

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

78. Method as in claim 25 wherein the schedule generation process is initiated if a substantial update data item is received.

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

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

81. Method as in claim 79 wherein the second stage operates according to a stochastic process.

82. Method as in claim 81 wherein the stochastic process is a Simulated Annealing process.

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

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

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

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

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

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

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

87. A method as in claim 86, wherein the second schedule is generated by modifying the first schedule and without re-generating the first schedule.

88. A method as in claim 86, wherein the second data is received by the computer system through a manual interface.

89. A method as in claim 86, wherein the second data is received by the computer system through input from an electronic device.

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

91. A method as in claim 86, wherein the second data is received during said given time period that tasks are performed.

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

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

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

94. A method as in claim 92, wherein the received data is received during said given period that tasks are performed.

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

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

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