Gantt charts, resource histograms and levellingAQA A-Level Further Maths: Revision notes

A cascade diagram (Gantt chart) shows each activity as a horizontal bar against a time axis, so you can see what is happening on any given day. To construct one, first carry out a forward and backward pass on the activity network and find the float of every activity.

• Draw the critical activities first (on one line, or the top lines), each starting at its earliest start time. They have no float, so they form an unbroken chain from time 0 to the minimum completion time.
• Draw every other activity as a bar from its earliest start time, and show its float after the bar (usually shaded or dashed), so that the bar plus float ends at the latest finish time.
• Show the order of activities with their precedences, so an activity never starts before its predecessors' bars end.

Reading the chart: the bar for an activity gives its earliest start and finish, the float tells you how far it can slip without delaying the project, and drawing a vertical line at any time shows which activities are running then.

A resource histogram is a bar chart of the number of workers (or other resource) needed in each time period. To construct one from a cascade diagram, draw a vertical line at each unit of time and add up the workers for every activity running in that period.

• Work out the demand period by period. If P needs 2 workers from day 0 to day 3 and Q needs 3 workers from day 0 to day 4, the demand on days 0 to 3 is $2+3=5$. If R (2 workers) starts on day 3, the demand from day 3 to day 4 is $3+2=5$.
• The peak of the histogram is the largest number of workers needed at any time.
• The total number of worker-days is the sum over all activities of (duration $\times$ workers), which equals the area under the histogram.

Reading a histogram tells you whether the available workforce is enough, and which periods are overloaded.

Resource levelling smooths the histogram so that the demand is as even as possible, or never exceeds a limit, without making the project later. There is no algorithm that always gives the best answer, so a heuristic procedure is used:

1. Draw the cascade diagram with every activity at its earliest start and the resource histogram below it.
2. Find the periods where demand is too high.
3. Delay non-critical activities that run in those periods, using their floats, until the demand is acceptable. Delaying a critical activity delays the whole project.
4. Redraw the histogram, check the precedences, and check that no new peak has been created.

A delayed activity uses up some of its float and may also reduce the float of activities that follow it, so recalculate. If the limit cannot be met without moving critical activities, the project must be extended.

When each activity needs one worker and the number of workers is limited, ask two questions.

• Lower bound: the minimum number of workers needed to finish in the minimum time $T$ is at least $\frac{\text{total of all durations}}{T}$, rounded up to the next integer.
• Schedule: build a schedule (a list of what each worker does and when) to show that this number really is enough. Start critical activities at their earliest time, then use free workers on non-critical activities, respecting precedences.

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). The minimum time is $\max(4,\ 3+2)+5=10$ days, with X, Z, W critical. Total duration is $3+4+2+5=14$, and $\frac{14}{10}=1.4$, so at least 2 workers. Worker 1 does X, Z, W and worker 2 does Y (days 0 to 4), which works.

If there are fewer workers than the lower bound, the project takes longer than the minimum time.