7.05d Latest start and earliest finish: independent and interfering float

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 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}

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. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 1. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Complete the precedence table in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. 1. State the minimum project completion time.
   2. List the critical activities.
4. Calculate the maximum number of hours by which activity H could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used in your calculation clear.
5. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
6. Draw a cascade chart for this project on Grid 1 in the answer book.
7. Using the answer to (f), explain why it is not possible to complete the project in the shortest possible time using the number of workers found in (e).

1. Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of \(\pounds 250\) for that month. In any month in which sheds are made, the overhead costs are \(\pounds 35\) for each shed made that month. A maximum of three sheds can be held in storage at the end of any one month, at a cost of \(\pounds 80\) per shed per month. Sheds must be delivered at the end of the month.
The order schedule for sheds is There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery. Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.

\includegraphics{figure_2} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

1. Explain the significance of the dummy activity
   1. from event 5 to event 6
   2. from event 7 to event 9.
   \hfill [2]
2. Complete Diagram 3 in the answer book to show the early event times and the late event times. \hfill [4]
3. State the minimum project completion time. \hfill [1]
4. Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time. You must show your working. \hfill [2]
5. On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project. \hfill [4]
6. On Grid 2 in your answer book, construct a scheduling diagram to show that this project can be completed with three workers in just one more hour than the minimum project completion time. \hfill [3]

\includegraphics{figure_3} A project is modelled by the activity network shown in Fig 3. The activities are represented by the edges. The number in brackets on each edge gives the time, in days, taken to complete the activity.

1. Calculate the early time and the late time for each event. Write these in the boxes on the answer sheet. [4]
2. Hence determine the critical activities and the length of the critical path. [2]
3. Obtain the total float for each of the non-critical activities. [3]
4. On the first grid on the answer sheet, draw a cascade (Gantt) chart showing the information obtained in parts (b) and (c). [4]

Each activity requires one worker. Only two workers are available.

1. On the second grid on the answer sheet, draw up a schedule and find the minimum time in which the 2 workers can complete the project. [4]

\includegraphics{figure_3} A project is modelled by the activity network in Fig. 3. The activities are represented by the arcs. One worker is required for each activity. The number in brackets on each arc gives the time, in hours, to complete the activity. The earliest event time and the latest event time are given by the numbers in the left box and right box respectively.

1. State the value of \(x\) and the value of \(y\). [2]
2. List the critical activities. [2]
3. Explain why at least 3 workers will be needed to complete this project in 38 hours. [2]
4. Schedule the activities so that the project is completed in 38 hours using just 3 workers. You must make clear the start time and finish time of each activity. [4]

\includegraphics{figure_5} A project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

1. Explain the purpose of the dotted line from event 6 to event 8. (1)
2. Calculate the early time and late time for each event. Write these in the boxes in the answer book. (4)
3. Calculate the total float on activities \(D\), \(E\) and \(F\). (3)
4. Determine the critical activities. (2)
5. Given that the sum of all the times of the activities is 95 hours, calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. (2)
6. Given that workers may not share an activity, schedule the activities so that the process is completed in the shortest time using the minimum number of workers. (4)

(Total 16 marks)

\includegraphics{figure_3} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.

1. Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet. [4]
2. Hence determine the critical activities. [2]
3. Calculate the total float time for \(D\). [2]

Each activity requires only one person.

1. Find a lower bound for the number of workers needed to complete the process in the minimum time. [2]

Given that there are only three workers available, and that workers may not share an activity,

1. schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time. [5]