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

106 questions

Sort by: Default | Easiest first | Hardest first
OCR MEI D1 2006 January Q1
8 marks Moderate -0.3
1 Table 1 shows a precedence table for a project. \begin{table}[h]
ActivityImmediate predecessorsDuration (days)
A-5
B-3
CA3
DA, B4
EA, B5
\captionsetup{labelformat=empty} \caption{Table 1}
\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?
OCR MEI D1 2011 January Q4
16 marks Moderate -0.5
4 The table shows the tasks involved in preparing breakfast, and their durations.
TaskDescriptionDuration (mins)
AFill kettle and switch on0.5
BBoil kettle1.5
CCut bread and put in toaster0.5
DToast bread2
EPut eggs in pan of water and light gas1
FBoil eggs5
GPut tablecloth, cutlery and crockery on table2.5
HMake tea and put on table0.5
ICollect toast and put on table0.5
JPut eggs in cups and put on table1
  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.
OCR MEI D1 2012 June Q6
16 marks Moderate -0.8
6 The table shows the tasks involved in making a batch of buns, the time in minutes required for each task, and their precedences.
TaskTime (minutes)Immediate predecessors
Ameasure out flour0.5-
Bmix flour and water1A
Cshell eggs0.5-
Dmix in eggs and fat2B, C
Eget currants ready0.5-
Fget raisins ready0.5-
Gfold fruit into mix0.5D, E, F
Hbake10G
  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.
Edexcel D1 Q7
15 marks Moderate -0.3
7. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-08_586_1372_333_303} \captionsetup{labelformat=empty} \caption{Fig. 5}
\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}
    ABCDE\(F\)
    A-130190155140125
    B130-215200190170
    C190215-110180100
    D155200110-7045
    E14019018070-75
    \(F\)1251701004575-
    \section*{Please hand this sheet in for marking}
    1. \(n\)\(x _ { n }\)\(a\)Any more data?\(x _ { n + 1 }\)\(b\)\(( b - a ) > 0\) ?\(a\)
      188Yes22No2
      2--
      Final output
    2. \(\_\_\_\_\) Sheet for answering question 3
      NAME \section*{Please hand this sheet in for marking}
      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 =
      1. \(\_\_\_\_\)
      2. \(\_\_\_\_\) \section*{Please hand this sheet in for marking}
    3. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
    4. \(\_\_\_\_\)
    5. \(\_\_\_\_\)
    6. \(\_\_\_\_\)
    7. \(\_\_\_\_\)
Edexcel D1 Q7
14 marks Standard +0.3
7. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-07_576_1360_331_278} \captionsetup{labelformat=empty} \caption{Fig. 2}
\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\) ?
      1005026No
      -2614.923No
      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. 051015202530354045505560
      Worker 1
      Worker 2
    10. 051015202530354045505560
      Worker 1
      Worker 2
      Worker 3
AQA D2 2010 January Q1
13 marks Moderate -0.8
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 required2232321352
    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.
AQA D2 2011 January Q1
14 marks Moderate -0.5
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.
ActivityA\(B\)CD\(E\)\(F\)GHI\(J\)\(K\)\(L\)
Duration (days)256794323231
Number of workers required635252445324
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}
        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 \(\_\_\_\_\)
AQA D2 2012 January Q1
14 marks Standard +0.3
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 required4234243356
    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}
AQA D2 2013 January Q1
13 marks Moderate -0.5
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 their values on Figure 1.
  2. On Figure 2 opposite, complete the precedence table.
  3. Find the critical path.
  4. Find the float time of activity \(E\).
  5. Using Figure 3 on page 5, 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.
  6. Given that there are two workers available for the project, find the minimum completion time for the project.
  7. Given that there is only one worker available for the project, find the minimum completion time for the project. Figure 1 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(a)} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-02_629_1550_1818_292}
    \end{figure} (b) \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2}
    ActivityImmediate predecessor(s)
    A
    B
    C
    D
    E
    \(F\)
    G
    H
    I
    J
    \(K\)
    \end{table}
    \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-05_2486_1717_221_150}
AQA D2 2010 June Q1
13 marks Moderate -0.8
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 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. A delay in supplies means that Activity \(I\) takes 9 days instead of 2 .
    1. Determine the effect on the earliest possible starting times for activities \(K\) and \(L\).
    2. State the number of days by which the completion of the project is now delayed.
      (1 mark) \section*{Figure 1}
      1. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-02_815_1337_1573_395}
      2. Critical paths are \(\_\_\_\_\) Minimum completion time is \(\_\_\_\_\) days. QUESTION PART REFERENCE
      3. \begin{figure}[h]
        \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-03_978_1207_354_461}
        \end{figure}
