7.05a Critical path analysis: activity on arc networks

2. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 1. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the corresponding activity. The numbers in circles are the event numbers. Each activity requires one worker, and the project is to be completed in the shortest possible time.

1. Explain the significance of the dummy activity from event 3 to event 4
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the critical activities.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
5. Draw a Gantt chart for this project on Grid 1 in the answer book.

2. A company manages an awards evening. The table below lists the activities required to set up the room for the evening, and their immediately preceding activities. Each activity requires exactly one person. Figure 1 shows a partially completed activity network used to model the project. Each activity is represented by an arc. \begin{figure}[h] \end{figure}

1. Add the remaining five activities to Diagram 1 in the answer book to complete the activity network, using exactly two dummies. In addition to setting up the room, the company must prepare the meals for the guests. Figure 2 shows the activity network for preparing the main courses. The numbers in brackets represent the time, in minutes, to complete each task. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{ca57c64b-0b33-4179-be7f-684bd6ea2162-05_793_1515_451_373} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}
2. Complete Diagram 2 in the answer book to show the early event times and the late event times for the activity network shown in Figure 2.
3. State the critical activities.
4. Given that the main courses need to be ready to be served (with all activities completed) at 8 pm , state the latest time that activity \(R\) can start.

3. The table above shows the activities required for the completion of a building project. For each activity, the table shows the time taken in days to complete the activity and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Draw the activity network described in the table, using activity on arc. Your activity network must contain the minimum number of dummies only.
2. 1. Show that the project can be completed in 21 days, showing your working.
   2. Identify the critical activities.

5.

1. Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies. Given that all the activities shown in the precedence table have the same duration, (b) state the critical path for the network.

2. \begin{figure}[h] \end{figure} The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets.

1. Explain why each of the dummy activities is required.
2. Complete the table in the answer book to show the immediately preceding activities for each activity.
3. 1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
   2. State the minimum completion time for the project.
   3. State the critical activities. Each activity requires one worker. Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption.
4. On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time.
5. Determine whether or not the project can be completed in the minimum possible time using fewer workers than the number indicated by the resource histogram in (d). You must justify your answer with reference to the resource histogram and the completed Diagram 1.

2. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
2. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
3. Schedule the activities using Grid 1 in the answer book.

7. \begin{figure}[h] \end{figure} Figure 5 shows a partially completed activity network for a project that consists of 14 activities.

1. Complete the precedence table in the answer book for the 8 activities in Figure 5. The precedence table for the remaining 6 activities is given below.

   Activity	Immediately preceding activities
   I	D, E, G, H
   J	D, E, G, H
   K	E, G, H
   L	I, J, K
   M	J, K
   N	J, K

2. Complete the activity network in the answer book for the project. Your completed activity network must contain only the minimum number of dummies. Given that all 14 activities have the same duration,
3. explain why activity D cannot be critical.

5. \begin{figure}[h] \end{figure} The network in Figure 2 shows the activities that need to be completed for a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times are shown in Figure 2.

1. Complete Table 1 in the answer book to show the immediately preceding activities for each activity. It is given that \(4 < x \leqslant m\)
2. State the largest possible integer value of \(m\).
3. 1. Complete Diagram 1 in the answer book to show the late event times.
   2. State the activities that must be critical.
4. Calculate the total float for activity G. The resource histogram in Figure 3 shows the number of workers required when each activity starts at its earliest possible time. The histogram also shows which activities happen at each time. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-09_682_1612_356_230} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure}
5. Complete Table 2 in the answer book to show the number of workers required for each activity of the project.
6. Draw a Gantt chart on Grid 1 in the answer book to represent the activity network.

2. \begin{figure}[h] \end{figure} The network in Figure 3 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets.

1. 1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
   2. State the minimum completion time of the project. The table below lists the number of workers required for each activity in the project.

      Activity	Number of workers
      A	2
      B	1
      C	2
      D	2
      E	3
      F	2
      G	1
      H	3

      Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption. It is given that each activity begins at its earliest possible start time.
2. 1. On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time.
   2. Hence state the time interval(s) when six workers are required.

6. The precedence table below shows the twelve activities required to complete a project.

1. Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only.
   (5) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-11_654_1358_153_356} \captionsetup{labelformat=empty} \caption{Figure 6}
   \end{figure} Figure 6 shows a partially completed cascade chart for the project. The non-critical activities F, J and K are not shown in Figure 6. The time taken to complete each activity is given in hours and the project is to be completed in the minimum possible time.
2. State the critical activities. Given that the total float of activity F is 2 hours,
3. state the duration of activity F . The duration of activity J is \(x\) hours, and the duration of activity K is \(y\) hours, where \(x > 0\) and \(y > 0\)
4. 1. State, in terms of \(y\), the maximum possible total float for activity K.
   2. State, in terms of \(x\) and \(y\), the total float for activity J .

6. The precedence table below shows the 12 activities required to complete a project.

1. Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only.
   (5) Each of the activities shown in the precedence table requires one worker. The project is to be completed in the minimum possible time. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-11_303_1547_296_260} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 shows a schedule for the project using three workers.
2. 1. State the critical path for the network.
   2. State the minimum completion time for the project.
   3. Calculate the total float on activity B.
   4. Calculate the total float on activity G. Immediately after the start of the project, it is found that the duration of activity I, as shown in Figure 3, is incorrect. In fact, activity I will take 8 hours.
      The durations of all the other activities remain as shown in Figure 3.
