Chapter 12 Critical Path Analysis 12 CRITICAL PATH …

1 189 Chapter 12 CRITICAL path Analysis12 CRITICALPATHANALYSISO bjectivesAfter studying this Chapter you should be able to construct activity networks; be able to find earliest and latest starting times; be able to identify the CRITICAL path ; be able to translate appropriate real problems into a suitableform for the use of CRITICAL path IntroductionA complex project must be well planned, especially if a numberof people are involved. It is the task of management toundertake the planning and to ensure that the various tasksrequired in the project are completed in researchers developed a method of schedulingcomplex projects shortly after the Second World War. It issometimes called network Analysis , but is more usually knownas CRITICAL path Analysis (CPA). Its virtue is that it can beused in a wide variety of projects, and was, for example,employed in such diverse projects as the Apollo moonshot, thedevelopment of Concorde, the Polaris missile project and theprivatisation of the electricity and water boards.

2 Essentially,CPA can be used for any multi-task complex project to ensurethat the complete scheme is completed in the minimum its real potential is for helping to schedule complexprojects, we will illustrate the use of CPA by applying it torather simpler problems. You will often be able to solve theseproblems without using CPA, but it is an understanding of theconcepts involved in CPA which is being developed 12 CRITICAL path Activity networksIn order to be able to use CPA, you first need to be able to formwhat is called an activity network. This is essentially a way ofillustrating the given project data concerning the tasks to becompleted, how long each task takes and the constraints on theorder in which the tasks are to be completed. As an example,consider the activities shown below for the construction of (in days)Aprepare foundations7 Bmake and position door frame2 Clay drains, floor base and screed15 Dinstall services and fittings8 Eerect walls10 Fplaster ceiling2 Gerect roof5 Hinstall door and windows8 Ifit gutters and pipes2 Jpaint outside3 Clearly, some of these activities cannot be started until otheractivities have been completed.

3 For exampleactivity G - erect roofcannot begin untilactivity E - erect wallshas been completed. The following table shows which activitiesmust precede must follow EE must follow A and BF must follow D and GG must follow EH must follow GImust follow C and FJ must follow call these the precedence relations. 191 Chapter 12 CRITICAL path AnalysisAll this information can be represented by the network this networkeach activity is represented by a vertex;joining vertex X to vertex Y shows thatactivity X must be completed before Y can be started;the number marked on each arc shows the duration of theactivity from which the arc the use of 'arc' here to mean a directed we can easily form the activity network, but notalways, so we need to have a formal method. First try thefollowing 1 Making a setteeA furniture maker is going to produce a new wooden framedsettee with cloth-covered foam cushions.

4 These are the tasksthat have to be done by the furniture maker and his assistantsand the times they will take :activitytime in daysAmake wooden arms and legs3 Bmake wooden back1 Cmake wooden base2 Dcut foam for back and base1 Emake covers3 Ffit covers1 Gput everything together1 Each activity can only be undertaken by one 12 CRITICAL path AnalysisThe following list gives the order in which the jobs must be done:B must be after CA must be after B and CD must be after B and CE must be after DF must be after EG must be after A, B, C, D, E and FConstruct an appropriate activity network to illustrate Algorithm for constructingactivity networksFor simple problems it is often relatively easy to construct activitynetworks but, as the complete project becomes more complex, theneed for a formal method of constructing activity networksincreases.

5 Such an algorithm is summarised simple problems it is often easy to construct activity networks, but as the complete project becomes morecomplex, the need for a formal method of constructing activity networks increases. Such an algorithm issummarised down the original vertices and then a second copyof them alongside, as illustrated on the right. If activityY must follow activity X draw an arc from originalvertex Y to shadow vertex X. (In this way you constructa bipartite graph.)Step 1 Make a list of all the original vertices which have no arcsincident to 2 Delete all the vertices found in Step 1 and theircorresponding shadow vertices and all arcs incident tothese 3 Repeat Steps 1 and 2 until all the vertices have use of this algorithm will be illustrated using the first casestudy, constructing a garage, from Section 193 Chapter 12 CRITICAL path AnalysisThe precedence relations are.

