7.05a Critical path analysis: activity on arc networks

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from \(A\) to \(I\). \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-144_867_1644_552_191}

1. Working backwards from \(\boldsymbol { I }\), use dynamic programming to find the maximum number of bags that can be collected when driving from \(A\) to \(I\). You must complete the table opposite as your solution.
2. State the route that the collector should take in order to collect the maximum number of bags.

   1. Stage	State	From	Value
      1	G	I
      	H	I
      2

3 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A building project is to be undertaken. The table shows the activities involved.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. Find the critical path and state the minimum time for completion.
5. State the float time for each non-critical activity.
6. Given that each activity starts as early as possible, draw a resource histogram for the project on Figure 2.
7. There are only 3 workers available at any time. Use resource levelling to explain why the project will overrun and state the minimum extra time required.

1 [Figure 1, printed on the insert, is provided for use in this question.]
A building project is to be undertaken. The table shows the activities involved.

1. Complete an activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. State the minimum completion time for the building project and identify the critical paths.

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
A group of workers is involved in a building project. The table shows the activities involved. Each worker can perform any of the given activities.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
3. Find the critical path and state the minimum time for completion.
4. The number of workers required for each activity is given in the table above. Given that each activity starts as early as possible and assuming 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.
5. It is later discovered that there are only 7 workers available at any time. Use resource levelling to explain why the project will overrun and indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

2 [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 critical paths and state the minimum time for completion.
3. 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	3	3	4	2	3	4	1	2	2	5

   1. 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, indicating clearly which activities take place at any given time.
   2. It is later discovered that there are only 6 workers available at any time. Explain why the project will overrun, and use resource levelling to indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A construction project is to be undertaken. The table shows the activities involved.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. Find the critical path.
5. State the float time for each non-critical activity.
6. On Figure 2, draw a cascade diagram (Gantt chart) for the project, assuming each activity starts as late as possible.

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
The following diagram shows an activity diagram for a building project. The time needed for each activity is given in days. \includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-02_698_1321_767_354}

1. Complete the precedence table for the project on Figure 1.
2. Find the earliest start times and latest finish times for each activity and insert their values on Figure 2.
3. Find the critical path and state the minimum time for completion of the project.
4. Find the activity with the greatest float time and state the value of its float time.

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
The following diagram shows an activity network for a project. The time needed for each activity is given in days. \includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-02_940_1698_721_164}

1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
2. Find the critical paths and state the minimum time for completion.
3. On Figure 2, draw a cascade diagram (Gantt chart) for the project, assuming each activity starts as early as possible.
4. Activity \(C\) takes 5 days longer than first expected. Determine the effect on the earliest start time for other activities and the minimum completion time for the project.
   (2 marks)

1 [Figure 1, printed on the insert, is provided for use in this question.]
A decorating project is to be undertaken. The table shows the activities involved.

1. Complete an activity network for the project on Figure 1.
2. On Figure 1, indicate:
   1. the earliest start time for each activity;
   2. the latest finish time for each activity.
3. State the minimum completion time for the decorating project and identify the critical path.
4. Activity \(F\) takes 4 days longer than first expected.
   1. Determine the new earliest start time for activities \(H\) and \(I\).
   2. State the minimum delay in completing the project.

1
Figure 1 below shows an activity diagram for a construction project. The time needed for each activity is given in days.

1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
2. Find the critical paths and state the minimum time for completion of the project.
3. On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as early as possible.
4. Activity \(J\) takes longer than expected so that its duration is \(x\) days, where \(x \geqslant 3\). Given that the minimum time for completion of the project is unchanged, find a further inequality relating to the maximum value of \(x\).
   1. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{d0902228-7041-4449-9ccb-770352ce6bef-02_910_1355_1414_411}
      \end{figure}
   2. Critical paths are \(\_\_\_\_\) Minimum completion time is \(\_\_\_\_\) days. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{d0902228-7041-4449-9ccb-770352ce6bef-03_940_1160_390_520}
      \end{figure}
   3. \(\_\_\_\_\)

5 Dave plans to renovate three houses, \(A , B\) and \(C\), at the rate of one per year. The order in which they are renovated is a matter of choice, but some costs vary over the three years. The expected costs, in thousands of pounds, are given in the table below. (b) Optimum order \(\_\_\_\_\)

1 A major project has been divided into a number of tasks, as shown in the table. The minimum time required to complete each task is also shown. \section*{Answer space for question 1}

8 An activity diagram for a project is shown below. The duration of each activity is given in weeks. The earliest start time and the latest finish time for each activity are shown on the diagram. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-22_640_1626_475_209}

