7.05e Cascade charts: scheduling and effect of delays

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.

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}

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}

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}

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. 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. \section*{Schedule}

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}

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. Optimal route is

7. Susie has hired a team of four workers who can make three types of toy. The total number of toys the team can produce will depend on which toys they make, and on how many workers are assigned to make each type of toy. The table shows how many of each toy would be made if different numbers of workers were assigned to make them. Each worker is to be assigned to make just one type of toy and all four workers are to be assigned. Susie wishes to maximise the total number of toys produced.

1. Use dynamic programming to determine the allocation of workers which maximises the total number of toys made. You should show your working in the table provided in the answer book.
   (12)
2. State the maximum total number of toys produced by this team.
   (1)
   (Total 13 marks)

7. A company assembles microlight aircraft. They can assemble up to four aircraft in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 1000\) per month.
They can store up to two aircraft at a cost of \(\pounds 500\) each per month.
The overhead costs are \(\pounds 2000\) in any month in which work is done. Aircraft are delivered at the end of each month. There are no aircraft in stock at the beginning of March and there should be none in stock at the end of July.
The order book for aircraft is Use dynamic programming to determine the production schedule which minimises the costs. Show your working in the table provided in the answer book and state the minimum production cost.
(Total 14 marks)

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, \(\mathrm { S } , \mathrm { A }\), B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.

1. Write down the type of dynamic programming problem that Janet needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence find the maximum weight of the truck Janet can use.
4. Write down the route that Janet should take. Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.
5. 1. Determine which of the three roads she should choose and its new minimum weight limit.
   2. Write down the maximum weight of the truck she would be able to use and the new route she would take.

7. Remy builds canoes. He can build up to five canoes each month, but if he wishes to build more than three canoes in any one month he has to hire an additional worker at a cost of \(\pounds 400\) for that month. In any month when canoes are built, the overhead costs are \(\pounds 150\) A maximum of three canoes can be held in stock in any one month, at a cost of \(\pounds 25\) per canoe per month. Canoes must be delivered at the end of the month. The order book for canoes is There is no stock at the beginning of January and Remy plans to have no stock after the May delivery.

1. Use dynamic programming to determine the production schedule that minimises the costs given above. Show your working in the table provided in the answer book and state the minimum cost.
   (13) The cost of materials is \(\pounds 200\) per canoe and the cost of Remy's time is \(\pounds 450\) per month. Remy sells the canoes for \(\pounds 700\) each.
2. Determine Remy's total profit for the five-month period.
   (2)
   (Total 15 marks)

2 Karl is considering investing in a villa in Greece. It will cost him 56000 euros ( € 56000 ). His alternative is to invest his money, \(\pounds 35000\), in the United Kingdom. He is concerned with what will happen over the next 5 years. He estimates that there is a \(60 \%\) chance that a house currently worth \(€ 56000\) will appreciate to be worth \(€ 75000\) in that time, but that there is a \(40 \%\) chance that it will be worth only \(€ 55000\). If he invests in the United Kingdom then there is a \(50 \%\) chance that there will be \(20 \%\) growth over the 5 years, and a \(50 \%\) chance that there will be \(10 \%\) growth.

1. Given that \(\pounds 1\) is worth \(€ 1.60\), draw a decision tree for Karl, and advise him what to do, using the EMV of his investment (in thousands of euros) as his criterion. In fact the \(\pounds / €\) exchange rate is not fixed. It is estimated that at the end of 5 years, if there has been \(20 \%\) growth in the UK then there is a \(70 \%\) chance that the exchange rate will stand at 1.70 euros per pound, and a \(30 \%\) chance that it will be 1.50 . If growth has been \(10 \%\) then there is a \(40 \%\) chance that the exchange rate will stand at 1.70 and a \(60 \%\) chance that it will be 1.50 .
2. Produce a revised decision tree incorporating this information, and give appropriate advice. A financial analyst asks Karl a number of questions to determine his utility function. He estimates that for \(x\) in cash (in thousands of euros) Karl's utility is \(x ^ { 0.8 }\), and that for \(y\) in property (in thousands of euros), Karl's utility is \(y ^ { 0.75 }\).
3. Repeat your computations from part (ii) using utility instead of the EMV of his investment. Does this change your advice?
4. Using EMVs, find the exchange rate (number of euros per pound) which will make Karl indifferent between investing in the UK and investing in a villa in Greece.
5. Show that, using Karl's utility function, the exchange rate would have to drop to 1.277 euros per pound to make Karl indifferent between investing in the UK and investing in a villa in Greece.