AQA D2 2010 June Q5
10 marks Standard +0.3
5 A three-day journey is to be made from \(P\) to \(V\), with overnight stops at the end of the first day at one of the locations \(Q\) or \(R\), and at the end of the second day at \(S , T\) or \(U\). The network shows the journey times, in hours, for each day of the journey. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-10_737_1280_447_388} The optimal route, known as the minimax route, is that in which the longest day's journey is as small as possible.
  1. Explain why the route \(P Q S V\) is better than the route \(P Q T V\).
  2. By completing the table opposite, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { V }\), to find the optimal (minimax) route from \(P\) to \(V\). You should indicate the calculations as well as the values at stages 2 and 3.
    (8 marks)
    \(\ldots . . .\).\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159}
AQA D2 2011 June Q1
13 marks Moderate -0.5
1 Figure 1 below shows an activity diagram for a cleaning project. The duration of 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. Find the activity with the greatest float time and state the value of its float time.
  4. On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as late as possible.
    1. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-02_846_1488_1391_292}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1295_1714_219_150} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(d)} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1023_1584_1589_278}
      \end{figure}
AQA D2 2011 June Q6
9 marks Moderate -0.5
6 Bob is planning to build four garden sheds, \(A , B , C\) and \(D\), at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below.
\multirow{2}{*}{Day}\multirow{2}{*}{Already built}Expected profit (£)
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)
Monday-50657080
\multirow{4}{*}{Tuesday}A-728384
B60-8083
C5768-85
D627081-
\multirow{6}{*}{Wednesday}\(\boldsymbol { A }\) and \(\boldsymbol { B }\)--8488
\(\boldsymbol { A }\) and \(\boldsymbol { C }\)-71-82
\(A\) and \(D\)-7483-
\(\boldsymbol { B }\) and \(\boldsymbol { C }\)65--86
\(\boldsymbol { B }\) and \(\boldsymbol { D }\)69-85-
\(\boldsymbol { C }\) and \(\boldsymbol { D }\)6673--
\multirow{4}{*}{Thursday}\(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { C }\)---90
\(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { D }\)--87-
\(A , C\) and \(D\)-76--
\(\boldsymbol { B } , \boldsymbol { C }\) and \(\boldsymbol { D }\)70---
By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit.
Stage (Day)State (Sheds already built)Action (Shed to build)CalculationProfit in pounds
Thursday\(A , B , C\)D90
\(A , B , D\)C87
A, C, DB76
B, C, DA70
WednesdayA, BC\(84 + 90\)174
D\(88 + 87\)175
A, \(C\)B\(71 + 90\)161
D\(82 + 76\)158
A, \(D\)B
C
\(B , C\)A
D
\(B , D\)A
C
\(C , D\)A
B
TuesdayAB\(72 + 175\)247
C\(83 + 161\)244
D
Monday
\section*{Schedule}
\cline { 2 - 5 } \multicolumn{1}{c|}{}MondayTuesdayWednesdayThursday
Shed to build
\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-18_2486_1714_221_153}
AQA D2 2013 June Q1
9 marks Moderate -0.8
1 Figure 1 opposite shows an activity diagram for a project. The duration required for each activity is given in hours. The project is to be completed in the minimum time.
  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 path.
  3. Find the float time of activity \(E\).
  4. Given that activities \(H\) and \(K\) will both overrun by 10 hours, find the new minimum completion time for the project.
    \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-02_1515_1709_1192_153}
    \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-03_1656_869_627_611}
    \end{figure}
AQA D2 2013 June Q4
9 marks Standard +0.3
4 A haulage company, based in town \(A\), is to deliver a tall statue to town \(K\). The statue is being delivered on the back of a lorry. The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road. The company wants to ensure that the height of the lowest bridge along the route from \(A\) to \(K\) is maximised. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221} Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution.
StageStateFromValue
1H\(K\)
I\(K\)
JK
2
Optimal route is
OCR D2 2010 January Q3
15 marks Standard +0.3
3 The table lists the duration (in hours), immediate predecessors and number of workers required for each activity in a project.
ActivityDurationImmediate predecessorsNumber of workers
\(A\)6-2
B5-4
C4-1
D1\(A , B\)3
E2\(B\)2
\(F\)1\(B , C\)2
\(G\)2D, E4
\(H\)3D, E, F3
  1. Draw an activity network, using activity on arc, to represent the project. You should make your diagram quite large so that there is room for working.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early and late event times clearly at the vertices of your network. State the minimum project completion time and list the critical activities.
  3. Using graph paper, draw a resource histogram to show the number of workers required each hour. Each activity begins at its earliest possible start time. Once an activity has started it runs for its duration without a break. A delay from the supplier means that the start of activity \(F\) is delayed.
  4. By how much could the start of activity \(F\) be delayed without affecting the minimum project completion time? Suppose that only six workers are available after the first four hours of the project.
  5. Explain carefully what delay this will cause on the completion of the project. What is the maximum possible delay on the start of activity \(F\), compared with its earliest possible start time in part (iii), without affecting the new minimum project completion time? Justify your answer.
