6B Critica! porh analysis 5 The servicing of a vacuum cleaner consists of the following activities: Activity Duration (min) Predecessors ‘A. disconnect power 1 - B check electrical connections 5 A C empty bag 5 - D remove cover 2 A E clean brushes 10 AandC F replace drive band 6 D G oil motor 3 D H_replace cover and test machine 5 all ee Make a table of immediate predecessors and construct an activity network for this project. Assuming that several people are available to help (with each activity only done by one person) show that the vacuum cleaner can be serviced in 20 minutes, [A] 3.3 Critical paths You have now constructed some activity networks and used common-sense to calculate the minimum time needed to complete a project. However, more complicated projects will need a more systematic approach. In this section we shall introduce an algorithm for calculating the possible timings of each event (i.e. of reaching each vertex) which will then enable us to see the minimum time required for the project and which activities are critical. Then in the next section we shall be able to look at the timings of each individual activity. Given the activity network of a project we shall now associate two times with each vertex: carly event time the earliest time by Which all incoming activities can be finished late event time the latest time by which all incoming activities must be, finished ‘= the latest time at which the outgoing activities can start (ke. for at least one of them, any later start would delay the completion of the project)So the early event time is the earliest time at which the = vertex can be reached with all the incoming activities having been completed. The late event time is the latest time at which all incoming activities must be finished because at least one of the outgoing activities must start by then. ‘The time between the two is the maximum possible period of inaction during whieh all the incoming activities can be completed and none of the outgoing activities have started. All this will become clearer after a worked example and so we return to our ‘garage construction project’ Worked example 2 Find all the early and late event times for the activity network of the garage construction project from Worked example 1 Solution ° Here is the earlier activity network with spaces left at each vertex for its early and late event times, and we call the start time 0: longest path from _. longest path to start to here has here has length length 7 T+10=17 We've put two early event times into their places, the 7 and 17. You can reach the event marked 7 in two ways, one will take 7 days and the other will take only 2. Since both A and B have to. completed to reach the event, the earliest time we can get there is 7 days after the start: hence its early event time is 7, as shown. Actually 7 is simply the length of the longest path from the start to that event. Similarly, the length of the longest path from the start to the next event is 7 + 10 = 17, giving 17 as its early event time. It is then straightforward to continue this forward pass to work out all the other early event times: essentially we are70 critica! pote anaiysis finding the length of the longest path from the start to each vertex. In this way we obtain the following results: finish, So the earliest time that we can reach the finish is after 30 days (as we guessed earlier). Therefore it is now our aim to definitely complete the work in that minimum completion time of 30 days. Hence our late event time at the final vertex is also 30, and that accounts for the right-hand number there. We can now carry out a backward pass to work out the late event times. must allow 2 days xe x toreach the finish / must allow 3 days mustallow3+2=5 toreach the finish days from here etc from here Consider, for example, the late event times of 27 and 25 which we have entered. Going back through the network from the finishing point along L it takes 3 days to reach the next event. So the latest time to leave that event is 3 days before the end; i.e. after 30 — 3 = 27 days. Similarly the next event, reached going back along J, has late event time 27 ~ 2 = 25. But what about the event marked *? for event * there are two paths to the finish, one taking 6 days and the other taking 7. Therefore we must allow 7 days to get from there to the finish and hence its late event time is 30 — 7 = 23: essentially it is the length of the longest path from there to the finish deducted from 30. But there is a quicker way of seeing it than that, Since there are two ways of proceeding from * its late event time can be calculated quickly as the smaller of 28-4 (the route back along I) and 23-0 (the route back along the dummy) which gives 23. Similarly the late event time of ** is then the smaller of 23-6 (back along F) and 23-4 (back along G) which is 17, etc. Completing the backward pass in this case gives the following final result:Early and late event times at a vertex You may have spotted that there is a natural symmetry between the forward and backward passes and you will soon be able to execute them easily. Do not forget what the event times mean in practice: for example, for the event with times 17 and 17 above, the longest path to it from the start is of length 17, and the longest path from it to the finish is 13 giving 30 ~ 13 = 17. Similarly, for the event with times 6 and 14, the longest path to it from the start has length 6 and the longest path from it to the finish has length 16, giving 30 — 16 = 14, longest path leading from the start to that vertex. And if the minimum completion time for the whole project is 7, then the late event time at a vertex is T ~ the length of the longest path from that vertex to the finish. > In general the early event time at a vertex is the length of the Critical events and activities Events whose early and late times are the same are called critical events. At a critical event with early and late times f, its incoming activities finish by time f (with at least one of them not being able to finish any sooner) and immediately at least one of its outgoing activities must start. Now let us use the critical events above to interpret our results. We shall start by looking at some activities which go from one critical event to another. For example activity F is as shown. The early time of 17 at the left- hand event means that F cannot start until after at least 17 days, and the late time of 23 at the right-hand event means that F must be completed by 23 days. Therefore as 23 — 17 = 6, which is the time which F takes, it follows that F must start precisely after 17 days and finish after 23. We also illustrate activity G: it must also occur during the period 17 to 23 days. But because 23 — 17 = 6 whereas G only takes 4 days, G can start at any time during the 2-day period from the beginning of the 17th day to the beginning of the 19th day. In the next section we shall look more closely at the activities like G which have a little leeway (or float) but for the moment we are interested only in those activities, like F which must start and finish punctually. 6 & 4 eh) eb)T2 crivca! path anavysis | In general if activity X takes x days and lies between two CP) x (s) critical events whose times differ by x then the activity 3 © X must start punctually: X is called a critical activity. critical activity In the completed network for our ‘garage construction project’ y D above the critical activities are A, E, E, H, J and L (and the 3 dummy) and these together form the critical path from start to Z| finish, as shown: Gp) > D not critical All the activities along that path must be started and finished , punctually in order for the project to be completed in the minimum of 30 days. The remaining activities (B, C, D, G, !and K) have a little leeway in their starting times, and we shall investigate that shortly. EXERCISE 3B 1 Find the carly and late event times, the critical path and the minimum completion times for each of the activity networks shown below. (Note that in one of them the critical activities | form more than 1 critical path.) | (a) start finish (b) start(©) start finish 2. Anextension is to be built to a sports hall. Details of the activities are given below, together with their immediate predecessors. Construct an activity network for this project. Find the early and late event times and the critical path and confirm that the minimum completion time for the project is 30 days. [A] ‘Activity Time (days) Immediate predecessors A lay foundations and build drains 7 - B build walls, 10 A Clay floor 15 A D install fittings 8 Es E make and fit door frames 2 B F erect roof 5 B G plaster ceiling 2 F H__ fitand paint doors and windows 8 Band F 1 paint outside 3 F J fit gutters and drain-pipes 2 1 3 Aschool decides to put on a musical. These are the many jobs to be done by the organising committee, and the times they take. A B c D E F G H 1 J K L M N ° P Q R make the costumes rehearsals get posters and tickets printed get programmes printed organise and make scenery and props get rights to perform musical choose cast arrange hire of hall arrange people to do the refreshments decide which show to do organise lighting dress rehearsals choose programme sellers decide performance dates decide on seating arrangements display posters sell tickets actual performance 6 weeks 12. weeks 3 weeks 3 weeks T weeks 2weeks 1 week 1 week 1 week 1 week 1 week 2 days 1 day 1 day 1 day 4 weeks 3 weeks 1 week Critical path analysis 73TA. creat path onaiysis (a) Although there is no absolute answer (because you probably need to know in more detail what the activities involve), decide on a fairly sensible arrangement of which jobs should precede which and draw up a table of immediate predecessors. (b) Construct an activity network. (c) Find the minimum completion time and identify the critical path. Try to analyse a similar major school project with which you are familiar. 3.4 Float times Given a multi-activity project you should now be able to construct an activity network for it and to identify the critical path, This shows you which activities must be completed without any delay. Before proceeding to the problem of arranging the timing of all the other activities we shall combine and * consolidate what we have learned with another example. Worked exam question | A last-minute article needs to be prepared for a newspaper. The activities required are shown in the table. ‘Activity ‘Time (min) Immediate predecessors ‘A. Tead archive material 14 = B__ telephone photograph library B - C prepare charts and graphs 18 - D__ receive fax of required picture 3 B E write the words 16 AandB F _ prepare all the illustrations 10 CandD (a) Construct an activity network for this project, (b) Carry out forward and backward passes to find all the early and late event times and the minimum completion time for the project. (c) Identify the critical path. Solution (a) . The precedence conditions give the following requirements for the activity network. (Examiner's tip: check first for where dummy arcs will be needed.)Leica parm anaysis + 4 the arcs for A, B and C commence at the start a 7 ¢ E SO E follows A and B but D follows B alone, so a dummy arc is needed as shown = BD c F F follows C and D ‘s nish E and F lead to the finish. dl Putting these together leads to the activity network shown. finish (b) The early event times are easy to calculate: for example the longest path to the event marked * is 18 and the longest path to the finish is AE of length 30, giving a minimum completion time of 30 minutes and completed early times as shown: Then you have to find the longest paths back from the finish to cach vertex. For example the longest path back from the finish to the event marked ** is of length 16 (along76 cocico! pooh analyse E and the dummy) giving that event a late time of 30 ~ 16 = 14. In this way we get completed times as. follows (ec) Only activities A and E are critical, and the critical path is highlighted, Establishing total float In that example recall the meanings of the event times. For example, at the event with times 18 and 20 all incoming. activities can be completed by 18 at the earliest and by 20 at the latest. This is because some outgoing activity must start by 20 at the latest. The period 18 to 20 is the maximum possible period of inaction at that vertex. Now it is clear that the newspaper article can be ready in 30 minutes, with critical activities A and E. Suppose that the article is needed by 4.30. Our analysis so far shows that activity A must be started at 4 o'clock and immediately followed by E at 4.14, But what about the other activities? A little common-sense applied to the network shows, for example, that C must be completed by 4.20 and therefore it can start at any time between 4 and 4.02: we say that it has a float (or total float) of 2 minutes: it is the difference between the activity’s earliest and latest possible start times, Similarly, the earliest time that activity F can start is 4.18 and the latest is 4.20 so it too has a float of 2 minutes. And clearly the critical activities A and E have float equal to 0. But how could the range of starting times be worked out for less obvious activities like D? In fact its possible starting times and float can easily be worked out from the events at its ends: D cannot start until all incoming activities are ‘completed. The earliest this can happen is 13, The latest time that all incoming activities here can finish is 20, $0 D must finish by 20 at the latest.<. D's earliest start time D’s latest finish time = 20 D's latest start time = 20 — 3 = 17 D’s float = latest start — earliest start = 17-13 =4 3 Tn general the float (sometimes called the total float) of Di an activity is calculated as follows: for activity X of duration x | D-O X’s earliest start time X’s latest finish time = 4 X’s latest start time = X's float = latest start ~ earliest start ox d-x-a Applying these calculations to all the activities in the newspaper article project above gives the following results: Activity Earliest start Latest start Float (total)'~ A 0 14-14=0 oO 0 14-131 1 0 20-18 =2 2 B 20-3=17 4 30-16 = 14 o 18 30~10=20 2 mm oom You will notice that the activities of zero float (*) are precisely the critical activity. Independent float Now, assuming that the project started at 4 o'clock, here are the possible starting times of the activities: Activity Possible starting times A 4.00 4.00-4.01 4.00-4.02 413-417 414 4,18-4.20 amoaw For example C could start at 4.02 (but then the start of F would have to be delayed until 4.20). So the choices of starting times for the activities are not independent. But now let us look in detail at the possible starting times of activity D:78 Critical path analysis Starting time for D _ Effect on other activities 43414 B must be finished in time for D to start, so in this case B's choice of starting time is more restricted than in the previous table. 414415 None of the other activities is affected: their choices of starting times are still the same as in the previous table. 415-417 F must not start until D has finished, so in this case F's choice of starting time is more restricted than before. Therefore for a 1-minute period (4.14-4.15) D can start without further restricting the start times of any of the other activities: D is said to have an independent float of 1 minute and independent starting times between 4.14 and 4.15. The independent float can be calculated from the network as follows for activity D D if D Hnishes by 18 the maximum period of inaction here (18 to 20) ‘will remain untouched: for this to happen D must start by 18-3 = 15, ACD starts after 14 or more minutes the maximum period of inaction here (03 to 14) will remain untouched, i.e. for independence D must occur entirely in the period 14 to 18 <.D’s independent starting times are between 14 and 15, and D’s independent float = difference of the late and early starts =15-14=1 In some cases an activity has no independent starting times, in which case the activity does not have an independent float. Tn general, to calculate an activity’s independent float: for activity X of duration x P- for independence X must occur entirely within the period btoe X's independent starting times are between b and ¢ — x, and X’s independent float = difference of those late and early starts = ¢ — x ~ b (provided that is 0 or more). If ¢ — xis less than b then the activity X has no independent starting times, the calculation of its independent float leads to a negative number, and X is said to have no independent float. | | i |It is because there are two concepts of float that the earlier concept is sometimes referred to as the total float. We shall see the significance of the floats in the next section when we try to schedule all the activities. Worked example 3 For the ‘garage construction project’, of the previous two worked examples, work out the total float, independent float and possible starting times of each activity, Solution Let us refer back to the activity network from our solution of Worked example 2. For example activity G is as shown and hence it has both total and independent float equal to 23 ~ 4 — 17: its earliest starting time is 17 and its latest starting time is 19 and all the starting times 17-19 are independent. On the other hand, looking at activity D shows that it has total float 25 — 11-6 = 8 and independent float 25 ~ 11 ~ 14 = 0. Its earliest starting time is 6 and its latest is 14, and its only independent starting time is 14, Carrying on in this way we get the following results: °* ‘Activity Earliest Latest Total Independent Independent start start float float start times A o ° 0 0 0 B ° 5 5 5 os. c ° 8 8 ° 0 D 6 4 8 ° 4 E 7 7 0 ° 7 F v7 7 0 ° 7 G 7 19 2 2 119 H 2B 2B o ° 23 1 B 24 1 ° 23 J 25 23 0 ° 25 K 27 28 1 ° 28 L 27 27 0 0 27 EXERCISE 3C 1 The completion of a project requires four activities to be done. Their durations (in hours) and the order in which they must be done are given in the table. Activity Duration Predecessors 3 = 6 - 9 A 7 Aand B vow