Gantt charts and schedulingEdexcel International A Level Maths: Revision notes

A Gantt chart (also called a cascade chart) shows when each activity takes place. Time runs along a horizontal axis, and each activity has its own row. The standard way of drawing one:

• draw each activity as a bar from its earliest start time to its earliest finish time ($e(i)$ to $e(i)+d$);
• the critical activities have no float, and are often drawn first (or at the top) as a continuous chain of bars;
• show each non-critical activity's float as a dotted or lighter line after its bar, extending to its latest finish time;
• draw an arrow, or order the rows, so that an activity starts only after all its predecessors have finished. The chart is built from the precedence table and the earliest and latest times found by forward and backward passes.

A cascade chart lets you read:

• the minimum completion time: the finish of the last critical activity;
• the critical activities: those with no float line;
• the float on each activity: the length of its float line, or latest finish minus earliest finish;
• which activities are in progress at any time, by drawing a vertical line at that time (the activities it crosses) and counting. Example: with A 0 to 4, B 0 to 3, C 4 to 9 and D 4 to 10, at time 5 the activities in progress are C and D, so at least two workers are needed then. If an activity is delayed by up to its float, nothing else changes; a delay greater than its float delays the project by the excess.

Scheduling means deciding which worker does which activity and when, so that the project is completed in a given time, subject to precedence. The usual assumptions are that each worker does one activity at a time, an activity cannot be interrupted or shared, and workers are equally skilled. Because the critical path decides the minimum time, a schedule can never be shorter than it, however many workers there are. Workers can be idle at times (for example while waiting for a predecessor), so more workers than the lower bound may be needed.

If the total of all activity durations is $S$ and the project must be completed in time $T$ (usually the minimum completion time), the number of workers needed is at least $\left\lceil\frac{S}{T}\right\rceil,$ that is, $\frac{S}{T}$ rounded up to the next whole number. Example: durations $4+3+5+6+4+2+3=27$ and $T=16$ give $\frac{27}{16}=1.69$, so at least 2 workers. It is only a lower bound: the real number may be larger because precedence prevents the work being shared evenly. To prove 2 workers are not enough, show that the activities left for the second worker cannot all fit in the time available.

1. Find earliest and latest times, the critical activities and the minimum time.
2. Give the critical activities to one worker, at their earliest times, since they have no float.
3. Allocate the remaining activities to other workers, respecting precedence: an activity starts only after all its predecessors are finished, and when its worker is free.
4. Use float to fit activities in. Do the activities with the least float first.
5. Check every precedence relationship and the final completion time. If the target time cannot be met, say which activity is delayed and by how much. Example: critical tasks B, D, F (0 to 5, 5 to 11, 11 to 14) for one worker; A (0 to 3), C (3 to 7), E (7 to 9) for the other. Task E needs A and B finished, and F needs C, D, E finished, so the schedule is valid.