Gantt charts, resource histograms and levelling
Studying this course? Keep your progress in one place.
Key facts
- A cascade diagram shows each activity as a bar, with critical activities unbroken and float shown after non-critical bars.
- A resource histogram shows the workers needed in each period; its peak is the greatest demand.
- Worker-days are the sum of duration workers, equal to the area under the histogram.
- Resource levelling delays non-critical activities within their float to flatten peaks.
- With one worker per activity, the lower bound on workers is total duration minimum time, rounded up.
Cascade (Gantt) diagrams
Draw each activity as a bar from its earliest start, with its float shown after the bar.
A cascade diagram (Gantt chart) shows each activity as a horizontal bar against time.
First do a forward and backward pass to find every float. Draw the critical activities first; they have no float and form an unbroken chain from 0 to the minimum completion time. Draw every other activity from its earliest start and shade its float after the bar, so the bar plus float ends at the latest finish.
A vertical line at any time shows which activities are running then.
- 1
Passes
Forward and backward pass; find every float
- 2
Critical
Draw critical activities from their earliest starts
- 3
Others
Draw each other bar from its earliest start
- 4
Float
Shade the float after each bar
- 5
Check
No bar starts before its predecessors end
An activity has EST 2, duration 3 and LFT 9. How long is the float shown after its bar?
Resource histograms
Add up the workers for every activity running in each time period, then draw the totals as bars.
A resource histogram is a bar chart of the workers (or other resource) needed in each period. Draw a vertical line at each time unit of the cascade diagram and add the workers for every activity running.
If P needs 2 workers from day 0 to 3 and Q needs 3 workers from day 0 to 4, demand on days 0 to 3 is . The peak demand is the largest number needed at once. Worker-days are the sum over all activities of duration workers, equal to the area under the histogram.
Take X on days 0 to 3, Y on days 0 to 4, Z on days 3 to 5 and W on days 5 to 10, one worker each.
P needs 2 workers for days 0 to 3, and Q needs 3 workers for days 0 to 4. How many worker-days are used in total?
Resource levelling
Delay non-critical activities within their floats to flatten the peaks, without making the project later.
Resource levelling smooths the histogram so demand is even, or never exceeds a limit. No algorithm always gives the best answer, so a heuristic is used.
A delayed activity uses up some of its float and may reduce the float of activities that follow, so recalculate. If the limit cannot be met without moving critical activities, the project must be extended.
- 1
Earliest-start chart
Draw the cascade diagram and histogram
- 2
Find the peaks
Periods where demand is too high
- 3
Delay non-critical activities
Use their floats, never critical ones
- 4
Redraw and check
Precedences hold and no new peak appears
Move the activity with the most float first, and check the whole project still finishes on time.
Why can resource levelling only delay non-critical activities?
Scheduling with limited workers
Divide the total duration by the minimum time and round up, then show a schedule that works.
When each activity needs one worker, the lower bound on the number of workers needed to finish in the minimum time is the total of all durations divided by , rounded up.
Then build a schedule (what each worker does and when) to show that number is enough. Start critical activities at their earliest time, then use free workers on non-critical activities, respecting precedences.
With fewer workers than the lower bound, the project takes longer than the minimum time.
- Lower bound on workers, rounded up
Worked example
X takes 3 days (no predecessor), Y takes 4 days (no predecessor), Z takes 2 days (after X), W takes 5 days (after Y and Z). Each needs one worker. Find the minimum number of workers to finish in the minimum time.
- 1
Minimum time: days, with X, Z, W critical.
- 2
Total duration is .
- 3
Lower bound: , so at least 2 workers.
- 4
Schedule: worker 1 does X, Z, W. Worker 2 does Y (days 0 to 4).
The total of all durations is 21 days and the minimum completion time is 8 days. What is the lower bound on the number of workers?
Try an exam question
Each activity in a project needs one worker. The total of all the activity durations is days and the minimum completion time is days. Find a lower bound for the number of workers needed to finish in the minimum time, and explain what else is needed to show that this number is sufficient.
[3 marks]
- [1].
- [1]Rounded up, at least workers are needed.
- [1]A schedule must be constructed showing that workers can complete every activity in days, respecting the precedences.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the minimum time in which the project can be completed?
1 mark, marked against the mark scheme
What is the minimum time in which the project can be completed?
1 mark, marked against the mark scheme