Scheduling Activities (Edexcel International A Level Maths) : Revision Note

Scheduling Activities

What is meant by scheduling (activities)?

• Scheduling activities is the process of assigning workers to activities within a project

• The two types of problem that arise involve 

  • Finding the minimum number of workers such that a project can be completed in its minimum project duration

    • The minimum project duration is also called the critical time of the project

  • Finding the (new) minimum project duration given that there are constraints

    • E.g. There may be a maximum number of workers available at any given time

• In harder problems, certain workers may only be capable of carrying out particular activities

What assumptions are made in scheduling?

• In scheduling activities the following assumptions are made

  • Each activity requires only one worker

    • Or one team of workers, i.e. one resource

  • An activity is assigned the first available worker

  • If there is a choice of activities, assign a worker the activity with the lower late end time

    • This is the lower late event time at the activity end node

  • A worker can only work on one activity at a time

  • Once a worker has started an activity, that activity needs to be completed

How do I schedule activities for a project that requires the minimum number of workers?

• For this type of problem, the critical time of the project cannot change

  • The critical activities cannot be delayed

  • One worker (resource) will complete all the critical activities 

• Using a Gantt chart and considering the non-critical activities

  • Non-critical activities can be delayed, but only within their (total) float times

    • Early start times can be delayed but late end times cannot

  • Visualise each activity as its bar being able to 'slide' within its box (solid and dotted)

    • Aim for as few overlaps between activities as possible

  • Activities can then be combined into as few rows as possible

    • Place them 'back-to-back'

    • Where possible activities should start immediately after others end

  • Each row on the (reduced) Gantt chart will then be completed by one worker

    • The number of rows is the number of workers

• Remember that the precedence of activities needs to be maintained

  • E.g.  Activity H, say, cannot move so it starts after activity I, as activity I depends on H being completed first

    • H is an immediate predecessor of I

What is the lower bound for the (minimum) number of workers?

• The theoretical lower bound for the number of workers to complete a project in its minimum project duration is

  •  the smallest integer value that satisfies

• To find a practical lower bound for the number of workers

  • Imagine vertical lines drawn in between each unit

    • e.g. vertical lines at 0.5, 1.5, 2.5, etc

  • For each line, consider which activities can use their float to move so that the line does not touch them

  • Count the number of activities which cannot be moved and must happen at that time

  • The biggest number found is a lower bound 

• It is not always possible to schedule activities such that the lower bound can be met

How do I schedule activities for a project that has a maximum number of workers?

• For a problem, where there is a maximum number of workers available at any point in time

  • The maximum number of workers cannot be exceeded,

  • It may require activities to be delayed and the project's critical time to be increased

• Using a Gantt chart

  • Find the minimum number of workers required to complete the project in its critical time

    • The Gantt chart would have already been largely reduced

    • Do this using the process above

  • Consider how any activity (critical or non-critical) can be delayed

    • The Gantt chart must use no more rows than the (maximum) number of workers available at any time

• As in the first type of problem, the precedence of activities needs to be maintained

  • You may want to use the activity network to check this 

  • E.g.  Activity H, say, cannot move so it starts after activity I, as activity I depends on H being completed first

    • H is an immediate predecessor of I