A-level Mathematics/MEI/D1/Critical Path Analysis

Introduction

Critical path analysis is an analytical technique that can be used to determine how to best schedule and use resources to maximise efficiency. For example critical path analysis can be applied to a construction project, like building a house, where activities (such as 'laying the foundations') have two properties: duration and precedents, a table can be constructed showing which activities come before others (precedents) and the

Activity Networks

Activity networks model the precedence and duration of activities, once drawn they can used to analyse which activities are critical then critical path(s) can then be deduced and noted on the network.

Preparation

First a table of activities must be procured or produced, it should note which activities are precedents to others.

Creation

The network using the following abstractions:

• Nodes: Events (The start of an activity, or the end of an activity)
• Arcs: Activities

A start node is drawn, then the first activities (or activity) is drawn as an arc connecting the start node and a second node (which denotes the ending of the activity).

In the case of an activity with two or more precedents, dummy variables are used to model precedence.

Here activity D is only able to start after A,B and C have been completed, A,B and C are D's precendents, To model this as a network, A,B and C will be arcs leaving the start node each going to a different node (specifying the end of each respective activity), we can arbitrarily choose any of those nodes for activity D's arc to leave, in this case, B is chosen (though A or C could also be used as the choice is arbitrary)). Dummy activities (denoted by a dotted arc) are drawn from the end node of arcs A and C to the end node of arc B, these represent the precedence of the activities indicating A,B and C must be complete before D can be carried out.

Analysis

Having drawn the activity network, boxes with two cells are drawn:

These boxes will be used as we carry out the forward pass and the backward pass.

Float

There are three different types of float, each with a different physical interpretation:

• Total float: The amount of time a task can be delayed without delaying the completion of the project
• Independent float: The amount of time a task can be delayed without delaying the starts of any of it's successors

Formulas:

For an activity connecting node 'i' and node 'j' ('i' being the earlier node in the task), with duration 'd'.

• LET(i) = latest event time of i
• EET(i) = earliest event time of i

• Total float: LET(j) - EET(i) - d
• Independent float: EET(j) - LET(i) - d (if negative, answer = 0)

It shouldn't be necessary to memorise these formulas, readers are encouraged to develop an intuitive, tangible interpretation of the two types of float and derive the formulas when needed.

=====Example=====

Calculating the total and independent float of activity F.

• The nodes that shall be used to calculate the float are the start and end of the activity: 3 and 6.
• Total float: This is greatest amount of time we can wait before starting the activity and getting it finished before the next activity must start. Node 6 indicates the latest time the node can be left is 9, so our activity must be finished by then. Node 3 indicates we could start the activity as early as 2, the duration of the activity is 2, so in the space of (9-2)=7 units of time, the activity must be done, which takes 2 units of time, leaving 5 units of time, this is the total float
• Independent float: Now we want to know how much time the activity is left in the worst case scenario (i.e. minimize the chance of any float: leave the start node as late as possible, and enter the end node as early as possible). Node 3 can be left at 4 at the latest, and node 6 can be entered at 4 at the earliest, this means there is no independent float, if the earliest we could enter node 6 was 7 then we would do our task in 2 units of time leaving 1 unit of time over which would be the independent float of the activity.