Quantitative Tools for Service Operations Management by Dr. Scott Sampson ©2012 (return to menu)

Project Scheduling Analysis: The Critical Path Method (CPM)

What

Interactive service processes vary in heterogeneity.  Some services are somewhat standardized, such as the process of changing the oil in a car.  The oil change service provider pretty much does the same procedure on every car, although some peculiar cars may cause the procedure to vary.

Other services are so homogeneous that each customer receives a somewhat unique procedure.  In fact, sometimes the procedure needs to be redesigned for every customer.  An example is many consulting projects, where the consultant first evaluates the client’s needs and then develops an entire plan of action based on those needs.

Complexes service processes of this nature often require systematic project scheduling.  Each step of the custom procedure needs to be considered in a master schedule.  That master schedule then guides the coordination of people and other resources towards the completion of the project.

How

The objective of project scheduling analysis is to determine (a) when each step (or activity) of a project needs to begin and end, and (b) what alternative schedules may be used in case of unforeseen project difficulties.

An activity is a task that needs to be accomplished as part of a project.  Throughout projects, we also have events, which are points in time such as the starting or completion of a particular activity.

Each activity has a duration.  Sometimes the activity duration is known precisely.  Other times it may be random according to some probability distribution.  There is always the possibility that an activity will be delayed from the originally expected start time or duration.  Part of project scheduling analysis will be to determine what the best course of action is when an activity is delayed.

Project scheduling can be enhanced by creating a graph, which is a graphical representation of the project activities.  (Another name for a project graph is a project network.)  There are two types of project graphs:  activity-on-node and activity-on-arrow.

For example, consider the project for a home painting firm to paint a house may include:

Activity A must be first.  Activity B must be completed before any painting.  The trim and walls can be worked on simultaneously (by different workers) but both must be done before invoicing the customer.

This can be depicted with an activity-on-node graph.  A node is a point or circle on a graph that represents an event.  Activity nodes are connected by a directed line called an arrow or an arc.  The arrows show precedence relationships, which will be described below.

This graph could alternately be depicted as an activity-on-arrow graph.

Note that these two graphs are equivalent in that they represent the same project.  However, activity-on-arrow graphs sometimes need “dummy” activities that are not really activities but help accurately represents the project.  In the example above, the dummy activity allows us to connect activity C into activity E without using curved arrows.  (For some reason, we do not use curved arrows in project graphs – I do not know why.)

The most valuable thing about a project graph is that it depicts the precedence relationships between the various activities.  Some activities have predecessors, which are activities that must be completed before the current activity is started.  An immediate predecessor (I.P.) is an activity that comes immediately before a given activity on a graph. 

In the example above, activity A is an I.P. for activity B, and has an arrow showing this precedence relationship.  In other words, we cannot paint the walls until fixtures and windows are taped off.  Other immediate predecessors are as follows:

 

Activity

I.P.

A

(none)

B

A

C

B

D

B

E

C, D

The opposite of a predecessor is a successor, which is an activity that cannot be started until the current activity is completed.  With the activity-on-node method, we place arrows on the graph pointing from activities to their immediate successors (I.S.).  In the above example, activity B is an immediate successor of A.

Often we create a node that marks the start of the project called a start node.  The start node has zero duration, and has arrows pointing to all activities that have no immediate predecessor.  (The start node is their immediate predecessor.)  It is also common convention to create an end node with zero duration that has all activities without immediate successors pointing to it.  In the above example, activities B, C, and D might be actual activities, and A and E might be the start node and end node, respectively.  (For the example above we will assume that A is the start node and E is the end node, even though they are actual activities.)

It is useful to write the estimated activity durations on the graph by each node.  This information will be useful in determining the project schedule.  For the present we will assume that the activity durations are known as a fixed value (t).  The following are durations for our hypothetical example:

 

Activity

I.P.

t

A

(none)

0

B

A

3

C

B

2

D

B

4

E

C, D

0

The first thing we want to do is determine a schedule of the earliest each activity can begin.  As just suggested, we sometimes start project schedules with a “dummy” activity of 0 duration called the “start node.”  The start node always begins at time 0, which marks the beginning of the project.

(For simplicity, we will assume herein that each time period is a day.  However, this does not necessarily have to be the case.  A time period can be a week, an hour, or some other period.)

Any activities without any immediate predecessors have an arrow pointing to them from the start node.  These activities will all have an early start date, or ES, of 0.  The early start date is the first day an activity can start if there are no delays.  Once you have calculated the ES for any given activity you can immediately calculate the early finish date, or EF, as:

