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

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.

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.

4. \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 of the activity, in days, is shown in brackets. The early event times and late event times are to be shown at each vertex and one late event time has been completed for you. The total float of activity H is 7 days.

1. Explain, with detailed reasoning, why \(x = 11\)
2. Determine the missing early event times and late event times, and hence complete Diagram 1 in your answer book. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.
4. Schedule the activities using Grid 1 in the answer book.

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.

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

5 Answer this question on the insert provided. The diagram shows an activity network for a project. The table lists the durations of the activities (in days). \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-4_652_867_429_393}

1. Explain why each of the dummy activities is needed.
2. Complete the blank column of the table in the insert to show the immediate predecessors for each activity.
3. Carry out a forward pass to find the early start times for the events. Record these at the eight vertices on the copy of the network on the insert. Also calculate the late start times for the events and record these at the vertices. Find the minimum completion time for the project and list the critical activities.
4. By how much would the duration of activity \(C\) need to increase for \(C\) to become a critical activity? Assume that each activity requires one worker and that each worker is able to do any of the activities. The activities may not be split. The duration of \(C\) is 4 days.
5. Draw a resource histogram, assuming that each activity starts at its earliest possible time. How many workers are needed with this schedule?
6. Describe how, by delaying the start of activity \(E\) (and other activities, to be determined), the project can be completed in the minimum time by just three workers.

5 Answer this question on the insert provided. The diagram shows an activity network for a project. The figures in brackets show the durations of the activities in days. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-06_956_921_495_612}

1. Complete the table in the insert to show the precedences for the activities.
2. Use the boxes on the diagram in the insert to carry out a forward pass and a backward pass. Find the minimum project duration and list the critical activities. The number of people required for each activity is shown in the table below. The workers are all equally skilled at all of the activities.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers	4	1	2	2	3	2	3	3	1	2

3. On graph paper, draw a resource histogram for the project with each activity starting at its earliest possible time.
4. Describe how the project can be completed in 21 days using just six workers.

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.

2 Answer this question on the insert provided. The diagram shows an activity network for a project. The figures in brackets show the durations of the activities in days. \includegraphics[max width=\textwidth, alt={}, center]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_497_1230_493_459}

1. Complete the table in the insert to show the precedences for the activities.
2. Use the boxes on the diagram in the insert to carry out a forward pass and a backward pass. Show that the minimum project completion time is 28 days and list the critical activities. The resource histogram below shows the number of workers required each day when the activities each begin at their earliest possible start time. Once an activity has been started it runs for its duration without a break. \includegraphics[max width=\textwidth, alt={}, center]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_457_1543_1503_299}
3. By considering which activities are happening each day, complete the table in the insert to show the number of workers required for each activity. You are advised to start at day 28 and work back through the days towards day 1 . Only five workers are actually available, but they are all equally skilled at each of the activities. The project can still be completed in 28 days by delaying the start of activity \(E\).
4. Find the minimum possible delay and the maximum possible delay on activity \(E\) in this case.

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

4 Answer this question on the insert provided. The table shows activities involved in a "perm" in a hair salon, their durations and immediate predecessors. \begin{table}[h] \end{table}

1. Complete the activity-on-arc network in the insert to represent the precedences.
2. Perform a forward pass and a backward pass to find early and late event times. Give the critical activities and the time needed to complete the perm.
3. Give the total float time for the activity \(G\). Activities \(\mathrm { D } , \mathrm { F } , \mathrm { H } , \mathrm { K }\) and N require a stylist.
   Activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { E } , \mathrm { G } , \mathrm { J }\) and M are done by a trainee.
   Activities \(I\) and \(L\) require no-one in attendance.
   A stylist and a trainee are to give a perm to a customer.
4. Use the chart in the insert to show a schedule for the activities, assuming that all activities are started as early as possible.
5. Which activity would be better started at its latest start time?

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)