Scheduling Activities (Edexcel A Level Further Maths: Decision 1): Revision Note

Scheduling activities

What is meant by scheduling (activities)?

• Scheduling activities is the process of assigning workers (resources) 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 their are constraints (restrictions) on the 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 to assign a worker to choose the activity with the lower late end time

    • i.e.  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

    • i.e.  early start times can be delayed but late end times cannot

  • visualise each activity as its bar being able to 'slide' (back and forth) 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

    • by placing them 'back-to-back'

    • i.e.  where possible activities should start immediately after others end

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

    • i.e.  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

    • i.e.  H is an immediate predecessor of I

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

• The lower bound for the number of workers needed such that a project is completed in its minimum project duration is the smallest integer that satisfies

$\mathrm{Lower}\mathrm{bound}\ge \frac{\mathrm{Total}\mathrm{time}\mathrm{of}\mathrm{all}\mathrm{activities}}{\mathrm{Minimum}\mathrm{project}\mathrm{duration}}$

• 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 this type of problem, there will be a maximum number of workers available at any point in time

  • this cannot be exceeded, even if it requires activities to be delayed and the project's critical time 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

  • now consider how any activity (critical or non-critical) can be delayed such that

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

• As in the first type of problem, 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

    • i.e.  H is an immediate predecessor of I