1. Find the values of \(x , y\) and \(z\).
2. State the critical path.
3. Some of the activities can be speeded up at an additional cost. The following table lists the activities that can be speeded up together with the minimum possible duration of these activities. The table also shows the additional cost of reducing the duration of each of these activities by one week.

1 Figure 2, on the page opposite, shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.

1. On Figure 1 below, complete the precedence table.
2. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 2.
3. List the critical paths.
4. Find the float time of activity \(E\).
5. Using Figure 3 opposite, draw a Gantt diagram to illustrate how the project can be completed in the minimum time, assuming that each activity is to start as early as possible.
6. Given that there is only one worker available for the project, find the minimum completion time for the project.
7. Given that there are two workers available for the project, find the minimum completion time for the project. Show a suitable allocation of tasks to the two workers.
   [0pt] [2 marks] \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1}

   Activity	Immediate predecessor(s)
   A
   B
   C
   D
   E
   \(F\)
   G
   \(H\)
   I
   J

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_1071_1561_376_278}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_801_1301_1644_420}
   \end{figure}

1
Figure 1 below shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.

1. Find the earliest start time and the latest finish time for each activity and insert these values on Figure 1.
2. 1. Find the critical path.
   2. Find the float time of activity \(F\).
3. Using Figure 2 on page 3, draw a resource histogram to illustrate how the project can be completed in the minimum time, assuming that each activity is to start as early as possible.
4. 1. Given that there are two workers available for the project, find the minimum completion time for the project.
   2. Write down an allocation of tasks to the two workers that corresponds to your answer in part (d)(i). \section*{Answer space for question 1} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-02_687_1655_1941_189}
      \end{figure} \section*{Answer space for question 1} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-03_1115_1575_434_283}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{34de3f03-a275-44fb-88b2-b88038bcec97-03_1024_1593_1683_267}

2 A delivery company needs to transport heavy loads from its warehouse to a ferry port. Each of the roads that it can use has a bridge with a maximum weight limit. The directed network below represents the roads that can be used to get from the warehouse to the ferry port. Road junctions are labelled with (stage; state) labels. The weights on the arcs represent weight limits in tonnes. \includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-03_896_1561_468_292}

1. Explain what a maximin route is.
2. Set up a dynamic programming tabulation, working backwards from stage 1, to find the two maximin routes through the network. What is the maximum load that can be transported in one journey from the warehouse to the ferry port?
3. A new road is opened connecting ( \(2 ; 0\) ) and ( \(2 ; 1\) ). There is no bridge on this road so it does not restrict the weight of the load that can be carried. Using the new road, what is the maximum load that can be transported in one journey from the warehouse to the ferry port? State the route that the delivery company should use. (Do not attempt to apply dynamic programming in this part.)

4 Answer this question on the insert provided. The diagram shows an activity network for a project. The table lists the durations of the activities (in hours). \includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-05_680_1125_424_244} (ii) Key: \begin{figure}[h] \end{figure} Minimum completion time = \(\_\_\_\_\) hours Critical activities: \(\_\_\_\_\) (iii) \(\_\_\_\_\) (iv) \includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-11_513_1189_543_520} Number of workers required = \(\_\_\_\_\)

\(\_\_\_\_\)

	\(J\)	\(K\)	\(L\)	\(M\)	\(N\)	\(O\)
\(A\)	2	5	2	2	5	2
\(B\)	2	5	2	0	5	5
\(C\)	5	0	5	5	2	2
\(D\)
\(E\)
\(F\)

Answer part (iv) in your answer booklet.

6 Answer parts (i), (ii) and (iii) of this question on the insert provided. The activity network for a project is shown below. The durations are in minutes. The events are numbered 1, 2, 3, etc. for reference. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-06_747_1249_482_447}

1. Complete the table in the insert to show the immediate predecessors for each activity.
2. Explain why the dummy activity is needed between event 2 and event 3, and why the dummy activity is needed between event 4 and event 5 .
3. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Record your early event times and late event times in the table in the insert. Write down the minimum project completion time and the critical activities. Suppose that the duration of activity \(K\) changes to \(x\) minutes.
4. Find, in terms of \(x\), expressions for the early event time and the late event time for event 9 .
5. Find the maximum duration of activity \(K\) that will not affect the minimum project completion time found in part (iii). \section*{ADVANCED GCE
   MATHEMATICS} Decision Mathematics 2
   INSERT for Questions 5 and 6 (ii) Dummy activity is needed between event 2 and event 3 because \(\_\_\_\_\) Dummy activity is needed between event 4 and event 5 because \(\_\_\_\_\) (iii)

   Event	1	2	3	4	5	6	7	8	9	10
   Early event time
   Late event time

   Minimum project completion time = \(\_\_\_\_\) minutes Critical activities: \(\_\_\_\_\) \section*{Answer part (iv) and part (v) in your answer booklet.} OCR
   RECOGNISING ACHIEVEMENT

