7.05b Forward and backward pass: earliest/latest times, critical activities

5 The network below represents a project using activity on arc. The durations of the activities are not yet shown. \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-6_597_1257_340_386}

1. If \(C\) were to turn out to be a critical activity, which two other activities would be forced to be critical?
2. Complete the table, in the Answer Book, to show the immediate predecessor(s) for each activity. In fact, \(C\) is not a critical activity. Table 1 lists the activities and their durations, in minutes. \begin{table}[h]

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Duration	10	15	10	5	15	5	10	15	5	15

   \captionsetup{labelformat=empty} \caption{Table 1}
   \end{table}
3. Carry out a forward pass and a backward pass through the activity network, showing the early event time and late event time at each vertex of the network. State the minimum project completion time and list the critical activities. Each activity requires one person.
4. Draw a schedule to show how three people can complete the project in the minimum time, with each activity starting at its earliest possible time. Each box in the Answer Book represents 5 minutes. For each person, write the letter of the activity they are doing in each box, or leave the box blank if the person is resting for those 5 minutes.
5. Show how two people can complete the project in the minimum time. It is required to reduce the project completion time by 10 minutes. Table 2 lists those activities for which the duration could be reduced by 5 minutes, and the cost of making each reduction. \begin{table}[h]

   Activity	\(A\)	\(B\)	\(C\)	\(E\)	\(G\)	\(H\)	\(J\)
   Cost \(( \pounds )\)	200	400	100	600	100	500	500
   New duration	5	10	5	10	5	10	10

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
6. Explain why the cost of saving 5 minutes by reducing activity \(A\) is more than \(\pounds 200\). Find the cheapest way to complete the project in a time that is 10 minutes less than the original minimum project completion time. State which activities are reduced and the total cost of doing this.

4 Henry is planning a surprise party for Lucinda. He has left the arrangements until the last moment, so he will hold the party at their home. The table below lists the activities involved, the expected durations, the immediate predecessors and the number of people needed for each activity. Henry has some friends who will help him, so more than one activity can be done at a time.

1. Draw an activity network to represent these activities and the precedences. Carry out forward and reverse passes to determine the minimum completion time and the critical activities. If Lucinda is expected home at 7.00 p.m., what is the latest time that Henry or his friends can begin telephoning the other friends?
2. Draw a resource histogram showing time on the horizontal axis and number of people needed on the vertical axis, assuming that each activity starts at its earliest possible start time. What is the maximum number of people needed at any one time?
3. Now suppose that Henry's friends can start buying the food and making the decorations as soon as the telephoning begins. Construct a timetable, with a column for 'time' and a column for each person, showing who should do which activity when, in order than the party can be organised in the minimum time using a total of only six people (Henry and five friends). When should the telephoning begin with this schedule?

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.

3. This question should be answered on the sheet provided. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue. \begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.
(9 marks)

4. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses. Use dynamic programming to find the route which should maximise the salesman's net profit. State the expected profit from using this route.
(10 marks)

3. This question should be answered on the sheet provided. Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times - at \(B , C\) or \(D\), at \(E , F , G\) or \(H\) and at \(I , J\) or \(K\). \begin{figure}[h] \end{figure} Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the maximum waiting time at any one stop is as small as possible. Use dynamic programming to find the route that Arthur should use.
(9 marks)

4. This question should be answered on the sheet provided. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h] \end{figure} Figure 2 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. As her plane does not have a large fuel tank, the owner wishes to choose a route that minimises the maximum distance of any one flight. Find the route that she should use and state the maximum distance of any one stage on this route.

2. This question should be answered on the sheet provided. A pool player is to play in four tournaments. Some of the tournaments take place simultaneously and the player has to choose one of each of the following: $$\begin{array} { l l } 1 ^ { \text {st } } \text { tournament: } & A , B \text { or } C , \\ 2 ^ { \text {nd } } \text { tournament: } & D , E \text { or } F , \\ 3 ^ { \text {rd } } \text { tournament: } & G , H \text { or } I , \\ 4 ^ { \text {th } } \text { tournament: } & J , K \text { or } L \end{array}$$ Each tournament has six rounds and the player estimates how well he will do in each tournament based on which tournament he plays before it. The table below shows his expectations with each number indicating the round he expects to reach and a "7" indicating he expects to win the tournament. He wishes to choose the tournaments such that his worst performance is as good as possible. Use dynamic programming to find which tournaments he should play.
(10 marks)

