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

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