7.05a Critical path analysis: activity on arc networks

1 Table 1 shows a precedence table for a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and late event time for each vertex of your network, and list the critical activities.
3. Extra resources become available which enable the durations of three activities to be reduced, each by up to two days. Which three activities should have their durations reduced so as to minimise the completion time of the project? What will be the new minimum project completion time?

5 The table shows some of the activities involved in building a block of flats. The table gives their durations and their immediate predecessors.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early and late times for each event. Give the minimum completion time and the critical activities. Each of the tasks E, F, H and J can be speeded up at extra cost. The maximum number of weeks by which each task can be shortened, and the extra cost for each week that is saved, are shown in the table below.

   Task	E	F	H	J
   Maximum number of weeks by which task may be shortened	3	3	1	3
   Cost per week of shortening task (in thousands of pounds)	30	15	6	20

3. Find the new shortest time for the flats to be completed.
4. List the activities which will need to be speeded up to achieve the shortest time found in part (iii), and the times by which each must be shortened.
5. Find the total extra cost needed to achieve the new shortest time.

5 The tasks involved in turning around an "AirGB" aircraft for its return flight are listed in the table. The table gives the durations of the tasks and their immediate predecessors.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Because of delays on the outbound flight the aircraft has to be turned around within 50 minutes, so as not to lose its air traffic slot for the return journey. There are four tasks on which time can be saved. These, together with associated costs, are listed below.

   Task	A	B	D	E
   New time (mins)	20	20	15	15
   Extra cost	250	50	50	100

3. List the activities which need to be speeded up in order to turn the aircraft around within 50 minutes at minimum extra cost. Give the extra cost and the new set of critical activities.

1 The table shows the activities involved in a project, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the critical activities.

4 The table shows the tasks involved in preparing breakfast, and their durations.

1. Show the immediate predecessors for each of these tasks.
2. Draw an activity on arc network modelling your precedences.
3. Perform a forward pass and a backward pass to find the early time and the late time for each event.
4. Give the critical activities, the project duration, and the total float for each activity.
5. Given that only one person is available to do these tasks, and noting that tasks B, D and F do not require that person's attention, produce a cascade chart showing how breakfast can be prepared in the least possible time.

6 The table shows the tasks involved in making a salad, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early and late times for each event. Give the minimum completion time and the critical activities.
3. Given that each task can only be done by one person, how many people are needed to prepare the salad in the minimum time? What is the minimum time required to prepare the salad if only one person is available?
4. Show how two people can prepare the salad as quickly as possible.

4 A room has two windows which have the same height but different widths. Each window is to have one curtain. The table lists the tasks involved in making the two curtains, their durations, and their immediate predecessors. The durations assume that only one person is working on the activity.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Kate and Pete have two rooms to curtain, each identical to that above. Tasks A, B, C and D only need to be completed once each. All other tasks will have two versions, one for room 1 and one for room 2, eg E1 and E2. Kate and Pete share the tasks between them so that each task is completed by only one person.
3. Complete the diagram to show how the tasks can be shared between them, and scheduled, so that the project can be completed in the least possible time. Give that least possible time.
4. How much extra help would be needed to curtain both rooms in the minimum completion time from part (ii)? Explain your answer.

3 Table 3 gives the durations and immediate predecessors for the five activities of a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early and late event times for the vertices of your network, and list the critical activities.
3. Give the total and independent float for each activity which is not critical.

4 Table 4.1 shows some of the activities involved in preparing for a meeting. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and the late event time for each vertex of your network, and list the critical activities.
3. Assuming that each activity requires one person and that each activity starts at its earliest start time, draw a resource histogram.
4. In fact although activity A has duration 1 hour, it actually involves only 0.5 hours work, since 0.5 hours involves waiting for replies. Given this information, and the fact that there is only one person available to do the work, what is the shortest time needed to prepare for the meeting? Fig. 4.2 shows an activity network for the tasks which have to be completed after the meeting. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-5_533_844_1688_294} \captionsetup{labelformat=empty} \caption{Fig. 4.2}
   \end{figure} P: Clean room
   Q: Prepare draft minutes
   R: Allocate action tasks
   S: Circulate draft minutes
   T: Approve task allocations
   U: Obtain budgets for tasks
   V: Post minutes
   W: Pay refreshments bill