3 Emma has won a holiday worth \(\pounds 1000\). She is wondering whether or not to take out an insurance policy which will pay out \(\pounds 1000\) if she should fall ill and be unable to go on the holiday. The insurance company tells her that this happens to 1 in 200 people. The insurance policy costs \(\pounds 10\). Thus Emma's monetary value if she buys the insurance and does not fall ill is \(\pounds 990\).

1. Draw a decision tree for Emma's problem. Use the EMV criterion in your calculations.
2. Interpret your tree and say what the maximum cost of the insurance would have to be for Emma to consider buying it if she uses the EMV criterion. Suppose that Emma's utility function is given by utility \(= \sqrt [ 3 ] { \text { monetary value } }\).
3. Using expected utility as the criterion, should Emma purchase the insurance? Under this criterion what is the cost at which she will be indifferent to buying or not buying it? Emma could pay for a blood pressure check to help her to make her decision. Statistics show that \(75 \%\) of checks are positive, and that when a check is positive the chance of missing a holiday through ill heath is 0.001 . However, when a check is negative the chance of cancellation through ill health is 0.017.
4. Draw a decision tree to help Emma decide whether or not to pay for the check. Use EMV, not expected utility, in your calculations and assume that the insurance policy costs \(\pounds 10\). What is the maximum amount that she should pay for the blood pressure check?

2 Bill is at a horse race meeting. He has \(\pounds 2\) left with two races to go. He only ever bets \(\pounds 1\) at a time. For each race he chooses a horse and then decides whether or not to bet on it. In both races Bill's horse is offered at "evens". This means that, if Bill bets \(\pounds 1\) and the horse wins, then Bill will receive back his \(\pounds 1\) plus \(\pounds 1\) winnings. If Bill's horse does not win then Bill will lose his \(\pounds 1\).

1. Draw a decision tree to model this situation. Show Bill's payoffs on your tree, i.e. how much money Bill finishes with under each possible outcome. Assume that in each race the probability of Bill's horse winning is the same, and that it has value \(p\).
2. Find Bill's EMV when
   (A) \(p = 0.6\),
   (B) \(p = 0.4\). Give his best course of action in each case.
3. Suppose that Bill uses the utility function utility \(= ( \text { money } ) ^ { x }\), to decide whether or not to bet \(\pounds 1\) on one race. Show that, with \(p = 0.4\), Bill will not bet if \(x = 0.5\), but will bet if \(x = 1.5\).

2 Jane has a house on a Mediterranean island. She spends eight weeks a year there, either visiting twice for four weeks each trip or four times for two weeks each trip. Jane is wondering whether it is best for her to fly out and rent a car, or to drive out.
Flights cost \(\pounds 500\) return and car rental costs \(\pounds 150\) per week.
Driving out costs \(\pounds 900\) for ferries, road tolls, fuel and overnight expenses.

1. Draw a decision tree to model this situation. Advise Jane on the cheapest option. As an alternative Jane considers buying a car to keep at the house. This is a long-term alternative, and she decides to cost it over 10 years. She has to cost the purchase of the car and her flights, and compare this with the other two options. In her costing exercise she decides that she will not be tied to two trips per year nor to four trips per year, but to model this as a random process in which she is equally likely to do either.
2. Draw a decision tree to model this situation. Advise Jane on how much she could spend on a car using the EMV criterion.
3. Explain what is meant by "the EMV criterion" and state an alternative approach.

2 Zoe is preparing for a Decision Maths test on two topics, Decision Analysis (D) and Simplex (S). She has to decide whether to devote her final revision session to D or to S . There will be two questions in the test, one on D and one on S . One will be worth 60 marks and the other will be worth 40 marks. Historically there is a 50\% chance of each possibility. Zoe is better at \(D\) than at \(S\). If her final revision session is on \(D\) then she would expect to score \(80 \%\) of the \(D\) marks and \(50 \%\) of the \(S\) marks. If her final session is on \(S\) then she would expect to score \(70 \%\) of the S marks and \(60 \%\) of the D marks.

