7.05a Critical path analysis: activity on arc networks

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)

4.

1. Explain what is meant by a maximin route in dynamic programming, and give an example of a situation that would require a maximin solution.
   (3) \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-2_700_1392_1069_338} A maximin route is to be found through the network shown in the diagram.
2. Complete the table in the answer book, and hence find a maximin route.
   (9)
3. List all other maximin routes through the network.
   (Total 14 marks)
   

7. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121} Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath. The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next. Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.

1. Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie. Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
2. Find an optimal route for Agent Goodie avoiding tunnel XA.

4.

1. Explain the difference between a maximin route and a minimax route in dynamic programming.
   (2) \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376} A maximin route from L to R is to be found through the staged network shown above.
2. Use dynamic programming to complete a table below and hence find a maximin route.
   (10) (Total 12 marks)
   

7. Minty has \(\pounds 250000\) to allocate to three investment schemes. She will allocate the money to these schemes in units of \(\pounds 50000\). The net income generated by each scheme, in \(\pounds 1000\) s, is given in the table below. Minty wishes to maximise the net income. She decides to use dynamic programming to determine the optimal allocation, and starts the table shown in your answer book.

1. Complete the table in the answer book to determine the amount Minty should allocate to each scheme in order to maximise the income. State the maximum income and the amount that should be allocated to each scheme.
2. For this problem give the meaning of the table headings
   1. Stage,
   2. State,
   3. Action.

4. \begin{figure}[h] \end{figure} Figure 1 represents the maintenance choices a council can make and their costs, in \(\pounds 1000\) s, over the next four years. The council wishes to minimise the greatest annual cost of maintenance.

1. Use dynamic programming to find a minimax route from S to T .
   (9)
2. State your route and the greatest annual cost incurred by the council.
   (2)
3. Calculate the average annual cost to the council.
   (2)

7. Patrick is to take orders for his company's products. He will visit four countries over the next four weeks.
He will visit just one country each week.
He will leave from his office in London and will only return there after visiting the four countries.
He will travel directly from one country to the next.
He wishes to determine a schedule of four countries to visit. Table 1 shows the countries he could visit in each week. \begin{table}[h] \end{table} Table 2 shows the value of the orders, in \(\pounds 100\) s, he expects to take in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the various countries. \begin{table}[h] \end{table} The expected income is the value of the expected orders minus the cost of travel. It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.

1. Complete the table in the answer book to determine the optimal expected income.
2. State Patrick's two optimal schedules.

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.