5. Draw a precedence table for these activities.

4 Colin is setting off for a day's sailing. The table and the activity network show the major activities that are involved, their durations and their precedences. \includegraphics[max width=\textwidth, alt={}, center]{21ab732d-435e-4f0b-bc88-21ddc2a398c9-3_480_912_555_925}

1. Complete the table in your answer book showing the immediate predecessors for each activity.
2. Find the early time and the late time for each event. Give the project duration and list the critical activities. When he sails on his own Colin can only do one thing at a time with the exception of activity G, motoring out of the harbour.
3. Use the activity network to determine which activities Colin can perform whilst motoring out of the harbour.
4. Find the minimum time to complete the activities when Colin sails on his own, and give a schedule for him to achieve this.
5. Find the minimum time to complete the activities when Colin sails with one other crew member, and give a schedule for them to achieve this.

5

1. The graphs below illustrate the precedences involved in running two projects, each consisting of the same activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Project 1} \includegraphics[alt={},max width=\textwidth]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-6_280_385_429_495}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Project 2} \includegraphics[alt={},max width=\textwidth]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-6_255_392_429_1187}
   \end{figure}
   1. For one activity the precedences in the two projects are different. State which activity and describe the difference.
   2. The table below shows the durations of the five activities.

      Activity	A	B	C	D	E
      Duration	2	1	\(x\)	3	2

      Give the total time for project 1 for all possible values of \(x\).
      Give the total time for project 2 for all possible values of \(x\).
2. The durations and precedences for the activities in a project are shown in the table.

   Activity	Duration	Immediate predecessors
   R	2	-
   S	1	-
   T	5	-
   w	3	R, S
   X	2	R, S, T
   Y	3	R
   Z	1	W, Y

   1. Draw an activity on arc network to represent this information.
   2. Find the early time and the late time for each event. Give the project duration and list the critical activities.

6 Joan and Keith have to clear and tidy their garden. The table shows the jobs that have to be completed, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities.
3. Each job is to be done by one person only. Joan and Keith are equally able to do all jobs. Draw a cascade chart indicating how to organise the jobs so that Joan and Keith can complete the project in the least time. Give that least time and explain why the minimum project completion time is shorter.

6 The table shows the tasks that have to be completed in building a stadium for a sporting event, their durations and their precedences. The stadium has to be ready within two years.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the project duration and the critical activities. In the later stages of planning the project it is discovered that task J will actually take 9 months to complete. However, other tasks can have their durations shortened by employing extra resources. The costs of "crashing" tasks (i.e. the costs of employing extra resources to complete them more quickly) are given in the table.

   Tasks which can be completed more quickly by employing extra resources	Number of months which can be saved	Cost per month of employing extra resources (£m)
   A	2	3
   D	1	1
   C	3	3
   F	2	2
   G	2	4

3. Find the cheapest way of completing the project within two years.
4. If the delay in completing task J is not discovered until it is started, how can the project be completed in time, and how much extra will it cost?

5 The activity network and table together show the tasks involved in constructing a house extension, their durations and precedences. \includegraphics[max width=\textwidth, alt={}, center]{2e03f6fb-69db-438a-a79e-3e04fab0d08a-5_231_985_338_539}

1. Show the immediate predecessors for each activity.
2. Perform a forward pass and a backward pass to find the early time and the late time for each event.
3. Give the critical activities, the project duration, and the total float for each activity.
4. The activity network includes one dummy activity. Explain why this dummy activity is needed. Whilst the foundations are being dug the customer negotiates the installation of a decorative corbel. This will take one day. It must be done after the walls have been built, and before the roof is constructed. The windows and doors cannot be installed until it is completed. It will not have any effect on the construction of the floor.
5. Redraw the activity network incorporating this extra activity.
6. Find the revised critical activities and the revised project duration.

