System and method for generating a schedule based on resource assignments

• US 6,571,215 B1
• Filed: 01/21/1997
• Issued: 05/27/2003
• Est. Priority Date: 01/21/1997
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mahapatro, Neelamadhaba
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Irshadullah, M.
• Application Number:
  US08/786,489
• Time in Patent Office: 2,317 Days
• Field of Search: 705/9, 705/8, 705/7, 717/1, 717/101, 707/10, 706/13
• US Class Current: 705/7.12
• 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/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment

Abstract

A system for generating a schedule by generating assignments for the tasks of a project and sequentially scheduling the individual assignments to available resources. First, input information is received which includes a resource calendar and a task list. A resource calendar identifies the resources available to work on a project and any constraints that are associated with the resources. A task list identifies the tasks that must be performed and any constraints that are associated with the tasks. At a minimum, the constraints associated with the tasks must identify each of the resources assigned to the task, and the work-amount that each resource must perform. Next, assignments are generated for each of the tasks. Each of the assignments identifies a specific resource and the work-amount required by the specific resource. Finally, each of the assignments are scheduled in accordance with the provided resource constraints identified in the resource calendar. The resulting schedule maximizes the utilization of the resources by scheduling on an assignment basis. The assignments are individually scheduled into the next available time-slot of the resources, thus, eliminating idle time where a resource is under-utilized.

Claims

1. A computer-readable medium having computer-executable instructions for performing a method for creating an assignment-oriented schedule, the method comprising the steps of:

a. receiving input information comprising;

a resource calendar which identifies resources, available time-slots for each of the resources, and an earliest start date for each of the resources, and

a task list which identifies tasks, each of the tasks having a set of task constraints and a priority which is a function of the task constraints, each set of task constraints identifying at least one resource assigned to the task associated with the set of task constraints and a work-amount for each of the assigned resources;

b. generating assignments for each of the tasks, each of the assignments representing a component of a task and identifying a specific assigned resource, a specific work-amount required by the specific assigned resource, the task from which the assignment is generated as a parent task, and a predecessor count indicating a number of predecessor tasks upon which the assignment depends;

c. ordering the assignments by;

1. identifying a first assignment group comprising assignments having a start-on scheduling constraint in the set of task constraints of their corresponding parent task,

2. identifying a second assignment group comprising assignments having a must-finish-by scheduling constraint in the set of task constraints of their corresponding parent task and which are not identified for the first assignment group;

3. identifying a third assignment group comprising assignments having a predecessor count with a value of zero and which are not identified for the first assignment group, and

4. identifying a fourth assignment group comprising assignments which are not identified for one of the first and third assignment groups;

d. scheduling each of the assignments in the first assignment group into a time-slot for the assigned resource which corresponds with the start-on scheduling constraint for each respective assignment; and

e. scheduling remaining unscheduled assignments by;

1. selecting a first resource as a current resource,

2. selecting a first assignment from the third assignment group as a current assignment, the current assignment identifying the current resource,

3. if there is an unscheduled assignment in the fourth assignment group which identifies the current resource and has a higher priority than the current assignment, then selecting a next resource as the current resource and continuing at step e2,

4. calculating a current end date based on all of the assignments that have been scheduled and the current assignment as though it has been scheduled,

5. if any assignments in the second assignment group identify the current resource and have a must-finish-by scheduling constraint that identifies a date earlier than the current end date, scheduling any such assignments in the second group into the first available time-slot for the current resource and continuing at step e7,

6. scheduling the current assignment in the first available time-slot for the current resource,

7. if all of the assignments having a common parent task have been scheduled;

decrementing the predecessor counts for each of the assignments which are dependent upon the common parent task, and

moving all of the assignments in the fourth assignment group, which have a predecessor count equal to the value of zero, to the third assignment group,

8. selecting a next assignment from the third assignment group as a current assignment, the current assignment identifying the current resource, and repeating steps e3 through e8 until all of the assignments in the third assignment group which identify the current resource have been scheduled, and

9. selecting a next resource as the current resource and repeating steps e2 through e9 until all of the assignments have been scheduled.

2. A computer-readable medium according to claim 1, wherein the method further comprises the steps of:

receiving a new set of resource constraints for a resource, the new set of resource constraints replacing an original set of resource constraints for the resource; and

rescheduling each of the assignments in accordance with the set of resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.

3. A computer-readable medium according to claim 1, wherein the method further comprises the steps of:

receiving a new set of task constraints for a task, the new set of task constraints replacing an original set of task constraints for the task; and

rescheduling each of the assignments in accordance with the resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.

4. A computer system for creating an assignment-oriented schedule, comprising:

a processing unit;

a memory storage device;

an input device coupled to said processing unit for receiving information;

a pixel-based display device coupled to said processing unit for displaying data; and

a program module, stored in the memory storage device, for providing instructions to the processing unit,

the processing unit, responsive to the instructions of the program module, operative for;

a. receiving, from the input device, input information comprising;

a resource calendar which identifies resources available for scheduling, available time-slots for each of the resources, and an earliest start date for each of the resources, and

