Upcoming Events
Unite 2010
11/10 - 11/12 @ Montrιal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
66 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Critical Path Analysis and Scheduling for Game Development


Critical Path Analysis: Step 5

Now you have analysed the project, worked out what activities are involved, decided what the dependency list is, and calculated some times for those activities – and it's all included in your graph. You can now start the algorithm.

There is one final thing that you must do (to make it easier for you), which is to add in events. So far you've just added activities. Events are actually already in the graph – the red dots - but you need a way of identifying them. As you're already using letters for activities you'll use numbers for the events. Below is the revised graph:

Now, on with the algorithm. The first step is to work out what the earliest times are for each of the events (the numbered boxes). The value that you calculate will be the earliest possible time that you can arrive there with all incoming events completed. To work them out you scan forward through the network adding the previous events' earliest time and the activity length together. If there are multiple activities coming into an event you must select the largest one – this is simply because you cannot get to the event until ALL activities are complete, and you know all activities are complete when the one with the longest duration is complete.

While the above isn't too complicated, we'll work through the example graph to see how it all works. You're going to use a simple table to accumulate all the results:

EVENTS 0 1 2 3 4 5 6 7 8
Ei                  

Starting at event 0: there are no incoming activities, and as it's the start you know the earliest time it can be reached is 0 (days).

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0                

Moving to event 1 now, this only relies on activity G being completed, which has a duration of 14 days. Therefore the earliest time that you can get to Event 1 is 14 days.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14              

Event 2 only has activity A to depend on; therefore the earliest arrival time will be 14 days

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14            

Event 3 only depends on activity I being complete; earliest time is therefore 14 days

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14          

Event 4 only depends on activity J, so the earliest time of arrival is 9.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9        

Event 5; has 3 incoming activities; the 3 possible earliest times are:

(2)->(5) = 14 + 10 = 24
(3)->(5) = 14 + 9 = 23

(4)->(5) = 9 + 5 = 14

You must choose the largest value (see the rules at the top), so the earliest time you can get to event 5 is 24 days

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24      

Event 6 only depends on activity E, so the earliest time of arrival is the earliest time of arrival at event 5 plus the duration of activity E, or 24 + 31 = 55.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55    

Event 7 only depends on event 6 and activity F, so the earliest time is 55 + 7 = 62.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62  

Finally, Event 8. Event 8 depends on two activities:

(1)->(8) = 14 + 21 = 35

(7)->(8) = 62 + 21 = 83

You must choose the largest value, which in this case is 83.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83

Hardly a complex task, but if you have a complicated network it can get a little tedious after a while! From the data that you've just calculated you can tell that the earliest time the whole project can be completed is 83 days. If nothing goes wrong then this is how long it will take.

You aren't finished yet though; you need to calculate another set of numbers (and then some more). The next set of numbers is the latest time – the latest time that you can arrive at the event and still complete the project on time. You'll see why this is important later on in the process.

To calculate the latest time of arrival you use a very similar method to the earliest time method. The only main difference is that you start from the end and go backwards, and in the case of multiple choices you choose the lowest value (instead of the largest value). Here goes then:

Event 8, as with the start node. The latest you can get here and still complete the project on time is the total project length – 83 days.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li                 83

Event 7 only has 1 activity coming out of it – K, so you take K away from 83 and you'll have the latest time of arrival: 83 – 21 = 62.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li               62 83

Event 6 only has activity F coming out of it, so the latest time of arrival is (7) – F(7) = 62 – 7 = 55.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li             55 62 83

If you're starting to notice a pattern here you're on the right track – I'll explain this pattern later.

Event 5 only has E(31) coming out of it, so the latest time of arrival is (6) – E(31) = 55 – 31 = 24.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li           24 55 62 83

Now event 4, which only has activity C(5) coming out of it. The latest time of arrival is therefore (5) – C(5) = 24 – 5 = 19.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li         19 24 55 62 83

The pattern seems to have stopped – you may be thinking. But you don't know what the pattern means yet…

Event 3 only has B(5) coming out of it, the latest time of arrival is (5) – B(5) = 24 – 5 = 19.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li       19 19 24 55 62 83

Event 2 only has activity D(10) coming out of it, so the latest time of arrival is (5) – D(10) = 24 – 10 = 14.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li     14 19 19 24 55 62 83

Event 1 only has activity H(21) coming out of it, so the latest time of arrival is (8) – H(21) = 83 – 21 = 62.

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li   62 14 19 19 24 55 62 83

Finally, Event 0 has 4 activities coming out of it:

(0)->(1) via G(14) = (1) – G(14) = 62 – 14 = 48

(0)->(2) via A(14) = (2) – A(14) = 14 – 14 = 0

(0)->(3) via I(14) = (3) – I(14) = 19 – 14 = 5

(0)->(4) via J(9) = (4) – J(9) = 19 – 9 = 10

You have to pick the smallest value, which in this case is 0. So your final table looks like:

EVENTS 0 1 2 3 4 5 6 7 8
Ei 0 14 14 14 9 24 55 62 83
Li 0 62 14 19 19 24 55 62 83




Step 6


Contents
  Steps 1 & 2
  Steps 3 & 4
  Step 5
  Step 6
  Step 7

  Printable version
  Discuss this article