How to Find a Project's Critical Path Using CPM

TL;DR

Find the critical path by building the activity-on-node network, calculating earliest times with a forward pass, and calculating latest times with a backward pass. Activities with zero slack form the critical path. In the worked example, the project finishes at time 19, and the critical path is A, B, D, F.

Transcript

Hello friends, welcome to the Gate Smashers. In today's video, we are going to discuss questions on optimization. There are basically two types of questions in optimization, either linear programming LPP or PERT/CPM. So in this video, we are going to discuss the question on CPM. So guys, quickly like the video. Subscribe to the channel if you haven... Read More

Key Insights

• The activity-on-node network is built from predecessor relationships. A has no predecessor, B and C depend on A, D depends on B, E depends on C, and F depends on both D and E before the project can finish.
• The forward pass is used to calculate each activity's earliest start and earliest finish. An activity's earliest finish equals its earliest start plus its duration, beginning with activity A at time 0 because no earlier activity must be completed.
• The earliest start of an activity with one predecessor equals that predecessor's earliest finish. B therefore starts when A finishes at 5, D starts when B finishes at 9, C starts at 5, and E starts when C finishes at 10.
• The earliest start of an activity with multiple predecessors uses the maximum predecessor finish time. F depends on D and E, which finish at 15 and 13, so F starts at 15 and finishes at 19 after its duration of 4.
• The backward pass moves from the project finish toward the start to calculate latest finish and latest start. The latest start of an activity equals its latest finish minus its duration, while slack equals latest finish minus earliest finish.
• The latest finish of a predecessor is determined by the successor's latest start. When a predecessor leads to multiple successors, the backward calculation uses the minimum successor value, so A uses 5 rather than 7 as its latest finish.
• Slack time represents the available delay for an activity under the demonstrated calculation. A, B, D, and F have slack of 0, while C and E each have slack of 2, distinguishing the critical activities from the noncritical branch.
• The critical path is A, B, D, F because every activity on that path has zero slack. The other valid route, A, C, E, F, is not critical because C and E each have slack of 2.

Questions & Answers

Q: How do you create an activity-on-node CPM network?

Create the network by placing each activity in a node and connecting it according to its predecessor relationship. In the example, A comes first because it has no predecessor. B and C follow A, D follows B, and E follows C. F follows both D and E, meaning both activities must finish before F can begin and the project can be completed.

Q: How do you calculate earliest start and finish in CPM?

Use a forward pass from the start of the project to its finish. The first independent activity has an earliest start of 0. For each activity, add its duration to its earliest start to obtain its earliest finish. When there is one predecessor, the activity's earliest start equals that predecessor's earliest finish. This process produces the upper timing values for every node.

Q: What happens when a CPM activity has multiple predecessors?

An activity with multiple predecessors cannot start until all of them have finished, so its earliest start uses the maximum of their earliest finish times. F depends on both D and E. D finishes at 15 and E finishes at 13, so F must wait until 15. With a duration of 4, F then finishes at time 19.

Q: How do you calculate latest start and latest finish in CPM?

Use a backward pass beginning at the project's finish time. For F, the latest finish is 19 because that is when the project finishes. Its latest start is calculated as latest finish minus duration, giving 19 minus 4, or 15. Earlier activities receive latest finish values from the latest start values of the activities that follow them.

Q: What formulas are used to calculate CPM slack and latest start?

The demonstrated slack formula is latest finish minus earliest finish. The latest-start formula is latest finish minus duration. For F, latest finish and earliest finish are both 19, so its slack is 0. Its duration is 4, so its latest start is 15. These formulas are applied to each activity during the backward pass.

Q: Why does the CPM backward pass use the minimum value?

When moving backward through a branching network, the predecessor must be completed early enough for every following activity to meet its latest start. A leads to B and C, whose relevant backward values are 5 and 7. The minimum is 5, so A receives a latest finish of 5. Using 7 would not satisfy the earlier requirement associated with B.

Q: How do you identify the critical path from slack times?

Identify the valid paths through the dependency network, then select the path whose activities all have zero slack. The two valid paths in the example are A, B, D, F and A, C, E, F. A, B, D, and F each have zero slack, while C and E each have slack of 2. Therefore, A, B, D, F is critical.

Q: What is the project duration in the CPM example?

The project duration is 19 time units. Along the controlling branch, A finishes at 5, B finishes at 9, and D finishes at 15. The other branch reaches E's finish at 13, but F must wait for D at 15 because it depends on both branches. F then takes 4 more time units and finishes at 19.

Summary & Key Takeaways

• The project contains activities A through F with predecessor relationships and durations. A starts independently, B and C follow A, D follows B, E follows C, and F begins only after both D and E finish. These dependencies create an activity-on-node network with two valid paths from project start to completion.

• A forward pass calculates earliest start and earliest finish times. A runs from 0 to 5, B from 5 to 9, D from 9 to 15, C from 5 to 10, and E from 10 to 13. F must wait for D, so it runs from 15 to 19.

• A backward pass calculates latest finish, latest start, and slack. F, D, B, and A each have zero slack, while E and C each have slack of 2. Therefore, A, B, D, F is the critical path. The alternative path, A, C, E, F, contains activities with nonzero slack.