EF = ES + t

 

where t is the given activities duration (which is sometimes denoted by d).  Note that EF actually calculates as the day after the activity is completed, since time is treated as being continuous.  If an activity has a ES=5, a t=2, then EF=7.  That activity will start at the beginning of day 5, will take 2 days, and will be done just prior to day 7 (at the earliest).

All activities that have ES days should also have EF days calculated.  This will be demonstrated below.

At this point, some activities in the graph may not have ES days yet.  Any such activity for which all immediate predecessors have EF days will have the ES day equal to the maximum EF day for all immediate predecessors.  The maximum is used because the given activity cannot be started until all immediate predecessors are completed.

This process of determining ES and EF days is repeated throughout the graph until they are calculated for all activities.  Again, by convention, all activities in the project that have no immediate successors have an arrow pointing to a end node, which is a zero-duration activity that signifies the completion of the project.  So, of course, the end node has an ES and EF day equal to the maximum EF day of the graph.

This process of calculating ES and EF days is called the forward pass.

The overall completion of the project, which is the EF of the end node, is generally denoted T (capital T).  T represents the number of days it will take to complete the project if everything goes exactly as planned in this schedule.  The fact is, things seldom go as planned.  Activities are delayed or other problems arise.

One important question may be how many days can an activity can be delayed from its early start day before delaying the entire project.  This can be determined by doing a backward pass of calculations.

We begin the backward pass by calculating the late finish, or LF, of the end node, which is the latest that activity can be completed without delaying the entire project completion.  Of course, the latest the end node can be completed is T, the overall project duration.  Once we have the LF for any given activity, we can immediately calculate the late start, or LF, for that activity by:

LS = LF - t

where, again, t is the activity’s duration.

Any activity for which all immediate successors have LS days calculated will have a LF value equal to the minimum of the LS values for all immediate successors.  It is the minimum because the given activity has to be finished before any of the immediate successors begin.

This process, the backward pass, is repeated until LS and LF days are calculated for all activities of the project.  If it is done correctly, then you will find that the LS of the start node will be 0, indicating that then entire project cannot be delayed from the start without delaying the entire project at the end.

The question is, how much an each specific activity be delayed without delaying the entire project.  This possible delay amount for each activity is called the slack (although some people call it float).  The slack, or S, for a given activity is calculated as:

S = LS - ES

which is mathematically equivalent to

S = LF - EF.

All activities that have a slack which is greater than 0 can be delayed up to S periods without delaying the entire project.  (However, this may not be true if any predecessor activities have been delayed, which can consume some of the slack.)  The cost of delaying an activity with sufficient slack can be effectively zero.

Any activities that have a slack of exactly 0 are on the critical path.  These activities cannot be delayed even one day without delaying the entire project.  The cost of delaying any critical path activities will at least include the cost of delaying the entire project, unless the duration of other critical path activities can be reduced.  The significance of the critical path is why this analysis approach is called the critical path method, or CPM.

When faced with a choice between delaying a critical path activity or delaying a non-critical path activity, it us probably best to delay the latter.  Other analysis methods, such as PERT/Cost, help us to determine which activities to “crash,” or complete on an accelerated schedule to recover lost time.

With the simple example of a graph above, imagine that activity A is the start node, E is the end node, and activities B, C, and D have durations of 3, 2, and 4 respectively.  The following are the forward pass calculations for this project:

 

Activity

I.P.

t

 

ES

EF

A

(none)

0

 

0

0

B

A

3

 

0

0+3=3

C

B

2

 

3

3+2=5

D

B

4

 

3

3+4=7

E

C, D

0

 

max(5,7)=7

7+0=7

The overall project duration is the EF of the end node, in this case 7.  That means that the project could possibly be completed in 7 days.  That 7 becomes the LF value for the end node, allowing us to work backwards in the backward pass and calculate LF and LS values.  This requires that we follow the sequence if immediate successor (I.S.) activities, as defined above.  LF values are the minimum LS value for the immediate successor activities.  If an activity has only one immediate successor, then the LF for that activity is the ES for that immediate successor.  Calculations for the example are as follows:

 

Activity

I.P.

t

 

ES

EF

I.S.

LS

LF

A

(none)

0

 

0

0

B

0–0=0

0

B

A

3

 

0

3

C, D

3–3=0

min(5,3)=3

C

B

2

 

3

5

E

7–2=5

7