1. Compute Zoe's expected mark under each of the four possible circumstances, i.e. Zoe revising \(D\) and the D question being worth 60 marks, etc.
2. Draw a decision tree for Zoe. Michael claims some expertise in forecasting which question will be worth 60 marks. When he forecasts that it will be the D question which is worth 60 , then there is a \(70 \%\) chance that the D question will be worth 60 . Similarly, when he forecasts that it will be the S question which is worth 60 , then there is a \(70 \%\) chance that the S question will be worth 60 . He is equally likely to forecast that the D or the S question will be worth 60.
3. Draw a decision tree to find the worth to Zoe of Michael's advice.

3 Magnus has been researching career possibilities. He has just completed his GCSEs, and could leave school and get a good job. He estimates, discounted at today's values and given a 49 year working life, that there is a \(50 \%\) chance of such a job giving him lifetime earnings of \(\pounds 1.5 \mathrm {~m}\), a \(30 \%\) chance of \(\pounds 1.75 \mathrm {~m}\), and a \(20 \%\) chance of \(\pounds 2 \mathrm {~m}\). Alternatively Magnus can stay on at school and take A levels. He estimates that, if he does so, there is a 75\% chance that he will achieve good results. If he does not achieve good results then he will still be able to take the same job as earlier, but he will have lost two years of his lifetime earnings. This will give a \(50 \%\) chance of lifetime earnings of \(\pounds 1.42 \mathrm {~m}\), a \(30 \%\) chance of \(\pounds 1.67 \mathrm {~m}\) and a \(20 \%\) chance of \(\pounds 1.92 \mathrm {~m}\). If Magnus achieves good A level results then he could take a better job, which should give him discounted lifetime earnings of \(\pounds 1.6 \mathrm {~m}\) with \(50 \%\) probability or \(\pounds 2 \mathrm {~m}\) with \(50 \%\) probability. Alternatively he could go to university. This would cost Magnus another 3 years of lifetime earnings and would not guarantee him a well-paid career, since graduates sometimes choose to follow less well-paid vocations. His research shows him that graduates can expect discounted lifetime earnings of \(\pounds 1 \mathrm {~m}\) with \(20 \%\) probability, \(\pounds 1.5 \mathrm {~m}\) with \(30 \%\) probability, \(\pounds 2 \mathrm {~m}\) with \(30 \%\) probability, and \(\pounds 3 \mathrm {~m}\) with \(20 \%\) probability.

1. Draw up a decision tree showing Magnus's options.
2. Using the EMV criterion, find Magnus's best course of action, and give its value. Magnus has read that money isn't everything, and that one way to reflect this is to use a utility function and then compare expected utilities. He decides to investigate the outcome of using a function in which utility is defined to be the square root of value.
3. Using the expected utility criterion, find Magnus's best course of action, and give its utility.
4. The possibility of high earnings ( \(\pounds 3 \mathrm {~m}\) ) swings Magnus's decision towards a university education. Find what value instead of \(\pounds 3 \mathrm {~m}\) would make him indifferent to choosing a university education under the EMV criterion. (Do not change the probabilities.)

2 Adrian is considering selling his house and renting a flat.
Adrian still owes \(\pounds 150000\) on his house. He has a mortgage for this, for which he has to pay \(\pounds 4800\) annual interest. If he sells he will pay off the \(\pounds 150000\) and invest the remainder of the proceeds at an interest rate of \(2.5 \%\) per annum. He will use the interest to help to pay his rent. His estate agent estimates that there is a \(30 \%\) chance that the house will sell for \(\pounds 225000\), a \(50 \%\) chance that it will sell for \(\pounds 250000\), and a \(20 \%\) chance that it will sell for \(\pounds 275000\). A flat will cost him \(\pounds 7500\) per annum to rent.

