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

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

• 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