Draw activity network from table

1 Table 1 shows a precedence table for a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and late event time for each vertex of your network, and list the critical activities.
3. Extra resources become available which enable the durations of three activities to be reduced, each by up to two days. Which three activities should have their durations reduced so as to minimise the completion time of the project? What will be the new minimum project completion time?

4 A room has two windows which have the same height but different widths. Each window is to have one curtain. The table lists the tasks involved in making the two curtains, their durations, and their immediate predecessors. The durations assume that only one person is working on the activity.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Kate and Pete have two rooms to curtain, each identical to that above. Tasks A, B, C and D only need to be completed once each. All other tasks will have two versions, one for room 1 and one for room 2, eg E1 and E2. Kate and Pete share the tasks between them so that each task is completed by only one person.
3. Complete the diagram to show how the tasks can be shared between them, and scheduled, so that the project can be completed in the least possible time. Give that least possible time.
4. How much extra help would be needed to curtain both rooms in the minimum completion time from part (ii)? Explain your answer.

5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown. Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.

1. Complete the table in your answer book by showing the immediate predecessors for each activity.
2. Draw an activity on arc network for these activities.
3. Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
4. Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.

7. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-09_2036_1555_349_248}

1. \(\_\_\_\_\)
2. \(\_\_\_\_\) \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking} Sheet for answering question 6
   NAME \section*{Please hand this sheet in for marking}
   2. 1. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_666_1280_461_374}
      2. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_657_1276_1356_376} Maximum Flow = \(\_\_\_\_\)
   3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   4. \(\_\_\_\_\)
   5. \(\_\_\_\_\)

2 The table lists the durations (in minutes), immediate predecessors and number of workers required for each activity in a project to decorate a room.

1. Draw an activity network, using activity on arc, to represent the project. Your network will require a dummy activity.
2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities.
3. Draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. Suppose that there is only one worker available at the start of the project, but another two workers are available later.
4. Find the latest possible time for the other workers to start and still have the project completed on time. Which activities could happen at the same time as painting the ceiling if the other two workers arrive at this latest possible time?
   [0pt] [Do not change your resource histogram from part (iii).]

3 The table shows the activities involved in a project, their durations and precedences, and the number of workers needed for each activity.

1. On the insert, complete the last two columns of the table.
2. State the minimax value and write down the minimax route.
3. Complete the diagram on the insert to show the network that is represented by the table.

5 Following a promotion at work, Khalid needs to clear out his office to move to a different building. The activities involved, their durations (in hours) and immediate predecessors are listed in the table below. You may assume that some of Khalid's friends will help him and that once an activity is started it will be continued until it is completed.

1. Represent this project using an activity network.
2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and late event time at each vertex of your network. State the minimum project completion time and list the critical activities.
3. How much longer could be spent on sorting the items from the desk and throwing out the rubbish (activity \(C\) ) without it affecting the overall completion time? Khalid says that he needs to do activities \(A , C , E\) and \(G\) himself. These activities take a total of 8.5 hours.
4. By considering what happens if Khalid does \(A\) first, and what happens if he does \(C\) first, show that the project will take more than 8.5 hours.
5. Draw up a schedule to show how just two people, Khalid and his friend Mia, can complete the project in 9 hours. Khalid must do \(A , C , E\) and \(G\) and activities cannot be shared between Khalid and Mia. [2]

4 Bob is extending his attic with the help of some friends, including his architect friend Archie. The activities involved, their durations (in days) and Bob's notes are given below. Archie has started to construct an activity network to represent the project. \includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-5_401_1253_1475_406}

1. Complete the activity network in the Printed Answer Booklet and use it to determine

2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. The table below shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .

   	A	B	C	D	E	F	G
   A	-	17	-	19	30	-	-
   B	17	-	21	23	-	-	-
   C	-	21	-	27	29	31	22
   D	19	23	27	-	-	40	-
   E	30	-	29	-	-	33	25
   F	-	-	31	40	33	-	39
   G	-	-	22	-	25	39	-

3. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
4. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
5. State the weight of the minimum spanning tree.

8. \begin{figure}[h] \end{figure} 4. \begin{figure}[h] \end{figure} 5. \begin{figure}[h] \end{figure} 6. \(\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}\) 7.

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

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

