Gantt charts and scheduling

Gantt charts and scheduling

Spec 4.4 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A cascade (Gantt) chart draws each activity as a bar from its earliest start to its earliest finish, with float as a dotted line.
  • Critical activities form an unbroken chain with no float.
  • From a chart you can read the minimum time, the critical activities, each float, and which activities are in progress at a time.
  • In scheduling each activity is done by one worker, without interruption, and no schedule beats the critical path.
  • The number of workers needed is at least ⌈ST⌉\left\lceil\frac{S}{T}\right\rceil: total duration over completion time, rounded up.

Cascade charts

A cascade chart has a row for each activity: a bar from earliest start to earliest finish, with a dotted line showing float up to the latest finish.

A Gantt chart (also called a cascade chart) shows when each activity takes place. Time runs along a horizontal axis, with one row per activity.

  • Draw each bar from e(i)e(i) to e(i)+de(i)+d.
  • Critical activities have no float, so draw them first as a chain of bars.
  • Show each non-critical activity's float as a dotted line after its bar.

It is built from the precedence table and the earliest and latest times.

  1. 1

    Find the times

    earliest start, latest finish and float for each activity

  2. 2

    Critical chain

    bars with no float, joined end to end

  3. 3

    Other bars

    from earliest start to earliest finish

  4. 4

    Float lines

    dotted, up to the latest finish

  5. 5

    Check precedence

    no bar starts before its predecessors finish

Drawing a cascade chart

What does a dotted line after a bar show?

Reading a chart

You can read the minimum time, the critical activities, each activity's float, and which activities are in progress at any time.

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.

To see what is in progress at a time, draw a vertical line at that time and count the bars it crosses.

A (0 to 4)B (0 to 3)C (4 to 9)D (4 to 10)A1A2B1B2C1C2D1D2t = 5T2
Reading a chart: at time 5, a vertical line crosses the bars for C and D, so two activities are in progress

Where to read it

Minimum time:
End of the last critical bar
Critical activities:
Bars with no float line
Float:
Length of the dotted float line
In progress at time t:
Vertical line at time t

Same as

Minimum time:
Critical path length
Critical activities:
A chain from start to finish
Float:
Latest finish − earliest finish
In progress at time t:
Count the bars it crosses
Information on a chart

Worked example

A runs 0 to 4, B runs 0 to 3, C runs 4 to 9 and D runs 4 to 10. How many activities are in progress at time 5?

An activity has a float line of length 3 after its bar. It is delayed by 5. By how much is the project delayed?

The idea of scheduling

Scheduling decides which worker does which activity and when, so the project meets a target time while following the precedence rules.

Scheduling means deciding which worker does which activity and when.

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, no schedule can be shorter than it, however many workers there are.

Workers can be idle while waiting for a predecessor, so more workers than the lower bound may be needed.

  1. 1

    Find the critical path

    no schedule can finish sooner than this

  2. 2

    Allocate activities to workers

    each worker does one activity at a time, without breaks

  3. 3

    Check precedence

    an activity starts only after its predecessors finish

Scheduling activities
  • Any scheduletakes at least as long as the critical path

Why can adding more workers never make the project shorter than the critical path?

Lower bound for workers

The number of workers needed is at least the total of all durations SS divided by the completion time TT, rounded up to the next whole number.

If the total of all durations is SS and the project must be completed in time TT (usually the minimum completion time), the number of workers is at least ST\frac{S}{T} rounded up.

It is only a lower bound. The real number may be larger because precedence prevents work being shared evenly.

To prove 2 workers are not enough, show the activities left for the second worker cannot all fit in the time available.

051015202530Total work S1 worker, T = 162 workers, 2T = 32Days of work
Total work S = 27 days against the time available: one worker has 16 days, two workers have 32
  • Number of workers≥⌈ST⌉\ge\left\lceil\dfrac{S}{T}\right\rceil

Worked example

The durations are 4, 3, 5, 6, 4, 2 and 3, and the project must finish in 16 days. Find a lower bound for the number of workers.

Total work is 30 days and the project must finish in 8 days. What is the lower bound for workers?

Constructing a schedule

Give the critical activities to one worker at their earliest times, then fit the others around them, using float and checking every predecessor.

  1. Find the times, the critical activities and the minimum time.
  2. Give the critical activities to one worker at their earliest times.
  3. Allocate the other activities to other workers, respecting precedence. An activity starts only when all its predecessors are finished and its worker is free.
  4. Use float to fit activities in, doing those with the least float first.
  5. Check every precedence and the final completion time. If the target cannot be met, say which activity is delayed and by how much.
BDFACEB1B2D1D2F1F2A1A2C1C2E1E2
A valid schedule finishing at 14: Worker 1 does B, D, F; Worker 2 does A, C, E

Worker 1 (critical)

  • B (0 to 5)
  • D (5 to 11)
  • F (11 to 14)

Worker 2

  • A (0 to 3)
  • C (3 to 7)
  • E (7 to 9)
A valid schedule finishing at 14

Here E needs A and B finished, and F needs C, D and E finished. E starts at 7, after B (5) and A (3). F starts at 11, after C (7), D (11) and E (9). The schedule is valid and finishes at 14.

When allocating non-critical activities, which should you place first?

Try an exam question

A project has activities A (4 days, no predecessor), B (3 days, none), C (5 days, after A), D (4 days, after A and B) and E (2 days, after C and D). (a) Find the minimum completion time and the critical activities. (b) Find a lower bound for the number of workers needed to finish in the minimum time.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the earliest start time of activity E?

1 mark, marked against the mark scheme

Revision notes