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

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}

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

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from \(A\) to \(I\). \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-20_867_1644_552_191}

1. Working backwards from \(\boldsymbol { I }\), use dynamic programming to find the maximum number of bags that can be collected when driving from \(A\) to \(I\). You must complete the table opposite as your solution.
2. State the route that the collector should take in order to collect the maximum number of bags.

   1. Stage	State	From	Value
      1	G	I
      	H	I
      2

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

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)

2 The table shows the activities involved in a project, their durations, precedences and the number of workers needed for each activity. The graph gives a schedule with each activity starting at its earliest possible time. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-03_473_1591_964_278}

1. Using the graph, find the minimum completion time for the project and state which activities are critical.
2. Draw a resource histogram, using graph paper, assuming that there are no delays and that every activity starts at its earliest possible time. Assume that only four workers are available but that they are equally skilled at all tasks. Assume also that once an activity has been started it continues until it is finished.
3. The critical activities are to start at their earliest possible times. List the start times for the non-critical activities for completion of the project in the minimum possible time. What is this minimum completion time?

7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.

• Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
• Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
• Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
• Diane wants to do task \(H\)

Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).

1. Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
2. Maximin value \(=\) Route \(=\)

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.