Optimizing regular scheduling objectives: Priority rule calculations

Submitted by Mario Vanhoucke on Fri, 01/13/2012 - 16:59

Priority based project scheduling is a quick and easy heuristic scheduling technique that makes use of two components to construct a resource feasible project schedule, a priority rule and a schedule generation scheme (see “Optimizing regular scheduling objectives: Priority rule based scheduling”). In this article, the use and calculations of priority rules will be illustrated on a fictitious project example network. More precisely, the calculations of activity priorities will be based on four sources of information, as follows:

Activity information: information about time or cost estimates of the activities determines the activity priorities.
Network information: information on the project network logic determines the activity priorities.
Scheduling information: information obtained from simple critical path scheduling tools determines the activity priorities.
Resource information: information about the project resources determines the activity priorities.

Figure 1 displays a project network with 11 activities and finish-start precedence relations Each number above the node denotes the estimated duration of the activity while the number below the node is used to refer to the renewable resource demand. The maximum availability of the resource is equal to 6 units (e.g. people). More information on renewable resources can be found in “Resource types: Renewable and consumable resources”.

Figure 1: Project network and activity data

Below, a summary of the most commonly used priority rules is given for each of the first four classes. It should be noted that this is certainly an incomplete list of priority rules since one can think of many other priority rules or extensions or combinations of these rules.

Activity information

The construction of an activity list is based on a priority rule taking the characteristics of the project activities into account, such as the duration of each activity. Example priority rules are:

Shortest Processing Time (SPT): Put the activities in an increasing order of their durations in the list.
Longest Processing Time (LPT): Put the activities in a decreasing order of their durations in the list.

Network information

The construction of an activity list is based on a priority rule taking the logic of the network structure into account, i.e. the set of activities and the precedence relations between them. Example priority rules are:

Most Immediate Successors (MIS): Put the activities with the most direct successors first in the activity list. As an example, activity 4 has two immediate successors (activities 7 and 8) and will therefore come before activity 3 (which has only one immediate successor).
Most Total Successors (MTS): Put the activities with the most direct and indirect successors first in the activity list. As an example, activity 4 has four successors (activities 7, 8, 10 and 11) and will therefore come before activity 3 (which has three successor activities 6, 9 and 11).
Least Non-Related Jobs (LNRJ): A job (or activity) is not related to another job if there is no precedence related path between the two activities in the project network. As an example, activity 7 is not related to activities 3, 5, 6, 8, 9, 10 and consequently has six non-related jobs. Activities are ranked in an increasing order of their number of non-related activities.
Greatest Rank Positional Weight (GRPW): The GRPW is calculated as the sum of the duration of the activity and the durations of its immediate successors. As an example, activity 4 has a GRPW value equal to 12 and should therefore be put before activity 5 (GRPW value = 10) in the activity list.

Scheduling information

Priority rules are used to construct feasible project schedules with resource constraints. However, simple scheduling techniques that ignore these resource constraints, such as the critical path method, can also be used to define new priority rules. Example priority rules are:

Earliest Start Time (EST): Put the activities in an increasing order of their earliest start in the list.
Earliest Finish Time (EFT): Put the activities in an increasing order of their earliest finish in the list.
Latest Start Time (LST): Put the activities in an increasing order of their latest start in the list.
Latest Finish Time (LFT): Put the activities in an increasing order of their latest finish in the list.
Minimum Slack (MSLK): Put the activities in an increasing order of their slack value in the list.?

More information on the calculation of these earliest/latest start/finish times and the activity slack can be found in “Scheduling projects: How to determine the critical path using activity slack calculations?”.?

Resource information

The construction of an activity list is based on a priority rule taking the logic of the network structure as well as information from the resource constraints into account. The resource work content is here defined as the product of the duration of the activity and the resource requirements. Example priority rules are:

Greatest Resource Work Content (GRWC): Put the activities in a decreasing order of their work content in the list. As an example, activity 4 has a total work content equal to 16 and should therefore be put before activity 3 (work content = 4) in the list.
Greatest Cumulative Resource Work Content (GCRWC): Put the activities in a decreasing order of the sum of their work content and the work content of all their immediate successors in the list. As an example, activity 4 has a total cumulative work content equal to 16 + 10 + 6 = 32 and should therefore be put before activity 3 (cumulative work content = 4 + 12 = 16) in the list.

More information on the demand of resources in a project can be found in “Linking resources to activities: Resource availability and resource demand”.?

Table 1 shows for each of the priority rules the corresponding activity lists for the project network of figure 1. Each activity list can then be used as an input for a schedule generation scheme (see “Optimizing regular scheduling objectives: Schedule generation schemes”) which transforms the project network into a resource-feasible schedule.

It should be noted that for each activity list, the network structure has been taken into account. This means that an activity can never be placed in the list before another activity if the latter is a (direct or indirect) predecessor of the former. As an example, the SPT rule should place activity 8 with a duration of 3 time units before activity 5 that has a duration of 7 time units. However, due to the network structure, activity 8 can never be scheduled before activity 5, and therefore, this situation will never occur. This extra feature facilitates the construction of a resource-feasible schedule using the schedule generation schemes but is not a necessary requisite to obtain a feasible schedule.

Table 1: The priority rules and their corresponding activity lists for the example project of figure 1

Priority rule	Activity list
SPT	[1, 2, 3, 6, 4, 7, 5, 8, 10, 9, 11]
LPT	[1, 2, 5, 4, 7, 8, 3, 6, 9, 10, 11]
MIS	[1, 2, 4, 3, 5, 6, 7, 8, 9, 10, 11]
MTS	[1, 2, 4, 3, 5, 6, 8, 7, 9, 10, 11]
LNRJ	[1, 2, 4, 3, 5, 8, 10, 6, 9, 7, 11]
GRPW	[1, 2, 4, 5, 7, 3, 6, 9, 8, 10, 11]
EST	[1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 11]
EFT	[1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 11]
LST	[1, 2, 3, 5, 6, 4, 9, 7, 8, 10, 11]
LFT	[1, 2, 3, 6, 4, 5, 8, 7, 9, 10, 11]
MSLK	[1, 2, 3, 5, 6, 9, 4, 8, 10, 7, 11]
GRWC	[1, 2, 4, 5, 7, 8, 3, 6, 9, 10, 11]
GCRWC	[1, 2, 4, 5, 3, 6, 9, 7, 8, 10, 11]

PM Knowledge Center

Optimizing regular scheduling objectives: Priority rule calculations