6 The table shows the tasks involved in making a batch of buns, the time in minutes required for each task, and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Preparing the batch for baking consists of tasks A to G ; each of these tasks can only be done by one person. Baking, task H, requires no people.
3. How many people are required to prepare the batch for baking in the minimum time?
4. What is the minimum time required to prepare the batch for baking if only one person is available? Jim is preparing and baking three batches of buns. He has one oven available for baking. For the rest of the question you should consider 'preparing the batch for baking' as one activity.
5. Assuming that the oven can bake only one batch at a time, draw an activity on arc diagram for this situation and give the minimum time in which the three batches of buns can be prepared and baked.
6. Assuming that the oven is big enough to bake all three batches of buns at the same time, give the minimum time in which the three batches of buns can be prepared and baked.

4 The table lists tasks which are involved in adding a back door to a garage. The table also lists the duration and immediate predecessor(s) for each task. Each task is undertaken by one person.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities.
3. Produce a schedule to show how two people can complete the project in the minimum time. Soon after starting activity D , the marble step breaks. Getting a replacement step adds 4 hours to the duration of activity D.
4. How does this delay affect the minimum completion time, the critical activities and the minimum time needed for two people to complete the project? \section*{Question 5 begins on page 6}

5 The table lists activities which are involved in framing a picture. The table also lists their durations and their immediate predecessors. Except for activities C and H, each activity is undertaken by one person. Activities C and H require no people.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. A picture is to be framed as quickly as possible. Two people are available to do the job.
3. Produce a schedule to show how two people can complete the picture framing in the minimum time. To reduce the completion time an instant glue is to be used. This will reduce the time for activities C and H to 0 minutes.
4. Produce a schedule for two people to complete the framing in the new minimum completion time, and give that time.

5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown. Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.

1. Complete the table in your answer book by showing the immediate predecessors for each activity.
2. Draw an activity on arc network for these activities.
3. Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
4. Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.

3. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows an activity network. The nodes represent events and the arcs represent the activities. The number in each bracket gives the time, in days, needed to complete the activity.

1. Calculate the early and late times for each event using appropriate forward and backward scanning.
   (5 marks)
2. Hence, determine the activities which lie on the critical path.
3. State the minimum number of days needed to complete the entire project.

7. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The activity network in Figure 5 models the work involved in laying the foundations and putting in services for an industrial complex. The activities are represented by the arcs and the numbers in brackets give the time, in days, to complete each activity. Activity \(C\) is a dummy.

1. Execute a forward scan to calculate the early times and a backward scan to calculate the late times, for each event.
2. Determine which activities lie on the critical path and list them in order.
3. State the minimum length of time needed to complete the project. The contractor is committed to completing the project in this minimum time and faces a penalty of \(\pounds 50000\) for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity \(F\) will take 3 days longer than the 7 days allocated.
4. Activity \(N\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
   (3 marks)
5. If the time taken to complete any one activity, other than \(F\), could be reduced by 2 days at an extra cost of \(\pounds 80000\), for which activities on their own would this be profitable. Explain your reasoning.
   (3 marks) END \section*{Please hand this sheet in for marking}

   	A	B	C	D	E	\(F\)
   A	-	130	190	155	140	125
   B	130	-	215	200	190	170
   C	190	215	-	110	180	100
   D	155	200	110	-	70	45
   E	140	190	180	70	-	75
   \(F\)	125	170	100	45	75	-

   \section*{Please hand this sheet in for marking}

   1. \(n\)	\(x _ { n }\)	\(a\)	Any more data?	\(x _ { n + 1 }\)	\(b\)	\(( b - a ) > 0\) ?	\(a\)
      1	8	8	Yes	2	2	No	2
      2	-	-

      Final output
   2. \(\_\_\_\_\) Sheet for answering question 3
      NAME \section*{Please hand this sheet in for marking}
   4. 1. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_716_1218_502_331}
      2. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_709_1214_1498_333} Maximum flow =
   5. 1. \(\_\_\_\_\)
      2. \(\_\_\_\_\) \section*{Please hand this sheet in for marking}
   6. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
   7. \(\_\_\_\_\)
   8. \(\_\_\_\_\)
   9. \(\_\_\_\_\)
   10. \(\_\_\_\_\)

7. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-09_2036_1555_349_248}

