Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1997-01-21
2003-05-27
Hafiz, Tariq R. (Department: 3623)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C706S013000, C707S793000, C717S101000
Reexamination Certificate
active
06571215
ABSTRACT:
TECHNICAL FIELD
The present invention is generally directed to computer programs for generating schedules and, more particularly, relates to a method for generating a schedule which is based on resource assignments, and optimally uses the available resources to complete a list of tasks.
BACKGROUND OF INVENTION
Scheduling programs have gained considerable popularity among project-oriented professions such as product engineering companies, construction firms, and manufacturing plants. Scheduling programs allow a project manager to organize and track the development of a project. In the most general sense, a scheduling program operates by receiving an input of project-related information, generating a schedule based on this information, and then graphically or in a tabular manner, displaying the details concerning the status of the project, projected completion date, anticipated delays, etc.
The critical path method (CPM) of scheduling is used in a significant number of scheduling programs. CPM scheduling generally operates by receiving a list of tasks, each task having varying restrictions or constraints, and generating a schedule based on the task restrictions or constraints. More specifically, a set of tasks are provided to the scheduling program. Each task represents a specific job or discrete amount of work that must be performed on a project. Additionally, each task has a set of restrictions or constraints which dictate when and how long the task should be performed. To generate a meaningful schedule, CPM scheduling requires the input of information which identifies when each task is to be performed. This information can be provided by specifying constraints such as: a start date and a finish date, a start date and a task duration, a task duration and a finish date, or a task duration and a start or finish date which is dependent upon another task. If this information is not specified, the typical CPM scheduling program will assume the start date for each task to be the current date, and the duration of the task will default to a specific granularity such as one day, one week, etc.
Linking information concerning one or more of the tasks may also be entered. For instance, if a project consists of three tasks (Task 1, Task 2, and Task 3), the user may specify that Task 1 must be completed before Task 2 and Task 2 must be completed before Task 3. This information can be provided in the form of entering a start date for Task 2, which is equivalent to the finish date for Task 1, or by specifying that the start date for Task 2 is dependent upon the completion of Task 1. The latter method is referred to as a link.
Once the user enters the task information, a CPM scheduling program generates a schedule based on the provided task constraints. This is accomplished by performing a forward pass in which each task is examined. At the completion of the forward pass, a schedule is created that starts on the start date of the first task that can be scheduled and satisfies all of the provided task constraints. Next, the critical path for the project is determined. The critical path can be defined as the longest duration path through the network of task dependencies. The critical path is calculated by performing a backward pass from the last finish date to the earliest start date.
CPM scheduling programs are most beneficial for projects in which the tasks have dependencies on each other. Because of this, they are well suited for product-oriented projects which inherently have tasks that must be performed in a specific order. As an example, in building a house, the tasks of laying a foundation, framing the house, and shingling the roofing must be performed in this order. There are, however, many situations where the order of performing certain tasks of a project are arbitrary. For instance, in publishing a news letter, the order in which the articles are written is arbitrary. CPM scheduling programs typically do not produce meaningful results when the tasks do not have dependencies. As an example, if the three tasks (Task 1, Task 2 and Task 3) are not required to be performed in any specific order (i.e., do not have any dependencies), a CPM scheduling program will generate a “flat schedule” as illustrated in Schedule Example 1.
The problems associated with flat scheduling are evident when the tasks are viewed with respect to the resources assigned to the tasks. For instance, if a single resource is assigned to each of these three tasks, the flat schedule indicates that the resource will be required to work on three tasks at the same time. This results in “overloading” the resource. Alternatively, separate resources (Resource 1, Resource 2 and Resource 3) could be assigned to each of the three tasks respectively. This would result in a 100% utilization of Resource 2 and Resource 3; however, after the completion of Task 1, Resource 1 would be idle. This is referred to as “under-utilizing” a resource.
To avoid the generation of a flat schedule by a CPM scheduling program, the user is required to enter artificial dependency information such as links or start dates. Thus, to avoid the flat schedule shown in Schedule Example 1, the user could define the start date of Task 2 as dependent upon the completion of Task 1, and the start date of Task 3 as dependent upon the completion of Task 2. For projects with several tasks, this process may require a significant amount of effort for the user. Thus, there is a need for a scheduling program which can generate a meaningful schedule for a set of non-dependent tasks. Furthermore, there is a need for a scheduling program that can generate a meaningful schedule for a set of non-dependent tasks without requiring the input of artificial constraints such as start dates or dependencies.
A schedule in which resources are overloaded and/or under-utilized is referred to as an “unbalanced” schedule. As previously illustrated, CPM scheduling programs are susceptible to producing unbalanced schedules. One method that has been developed to address this deficiency in CPM scheduling programs is referred to as “leveling”. The leveling process operates separately from the CPM scheduling and is designed to balance the resource utilization of a schedule. In this process, an overloaded resource is identified, and the task or tasks causing the first instance of the overload are determined. Next, adjustments are made to the start and/or finish dates of the task or tasks causing the overload to reduce the resource usage to 100%. Because this adjustment may result in changing the critical path, each time a leveling adjustment is made, the critical path must be recalculated before further leveling adjustments can be performed. Thus, for each leveling adjustment, a forward pass is performed to reschedule the tasks, and a backward pass is performed to recalculate the critical path. Depending on the number of tasks and the amount of overloading, this process can require a significant amount of iterative processing which wastes valuable processor time. Thus, there is a need for a method of scheduling which produces a balanced schedule. There is also a need for a method of scheduling that efficiently and quickly produces a balanced schedule which maximizes the use of the available resources.
CPM scheduling programs operate on a task-oriented basis. A problem that results from task-oriented scheduling is the tendency to under-utilize the available resources. The following example is illustrative of this problem. If the following information is provided to a CPM scheduling program:
Resource 1 (R1) is assigned to Task 1,
Resources 1 and 2 (R1,R2) are assigned to Task 2, and
Resource 2 is assigned to Task 3,
upon completion of the scheduling process, the schedule shown in Schedule Example 1 would be created. Next, upon completion of the leveling process, a possible outcome of the schedule is shown in Schedule Example 2.
In Schedule Example 2, Task 2 has been scheduled to start upon the completion of Task 1 and Task 3 has been scheduled to start upon the completion of Task 2. Task 2 is s
Hafiz Tariq R.
Irshadullah M.
King & Spalding LLP
Microsoft Corporation
LandOfFree
System and method for generating a schedule based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for generating a schedule based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating a schedule based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3017684