3. Determine whether the project can still be completed in the minimum completion time using only three workers when the duration of activity I is 8 hours. Your answer must make specific reference to workers, times and activities.

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

1. Calculate the early time and the late time for each event, using Diagram 1 in the answer book.
2. On Grid 1 in the answer book, complete the cascade (Gantt) chart for this project.
3. On Grid 2 in the answer book, draw a resource histogram to show the number of workers required each day when each activity begins at its earliest time. The supervisor of the project states that only three workers are required to complete the project in the minimum time.
4. Use Grid 2 to determine if the project can be completed in the minimum time by only three workers. Give reasons for your answer.

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, \(S , A , B , C , D , E , F , G , H , I , J\) and \(T\). The number on each arc shows the distance between these towns, in miles. Bradley is planning a four-day cycle ride from \(S\) to \(T\).
He plans to leave his home at \(S\). On the first night he will stay at \(A , B\) or \(C\), on the second night he will stay at \(D , E , F\) or \(G\), on the third night he will stay at \(H , I\) or \(J\), and he will arrive at his friend's house at \(T\) on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.

1. Write down the type of dynamic programming problem that Bradley needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence write down the possible routes that Bradley could take.

6. Polly is a motivational speaker who is planning her engagements for the next four weeks. Polly will

• visit four different countries in these four weeks
• visit just one country each week
• leave from her home, S , and return there only after visiting the four countries
• travel directly from one country to the next

Polly wishes to determine a schedule of four countries to visit.
Table 1 shows the countries Polly could visit each week. \begin{table}[h] \end{table} Table 2 shows the speaker fee, in \(\pounds 100\) s, Polly would expect to earn in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the countries. \begin{table}[h] \end{table} Polly's expected income is the value of the speaker fee minus the cost of travel.
She wants to find a schedule that maximises her total expected income for the four weeks. Use dynamic programming to determine the optimal schedule. Complete the table provided in the answer book and state the maximum expected income.
(13)

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns. Elena plans to drive from S to T . She must arrive at T by 9 pm .

1. By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm .
2. Hence write down the route that Elena should take.

7. A company assembles boats. They can assemble up to five boats in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 800\) per month. The company can store up to two boats at a cost of \(\pounds 350\) each per month.
The overhead costs are \(\pounds 1500\) in any month in which work is done.
Boats are delivered at the end of each month. There are no boats in stock at the beginning of January and there must be none in stock at the end of May. The order book for boats is Use dynamic programming to determine the production schedule which minimises the costs to the company. Show your working in the table provided in the answer book and state the minimum production cost.

6 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

2 Answer this question on the insert provided. The diagram shows a directed network of paths with vertices labelled with (stage; state) labels. The weights on the arcs represent distances in km . The shortest route from \(( 3 ; 0 )\) to \(( 0 ; 0 )\) is required. Complete the dynamic programming tabulation on the insert, working backwards from stage 1 , to find the shortest route through the network. Give the length of this shortest route. \begin{figure}[h] \end{figure}

1 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

6 Answer this question on the insert provided. Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation. Let the stages be \(0,1,2,3,4,5\). Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be \(0,1,2,3,4\) representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

1. Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\), or this in reverse, taking 27 minutes.
2. Explain why the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\) is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state \(1 ( 234 )\) means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
3. For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.
4. Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

   Stage	State	Action	Working	Suboptimal minimum
   \multirow{4}{*}{4}	1(234)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4

3 The activities involved in a project and their durations are represented in the activity network below. \includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-3_494_700_306_683}

1. Carry out a forward pass and a backward pass through the network.
2. Find the float for each activity. A delay means that the duration of activity E increases to \(x\).
3. Find the values of \(x\) for which activity E is not a critical activity.

4 Deva is having some work done on his house. The table shows the activities involved, their durations and their immediate predecessors.

1. Model this information as an activity network.
2. Find the minimum time in which the work can be completed.
3. Describe the effect on the minimum project completion time of each of the following happening individually.
   1. The duration of activity A is increased to 3.5 hours.
   2. The duration of activity D is increased to 4 hours.
   3. The duration of activity F is decreased to 2 hours. The decorators working on activity H cannot work for 3 hours without a break.
   4. How would you adapt your model to incorporate the break?

4 A project is represented by the activity network below. The times are in days. \includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-4_384_935_1110_566}

1. Explain the reason for each dummy activity.
2. Calculate the early and late event times.
3. Identify the critical activities.
4. Calculate the independent float and interfering float on activity A .
5. (a) Draw a cascade chart to represent the project, using the grid in the Printed Answer Booklet.
   (b) Describe the effect on
   The number of workers needed for each activity is shown below.

   Activity	A	B	C	D	E	F	G	H
   Workers	2	1	1	2	1	1	1	1

   The project needs to be completed in at most 3 weeks ( 21 days).
   The duration of activity D is 9 days.
6. Find the minimum number of workers needed. You should explain your reasoning carefully.

5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.

1. Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
2. Hence determine the critical activities and the length of the critical path. Each activity requires one worker. The project is to be completed in the minimum time.
3. Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities.
   (5 marks)

5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.

1. Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
   (6 marks)
2. Hence determine the critical activities and the length of the critical path.
   (2 marks)
   Each activity requires one worker. The project is to be completed in the minimum time.
3. Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities.
   (5 marks)