7.05c Total float: calculation and interpretation

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

2. An engineering firm makes motors. They can make up to five in any one month, but if they make more than four they have to hire additional premises at a cost of \(\pounds 500\) per month. They can store up to two motors for \(\pounds 100\) per motor per month. The overhead costs are \(\pounds 200\) in any month in which work is done.
Motors are delivered to buyers at the end of each month. There are no motors in stock at the beginning of May and there should be none in stock after the September delivery. The order book for motors is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided below. \section*{Production schedule} Total cost: \(\_\_\_\_\)

6. Kris produces custom made racing cycles. She can produce up to four cycles each month, but if she wishes to produce more than three in any one month she has to hire additional help at a cost of \(\pounds 350\) for that month. In any month when cycles are produced, the overhead costs are \(\pounds 200\). A maximum of 3 cycles can be held in stock in any one month, at a cost of \(\pounds 40\) per cycle per month. Cycles must be delivered at the end of the month. The order book for cycles is Disregarding the cost of parts and Kris' time,

1. determine the total cost of storing 2 cycles and producing 4 cycles in a given month, making your calculations clear. There is no stock at the beginning of August and Kris plans to have no stock after the November delivery.
2. Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table below.

   Stage	Demand	State	Action	Destination	Value
   \multirow[t]{3}{*}{1 (Nov)}	\multirow[t]{3}{*}{2}	0 (in stock)	(make) 2	0	200
   		1 (in stock)	(make) 1	0	240
   		2 (in stock)	(make) 0	0	80
   \multirow[t]{2}{*}{2 (Oct)}	\multirow[t]{2}{*}{5}	1	4	0	\(590 + 200 = 790\)
   		2	3	0

   The fixed cost of parts is \(\pounds 600\) per cycle and of Kris' time is \(\pounds 500\) per month. She sells the cycles for \(\pounds 2000\) each.
3. Determine her total profit for the four month period.
   (3)
   (Total 18 marks)

3 The table lists the duration (in hours), immediate predecessors and number of workers required for each activity in a project.

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.

3 The table lists the duration, immediate predecessors and number of workers required for each activity in a project.

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.

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.

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).]

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.

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

3 The table lists the activities involved in preparing for a cycle ride, their expected durations and their immediate predecessors.

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.

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.

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.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, 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).

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.

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.

6 Tariq wants to advertise his gardening services. The activities involved, their durations (in hours) and immediate predecessors are listed in the table.

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.

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]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-3_595_1054_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.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, 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).

5 Following a promotion at work, Khalid needs to clear out his office to move to a different building. The activities involved, their durations (in hours) and immediate predecessors are listed in the table below. You may assume that some of Khalid's friends will help him and that once an activity is started it will be continued until it is completed.

1. Represent this project using an activity network.
2. 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 your network. State the minimum project completion time and list the critical activities.
3. How much longer could be spent on sorting the items from the desk and throwing out the rubbish (activity \(C\) ) without it affecting the overall completion time? Khalid says that he needs to do activities \(A , C , E\) and \(G\) himself. These activities take a total of 8.5 hours.
4. By considering what happens if Khalid does \(A\) first, and what happens if he does \(C\) first, show that the project will take more than 8.5 hours.
5. Draw up a schedule to show how just two people, Khalid and his friend Mia, can complete the project in 9 hours. Khalid must do \(A , C , E\) and \(G\) and activities cannot be shared between Khalid and Mia. [2]

2 The diagram below shows an activity network for a project. The figures in brackets show the durations of the activities, in hours. \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-3_371_1429_367_319}

1. Complete the table in your answer book to show the immediate predecessors for each activity.
2. Carry out a forward pass and a backward pass on the copy of the network in your answer book, showing the early event times and late event times. State the minimum project completion time, in hours, and list the critical activities.
3. How much longer could be spent on activity \(F\) without it affecting the overall completion time? Suppose that each activity requires one worker. Once an activity has been started it must continue until it is finished. Activities cannot be shared between workers.
4. (a) State how many workers are needed at the busiest point in the project if each activity starts at its earliest possible start time.
   (b) Suppose that there are fewer workers available than given in your answer to part (iv)(a). Explain why the project cannot now be completed in the minimum project completion time from part (ii). Suppose that activity \(C\) is delayed so that it starts 2 hours after its earliest possible start time, but there is no restriction on the number of workers available.
5. Describe what effect this will have on the critical activities and the minimum project completion time.

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?

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