6. 2. \begin{figure}[h] \end{figure} Shortest route: \(\_\_\_\_\) Length of shortest route: \(\_\_\_\_\) \begin{figure}[h] \end{figure} 3. \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \begin{figure}[h] \end{figure} 4. \includegraphics[max width=\textwidth, alt={}, center]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_572_1454_1021_248} \section*{Key:} \section*{Diagram 1} 5. \section*{Diagram 1} 6.

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. The precedence table for activities involved in a small project is shown below

Draw an activity network, using activity on edge and without using dummies, to model this project.
(5)

7. The table shows the activities required for the completion of a building project. For each activity the table shows the time taken, 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 6 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. Add activities, E, F and I, and exactly one dummy to Diagram 1 in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and late event times.
3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
   (2)
4. Schedule the activities, using the minimum number of workers, so that the project is completed in the minimum time.
   (Total 13 marks)

3. The table above shows the activities required for the completion of a building project. For each activity, the table shows the time it takes, 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 number in brackets on each arc is the time taken, in days, to complete the corresponding activity.

1. Add the missing activities and necessary dummies to Diagram 1 in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the critical activities. At the beginning of the project it is decided that activity G is no longer required.
4. Explain what effect, if any, this will have on
   1. the shortest completion time of the project if activity G is no longer required,
   2. the timing of the remaining activities.

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.

4. \begin{figure}[h] \end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

1. Set up the initial time matrix.
2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	A	B	C	D	E	F
   A	-	57	95	147	63	220
   B	57	-	72	204	120	197
   C	95	72	-	242	158	125
   D	147	204	242	-	84	275
   E	63	120	158	84	-	191
   F	220	197	125	275	191	-

   A route is needed that minimises the total time taken to traverse each road at least once.
   The route must start at B and finish at E .
3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
4. Write down the length of the route.

8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should

• maximise the total time spent cycling and running
• train for at most 39 hours
• spend at least \(40 \%\) of her time swimming
• spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

• \(x\) represent the number of hours swimming
• \(y\) represent the number of hours cycling
• \(z\) represent the number of hours running
  1. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.
     (5)

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how

The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.

b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(\mathrm { S } _ { 2 }\)	\(S _ { 3 }\)	Value
\(y\)	0	1	0	1	0	1	11
\(s _ { 2 }\)	0	0	5	-2	1	-5	62
\(x\)	1	0	1	0	0	-1	28
\(P\)	0	0	-1	1	0	1	11

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.

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?

1 A major project has been divided into a number of tasks, as shown in the table. The minimum time required to complete each task is also shown. \section*{Answer space for question 1}

4.
\$ FMMUMITI7 IP HIZ3 UFHGHQFHIT
ா\$ மோங்கோ
ா\%\%mmum \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_268_424_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_46_465_482_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_533_539_301} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_472_593_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_497_648_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_54_501_703_306} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_45_467_762_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_463_813_303} \includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_47_460_872_303} \(\square\) \(\square\) Fig. 2
Construct an activity network to model the work involved in laying the foundations and putting in services for an industrial complex.

1. Execute a forward scan to find the minimum time in which the project can be completed.
2. Execute a backward scan to determine which activities lie on the critical path. The contractor is committed to completing the project in this minimum time and faces a penalty of \(\pounds 50000\) for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity \(E\) will take 3 days longer than the 7 days allocated.
3. Activity \(K\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
   (2 marks)
4. If the time taken to complete any one activity, other than \(E\), could be reduced by 2 days at an extra cost of \(\pounds 80000\), for which activities on their own would this be profitable. Explain your reasoning.
   (3 marks)
   11 marks

1. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below.

1. Draw an activity network for this project.
2. By labelling your network, find the critical path and the minimum duration of the project. An extra condition is now imposed. Task \(A\) may not begin until task \(B\) has been underway for at least 10 minutes.
3. Draw a new network taking into account this restriction.
4. Find a revised value for the minimum duration of the project and state the new critical path.

1. A project consists of the activities listed in the table below. For each activity the table shows how long it will take, which other activites must be completed before it can be done and the number of workers needed to complete it.

1. Draw an activity network for the project.
2. Find the critical path and the minimum time in which the project can be completed.
3. Represent all of the activities on a Gantt diagram.
4. By drawing a resource histogram, find out the maximum number of workers required at any one time if each activity is begun as soon as possible.
5. Draw another resource histogram to show how the project can be completed in the minimum time possible using a maximum of 10 workers at any one time. Sheet for answering question 4 \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_729_1227_482_338} \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_723_1223_1466_338}