OCR D2 2011 January Q3
12 marks Moderate -0.3
3 The table lists the duration, immediate predecessors and number of workers required for each activity in a project.
ActivityDuration (hours)Immediate predecessorsNumber of workers
\(A\)3-1
\(B\)2-1
C2\(A\)2
\(D\)3\(A\), \(B\)2
E3\(C\)3
\(F\)3C, D3
\(G\)2D3
\(H\)5\(E , F\)1
I4\(F , G\)2
  1. Represent the project by an activity network, using activity on arc. You should make your diagram quite large so that there is room for working.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event times and late event times clearly at the vertices of your network. State the minimum project completion time and list the critical activities.
  3. Draw a resource histogram to show the number of workers required each hour when each activity begins at its earliest possible start time.
  4. Show how it is possible for the project to be completed in the minimum project completion time when only six workers are available.
OCR D2 2012 January Q2
11 marks Moderate -0.8
2 The table lists the durations (in minutes), immediate predecessors and number of workers required for each activity in a project to decorate a room.
ActivityDuration (minutes)Immediate predecessorsNumber of workers
A Cover furniture with dust sheets20-1
B Repair any cracks in the plaster100A1
C Hang wallpaper60B1
D Paint feature wall90B1
\(E\) Paint woodwork120C, D1
\(F\) Put up shelves30C2
G Paint ceiling60A1
\(H\) Clean paintbrushes10\(E , G\)1
I Tidy room20\(F , H\)2
  1. Draw an activity network, using activity on arc, to represent the project. Your network will require a dummy activity.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities.
  3. Draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. Suppose that there is only one worker available at the start of the project, but another two workers are available later.
  4. Find the latest possible time for the other workers to start and still have the project completed on time. Which activities could happen at the same time as painting the ceiling if the other two workers arrive at this latest possible time?
    [0pt] [Do not change your resource histogram from part (iii).]
OCR D2 2013 January Q2
12 marks Moderate -0.5
2 A project is represented by this activity network. The weights (in brackets) on the arcs represent activity durations, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-3_645_1235_356_415}
  1. Complete the table in the answer book to show the immediate predecessors for each activity.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities. Suppose that the start of one activity is delayed by 2 minutes.
  3. List each activity which could be delayed by 2 minutes with no change to the minimum project completion time.
  4. Without altering your diagram from part (ii), state the effect that a delay of 2 minutes on activity \(A\) would have on the minimum project completion time. Name another activity which could be delayed by 2 minutes, instead of \(A\), and have the same effect on the minimum project completion time.
  5. Without altering your diagram from part (ii), state what effect a delay of 2 minutes on activity \(C\) would have on the minimum project completion time.
OCR D2 2013 January Q6
17 marks Standard +0.3
6 Simon makes playhouses which he sells through an agent. Each Sunday the agent orders the number of playhouses she will need Simon to deliver at the end of each day. The table below shows the order for the coming week.
DayMondayTuesdayWednesdayThursdayFriday
Number of
playhouses
23224
Simon can make up to 3 houses each day, except for Wednesday when he can make at most 2 houses. Because of limited storage space, Simon can store at most 2 houses overnight from one day to the next, although the number in store does not restrict how many houses Simon can make the next day. The process is modelled by letting the stages be the days and the states be the numbers of houses stored overnight. Simon starts the week, on Monday morning, with no houses in storage. This means that the start of Monday morning has (stage; state) label ( \(0 ; 0\) ). Simon wants to end the week on Friday afternoon with no houses in storage, so the start of Saturday morning will have (stage; state) label ( \(5 ; 0\) ).
  1. Explain why the (stage; state) label ( \(4 ; 0\) ) is not needed. Simon wants to draw up a production plan showing how many houses he needs to make each day. He prefers not to have to make several houses on the same day so he assigns a 'cost' that is the square of the number of houses made that day, apart from Monday when the 'cost' is the cube of the number of houses made. So, for example, if he makes 3 houses one day the cost is 9 units, unless it is Monday when the cost is 27 units.
  2. Complete the diagram in the answer book to show all the possible production plans and weight the arcs with the costs. Simon wants to find a production plan that minimises the sum of the costs.
  3. Set up a dynamic programming tabulation, working backwards from ( \(5 ; 0\) ), to find a production plan that solves Simon's problem.
  4. Write down the number of houses that he should make each day with this plan.
