STRAND: DISCRETE MATHS Unit 2 Critical Path Analysis

1 CMM Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextmepSTRAND: DISCRETE MATHSUnit 2 Critical path Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : Text2 Critical path Activity NetworksIn order to be able to use Critical path Analysis (CPA), you first need to be able to formwhat is called an activity network. This is essentially a way of illustrating the givenproject data concerning the tasks to be completed, how long each task takes and theconstraints on the order in which the tasks are to be completed. As an example, considerthe activities shown below for the construction of a (in days)A prepare foundations7B make and position door frame2C lay drains, floor base and screed15D install services and fittings8E erect walls10F plaster ceiling2G erect roof5H install door and windows8I fit gutters and pipes2J paint outside3 Clearly, some of these activities cannot be started until other activities have beencompleted.

2 For exampleactivity G - erect roofcannot begin untilactivity E - erect wallshas been completed. The following table shows which activities must precede must followEE must followA and BF must followD and GG must followEH must followGI must followC and FJ must followIWe call these the precedence this information can be represented by the following Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextIn this networkeach activity is represented by a vertex;joining vertex X to vertex Y shows that activity X must be completed beforeactivity Y can be started;the number marked on each arc shows the duration of the activity from whichthe arc the use of 'arc' here to mean a directed edge. Sometimes we can easily form theactivity network, but not always, so we need to have a formal method. First try thefollowing Example 1A furniture maker is going to produce a new wooden framed settee with cloth-coveredfoam cushions.