3. A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.

1. Draw an activity network for the project.
2. Find the critical path and the minimum time in which the project can be completed. Activity \(F\) can be carried out more cheaply if it is allocated more time.
3. Find the maximum time that can be allocated to activity \(F\) without increasing the minimum time in which the project can be completed.

4.
\$ FMMUMITI7 IP HIZ3 UFHGHQFHIT
ா\$ மோங்கோ
ா\%\%mmum \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_268_424_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_46_465_482_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_533_539_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_472_593_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_497_648_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_54_501_703_306} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_45_467_762_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_463_813_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_47_460_872_303} \(\square\) \(\square\) Fig. 2
Construct an activity network to model the work involved in laying the foundations and putting in services for an industrial complex.

1. Execute a forward scan to find the minimum time in which the project can be completed.
2. Execute a backward scan to determine which activities lie on the critical path. 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 \(E\) will take 3 days longer than the 7 days allocated.
3. Activity \(K\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
   (2 marks)
4. If the time taken to complete any one activity, other than \(E\), 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)
   11 marks

4. Construct an activity network to show the tasks involved in widening a bridge over the B451.

1. Find those tasks which lie on the critical path and list them in order.
2. State the minimum length of time needed to widen the bridge.
3. Represent the tasks on a Gantt diagram. Tasks \(F\) and \(J\) each require 3 workers, tasks \(B\), \(D\) and \(I\) each require 2 workers and the remaining tasks each require one worker.
4. Draw a resource histogram showing how it is possible for a team of 4 workers to complete the project in the minimum possible time.

1. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below.

1. Draw an activity network for this project.
2. By labelling your network, find the critical path and the minimum duration of the project. An extra condition is now imposed. Task \(A\) may not begin until task \(B\) has been underway for at least 10 minutes.
3. Draw a new network taking into account this restriction.
4. Find a revised value for the minimum duration of the project and state the new critical path.
   

1. A project consists of the activities listed in the table below. For each activity the table shows how long it will take, which other activites must be completed before it can be done and the number of workers needed to complete it.

1. Draw an activity network for the project.
2. Find the critical path and the minimum time in which the project can be completed.
3. Represent all of the activities on a Gantt diagram.
4. By drawing a resource histogram, find out the maximum number of workers required at any one time if each activity is begun as soon as possible.
5. Draw another resource histogram to show how the project can be completed in the minimum time possible using a maximum of 10 workers at any one time. Sheet for answering question 4 \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_729_1227_482_338} \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_723_1223_1466_338}

5 A group of friends want to prepare a meal. They start preparing the meal at 6:30 pm Activities to prepare the meal are shown in Figure 1 below. \begin{table}[h] \end{table} 5

1. 1. Use Figure 2 shown below to complete Figure 1 above. 5
      1. (ii) Complete Figure 2 showing the earliest start time and latest finishing time for each activity. \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5a826f8b-4751-4589-ad0a-109fc5c821f2-06_700_1650_1781_194}
         \end{figure} 5
   2. 1. State the activity which must be started first so that the meal is served in the shortest possible time. Fully justify your answer.
         5
   3. (ii) Determine the earliest possible time at which the preparation of the meal can be completed.
      Question 5 continues on the next page 5
   4. The group of friends want to cook spring rolls so that they are served at the same time as the rest of the meal. This requires the additional activities shown in Figure 3. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3}

      Label	Activity	Duration	Immediate predecessors
      J	Switch on and heat oven		-
      K	Put spring rolls in oven and cook
      \(L\)	Transfer spring rolls to serving dish

      \end{table} It takes 15 seconds to switch on the oven. The oven must be allowed to heat up for 10 minutes before the spring rolls are put in the oven. It takes 15 seconds to put the spring rolls in the oven.
      The spring rolls must cook in the hot oven for 8 minutes.
      It takes 30 seconds to transfer the spring rolls to a serving dish.
      5
   5. 1. Complete Figure 3 above. 5
   6. (ii) Determine the latest time at which the oven can be switched on in order for the spring rolls to be served at the same time as the rest of the meal.
      [0pt] [2 marks] \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-09_2488_1716_219_153}

2 Part of an activity network is shown in the diagram below. \(A B C\) is part of the critical path of the activity network. \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-04_264_908_447_566} The duration of activity \(B\) is \(d\).
Which of the following statements about \(d\) is correct? Circle your answer. $$0 < d < 10 \quad d = 10 \quad 10 < d < 20 \quad d = 20$$