1. \(\_\_\_\_\)
2. \(\_\_\_\_\) \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking} Sheet for answering question 6
   NAME \section*{Please hand this sheet in for marking}
   2. 1. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_666_1280_461_374}
      2. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_657_1276_1356_376} Maximum Flow = \(\_\_\_\_\)
   3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   4. \(\_\_\_\_\)
   5. \(\_\_\_\_\)

7. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows an activity network modelling the tasks involved in widening a bridge over the B451. The arcs represent the tasks and the numbers in brackets gives the time, in days, to complete each task.

1. Find the early and late times for each event.
2. Determine those activities which lie on the critical path and list them in order.
3. State the minimum length of time needed to widen the bridge. Each task needs a single worker.
4. Show that two men would not be sufficient to widen the bridge in the shortest time.
   (2 marks)
5. Draw up a schedule showing how 3 men could complete the project in the shortest time. \section*{Please hand this sheet in for marking}
   1. Complete matching:

      \(P\)	\(\bullet\)	\(\bullet\)	\(D\)
      \(Q\)	\(\bullet\)	\(\bullet\)	\(G\)
      \(R\)	\(\bullet\)	\(\bullet\)	\(E\)
      \(S\)	\(\bullet\)	\(\bullet\)	\(L ( H )\)
      \(T\)	\(\bullet\)	\(\bullet\)	\(L\)

      \section*{Please hand this sheet in for marking}

   2. \(x\)	\(a\)	\(b\)	\(( a - b ) < 0.01\) ?
      100	50	26	No
      -	26	14.923	No

      Final output
   3. \(\_\_\_\_\)

   4. \(x\)	\(a\)	\(b\)	\(( a - b ) < 0.01 ?\)
      100

   5. \(\_\_\_\_\) \section*{Please hand this sheet in for marking}
   6. \includegraphics[max width=\textwidth, alt={}, center]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-11_768_1689_427_221}
   7. \(\_\_\_\_\)
   8. \(\_\_\_\_\)

   9. 0	5	10	15	20	25	30	35	40	45	50	55	60
      Worker 1
      Worker 2

   10. 0	5	10	15	20	25	30	35	40	45	50	55	60
       Worker 1
       Worker 2
       Worker 3

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
Figure 1 shows the activity network and the duration, in days, of each activity for a particular project.

1. On Figure 1:
   1. find the earliest start time for each activity;
   2. find the latest finish time for each activity.
2. Find the float for activity \(G\).
3. Find the critical paths and state the minimum time for completion.
4. The number of workers required for each activity is shown in the table.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers required	2	2	3	2	3	2	1	3	5	2

   Given that each activity starts as late as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.

1
A group of workers is involved in a decorating project. The table shows the activities involved. Each worker can perform any of the given activities. The activity network for the project is given in Figure 1 below.

1. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
2. Hence find:
   1. the critical path;
   2. the float time for activity \(D\).
      1. \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-02_647_1657_1640_180}
         \end{figure}
      2. 1. The critical path is \(\_\_\_\_\)
         2. The float time for activity \(D\) is \(\_\_\_\_\)
   3. Given that each activity starts as early as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2 below, indicating clearly which activities are taking place at any given time.
   4. It is later discovered that there are only 8 workers available at any time. Use resource levelling to construct a new resource histogram on Figure 3 below, showing how the project can be completed with the minimum extra time. State the minimum extra time required.
   5. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_586_1708_922_150}
      \end{figure}
   6. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_496_1705_1672_153}
      \end{figure} The minimum extra time required is \(\_\_\_\_\)

1 The diagram shows the activity network and the duration, in days, of each activity for a particular project. Some of the earliest start times and latest finish times are shown on the diagram. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-02_830_1447_678_301}

1. Find the values of the constants \(x , y\) and \(z\).
2. Find the critical paths.
3. Find the activity with the largest float and state the value of this float.
4. The number of workers required for each activity is shown in the table.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers required	4	2	3	4	2	4	3	3	5	6

   Given that each activity starts as early as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 1 below, indicating clearly which activities are taking place at any given time.
5. It is later discovered that there are only 9 workers available at any time. Use resource levelling to find the new earliest start time for activity \(J\) so that the project can be completed with the minimum extra time. State the minimum extra time required. (d) Number of workers \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-03_803_1330_1224_468}
   \end{figure}