Priority rule search technique for resource constrained project scheduling

• US 5,671,361 A
• Filed: 09/28/1995
• Issued: 09/23/1997
• Est. Priority Date: 09/28/1995
• Status: Expired due to Term

• Current Assignee: University of Central Florida Research Foundation Inc. (State University System of Florida)
• Original Assignee: University of Central Florida (State University System of Florida)
• Inventors: Brown, James T., Armacost, Robert L.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Shingala, Gita
• Application Number:
  US08/535,457
• Time in Patent Office: 726 Days
• Field of Search: 364/401, 364/402, 364/468, 395/207, 395/208, 395/209, 395/211
• US Class Current: 705/7.23
• 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/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource

Abstract

A Priority Rule Search Technique (PRST) heuristic computer controlled algorithm is disclosed that schedules single project, single resource and multiple project, multiple resource constrained project scheduling problems. Primary areas of utility include construction, manufacturing and research and development projects. The invention can schedule tasks/activities for large scale, multiple resource and multiple project networks that have different network and resource constraint characteristics while providing balance among different project network characteristics in order to provide an effective solution for a variety of network types. The novel PRST algorithm combines four heuristic rules (ACTM, LFT, MGRD and MACTRES) to determine a priority value for each job task/activity. The priority values are ranked to determine an optimum schedule of all job tasks and activities to complete the entire project. The invention incorporates the time (ACTM and LFT) and resource (MGRD and MACTRES) characteristics of project activities into a priority rule based search heuristic to determine an activity'"'"'s priority for scheduling. The PRST scheduling invention is composed of four priority rules that are individually weighted and combined. The first two priority rules are ACTIM and Late Finish Time (LFT) heuristics. The second two priority rules allow for the allocating of limited resources to activities that cannot be scheduled concurrently. One of these priority rules designated Multiple Greatest Resource Demand (MGRD) modifies a Greatest Resource Demand heuristic to accommodate a multiple resource case. MGRD is scaled measure of the resource demanded for each activity. The second priority rule is designated Multiple ACTRESS (MACTRES) which modifies a ACTRES heuristic to accommodate the multiple resource case. MACTRES is a measure of the time and resources controlled by the activity through the network. Alternatively, the schedule of each of the job tasks/activities can be scheduled by ranking priority values based separately on MACTRES computations or MGRD calculations.

Claims

1. A method of scheduling job tasks and activities of construction, manufacturing, research, and development projects to minimize overall duration time of the projects, comprising the steps of:

(a) identifying all job tasks of a project to be scheduled, wherein the project is chosen from at least one of;

a construction project, manufacturing project, research project and development project;

(b) identifying all resources available for the project to be scheduled;

(c) identifying time values for completing each task for the project to be scheduled;

(d) computing a priority index value for each job task in accordance with the equation;

space="preserve" listing-type="equation">PRST=w x(ACTIM)+(1-x)(MACTRES)!+ 1-w! y(MGRD)+(1-y)(LFT)!

where;

w is a variable incremented between 0 and 1,

x is a variable incremented between 0 and 1,

ACTIM is critical path time minus late start time for each task,

MACTRES is the task duration multiplied by the sum of the scaled resource requirements for the task, plus addition of maximum MACTRES value following the task,

MGRD is sum of scaled resource requirements for the activity multiplied by resource type complexity factor of the task,

LFT is the latest finish time to complete the task; and

(e) providing a schedule of job tasks based on the priority index values for each task, wherein the all job tasks for the project are in one schedule which minimizes the duration time to complete the project.

2. The method of scheduling job tasks and activities of construction and manufacturing projects of claim 1, wherein the project to be scheduled includes:

multiple projects.

3. The method of scheduling job tasks and activities of construction and manufacturing projects of claim 1, wherein the resources include:

multiple resources.

4. A method of scheduling job tasks and activities of construction and manufacturing projects having multiple job tasks and multiple resources in order to minimize overall duration time of the project, comprising the steps of:

(a) determining all individual job tasks required for a project;

(b) determining all resources necessary to compete each job task;

(c) calculating time duration of each job task;

(d) calculating latest time each job task can be started;

(e) calculating latest time each job task can be finished;

(f) determining priority rule values for each job task based on the resources, the time duration, the latest start time and the latest finish time of each job task;

(g) ranking the job tasks in order of each of the priority rule values; and

(h) scheduling the job tasks based on the ranking of the job tasks, wherein duration time to complete the projects is minimized.

5. The method of scheduling job tasks and activities of claim 4, wherein the job tasks include:

activities of the project.

6. The method of scheduling job tasks and activities of claim 4, further comprising:

calculating an ACTIM value for each job task, where the ACTIM value is critical path time minus late start time for each task.

7. The method of scheduling job tasks and activities of claim 6, further comprising:

calculating a MACTRES value for each job task, where the MACTRES value is the task duration multiplied by the sum of the scaled resource requirements for the task, plus addition of maximum value following the task.

8. The method of scheduling job tasks and activities of claim 7, further comprising:

calculating a MGRD value for each job task, where the MGRD value is sum of scaled resource requirements for the activity multiplied by resource type complexity factor of the task.

9. The method of scheduling job tasks and activities of claim 8, wherein step (f) of determining the priority rule values further includes:

computing a priority index value for each job task in accordance with the equation;

space="preserve" listing-type="equation">PRST=w x(ACTM)+(1-x)(MACTRES)!+(1-w) y(MGRD)+(1-y)(LFT)!

where;

w is a variable incremented between 0 and 1,

x is variable incremented between 0 and 1, and

y is variable incremented between 0 and 1.

10. A method of scheduling job tasks and activities of construction and manufacturing projects having multiple job tasks and multiple resources in order to minimize overall time duration to complete the projects, comprising the steps of:

(a) determining each job task and each activity to be required for a project;

(b) determining all resources necessary to complete each job task and each activity;

(c) calculating time duration of each job task and each activity;

(d) calculating latest time each job task and each activity can be started;

(e) calculating latest time each job task and each activity can be finished;

(f) determining a priority rule value for each job task and each activity based on the resources, the time duration, the latest start time and the latest finish time;

(g) ranking the job tasks in order of each of the priority rule values; and

(h) scheduling the job tasks based on the ranking of the job tasks, wherein time duration to complete the project has been minimized.

11. The method of scheduling job tasks and activities of construction and manufacturing projects of claim 10, wherein step (f) includes:

calculating a MACTRES value for each job task, where the MACTRES value is the task duration multiplied by the sum of the scaled resource requirements for the task, plus addition of maximum value following the task.

12. The method of scheduling job tasks and activities of construction and manufacturing projects of claim 10, wherein step (f) includes:

calculating a MGRD value for each job task, where the MGRD value is sum of scaled resource requirements for the activity multiplied by resource type complexity factor of the task.