D

B

4

 

3

7

E

7–4=3

7

E

C, D

0

 

7

7

(none)

7–0=7

7

We can then calculate activity slack time as LS–ES (or LF–EF):

 

Activity

I.P.

t

 

ES

EF

I.S.

LS

LF

S

A

(none)

0

 

0

0

B

0

0

0–0=0

B

A

3

 

0

3

C, D

0

3

0–0=0

C

B

2

 

3

5

E

5

7

5–3=2

D

B

4

 

3

7

E

3

7

3–3=0

E

C, D

0

 

7

7

(none)

7

7

7–7=0

The activities that have a slack of zero are on the critical path, meaning that if they are delayed from their ES times, the overall project will be delayed.  In this example, activities A, B, D, and E are on the critical path.

Activity C has a non-zero slack of two, meaning that activity C can be delayed up to two periods from the ES time without delaying the overall project.

This was an extremely simple example, just for illustration.  With more complex projects it is important to recognize that activities can possibly share slack times, so that if one activity uses up some slack, then later activities may have less slack than they did, and some new activities may join the critical path.  The way to know this is to recalculate the values for the portion of the project remaining to be completed.

How: Probabilistic Projects

In some situations the activities of a given project do not have known (“deterministic”) durations, but instead have a range of possible durations.  In that case we may desire to know the probability that the project will be completed by a specified time period.

A simple method for estimating the completion time of probabilistic projects is to estimate the mean and standard deviation of durations of each activity.  That information can be used to calculate the mean and standard deviation of the overall project.

Begin by estimating the following duration values for each activity:

·         the optimistic completion time, which is the shortest time the activity can be reasonably completed (designated to)

·         the most likely completion time (designated tm)

·         the pessimistic completion time, which is the longest time the activity can reasonably be expected to take to completion (designated tp)

From that information we can estimate the activity duration expected value by the following equation:

The activity duration standard deviation is estimate by:

implying that the activity duration variance is

If we sum the expected values of activities along a path (sequence) of activity, it will tell us the expected value of the path.  Likewise, if we sum the variances of activities along a path, it will tell us the variance of the path.  (Remember that we cannot sum standard deviations, but instead sum variances.)

If we have the duration mean and standard deviation of the activity path, we can calculate the probability of the path being completed by a given date.  First, we assume (according to the central limit theorem) that the project completion time will be normally distributed.  We calculate a z statistic using the following equation:

Looking that z statistic up in a cumulative normal distribution table, or using the Excel NORMDIST function, will tell us the probability that the path of activities will be completed by the target time.  If there are multiple independent paths, the probabilities for each can be multiplied together to determine the joint probability that all of the paths will be completed by the target date.  (This assumes the two paths are independent, including that they do not share the same labor or other resources.)

For example, a project has two paths, each with three activities as follows.

First path

Second path

Activity

to

tm

tp

Activity

to

tm

tp

A

3

4

5

D

2

6

9

B

2

5

7

E

4

5

6

C

4

6

7

F

3

4

6

We can calculate estimated path means and variances using the equations above:

First path

Second path

Activity

to

tm

tp

te

σ2

Activity

to

tm

tp

te

σ2

A

3

4

5

4.00

0.11

D

2

6

9

5.83

1.36

B

2

5

7

4.83

0.69

E

4

5

6

5.00

0.11

C

4

6

7

2.83

0.25

F

3

4

6

4.17

0.25

sums

14.67

1.06

sums

15.00

1.72

square root

1.03

square root

1.31

Imagine that we want to determine the probability that this project will be completed within 16 periods (our target time).  We can calculate a z statistic for the first path as (16-14.67)/1.03=1.30.  We can look up z=1.03 in a normal cumulative distribution table, or use the Excel NORMINV(1.03,0,1,TRUE) function to calculate a probability of 0.9028.  That means there is about a 90 percent chance the first path will be completed by 16 weeks.  (Note that we can have the NORMINV function calculate the z statistic for us by entering NORMINV(target,mean,standard deviation,TRUE) as in NORMIN(16,14.67,1.03,TRUE).)

Similarly, for the second path we have a z statistic of (16-15)/1.31=0.762, which corresponds to a probability of 0.777 or a 78 percent chance of completion.  For both paths to be completed we multiple 0.9028 times 0.762 to get 0.7015, implying a 70 percent probability both paths will be completed within 16 periods.

Quantitative Tools for Service Operations Management by Dr. Scott Sampson ©2012 (return to menu)