Resource allocation methods

• US 5,408,663 A
• Filed: 11/05/1993
• Issued: 04/18/1995
• Est. Priority Date: 11/05/1993
• Status: Expired due to Term

• Current Assignee: Gerald Cohen, Harold Roy Miller, Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Adrem Technologies Inc.
• Inventors: Miller, Harold R.
• Primary Examiner(s): Heckler, Thomas M.
• Assistant Examiner(s): Backenstose, Jonathan
• Application Number:
  US08/147,966
• Time in Patent Office: 529 Days
• Field of Search: 395/650, 364/DIG. 1, 364/221.9, 364/281.3, 364/281.8, 364/281.6, 364/942.5
• US Class Current: 718/104
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

Methods of operating a digital computer to optimize project scheduling. Where the overall effects of a schedule, such as total project duration or cost, are unsatisfactory, the schedule is processed iteratively so that on each iteration a particular task is selected for modification according to a preset policy and data defining an aspect of that task is adjusted in a small step. A schedule is further optimized to fit the available resources by a repetitive process of assigning resources having the proper capabilities to tasks according to a predetermined order of tasks and testing whether the assigned resource can permit shortening of the task duration. Further methods select an optimum mix of capabilities to be provided by each of several resources to be hired for a project.

Claims

1. A computer-implemented method of scheduling tasks constituting a project comprising the steps of:

(a) providing input signals in a computer representing the tasks constituting the project, the dependencies of said tasks on one another and data defining the duration of each said task;

(b) processing said input signals in said computer to calculate an initial set of schedule data which forms an initial schedule including an initial set of times for each said task including earliest starting and latest ending times and an initial subset of said tasks constituting a critical path and providing initial data signals representing said initial set of schedule data;

(c) calculating at least one effect parameter for said initial schedule by processing said initial data signals in said computer to produce an effect parameter signal in said computer;

(d) providing an effect criterion signal in said computer and comparing each said effect parameter to a corresponding effect criterion by processing said effect parameter signal and said effect criterion signal in said computer to determine if each said criterion is met;

(e) if any effects criterion is not met, revising said data by;

(1) automatically applying a preset selection policy set forth in a selection policy signal to the schedule to select a task for modification and a preset modification policy to adjust the input data for the so-selected task stepwise and providing adjusted input signals in said computer;

(2) recalculating said schedule data by reprocessing said adjusted input data signals to thereby provide recalculated schedule data in recalculated data signals;

(3) recalculating said at least one effect parameter based upon said recalculated schedule data; and

(f) repeating said comparing and revising steps until said at least one effect parameter meets said corresponding effect criterion.

2. A method as claimed in claim 1 further comprising the steps of providing resource data in said computer representing the quantities of individual resources available as a function of time and applicability data representing applicability of individual resources to individual tasks, and resource-adjusting at least one said schedule by assigning resources to individual tasks in accordance with said applicability data and in accordance with a preselected prioritization scheme, determining whether a shortage will exist in any resource during any time period and, if so, adjusting the duration of at least one task to alleviate said shortage.

3. A method as claimed in claim 2 wherein said step of resource-adjusting at least one said schedule is applied to said initial schedule prior to said step of calculating at least one effects parameter for said initial schedule.

4. A method as claimed in claim 1 further comprising the steps of providing resource data in said computer representing the quantities of individual resources available as a function of time and applicability data representing capabilities by each resource and a set of capability requirements for each task, and optimizing at least one said schedule with respect to available resources by treating each said schedule as a working schedule to be optimized and:

(1) setting an order of tasks for resource allocation;

(2) defining a set of resources available according to said resource data for a task during the interval from the earliest starting time to the latest ending time as defined by the working schedule, such set including only resources having capabilities matching the capability requirements of the task;

(3) assigning resources from said set of resources to the task according to a preset resource selection scheme and modifying said resource data to indicate that the assigned resources are unavailable to other tasks;

(4) repeating said defining and assigning steps for all of the tasks in the working schedule in said order of tasks;