1. Draw a decision tree to help Adrian to decide whether to keep his house, or to sell it and rent a flat. Compare the EMVs of Adrian's annual outgoings, and ignore the costs of selling.
2. Would the analysis point to a different course of action if Adrian were to use a square root utility function, instead of EMVs? Adrian's circumstances change so that he has to decide now whether to sell or not in one year's time. Economic conditions might then be less favourable for the housing market, the same, or more favourable, these occurring with probabilities \(0.3,0.3\) and 0.4 respectively. The possible selling prices and their probabilities are shown in the table.

   Economic conditions and probabilities		Selling prices ( £) and probabilities
   less favourable	0.3	200000	0.2	225000	0.3	250000	0.5
   unchanged	0.3	225000	0.3	250000	0.5	275000	0.2
   more favourable	0.4	250000	0.3	300000	0.5	350000	0.2

3. Draw a decision tree to help Adrian to decide what to do. Compare the EMVs of Adrian's annual outgoings. Assume that he will still owe \(\pounds 150000\) in one year's time, and that the cost of renting and interest rates do not change.

4 A project is represented by the activity network below. The activity durations are given in hours. \includegraphics[max width=\textwidth, alt={}, center]{f20391b2-e3c1-4021-9a87-47fd4ea7c490-5_346_1033_351_244}

1. By carrying out a forward pass, determine the minimum project completion time.
2. By carrying out a backward pass, determine the (total) float for each activity.
3. For each non-critical activity, determine the independent float and the interfering float.
4. Construct a cascade chart showing all the critical activities on one row and each non-critical activity on a separate row, starting at its earliest start time, and using dashed lines to indicate (total) float. You may not need to use all the grid. Each activity requires exactly one worker.
5. Construct a schedule to show how exactly two workers can complete the project as quickly as possible. You may not need to use all the grid. Issues with deliveries delay the earliest possible start of activity D by 3 hours.
6. Construct a schedule to show how exactly two workers can complete the project with this delay as quickly as possible. You may not need to use all the grid.

6 A project is represented by the activity on arc network below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-7_410_1095_296_486} The duration of each activity (in minutes) is shown in brackets, apart from activity I.

1. Suppose that the minimum completion time for the project is 15 minutes.
   1. By calculating the early event times, determine the range of values for \(x\).
   2. By calculating the late event times, determine which activities must be critical. The table shows the number of workers needed for each activity.

      Activity	A	B	C	D	E	F	G	H	I	J	K
      Workers	2	1	1	2	\(n\)	1	2	1	1	1	4

2. Determine the maximum possible value for \(n\) if 5 workers can complete the project in 15 minutes. Explain your reasoning. The duration of activity F is reduced to 1.5 minutes, but only 4 workers are available. The minimum completion time is no longer 15 minutes.
3. Determine the minimum project completion time in this situation.
4. Find the maximum possible value for \(x\) for this minimum project completion time.
5. Find the maximum possible value for \(n\) for this minimum project completion time.

6. \begin{figure}[h] \end{figure} [The sum of the durations of all the activities is 142 days]
A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the 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 late event times.
3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
5. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.

6. \begin{figure}[h] \end{figure} 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 days, to complete the activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and late event times.
2. State the critical activities.
3. Calculate the maximum number of days by which activity E could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
5. Draw a cascade (Gantt) chart for this project on the grid provided in the answer book.

4. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 3. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and late event times.
2. Determine the critical activities and the length of the critical path.
3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
4. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
5. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities.

5. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 6. 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 late event times.
3. State the minimum project completion time and list the critical activities.
4. Calculate the maximum number of hours by which activity E 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. The project is to be completed in the minimum time using as few workers as possible.
6. Schedule the activities using Grid 1 in the answer book.
   (3) Before the project begins it becomes apparent that activity E will require an additional 6 hours to complete. The project is still to be completed in the shortest possible time and the time to complete all other activities is unchanged.
7. State the new minimum project completion time and list the new critical activities.

5. \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 days, to complete the corresponding activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
3. Schedule the activities on Grid 1 in the answer book using the minimum number of workers so that the project is completed in the minimum time. Additional resources become available, which can shorten the duration of one of activities D, G or P by one day.
4. Determine which of these three activities should be shortened to allow the project to be completed in the minimum time. You must give reasons for your answer.