3 These are the tasks that have to be done by the furniture maker and hisassistants and the times they will take:ActivityTime in daysA make wooden arms and legs3B make wooden back1C make wooden base2D cut foam for back and base1E make covers3F fit covers1G put everything together1 Each activity can only be undertaken by one 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 this Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextSolutionExercises1. Suppose you want to redecorate a room and put in new self-assembly units. Theseare the jobs that need to be done, together with the time each takes:TimeActivity(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 its assembly section ready for puttingtogether as many bicycles as possible for the Christmas market.

4 This diagramshows the basic components of a together a bicycle is split up into small jobs which can be done by Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextThe activities are:ActivityTime(mins)A preparation of the frame9 Bmounting and aligning the front wheel7C mounting and aligning the back wheel7D attaching the chain wheel to the crank2E attaching the chain wheel and crankto the frame2F mounting the right pedal8G mounting the left pedal7H final attachments such as saddle,chain, stickers 21 The following chart shows the order of doing the must be afterAC must be afterAD must be afterAE must be afterDF must be afterD and EG must be afterD and EH must be afterA, B, C, D, E, F and GDraw an activity network to show this An extension is to be built to a sports hall. Details of the activities are given Time(mins)Alay foundations7 Bbuild walls10 Clay drains and floor15 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 until others have been Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : following chart shows the order of doing the must be afterCC must be afterAD must be afterBE must be afterCF must be afterD and EG must be afterFH must be afterGI must be afterFJ must be after HDraw an activity network to show this Critical PathYou have seen how to construct an activity network.

5 In this section you will see how thiscan be used to find the Critical path . This will first involve finding the earliest possiblestart for each activity, by going forwards through the network. Secondly, the latestpossible start time for each activity is found by going backwards through the which have equal earliest and latest start time are on the Critical path . Thetechnique will be illustrated using the 'garage construction' problem in Section in daysA prepare foundations7B make and position door frame2C lay drains, floor base and screed15D install services and fittings8E erect walls10F plaster ceiling2G erect roof5H install door and windows8I fit gutters and pipes2J paint outside3 The activity network for this problem is shown below, where sufficient space is made ateach activity node to insert two Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextThe numbers in the top half of each circle will indicate the earliest possible starting , for activities A, B and C, the number zero is forward through the network, the activity E is reached next.

6 Since both A and Bhave to be completed before E can be started, the earliest start time for E is 7. This is putinto the top half of the circle at E. The earliest times at D and G are then both 17, and forH, 22. Since F cannot be started until both D and G are completed, its earliest start timeis 25, and consequently, 27 for I. The earliest start time for J is then 29, which gives anearliest completion time of 32 is the earliest possible completion time, it is also assumed to be the completiontime in order to find the latest possible start times. So 32 is also put in the lower half ofthe 'finish' circle. Now working backwards through the network, the latest start times foreach activity are as follows:J32 3 29 =I29 2 27 =F27 2 25 =H32 8 24 =D25 8 17 =G the minimum of 25 5 20 = and 24 5 19 =E the minimum of 17 10 7 = and 19 10 9 =A770 =B725 =C27 15 12 =70010250151058 8 GHF22201771725 DAE0BC0007 CMM Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : TextThis gives a completed network as shown vertices with equal earliest and latest starting times define the Critical path .

7 This isclearly seen to be A E D F I JAnother way of identifying the Critical path is to define thefloat time = latest start time earliest start timeThe information for the activities can now be summarised in the table below. Start timesActivityEarliestLatestFloatA000 B055C01212E770 D17170 G17192F25250 H22242I27270 J29290 So now you know that if there are enough workers the job can be completed in 32 activities on the Critical path ( those with zero float time) must be startedpunctually; for example, A must start immediately, E after 7 days, F after 25 days, activities with a non-zero float time there is scope for varying their start times; forexample activity G can be started any time after 17, 18 or 19 days' work. Assuming thatall the work is completed on time, you will see that this does indeed give a workingschedule for the construction of the garage in the minimum time of 32 days.

8 However itdoes mean, for example, that on the 18th day activities D and C will definitely be in15700102501058 Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : Textprogress and G may be as well. The solution could well be affected if there was a limit tothe number of workers available, but you will consider that sort of problem in the Example 2 From the activity network for Question 2 in the Exercises in Section , find the criticalpath and the possible start times for all the activities in order to complete the job in theshortest possible is an activity network for the problem:0999277227821 BEACGFDHS tartFinish1390991321099927722782111 BEACGFDH42 StartFinishand with a backwards scan, we obtain:13149001414131321099927722782111 BEACGFDH42 StartFinish214211999 With a forward scan, we Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis .

9 TextHence the Critical path isA D E F Hand the earliest and latest start times in order to finish in the minimum time of 42 minutesare as given in the final Find the Critical paths for each of the activity networks ( * ) shown below .(a)(b)(c)(* Enlarged versions of these networks, for you to work on, are given at the end of this unit .) Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : Text2. Your local school decides to put on a musical. These are the many jobs to be doneby the organising committee, and the times they take:A make the costumes6 weeksB rehearsals 12 weeksC get posters and tickets printed 3 weeksD get programmes printed3 weeksE make scenery and props 7 weeksF get rights to perform the musical 2 weeksG choose cast 1 weekH hire hall 1 weekIarrange refreshments 1 weekJorganise make-up 1 weekK decide on musical 1 weekL organise lighting 1 weekM dress rehearsals 2 daysN invite local radio/press 1 dayP choose stage hands 1 dayQ choose programme sellers 1 dayR choose performance dates 12dayS arrange seating 12dayT sell ticketslast 4 weeksV display posterslast 3 weeks(a) Decide on the precedence relationships.

10 (b) Construct the activity network.(c) Find the Critical path and minimum completion Consider the following activity network, in which the vertices represent activitiesand the numbers next to the arcs represent time in days.(a) Assuming that an unlimited number of workers is available, write down:(i) the minimum completion time of the project;(ii) the corresponding Critical path .(b) Find the float time of activity Subject Support Strand: DISCRETE MATHS unit 2 Critical path Analysis : Text4. A project consists of ten activities, A-J. The duration (in days) of each activity, andthe activities preceding each of them, are as follows:PrecedingActivityDurationactivit iesA10 -B 4 -C 8BD 6CE 8IF 5-G 10A, DH 2GI 4-J10D, E, F(a) construct an activity network for this project;(b) find a Critical path in this activity network;(c) find the latest starting time for each A project consists of eight activities whose durations are as follows:ActivityABC DEFGHD uration443 54165 The precedence relations are as follows:B must follow AD must follow A and CF must follow C and EG must follow C and EH must follow B and D(a) Draw an activity network in which the activities are represented by vertices.