(5) testing each task on the critical path of the working schedule by determining whether the resources assigned to such task would permit completion of the task in an interval shorter than the earliest-start to latest-end interval associated with that task in the working schedule and, if so, generating a positive test signal; and

(6) if a positive-test signal is generated for any task in the working schedule, computing a new working schedule by setting the interval required for each task based upon the resources assigned to that task and computing earliest-start and latest-end times for all tasks based upon such intervals; and

p1 (7) repeating steps (1)-(6) for each newly-computed working schedule until no positive-test signal is generated,

whereby the last-computed schedule is substantially an optimum schedule with respect to available resources.

5. A method as claimed in claim 4 further comprising the step of computing at least one said effect parameter in said computer based at least in part upon the quantities of resources assigned to said tasks in said optimizing process.

6. A method as claimed in claim 5 wherein said at least one effect parameter includes at least one parameter selected from the group consisting of time, risk, cost and efficiency.

7. A method as claimed in claim 5 wherein said resource-optimizing step is performed in said computer for said initial set of schedule data prior to said comparing step.

8. A method as claimed in claim 1 wherein said selection policy includes selecting the task with the longest estimate of duration.

9. A method as claimed in claim 2 wherein said resource-adjusting step is performed in said computer prior to said calculating step and said modification policy includes the step of modifying the data representing quantities of resources available.

18. A programming element for an electronic digital computer comprising a programming medium and program data means resident on said medium for actuating a computer to execute a method as claimed in claim 1.

10. A computer-implemented method of finding substantially optimal working schedule data with respect to available resources, said working schedule data including data representing a plurality of tasks, a set of capability requirements and quantity requirements for each task, earliest-start and latest-end times associated with each task and a subset of tasks representing a critical path, the method including the steps of providing, resource data representing a set of capabilities possessed by each resource and quantities of individual resources available as a function of time:

(1) setting an order of tasks for resource allocation;

(2) defining a set of resources available according to said resource data for a task during the interval from the earliest starting time to the latest ending time as defined by the working schedule, such set including only resources having capabilities matching the capability requirements of the task;

(3) assigning resources from said set of resources to the task according to a preset resource selection scheme and modifying said resource data to indicate that the assigned resources are unavailable to other tasks;

(4) repeating said defining and assigning steps for all of the tasks in the working schedule in said order of tasks;

(5) testing each task on the critical path of the working schedule by determining whether the resources assigned to such task would permit completion of the task in an interval shorter than the earliest-start to latest-end interval associated with the task in the working schedule and, if so, generating a positive test signal; and

(6) if a positive-test signal is generated for any task in the working schedule, computing a new working schedule by setting the interval required for that task based upon the resources assigned to that task and computing earliest-start and latest-end times for all tasks based upon such intervals; and

(7) repeating steps (1)-(6) for each newly-computed working schedule until no positive-test signal is generated,

whereby the last-computed working schedule is substantially an optimum schedule.

11. A method as claimed in claim 10 wherein said step of setting an order of tasks for resource assignment includes the step of ordering said tasks according to latest-ending times with the earliest latest-ending time first.

12. A method as claimed in claim 10 wherein said preset resource selection scheme used in assigning resources to tasks includes ordering resources in accordance with quantities of such resources available during each interval and assigning resources over each interval in accordance with said order.

13. A method as claimed in claim 12 wherein said resource data includes scaling factors for said resources, said scaling factors being different for different ones of said resources, said scaling factors relating units of said resource consumed to quantities of individual capabilities provided, said quantity requirements for each said task including requirements for quantities of individual capabilities, said step of assigning resources to a task being performed so that the number of units of the resources assigned, scaled by the scaling factors, corresponds to the required quantities of individual capabilities for the task.

14. A method as claimed in claim 13 wherein said resource selection scheme includes assigning resources to tasks so that the resource available in greatest quantity during each interval is assigned to a task first.