OCR D2 2005 June Q3
14 marks Standard +0.3
3 The table lists the activities involved in preparing for a cycle ride, their expected durations and their immediate predecessors.
ActivityDuration (minutes)Preceded by
A: Check weather8-
B: Get maps out4-
C: Make sandwiches12-
D: Check bikes over20\(A\)
E: Plan route12A, B
\(F\) : Pack bike bags4A, B, \(C\)
G: Get bikes out ready2\(D , E , F\)
\(H\) : Change into suitable clothes12E, F
  1. Draw an activity network to represent the information in the table. Show the activities on the arcs and indicate the direction of each activity and dummy activity. You are advised to make your network quite large.
  2. Carry out a forward pass and a backward pass to determine the minimum completion time for preparing for the ride. List the critical activities.
  3. Construct a cascade chart, showing each activity starting at its earliest possible time. Two people, John and Kerry, are intending to go on the cycle ride. Activities \(A , B , F\) and \(G\) will each be done by just one person (either John or Kerry), but both are needed (at the same time) for activities \(C , D\) and \(E\). Also, each of John and Kerry must carry out activity \(H\), although not necessarily at the same time. All timings and precedences in the original table still apply.
  4. Draw up a schedule showing which activities are done by each person at which times in order to complete preparing for the ride in the shortest time possible. The schedule should have three columns, the first showing times in 4-minute intervals, the second showing which activities John does and the third showing which activities Kerry does.
OCR D2 2007 June Q3
15 marks Moderate -0.8
3 The table shows the activities involved in a project, their durations and precedences, and the number of workers needed for each activity.
  1. On the insert, complete the last two columns of the table.
  2. State the minimax value and write down the minimax route.
  3. Complete the diagram on the insert to show the network that is represented by the table.
OCR D2 2009 June Q2
20 marks Standard +0.3
2
  1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
  2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.
    ActivityDurationImmediate predecessors
    \(A\)8-
    \(B\)9-
    C7-
    D5\(A\)
    E6\(A\)
    \(F\)4\(B\)
    \(G\)5B
    \(H\)6\(B\)
    \(I\)10C
    \(J\)9\(C\)
    \(K\)6\(C\)
    \(L\)7D, F, I
    \(M\)6\(E , G , J\)
    \(N\)8\(H\), \(K\)
    Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
  3. Compare the solutions to parts (i) and (ii).
OCR D2 2011 June Q4
14 marks Moderate -0.3
4 Jamil is building a summerhouse in his garden. The activities involved, the duration, immediate predecessors and number of workers required for each activity are listed in the table.
ActivityDuration (hours)Immediate predecessorsNumber of workers
\(A\) : Choose summerhouse2-2
\(B\) : Buy slabs for base1-2
\(C\) : Take goods home2\(A , B\)2
\(D\) : Level ground3-1
E: Lay slabs2\(C , D\)2
\(F\) : Treat wood3C1
\(G\) : Install floor, walls and roof4\(E , F\)2
\(H\) : Fit windows and door2\(G\)1
\(I\) : Fit patio rail1\(G\)1
\(J\) : Fit shelving1\(G\)1
  1. Represent the project by an activity network, using activity on arc. You should make your diagram quite large so that there is room for working.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event times and late event times at the vertices of your network. State the minimum project completion time and list the critical activities.
  3. Draw a resource histogram to show the number of workers required each hour when each activity begins at its earliest possible start time.
  4. Describe how it is possible for the project to be completed in the minimum project completion time when only four workers are available.
  5. Describe how two workers can complete the project as quickly as possible. Find the minimum time in which two workers can complete the project.
OCR D2 2012 June Q6
17 marks Standard +0.3
6 Tariq wants to advertise his gardening services. The activities involved, their durations (in hours) and immediate predecessors are listed in the table.
ActivityDuration (hours)Immediate predecessors
AChoose a name for the gardening service2-
BThink about what the text needs to say3-
CArrange a photo shoot2B
DVisit a leaflet designer3A, \(C\)
EDesign website5A, \(C\)
\(F\)Get business cards printed3D
GIdentify places to publicise services2A, \(C\)
HArrange to go on local radio3B
IDistribute leaflets4D, G
JGet name put on van1E
  1. Draw an activity network, using activity on arc, to represent the project.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities. Tariq does not have time to complete all the activities on his own, so he gets some help from his friend Sally.
    Sally can help Tariq with any of the activities apart from \(C , H\) and \(J\). If Tariq and Sally share an activity, the time it takes is reduced by 1 hour. Sally can also do any of \(F , G\) and \(I\) on her own.
  3. Describe how Tariq and Sally should share the work so that activity \(D\) can start 5 hours after the start of the project.
  4. Show that, if Sally does as much of the work as she can, she will be busy for 18 hours. In this case, for how many hours will Tariq be busy?
  5. Explain why, if Sally is busy for 18 hours, she will not be able to finish until more than 18 hours from the start. How soon after the start can Sally finish when she is busy for 18 hours?
  6. Describe how Tariq and Sally can complete the project together in 18 hours or less.