7.05a Critical path analysis: activity on arc networks

5 A restoration project is divided into a number of activities. The duration and predecessor(s) of each activity are shown in the table below. 5

1. On the opposite page, construct an activity network for the project and fill in the earliest start time and latest finish time for each activity.
   [0pt] [4 marks] \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-09_533_289_2124_1548} \captionsetup{labelformat=empty} \caption{Turn over -}
   \end{figure} 5
2. Due to a change of materials during the project, the duration of activity \(C\) is extended by 3 weeks. Determine the new minimum completion time of the project. \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-11_2488_1716_219_153}

3 A project consists of 11 activities \(A , B , \ldots , K\) A completed activity network for the project is shown in the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{ecbeedf5-148e-40ad-b8a2-a7aa3db4a115-04_972_1604_445_219} All times on the activity network are given in days.
3

1. Write down the critical path.
   [0pt] [1 mark] 3
2. Due to an issue with the supply of materials, the duration of activity \(G\) is doubled. Deduce the effect, if any, that this change will have on the earliest start time and latest finish time for each of the activities \(I , J\) and \(K\)

4 A community project consists of 10 activities \(A , B , \ldots , J\), as shown in the activity network below. \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-06_899_1083_367_466} The duration of each activity is shown in days. 4

1. 1. Complete the activity network in the diagram above, showing the earliest start time and latest finish time for each activity. 4
      1. (ii) State the minimum completion time for the community project.
         4
   2. Write down the critical activities of the network.
      4
   3. Glyn claims that a project's activity network can be used to determine its minimum completion time by adding together the durations of all the project's critical activities. 4
   4. 1. Show that Glyn's claim is false for this community project's activity network.
         4
   5. (ii) Describe a situation in which Glyn's claim would be true.

8 A motor racing team is undertaking a project to build next season's racing car. The project is broken down into 12 separate activities \(A , B , \ldots , L\), as shown in the precedence table below. Each activity requires one member of the racing team. 8

1. 1. Complete the activity network for the project on Figure 3. 8
      1. (ii) Find the earliest start time and the latest finish time for each activity and show these values on Figure 3. 8
   2. Write down the critical path(s).
      \section*{Figure 3} Figure 3 \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-15_469_1360_356_338} 8
   3. 1. Using Figure 4, draw a resource histogram for the project to show how the project can be completed in the shortest possible time. Assume that each activity is to start as early as possible. \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-16_698_1534_541_251}
         \end{figure} 8
   4. (ii) The racing team's boss assigns two members of the racing team to work on the project. Explain the effect this has on the minimum completion time for the project.
      You may use Figure 5 in your answer. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-16_704_1539_1695_248}
      \end{figure}

1 Which of the following statements about critical path analysis is always true? Tick ( \(\checkmark\) ) one box. All activity networks have exactly one critical path. □ All critical activities have a non-zero float. □ The first activity in a critical path has an earliest start time of zero. □ A delay on a critical activity may not delay the project. □

7

1. 1. Find the earliest start time and the latest finish time for each activity and write these values on the activity network in Figure 1 7
      1. (ii) Write down the critical path. 7
   2. On Figure 2 below, draw a cascade diagram (Gantt chart) for the planned building project, assuming that each activity starts as early as possible. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-11_1127_1641_539_201}
      \end{figure} 7
   3. During further planning of the building project, Nova Merit Construction find that activity \(F\) is not necessary and they remove it from the project. Explain the effect removing activity \(F\) has on the minimum completion time of the project.

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 the precedence table in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. 1. State the minimum project completion time.
   2. List the critical activities.
4. Calculate the maximum number of hours by which activity H 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.
6. Draw a cascade chart for this project on Grid 1 in the answer book.
7. Using the answer to (f), explain why it is not possible to complete the project in the shortest possible time using the number of workers found in (e).

1. Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of \(\pounds 250\) for that month. In any month in which sheds are made, the overhead costs are \(\pounds 35\) for each shed made that month. A maximum of three sheds can be held in storage at the end of any one month, at a cost of \(\pounds 80\) per shed per month. Sheds must be delivered at the end of the month.
The order schedule for sheds is There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery. Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.

\includegraphics{figure_2} 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 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.
   \hfill [2]
2. Complete Diagram 3 in the answer book to show the early event times and the late event times. \hfill [4]
3. State the minimum project completion time. \hfill [1]
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. \hfill [2]
5. On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project. \hfill [4]
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. \hfill [3]

This question should be answered on the sheet provided in the answer booklet. \includegraphics{figure_2} 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.

1. 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]

The precedence table for activities involved in producing a computer game is shown below. An activity on arc network is to be drawn to model this production process.

1. Explain why it is necessary to use at least two dummies when drawing the activity network. [2]
2. Draw the activity network using exactly two dummies. [5]

\includegraphics{figure_5} The network in Figure 5 shows the activities involved in a process. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, taken to complete the activity.

1. Calculate the early time and late time for each event, showing them on the diagram in the answer book. [4]
2. Determine the critical activities and the length of the critical path. [2]
3. On the grid in the answer book, draw a cascade (Gantt) chart for the process. [4]

Each activity requires only one worker, and workers may not share an activity.

1. Use your cascade chart to determine the minimum numbers of workers required to complete the process in the minimum time. Explain your reasoning clearly. [2]
2. Schedule the activities, using the number of workers you found in part \((d)\), so that the process is completed in the shortest time. [3]

\includegraphics{figure_5} 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 hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

1. Explain the purpose of the dotted line from event 6 to event 8. (1)
2. Calculate the early time and late time for each event. Write these in the boxes in the answer book. (4)
3. Calculate the total float on activities \(D\), \(E\) and \(F\). (3)
4. Determine the critical activities. (2)
5. Given that the sum of all the times of the activities is 95 hours, calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. (2)
6. Given that workers may not share an activity, schedule the activities so that the process is completed in the shortest time using the minimum number of workers. (4)

(Total 16 marks)

\includegraphics{figure_3} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.

1. Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet. [4]
2. Hence determine the critical activities. [2]
3. Calculate the total float time for \(D\). [2]

Each activity requires only one person.

1. Find a lower bound for the number of workers needed to complete the process in the minimum time. [2]

Given that there are only three workers available, and that workers may not share an activity,

1. schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time. [5]

\includegraphics{figure_5} A project is modelled by the activity network shown in Fig. 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the activity. The numbers in circles give the event numbers. Each activity requires one worker.

1. Explain the purpose of the dotted line from event 4 to event 5. [1]
2. Calculate the early time and the late time for each event. Write these in the boxes in the answer book. [4]
3. Determine the critical activities. [1]
4. Obtain the total float for each of the non-critical activities. [3]
5. On the grid in the answer book, draw a cascade (Gantt) chart, showing the answers to parts (c) and (d). [4]
6. Determine the minimum number of workers needed to complete the project in the minimum time. Make your reasoning clear. [2]

The precedence table shows the activities involved in a project.

1. Draw the activity network for this project, using activity on arc and using two dummies. [4]
2. Explain why each of the two dummies is necessary. [3]

(Total 7 marks)

\includegraphics{figure_4} An engineering 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 the activity. Each activity requires one worker. The project is to be completed in the shortest time.

1. Calculate the early time and late time for each event. Write these in boxes in Diagram 1 in the answer book. [4]
2. State the critical activities. [1]
3. Find the total float on activities D and F. You must show your working. [3]
4. On the grid in the answer book, draw a cascade (Gantt) chart for this project. [4]

The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,

1. which activities must be happening on each of these two days? [3]

\includegraphics{figure_5} The network in Figure 5 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc. The number in brackets is the duration of the activity in days. The early and late event times are to be shown at each vertex and some have been completed for you.

