Resource scheduling method and system

• US 20070021998A1
• Filed: 06/27/2006
• Published: 01/25/2007
• Est. Priority Date: 06/27/2005
• Status: Active Grant

• Current Assignee: Trimble MRM Ltd. (Trimble Inc.)
• Original Assignee: Roads Corporation
• Inventors: Spragg, Jon, Keuthen, Ralf, Laithwaite, Bob
• Granted Patent: US 8,225,319 B2
• Time in Patent Office: Days
• US Class Current: 705/9
• 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/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change

Abstract

Embodiments of the invention are concerned with scheduling resources to perform tasks requiring a plurality of capabilities or capabilities and capacities, and has particular application to highly changeable or uncertain environments in which the status and the composition of tasks and/or resources changes frequently. Embodiments provide a method for use in a scheduling process for scheduling allocation of resources to a task, each resource having a plurality of attributes, wherein the task has one or more operational constraints including a required plurality of capabilities, and a performance condition associated therewith. The method comprises: receiving data indicative of a change to the status of the scheduling process; in response to receipt of the status data, reviewing the attributes of individual resources so as to identify combinations of resources able to collectively satisfy said capability requirements of the task; evaluating each identified combination of resources in accordance with a performance algorithm so as to identify an associated performance cost; selecting a combination of resources whose identified performance cost meets the performance condition; and scheduling said task on the basis of said selected combination of resources. In embodiments of this aspect of the invention, changes to resource configurations are effected as part of the scheduling process. These changes can be made dynamically, in response to the occurrence of events that have a bearing on the scheduling process, and involve aggregating resources together so as to create, essentially, a new resource pool from which selection can be made.

Claims

1. A method for use in a scheduling process for scheduling allocation of resources to a task, each resource having a plurality of attributes, the task having one or more operational constraints including a required plurality of capabilities, and having a performance condition associated therewith, the method comprising:

receiving data indicative of a change to the status of the scheduling process;

in response to receipt of the status data, reviewing the attributes of individual resources so as to identify combinations of resources able to collectively satisfy said capability requirements of the task;

evaluating each identified combination of resources in accordance with a performance algorithm so as to identify an associated performance cost;

selecting a combination of resources whose identified performance cost meets the performance condition; and

scheduling said task on the basis of said selected combination of resources.

2. A method according to claim 1, in which the scheduling process is performed in relation to a set of two or more tasks, individual tasks within the set being interrelated by one or more said operational constraints.

3. A method according to claim 2, including identifying temporal dependencies between said individual tasks and ordering the individual tasks in accordance with said temporal dependencies.

4. A method according to claim 3, including identifying individual tasks having comparable start time requirements and creating associations between individual tasks having comparable start times, said ordering being performed in respect of such associations.

5. A method according to claim 4, in which said step of reviewing the attributes of individual resources so as to identify combinations of resources able to collectively satisfy said capability requirements of the set of tasks is performed in respect of at least one said association of individual tasks.

6. A method according to claim 5, in which said reviewing step is performed in respect of respective associations of tasks, in an order dependent on the ordering of said associations.

7. A method according to claim 5, including selecting a group of individual resources and comparing attributes of the selected group in relation to attributes of tasks within respective associations, in order to identify said combinations.

8. A method according to claim 1, in which the operational constraints comprise a first type of constraint and a second type of constraint, the method including identifying said individual resources from the plurality on the basis of attributes of the plurality of resources satisfying the first type of constraint.

9. A method according to claim 8, in which the first type of constraint comprises temporal constraints, the method including identifying individual resources on the basis of resource availability satisfying said temporal constraints.

10. A method according to claim 1, including reviewing resource availability in relation to temporal constraints associated with the, or each, task in order to identify said individual resources.

11. A method according to claim 1, including selecting groups of individual resources and comparing attributes of the selected group and attributes of the or each task in order to identify said combinations.

12. A method according to claim 1, including aggregating individual resources so as to create a group of individual resources, individual resources being added to the group on the basis of the attributes of the individual resources and attributes of the, or each, task, thereby identifying said combinations.

13. A method according to claim 1, including, for each identified combination, evaluating the number of capabilities collectively available, and applying a score indicative of said evaluated number of capabilities, said performance condition being dependent on the score.

14. A method according to claim 1, including receiving data indicative of the scheduling process having started, receipt of said data triggering the method.

15. A method according to claim 1, including receiving data indicative of available resource capacity failing to satisfy an operational constraint associated with the task, receipt of said data triggering the method.

16. A method according to claim 1, including receiving data indicative of a change associated with a resource currently allocated to perform the task, receipt of said data triggering the method.

17. A method according to claim 1, including receiving data indicative of a change to the task, receipt of said data triggering the method.

18. A method according to claim 1, including using the selected combination to create a schedule.

