Welcome to Critical Path Analysis!
Ever wondered how massive projects like building a skyscraper, launching a satellite, or even organizing a music festival stay on track? They use a technique called Critical Path Analysis (CPA). In this chapter of Decision Mathematics 1, you will learn how to break down a complex project into individual tasks, find out which tasks are the most urgent, and figure out the quickest way to get the whole job done. Don’t worry if it seems like a lot of boxes and arrows at first—we’ll take it step-by-step!
1. Modeling a Project: Activity Networks
To analyze a project, we first need to represent it visually. We use an Activity Network. In this course, we specifically use the Activity on Arc (AoA) method.
The Basics
Activities: These are the tasks that need to be done (e.g., "Paint the walls"). They are represented by arcs (arrows). Each arrow has a direction showing the flow of time.
Events: These represent the start or completion of activities. They are represented by nodes (usually circles). Nodes don't take any time; they are just "milestones."
Precedence Table: A list that tells you which activities must be finished before others can start. If Activity B depends on Activity A, we say A is the immediate predecessor of B.
The Mystery of "Dummies"
Sometimes, you’ll need to draw a dashed arrow called a Dummy Activity. Dummies have a duration of zero. You need them for two reasons:
1. To show a specific precedence relationship that can't be drawn otherwise.
2. To ensure that two nodes are connected by only one activity (every activity must have a unique start and end node).
Analogy: Think of a dummy like a "ghost" worker who hands over a baton instantly. They don't do any work themselves, but they tell the next person, "Okay, you can start now!"
Key Takeaway: An activity network is a map of a project. Arrows are work; circles are the points in time when work starts or stops.
2. Finding the Timings: Forward and Backward Passes
Once your network is drawn, you need to calculate the event times. We divide our node circles into two halves to record these.
The Forward Pass (Earliest Event Times)
We start at the beginning (Node 0) and move forward through the network to find the Earliest Event Time (EET) for each node. This is the earliest time that all preceding activities can be finished.
The Rule: When you have multiple paths meeting at a node, take the largest value.
\( EET = \text{max}(EET \text{ of previous node} + \text{duration of activity}) \)
The Backward Pass (Latest Event Times)
We start at the very last node and move backward to find the Latest Event Time (LET). This is the latest time an event can happen without delaying the whole project.
The Rule: When moving backward and multiple paths meet, take the smallest value.
\( LET = \text{min}(LET \text{ of next node} - \text{duration of activity}) \)
Quick Review Box:
- Forward Pass: Move left to right, Add durations, pick the Biggest number.
- Backward Pass: Move right to left, Subtract durations, pick the Smallest number.
Key Takeaway: The forward pass tells you the project's minimum completion time. The backward pass tells you how much "wiggle room" you have.
3. Critical Activities and the Critical Path
A Critical Activity is a task where any delay will immediately delay the entire project. There is no wiggle room here!
How to identify a Critical Activity
An activity connecting node \( i \) to node \( j \) is critical if:
1. The EET and LET at the start node are the same (\( e_i = l_i \)).
2. The EET and LET at the end node are the same (\( e_j = l_j \)).
3. The duration of the activity fits perfectly: \( e_j - e_i = \text{duration} \).
The Critical Path is a continuous path of critical activities from the start node to the end node. A project can have more than one critical path!
Did you know? If you are managing a wedding and "Buying the Cake" is on the critical path, but "Buying Flowers" is not, a one-day delay in the cake means the whole wedding is delayed. A one-day delay in flowers might not matter at all!
Key Takeaway: The critical path is the "bottleneck" of the project. If you want to finish faster, you must shorten the activities on this path.
4. Total Float: Your "Wiggle Room"
Total Float is the amount of time an activity can be delayed without delaying the whole project.
The formula for the total float of an activity between node \( i \) and node \( j \) is:
\( F(i, j) = l_j - e_i - \text{duration}(i, j) \)
Simple way to remember: Latest finish time minus Earliest start time minus how long the task actually takes.
Common Mistake to Avoid: Students often forget that critical activities always have a total float of 0. If you calculate a float for a critical activity and get a number like 2, check your EET/LET subtractions again!
Key Takeaway: Float tells you how much flexibility you have with non-urgent tasks.
5. Visualizing the Schedule: Gantt Charts
A Gantt Chart (also called a cascade chart) is a horizontal bar chart showing when each activity happens.
- Each activity has a bar representing its duration.
- A dotted line or shaded area usually follows the bar to show its Total Float.
- Critical activities are usually listed at the top and have no float "tails."
Key Takeaway: Gantt charts make it easy for managers to see which tasks are happening on any given day.
6. Resource Management and Scheduling
In the real world, you don't have infinite workers. CPA helps us manage people efficiently.
Resource Histograms
A Resource Histogram is a bar chart showing the number of workers needed at any given time. We usually assume each activity needs exactly one worker (unless the question states otherwise).
By shifting activities within their "float" time, we can perform Resource Leveling. This means trying to keep the number of workers constant rather than having 10 workers on Monday and only 1 on Tuesday.
Calculating the Lower Bound of Workers
If you need to find the minimum number of workers required to finish the project on time, use this formula:
\( \text{Lower Bound} = \frac{\sum \text{all activity durations}}{\text{Critical path duration}} \)
Important: Always round up to the next whole number. You can't hire 2.3 workers!
Encouraging Phrase: Resource leveling can feel like a puzzle. Just remember you can move the "float" activities around, but you cannot move the critical ones!
Key Takeaway: Use the total work divided by the total time to find the minimum staff needed.
Final Summary of CPA
1. Model it: Create a network of arcs and nodes from the precedence table.
2. Time it: Use forward and backward passes to find EETs and LETs.
3. Analyze it: Identify critical activities (float = 0) and the critical path.
4. Schedule it: Use Gantt charts and histograms to manage your workers and time.
5. Optimize it: Calculate the lower bound of workers to ensure efficiency.