7.05a Critical path analysis: activity on arc networks

2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker. \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201} \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}

1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
4. 1. Find the number of ways that the workers for activity A can be chosen.
   2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).

2 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.

1. Model the project using an activity network.
2. Determine the minimum project completion time.
3. Calculate the total float for each non-critical activity.

1 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.

1. Model the project using an activity network.
2. Determine the minimum project completion time. The start of activity C is delayed by 2 hours.
3. Determine the minimum project completion time with this delay.

4 A project is represented by the activity network below. The activity durations are given in hours. \includegraphics[max width=\textwidth, alt={}, center]{f20391b2-e3c1-4021-9a87-47fd4ea7c490-5_346_1033_351_244}

1. By carrying out a forward pass, determine the minimum project completion time.
2. By carrying out a backward pass, determine the (total) float for each activity.
3. For each non-critical activity, determine the independent float and the interfering float.
4. Construct a cascade chart showing all the critical activities on one row and each non-critical activity on a separate row, starting at its earliest start time, and using dashed lines to indicate (total) float. You may not need to use all the grid. Each activity requires exactly one worker.
5. Construct a schedule to show how exactly two workers can complete the project as quickly as possible. You may not need to use all the grid. Issues with deliveries delay the earliest possible start of activity D by 3 hours.
6. Construct a schedule to show how exactly two workers can complete the project with this delay as quickly as possible. You may not need to use all the grid.

6 A project is represented by the activity on arc network below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-7_410_1095_296_486} The duration of each activity (in minutes) is shown in brackets, apart from activity I.

1. Suppose that the minimum completion time for the project is 15 minutes.
   1. By calculating the early event times, determine the range of values for \(x\).
   2. By calculating the late event times, determine which activities must be critical. The table shows the number of workers needed for each activity.

      Activity	A	B	C	D	E	F	G	H	I	J	K
      Workers	2	1	1	2	\(n\)	1	2	1	1	1	4

2. Determine the maximum possible value for \(n\) if 5 workers can complete the project in 15 minutes. Explain your reasoning. The duration of activity F is reduced to 1.5 minutes, but only 4 workers are available. The minimum completion time is no longer 15 minutes.
3. Determine the minimum project completion time in this situation.
4. Find the maximum possible value for \(x\) for this minimum project completion time.
5. Find the maximum possible value for \(n\) for this minimum project completion time.

2 Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc. \includegraphics[max width=\textwidth, alt={}, center]{0c9513fe-a471-427e-ba30-b18df11271e3-3_887_1751_1030_207}

1. Construct a cascade chart for the project, showing the float for each non-critical activity.
2. Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.
3. Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day.

5.

1. Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain only the minimum number of dummies.
   (5)
2. Explain why, in general, dummies may be required in an activity network.

7. \begin{figure}[h] \end{figure} The network in Figure 4 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 some have been completed for you. Given that activity F is a critical activity and that the total float on activity G is 2 days,

1. write down the value of \(x\) and the value of \(y\),
2. calculate 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.
3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.
4. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
5. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. (You do not need to provide a schedule of the 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 required, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

1. Explain the significance of the dummy activity
   1. from event 5 to event 6
   2. from event 7 to event 9
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the minimum project completion time.
4. Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time. You must show your working.
5. On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project.
6. On Grid 2 in your answer book, construct a scheduling diagram to show that this project can be completed with three workers in just one more hour than the minimum project completion time.
   (3)

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

1. Complete Diagram 1 in the answer book to show the early event times and late event times.
2. Explain what is meant by a critical path.
3. List the critical path for this network.
4. For each of the situations below, state the effect that the delay would have on the project completion date.
   1. A 4-day delay during activity J.
   2. A 4-day delay during activity M . The delays mentioned in (d) do not occur.
5. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
6. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.

2. \begin{figure}[h] \end{figure} The network in Figure 3 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. Each activity requires exactly one worker. The early event times and late event times are shown at each vertex. Given that the total float on activity B is 2 days and the total float on activity F is also 2 days,

1. find the values of \(w , x , y\) and \(z\).
2. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
3. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

3. \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 days, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. State the critical activities.
3. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
4. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the 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.
   (5) Given that D is a critical activity,
2. state which other activities must also be critical.
   (1)

6. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 17\) ]

1. Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
2. During rush hour one day \(x = 9\)
   1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
   2. Calculate the weight of the minimum spanning tree. You are now given that \(x > 3\) A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
3. Determine the value of \(x\), showing your working clearly.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration, in days, is shown in brackets. Each activity requires one worker. The early event times and late event times are shown at each vertex. The total float on activity D is twice the total float on activity E .

1. Find the values of \(x , y\) and \(z\).
2. Draw a cascade chart for this project on Grid 1 in the answer book.
3. Use your cascade chart to determine a lower bound for the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the 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 critical paths for the network include activity H ,
2. state which activities cannot be critical.
   (2)

6. The table above shows the activities required for the completion of a building project. For each activity the table shows the duration, in days, and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time. \begin{figure}[h] \end{figure} Figure 2 shows a partially completed activity network used to model the project. The activities are represented by the arcs and the numbers in brackets on the arcs are the times taken, in days, to complete each activity.

1. Complete the network in Diagram 1 in the answer book by adding activities \(\mathrm { G } , \mathrm { H }\) and I and the minimum number of dummies.
2. Add the early event times and the late event times to Diagram 1 in the answer book.
3. State the critical activities.
4. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
5. Schedule the activities on Grid 1 in the answer book, using the minimum number of workers, so that the project is completed in the minimum time.

3. \section*{Question 3 continued} Please redraw your activity network on this page if you need to do so.

4. \begin{figure}[h] \end{figure} \section*{Question 4 continued} \begin{figure}[h] \end{figure}

1. \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, in hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time using as few workers as possible.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. Calculate the total float for activity D. You must make the numbers used in your calculation clear.
3. Calculate a lower bound for the minimum number of workers required to complete the project in the shortest possible time. You must show your working.
4. Draw a cascade chart for this project on Grid 1 in the answer book.
5. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

4.

1. Draw the activity network described in the precedence table, using activity on arc and the minimum number of dummies.
2. Given that
   • the activity network contains only one critical path
   • activity E is on this critical path
     state
     1. which activities could never be critical,
     2. which activities must be critical.

6.

1. Draw the activity network described in this precedence table, using activity on arc and dummies only where necessary.

   Activity	Immediately preceding activities
   A	-
   B	-
   C	-
   D	B, C
   E	A
   F	C
   G	D, E
   H	D, E
   I	\(F , G\)
   J	C
   K	\(G , H\)

2. Explain the possible reasons dummies may be needed in activity networks.
   

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

1. Add early and late event times to Diagram 1 in the answer book.
2. State the critical path and its length.
3. On Diagram 2 in the answer book, construct a cascade (Gantt) chart.
4. By using your cascade chart, state which activities must be happening at
   1. time 7.5
   2. time 16.5 It is decided that the company may use up to 25 days to complete the project.
5. On Diagram 3 in the answer book, construct a scheduling diagram to show how this project can be completed within 25 days using as few workers as possible.

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

1. Complete the precedence table in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and late event times.
3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
5. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.

4.

1. Draw the activity network described in the precedence table below, using activity on arc and the minimum number of dummies.

   Activity	Immediately preceding activities
   A	-
   B	-
   C	-
   D	A
   E	A
   F	A, B, C
   G	C
   H	E, F, G
   I	E, F, G
   J	H, I
   K	H, I
   L	D, J

   A project is modelled by the activity network drawn in (a). Each activity requires one worker. The project is to be completed in the shortest possible time. The table below gives the time, in days, to complete some of the activities.

   Activity	Duration (in days)
   B	7
   F	4
   J	4
   L	6

   The critical activities for the project are B, F, I, J and L and the length of the critical path is 30 days.
2. Calculate the duration of activity I.
3. Find the range of possible values for the duration of activity K .