19. A method according to claim 1, including using the selected combination to modify an existing schedule.

20. A method according to claim 1, including using the selected combination to complete a partially complete schedule.

21. A method according to claim 1, in which at least one of said individual resources comprises a combination of resources.

22. A method according to claim 1, including assigning data, to the combined resources, indicative of the combination being temporary, for use in subsequently separating the combination.

23. A method according to claim 1, in which the operational constraints include a required plurality of capacities, and in which the attributes of individual resources are reviewed so as to identify combinations of resources able to collectively satisfy said capacity requirement of the task

40. A computer program, or a suite of computer programs, comprising a set of instructions for use in controlling operation of a processor, or a suite of processors, according to claim 1.

24. A method of scheduling resources to a plurality of tasks so as to create a schedule specifying resources allocated to at least some said tasks, each resource having a plurality of attributes and each task having one or more capability requirements, the resource schedule having a performance condition associated therewith, the method comprising:

for each of the tasks, identifying a plurality of resources capable of performing the task on the basis of attributes corresponding to said plurality of resources satisfying the capability requirements of the task and in dependence on two or more selection criteria, thereby generating a selection of potential resource assignments;

evaluating at least two resource assignments from the selection in accordance with a performance algorithm so as to identify an associated performance cost; and

scheduling resources to perform each of said at least some tasks on the basis of respective performance costs satisfying the performance condition.

30. A method according to claim 24, including reviewing the attributes of individual resources so as to identify combinations of resources able to collectively satisfy said capability requirements of the task prior to selecting resources on the basis of said selection criteria.

41. A computer program, or a suite of computer programs, comprising a set of instructions for use in controlling operation of a processor, or a suite of processors, according to claim 24.

25. A method of scheduling resources to a set of a plurality of tasks so as to create a schedule specifying resources allocated to at least some said tasks in the set, each resource having a plurality of attributes and each task having one or more operational constraints including one or more capability requirements, the resource schedule having a performance condition associated therewith, the method comprising:

for each of at least some of the tasks in the set, performing a process comprising;

identifying a plurality of resources capable of performing the task on the basis of attributes corresponding to said plurality of resources satisfying the operational constraints of the task;

selecting one or more identified resources on the basis of two or more selection criteria,

thereby generating a selection of potential resource assignments in respect of the set of tasks;

evaluating at least two resource assignments from the selection in accordance with a performance algorithm so as to identify an associated performance cost; and

scheduling a resource to perform each of said at least some tasks on the basis of respective performance costs satisfying the performance condition.

26. A method according to claim 25, in which the operational constraints include inter-task dependencies, the method including ordering the tasks within the set in accordance with said inter-task dependencies.

27. A method according to claim 26, in which said inter-task dependencies comprise temporal dependencies between said tasks, the method including ordering the tasks in accordance with said temporal dependencies.

28. A method according to claim 27, including identifying tasks having comparable start time requirements and creating associations between individual tasks having comparable start times, said ordering being performed in respect of such associations.

29. A method according to claim 28, in which said step of selecting one or more identified resources on the basis of two or more selection criteria is performed in respect of at least one said association of individual tasks.

31. A processing system for use in scheduling allocation of resources to a task, each resource having a plurality of attributes, the task having one or more operational constraints including a required plurality of capabilities, and having a performance condition associated therewith, the processing system comprising:

a combining function arranged to review the attributes of individual resources so as to identify combinations of resources capable of collectively satisfying said capability requirements of the task, said combining function being responsive to receipt of data indicative of a change to the task and/or a resource; and

an evaluation function arranged to evaluate each identified combination of resources in accordance with a performance algorithm so as to identify an associated performance cost.

32. A processing system according to claim 31, arranged to compare each evaluated combination of resources against the performance condition and to update a schedule in accordance with a combination of resources whose identified performance cost meets the performance condition.

33. A processing system according to claim 32, wherein the processing system is arranged to create or modify schedules corresponding to resources in the combination of resources so as to include data indicative of the or each task.

34. A processing system according to claim 31, including a storage system arranged to store data indicative of said schedules.

35. A processing system according to claim 31, including a receiver arranged to receive data indicative of the tasks.

36. A processing system according to claim 34 wherein, in the event that two or more of the stored schedules includes data indicative of a said task, the processing system is arranged to decompose the combination of resources to which the task has been scheduled and to input data indicative of said change to the task to the combining function.

37. A processing system according to claim 31, wherein the combining function is responsive to receipt of data indicative of an unseen task.

38. A processing system according to claim 31, wherein the combining function is responsive to receipt of data indicative of a task.

39. A processing system according to claim 31, wherein the combining function is responsive to a set of a plurality of tasks, individual tasks within the set being interrelated by one or more said operational constraints.