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

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.)

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.)

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.

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 .
   

6. \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 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. State the critical activities.
3. Calculate the maximum number of days by which activity E could be delayed without lengthening the completion time of the project. You must make the numbers used 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.
5. Draw a cascade (Gantt) chart for this project on the grid provided in the answer book.

4. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 3. 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. Determine the critical activities and the length of the critical path.
3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
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.

5. \begin{figure}[h] \end{figure} 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 hours, to complete the corresponding 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. State the minimum project completion time and list the critical activities.
4. Calculate the maximum number of hours by which activity E could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used in your calculation clear.
5. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. The project is to be completed in the minimum time using as few workers as possible.
6. Schedule the activities using Grid 1 in the answer book.
   (3) Before the project begins it becomes apparent that activity E will require an additional 6 hours to complete. The project is still to be completed in the shortest possible time and the time to complete all other activities is unchanged.
7. State the new minimum project completion time and list the new critical activities.

4. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 3. 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.

1. Explain the significance of the dummy activity
   1. from event 2 to event 3
   2. from event 6 to event 7
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 and list the critical activities. The duration of activity H changes to \(x\) hours.
4. Find, in terms of \(x\) where necessary,
   1. the possible new early event time for event 7
   2. the possible new late event time for event 7 Given that the duration of activity H is such that the minimum project completion time is four hours greater than the time found in (c),
5. determine the value of \(x\).

4.

1. Draw the activity network described by the precedence table below, using activity on arc. Use dummies only where necessary.
   (5)

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

   Given that K is a critical activity,
2. state which other activities must also be critical.
   (1) Given instead that all activities shown in the precedence table have the same duration and K is not necessarily critical,
3. state the critical path for the network.
   (1)
   

5. \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 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 the late event times.
2. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
3. 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. Additional resources become available, which can shorten the duration of one of activities D, G or P by one day.
4. Determine which of these three activities should be shortened to allow the project to be completed in the minimum time. You must give reasons for your answer.

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, in hours, 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. Draw a cascade 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.)

6.

1. Draw the activity network for the project described in the precedence table above, using activity on arc and the minimum number of dummies.
   (5)
2. State which activity is guaranteed to be critical, giving a reason for your answer.
   (2) It is given that each activity in the table takes two hours to complete.
3. State the minimum completion time and write down the critical path for the project.
   (2)

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 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. Given that

• CHN is the critical path for the project
• the total float on activity B is twice the duration of the total float on activity I
  1. find the value of \(x\) and show that the value of \(y\) is 7
  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.

Draw a cascade chart for this project on Grid 1 in your answer book, and use it 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.

5. The precedence table shows the eleven activities required to complete a project.

1. Draw the activity network for the project, using activity on arc and the minimum number of dummies.
   (5) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-07_314_1385_1464_347} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 shows a schedule for the project. Each of the activities shown in the precedence table requires one worker. The time taken to complete each activity is in hours and the project is to be completed in the minimum possible time.
2. 1. State the minimum completion time for the project.
   2. State the critical activities.
   3. State the total float on activity G and the total float on activity K .
      (4)

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 days, to complete the 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 the late event times.
2. Calculate the maximum number of days by which activity H could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
3. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
4. 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.

5.

1. Draw the activity network described in the precedence table above, using activity on arc and the minimum number of dummies. A project is modelled by the activity network drawn in (a). Each activity requires exactly one worker. The project is to be completed in the shortest possible time. The table below gives the time, in hours, to complete three of the activities.

   Activity	Duration (in hours)
   A	10
   E	7
   F	8

   The length of the critical path AEFK is 33 hours.
2. Determine the range of possible values for the duration of activity J. You must make your method and working clear.

2. \begin{figure}[h] \end{figure} [The sum of the durations of all the activities is 59 days.]
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 days, of the corresponding activity is shown in brackets. Each activity requires one worker. The project is to be completed in the shortest possible time.

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.
2. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
3. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.

6.

1. Draw the activity network for the project described in the precedence table, using activity on arc and the minimum number of dummies. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-10_880_1154_1464_452} \captionsetup{labelformat=empty} \caption{Grid 1}
   \end{figure} A cascade chart for all the activities of the project, except activity \(\mathbf { L }\), is shown on Grid 1. The time taken to complete each activity is given in hours and each activity requires one worker. The project is to be completed in the minimum time using as few workers as possible.
2. State the critical activities of the project.
3. Use the 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.) The duration of activity L is \(x\) hours. Given that the total float of activity L is at most 7 hours,
4. determine the range of possible values for \(\chi\).