6 D must follow EE must follow A and BF must follow D and GG must follow EH must follow GImust follow C and FJ must follow IThese are illustrated the algorithm until all vertices have been chosen is 1 - original vertices with no arcsStep 2 - delete all arcs incident on A, B, C and redraw asshownStep 3 - repeat iterationStep 1 - original vertices with no arcsStep 2 - delete all arcs incident on E and redraw as shownStep 3 - repeat iterationStep 1 - original vertices with no arcsStep 2 - delete all arcs incident on D, G and redraw as shownStep 3 - repeat iterationStep 1 - original vertices with no arcsStep 2 - delete all arcs incident on F, H and redraw as shownStep 3 - repeat iterationStep 1 - original vertices with no arcsStep 2 - delete all arcs incident on I and redraw as shownACABBCDEFEDFGHIGHIJJA, B, CEFEFGHIGHIJJDDEDFDFGHIGHIJJFHIFHIJJD, GIJIJ F, HJJ I194 Chapter 12 CRITICAL path AnalysisStep 3 - stop as all vertices have been chosenSo the vertices have been chosen in the following order:A D FB E IJ G HCThe activity diagram as shown belowcan now be 1st 2nd 3rdFrom the 'start' vertex, draw arcs to A, B and C, the firstiteration vertices, putting zero on each arc.

7 In the originalbipartite graph the shadow vertex A was joined to the originalvertex E - so join A to E. Similarly join B to E and C to the duration of the activity on any arc coming from thevertex representing the in this way and complete the activity network with a'finish' vertex into which any free vertices lead, again indicatingthe duration of the activity on the that the duration of the activity is shown on every arccoming from the vertex representing the activity. (So, forexample, arc ED and arc EG are both given 10.)G7 Start00A2E10FD2I52J3015105H8 8 BCFinish4th6th5th 195 Chapter 12 CRITICAL path AnalysisExercise 12A1. Use the algorithm to find the activity network forthe problem in Activity Suppose you want to redecorate a room and putin new self-assembly units. These are the jobsthat need to be done, together with the time eachtakes:time activity(in hrs) preceded bypaint woodwork (A)8-assemble units (B)4-fit carpet (C)5hang wallpaperpaint woodworkhang wallpaper (D)12paint woodworkhang curtains (E)2hang wallpaperpaint woodworkComplete an activity network for this The Spodleigh Bicycle Company is getting itsassembly section ready for putting together asmany bicycles as possible for the Christmasmarket.

8 This diagram shows the basiccomponents of a together a bicycle is split up into smalljobs which can be done by different are: time activity (mins)Apreparation of the frame9 Bmounting and aligning the front wheel7 Cmounting and aligning the back wheel7 Dattaching the chain wheel to the crank2 Eattaching the chain wheel and crankto the frame2 Fmounting the right pedal8 Gmounting the left pedal8 Hfinal attachments such as saddle,chain, stickers, etc. 21 The following chart shows the order of doing must be after AC must be after AD must be after AE must be after DF must be after D and EG must be after D and EH must be after A, B, C, D, E, F and GDraw an activity network to show An extension is to be built to a sports of the activities are given below.

9 Timeactivity (in days)Alay foundations7 Bbuild walls 10 Clay drains and floor 15 Dinstall fittings8 Emake and fit door frames2 Ferect roof5 Gplaster ceiling2 Hfit and paint doors and windows8 Ifit gutters and pipes2 Jpaint outside3 Some of these activities cannot be started untilothers have been completed:B must be after CC must be after AD must be after BE must be after CF must be after D and EG must be after FH must be after GI must be after FJ must be after HComplete an activity network for this 12 CRITICAL path CRITICAL pathYou have seen how to construct an activity network. In thissection you will see how this can be used to find the criticalpath. This will first involve finding the earliest possible startfor each activity, by going forwards through the , the latest possible start time for each activity is foundby going backwards through the network.

10 Activities whichhave equal earliest and latest start time are on the CRITICAL technique will be illustrated using the 'garage construction'problem from Sections and activity network for this problem is shown below, wheresufficient space is made at each activity node to insert numbers in the top half of each circle will indicate theearliest possible starting time. So, for activities A, B and C, thenumber zero is forward through the network, the activity E is reachednext. Since both A and B have to be completed before E can bestarted, the earliest start time for E is 7. This is put into the tophalf of the circle at E. The earliest times at D and G are thenboth 17, and for H, 22. Since F cannot be started until both Dand G are completed, its earliest start time is 25, andconsequently, 27 for I.