1. Calculate the missing early and late times and hence complete Diagram 2 in your answer book. [3]
2. List the two critical paths for this network. [2]
3. Explain what is meant by a critical path. [2]

The sum of all the activity times is 110 days and each activity requires just one worker. The project must be completed in the minimum time.

1. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. [2]
2. List the activities that must be happening on day 20. [2]
3. Comment on your answer to part (e) with regard to the lower bound you found in part (d). [1]
4. Schedule the activities, using the minimum number of workers, so that the project is completed in 30 days. [3]

(Total 15 marks)

\includegraphics{figure_7} A project is modelled by the activity network shown in Figure 7. 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 Diagram 2 in the answer book to show the early and late event times. [4]
2. State the critical activities. [1]
3. On Grid 1 in the answer book, draw a cascade (Gantt) chart for this project. [4]
4. Use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer. [2]

(Total 11 marks) TOTAL FOR PAPER: 75 MARKS END

Cassi is managing the building of a house. The table shows the major activities that are involved, their durations and their precedences.

1. Draw an activity-on-arc network to represent this information. [5]
2. Find the early time and the late time for each event. Give the project duration and list the critical activities. [6]
3. Calculate total and independent floats for each non-critical activity. [2]

Cassi's clients wish to take delivery in 42 days. Some durations can be reduced, at extra cost, to achieve this.

• The tiler will finish activity I in 9 days for an extra £250, or in 8 days for an extra £500.
• The bricklayer will cut his total of 7 days on activity B by up to 3 days at an extra cost of £350 per day.
• The electrician could be paid £300 more to cut a day off activity D, or £600 more to cut two days.

1. What is the cheapest way in which Cassi can get the house built in 42 days? [3]

A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information. Draw an activity network for the project. You should number the nodes and use as few dummies as possible. [7 marks]

Joan sells ice cream. She needs to decide which three shows to visit over a three-week period in the summer. She starts the three-week period at home and finishes at home. She will spend one week at each of the three shows she chooses travelling directly from one show to the next. Table 1 gives the week in which each show is held. Table 2 gives the expected profits from visiting each show. Table 3 gives the cost of travel between shows. Table 1 Table 2 Table 3 It is decided to use dynamic programming to find a schedule that maximises the total expected profit, taking into account the travel costs.

1. Define suitable stage, state and action variables. [3]
2. Determine the schedule that maximises the total profit. Show your working in a table. [12]
3. Advise Joan on the shows that she should visit and state her total expected profit. [3]

(Total 18 marks)

Victor owns some kiosks selling ice cream, hot dogs and soft drinks. The network below shows the choices of action and the profits, in thousands of pounds, they generate over the next four years. The negative numbers indicate losses due to the purchases of new kiosks. \includegraphics{figure_5} Use a suitable algorithm to determine the sequence of actions so that the profit over the four years is maximised and state this maximum profit. (Total 12 marks)

This question should be answered on the sheet provided. A rally consisting of four stages is being planned. The first stage will begin at A and the last stage will end at L. Various routes are being considered, with the end of one stage being the start of the next. The organisers want the shortest stage to be as long as possible. The table below shows the length, in miles, of each of the possible stages.

			Finishing point
		C	D	E	F	G	H	I
\multirow{3}{*}{Starting point}	A	1	4.5	13	10	8	11	4
	B					5	10.5
	C					9	6
	D					12	7	15
	E
	F							5
	G							8
	H							10
	I
	J
	K

Finishing point
J	K	L
		2
9	2	3
2	9
		5
		6
		10

Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route. [10 marks]

Activity	Time	Precedence
A	5
B	20	A
C	3	A
D	7	A
E	4	B
F	15	C
G	6	C
H	17	D
I	10	F, G
J	2	G, H
K	6	E, I
L	9	I, J
M	3	K, L

Fig. 1 Construct an activity network Use appropriate forward and backward scanning to find

1. the minimum number of days needed to complete the entire project, [3 marks]
2. the activities which lie on the critical path. [3 marks]

[6 marks]