6 Sheona and Tim are making a short film. The activities involved, their durations and immediate predecessors are given in the table below.

1. By using an activity network, find:
   • the minimum project completion time
   • the critical activities
   • the float on each non-critical activity.
   • Give two reasons why the filming may take longer than the minimum project completion time.
   Each activity will involve either Sheona or Tim or both.
   • The activities that Sheona will do are ticked in the S column.
   • The activities that Tim will do are ticked in the T column.
   • They will do the planning and finishing together.
   • Some of the activities involve other people as well.
   An additional restriction is that Sheona and Tim can each only do one activity at a time.
2. Explain why the minimum project completion is longer than in part (i) when this additional restriction is taken into account.
3. The project must be completed in 14 days. Find:
   1. the longest break that either Sheona or Tim can take,
   2. the longest break that Sheona and Tim can take together,
   3. the float on each activity.

2 The activities involved in a project and their durations, in hours, are represented in the activity network below. \includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-3_446_1139_338_230}

1. Carry out a forward pass and a backward pass through the network.
2. Calculate the float for each activity. A delay means that activity B cannot finish until \(t\) hours have elapsed from the start of the project.
3. Determine the maximum value of \(t\) for which the project can be completed in 16 hours.

5 Hiro has been asked to organise a quiz.
The table below shows the activities involved, together with the immediate predecessors and the duration of each activity in hours.

1. A sketch of the activity network is provided in the Printed Answer Booklet. Apply a forward pass to determine the minimum project completion time.
2. Use a backward pass to determine the critical activities. You can show your working on the activity network from part (a).
3. Give the total float for each non-critical activity. Hiro decides that there should be a final check of the answers which he will include as activity \(L\). Activity L needs to be done after checking the answers for rounds 1 and 2 and also after getting permission to use the pictures and music but before producing the answer sheets.
4. 1. Complete the activity network provided in the Printed Answer Booklet to show the new precedences, with the final check of the answers included as activity \(L\).
   2. As a result of including L , the minimum project completion time found in part (a) increases by 2.5 hours. Determine the duration of L .

4 A project is represented by the activity network below. The activity durations are given in minutes. \includegraphics[max width=\textwidth, alt={}, center]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-5_447_1020_392_246}

1. Give the reason for the dummy activity from event (3) to event (4).
2. Complete a forward pass to determine the minimum project completion time.
3. By completing a backward pass, calculate the float for each activity.
4. Determine the effect on the minimum project completion time if the duration of activity A changes from 2 minutes to 3 minutes. The duration of activity C changes to \(m\) minutes, where \(m\) need not be an integer. This reduces the minimum project completion time.
5. By considering the range of possible values of \(m\), determine the minimum project completion time, in terms of \(m\) where necessary.

4 Bob is extending his attic with the help of some friends, including his architect friend Archie. The activities involved, their durations (in days) and Bob's notes are given below. Archie has started to construct an activity network to represent the project. \includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-5_401_1253_1475_406}

1. Complete the activity network in the Printed Answer Booklet and use it to determine

2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker. \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201} \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}

1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
4. 1. Find the number of ways that the workers for activity A can be chosen.
   2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).

2 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.

1. Model the project using an activity network.
2. Determine the minimum project completion time.
3. Calculate the total float for each non-critical activity.

1 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.

1. Model the project using an activity network.
2. Determine the minimum project completion time. The start of activity C is delayed by 2 hours.
3. Determine the minimum project completion time with this delay.

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.

2 Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc. \includegraphics[max width=\textwidth, alt={}, center]{0c9513fe-a471-427e-ba30-b18df11271e3-3_887_1751_1030_207}

1. Construct a cascade chart for the project, showing the float for each non-critical activity.
2. Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.
3. Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day.