15. A method as claimed in claim 10 wherein said quantity data and said capability data includes one or more task requirement for each said task, each said task requirement specifying one capability and a quantity of such capability required, said step assigning resources to tasks being performed by assigning resources to said task requirements.

16. A method as claimed in claim 15 wherein said step of defining an order of tasks for resource allocation includes the step of associating the latest-ending time of each task with the task requirements constituting that task and sorting the task requirements for all of said tasks in order of latest-ending time, said step of defining a set of resources for each task including the step of establishing a set of resources for each task requirement having the capability specified in that task requirement.

17. A method as claimed in claim 10 further comprising the step of altering said resource data to indicate availabilities of different quantities of resources and repeating said steps to thereby find an optimum schedule for each of a plurality of different resource availabilities.

19. A programming element for an electronic digital computer comprising a programming medium and program data means resident on said medium for actuating a computer to execute a method as claimed in claim 10.

20. A computer-implemented method of operating a digital computer to generate output signals representing a substantially optimum set of resources for performing a task according to a schedule comprising the steps of:

(A) providing resource constraint data defining the number of resources which can be included in the optimum set;

(B) providing working schedule data representing a plurality of tasks and representing earliest-starting and latest-ending times constituting the event horizon for each task and providing capability and quantity requirement data for each task defining the identity and quantity of each capability required for the task;

(C) ranking all of the capabilities identified in said capability requirement data with respect to all of said tasks according to a preselected capability ranking scheme;

(D) setting an order of tasks for resource allocation;

(E) providing a resource data table in said computer including resource identity data defining a plurality of resources; and

resource schedule data defined the availability of each resource as a function of time, and resource capability data defining the capabilities assigned to each resource;

(F) selecting a capability according to said ranking of capabilities;

(G) using the selected capability to select a task by comparing data representing the selected capability with the capability requirement data of said tasks according to said order of tasks until a task is found having capability requirement data calling for the selected capability;

(H) processing the selected capability and task by;

(i) comparing the selected capability with the capability data in said resource data table to select a set of proper-capability resources for which the capabilities assigned to the resource include the selected capability;

(ii) comparing the availability of resources as a function of time to the event horizon for the selected task and the quantity requirement data for the task to select a set of adequate-availability resources for which the availability of the resource within the event horizon of the task is equal to or greater than the quantity requirement; and

(iii) determining whether any matching resource exists which is both a proper-capability resource and an adequate-availability resource;

(I) assigning a resource for time allocation by;

(i) if a matching resource is found in step (H)(iii), assigning said matching resource for time allocation; and

(ii) if no matching resource is found in step (H)(iii), applying a predetermined selection policy to select a resource, modifying the data in said resource data table with respect to said selected resource so that the selected resource is a matching resource and assigning said selected resource for time allocation;

(J) allocating the time of the assigned resource to the selected task by modifying the availability data in said resource data table for the assigned resource to decrease the available time by an amount equal to the quantity requirement for the selected capability in the selected task during the event horizon of the selected task;

(K) using the same selected capability, repeating steps (G) through (J) until all tasks have been compared in step (G) and, if selected, processed through step (J);

(L) repeating steps (F) through (K) using a new capability on each repetition, until all of said capabilities have been used; and

then

(K) outputting the contents of said resource data table as the output signal.

21. A method as claimed in claim 20 wherein said selection policy in step (I)(ii) includes selection of the resource having the smallest number of assigned capabilities.

22. A method as claimed in claim 20 wherein said selection policy in step (I)(ii) includes selection of the resource having the largest number of assigned capabilities.

23. A method as claimed in claim 20 wherein said selection policy includes selection of a resource in accordance with availability of such resource during the event horizon for the selected task.

24. A method as claimed in claim 20 wherein said resource capability data initially provided in step (e) indicates that none of said resources have any capabilities.

25. A method as claimed in claim 20 wherein said working schedule data represents unstarted tasks of a partially-completed project.

26. A method as claimed in claim 20 wherein said resource data represents capabilities of an existing set of resources.