a task list which identifies tasks to be performed, each of the tasks having task constraints, a priority-order which is a function of the task constraints, and a predecessor count, the task constraints comprising a list of assigned resources for each of the tasks, a work-amount for each of the assigned resources, and at least one scheduling constraint;

b. generating assignments for each of the tasks, each of the assignments identifying a specific assigned resource, a specific work-amount, and a parent task;

c. scheduling each of the assignments that have a parent task with a start-on scheduling constraint into a time-slot of the resource calendar for its specific assigned resource, the time-slot corresponding with the start-on scheduling constraint;

d. scheduling each of the assignments not previously scheduled by;

1. selecting a first resource from the resources as a current resource,

2. if at least one unscheduled assignment exists which identifies the current resource as the specific assigned resource, has a parent task with a predecessor count equal to zero, and has a priority-order greater than all other unscheduled assignments which identify the current resource as the specific assigned resource and have a parent task with a predecessor count greater than zero;

selecting a current assignment from the unscheduled assignments which identifies a parent task having a predecessor count equal to zero and a highest priority-order,

calculating a current end date based on all of the assignments that have been scheduled and the current assignment,

scheduling each of the assignments not previously scheduled, which identify the current resource as the specific assigned resource, identify a parent task having a must-finish-by scheduling constraint that is earlier than the current end date, and identify a parent task with a predecessor count equal to zero, in the first available time-slot for the current resource,

scheduling the current assignment in the first available time-slot for the current resource, and

if all of the assignments identifying a common parent task have been scheduled, decrementing the predecessor counts for each of the plurality of tasks which have a dependency constraint identifying the common parent task as a predecessor task, and repeating step d2, and

3. if any of the assignments have not been scheduled, selecting a next resource from the plurality of resources as the current resource and repeating steps d2 and d3.

5. A computer system according to claim 4, wherein said processing unit is further operative for:

receiving a new set of resource constraints for a resource, the new set of resource constraints replacing an original set of resource constraints for the resource; and

rescheduling each of the assignments in accordance with the set of resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.

6. A computer system according to claim 4, wherein said processing unit is further operative for:

receiving a new set of task constraints for a task, the new set of task constraints replacing an original set of task constraints for the task; and

rescheduling each of the assignments in accordance with the resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.

7. A computer-readable medium having computer-executable instructions for performing a method for generating a schedule for a plurality of unscheduled assignments, each of the unscheduled assignments identifying at least one of a plurality of resources, a work-amount, a priority-order, one of a plurality of parent tasks, and a predecessor count indicating a number of predecessor tasks upon which the assignment depends, each of the resources having a resource calendar identifying available time-slots for the resource and each of the plurality of parent tasks having at least one scheduling constraint, the method comprising the steps of:

a. selecting a current resource from the plurality of resources;

b. selecting a current assignment from the plurality of unscheduled assignments, the current assignment identifying the current resource, identifying a parent task having a start-on scheduling constraint, and having a highest priority-order;

c. scheduling the current assignment in the first available time-slot of the resource calendar for the current resource;

d. identifying the current assignment as scheduled and repeating steps b-d if additional unscheduled assignments identifying the current resource are remaining;

e. if additional unscheduled assignments which identify a parent task having a start-on scheduling constraint exist, selecting a next current resource and repeating steps a-e with the next current resource; and

f. scheduling each of the remaining unscheduled assignments by;

1. selecting a next resource from the plurality of resources as the current resource,

2. if at least one qualifying unscheduled assignment exists, the qualifying unscheduled assignments identifying the current resource, having a predecessor count equal to zero, and having a priority-order greater than any other unscheduled assignments which identify the current resource and have a predecessor count greater than zero;

selecting a qualifying unscheduled assignment with a greatest priority-order as the current assignment,

calculating a current end date based on all of the assignments that have been scheduled and the current assignment,

if any unscheduled assignments exist which identify the current resource and identify a parent task having a must-finish-by scheduling constraint that is earlier than the current end date, scheduling each such assignment into the first available time-slot for the current resource, otherwise, scheduling the current assignment in the first available time-slot for the current resource,

if all of the assignments identifying a common parent task have been scheduled, decrementing the predecessor counts for each of the plurality of assignments which have a dependency scheduling constraint identifying the common parent task as a predecessor task, and repeating step f2, and

3. if additional unscheduled assignments exists, selecting a next resource from the plurality of resources as the current resource and repeating steps f2 and f3.

8. A computer-readable medium according to claim 7, wherein the method further comprises the steps of:

receiving a new set of resource constraints for a resource, the new set of resource constraints replacing an original set of resource constraints for the resource; and

rescheduling each of the assignments in accordance with the set of resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.

9. A computer-readable medium according to claim 7, wherein the method further comprises the steps of:

receiving a new set of task constraints for a task, the new set of task constraints replacing an original set of task constraints for the task; and

rescheduling each of the assignments in accordance with the resource constraints for its corresponding specific assigned resource and the task constraints for its corresponding parent task.