7.05e Cascade charts: scheduling and effect of delays

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

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.

8. \begin{figure}[h] \end{figure} 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.
2. State the critical activities.
3. On Grid 1 in the answer book, draw a cascade (Gantt) chart for this project.
4. Use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer. \section*{END}

4. \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 hours, to complete the activity. Some of the early and late times for each event are shown.

1. Calculate the missing early and late times and hence complete Diagram 1 in your answer book.
2. Calculate the total float on activities D, G and I. You must make your calculations clear.
3. List the critical activities. Each activity requires one worker.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time.
   (2)

8. \begin{figure}[h] \end{figure} 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 the late time for each event, showing them on the diagram in the answer book.
2. Determine the critical activities and the length of the critical path.
3. Calculate the total float on activities F and G . You must make the numbers you used in your calculation clear.
4. On the grid in the answer book, draw a cascade (Gantt) chart for the process. Given that each task requires just one worker,
5. use your cascade chart to determine the minimum number of workers required to complete the process in the minimum time. Explain your reasoning clearly.

6. \begin{figure}[h] \end{figure} Figure 5 is the activity network relating to a building project. The number in brackets on each arc gives the time taken, in days, to complete the activity.

1. Explain the significance of the dotted line from event (2) to event (3).
2. Complete the precedence table in the answer booklet.
3. Calculate the early time and the late time for each event, showing them on the diagram in the answer booklet.
4. Determine the critical activities and the length of the critical path.
5. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project.

7. \begin{figure}[h] \end{figure} 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 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 4 to event 6 ,
   2. from event 5 to event 7
      (3)
2. Calculate the early time and the late time for each event. Write these in the boxes in the answer book.
3. Calculate the total float on each of activities D and G. You must make the numbers you use in your calculations clear.
4. Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time.
5. On the grid in your answer book, draw a cascade (Gantt) chart for this project.

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 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 late event times.
2. Calculate the total float for activity D. You must make the numbers you use 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. The project is to be completed in the minimum time using as few workers as possible.
4. Schedule the activities using Grid 1 in the answer book.

7.

1. In the context of critical path analysis, define the term 'total float'. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{818ba207-5839-4698-aacb-75dab88b218f-08_1310_1563_340_251} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 is the activity network for a building project. 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.
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 the maximum number of days by which activity G 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.
   

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)

7. \begin{figure}[h] \end{figure} The network in Figure 6 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 exactly one worker. The early event times and late event times are shown at each vertex. Given that the total float on activity D is 1 day,

1. find the values of \(\boldsymbol { w } , \boldsymbol { x } , \boldsymbol { y }\) and \(\boldsymbol { z }\).
2. On Diagram 1 in the answer book, draw a cascade (Gantt) chart for the project.
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 times and activities. It is decided that the company may use up to 36 days to complete the project.
4. On Diagram 2 in the answer book, construct a scheduling diagram to show how the project can be completed within 36 days using as few workers as possible.
   (3)

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. The exact duration, \(x\), of activity N is unknown, but it is given that \(5 < x < 10\) 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. List the critical activities. It is given that activity J can be delayed by up to 4 hours without affecting the shortest possible completion time of the project.
4. Determine the value of \(x\). You must make the numbers used in your calculation clear.
5. Draw a cascade chart for this project on Grid 1 in the answer book.

2 A manufacturing company is planning to build three new machines, \(A , B\) and \(C\), at the rate of one per month. The order in which they are built is a matter of choice, but the profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.

1. Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
2. Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.

3 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A building project is to be undertaken. The table shows the activities involved.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. Find the critical path and state the minimum time for completion.
5. State the float time for each non-critical activity.
6. Given that each activity starts as early as possible, draw a resource histogram for the project on Figure 2.
7. There are only 3 workers available at any time. Use resource levelling to explain why the project will overrun and state the minimum extra time required.

5 A three-day journey is to be made from \(S\) to \(T\), with overnight stops at the end of the first day at either \(A\) or \(B\) and at the end of the second day at one of the locations \(C , D\) or \(E\). The network shows the number of hours of sunshine forecast for each day of the journey. \includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-05_753_1284_479_386} The optimal route, known as the maximin route, is that for which the least number of hours of sunshine during a day's journey is as large as possible.

1. Explain why the three-day route \(S A E T\) is better than \(S A C T\).
2. Use dynamic programming to find the optimal (maximin) three-day route from \(S\) to \(T\). (8 marks)

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
A group of workers is involved in a building project. The table shows the activities involved. Each worker can perform any of the given activities.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
3. Find the critical path and state the minimum time for completion.
4. The number of workers required for each activity is given in the table above. Given that each activity starts as early as possible and assuming there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.
5. It is later discovered that there are only 7 workers available at any time. Use resource levelling to explain why the project will overrun and indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

5 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows 11 vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown. \includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-05_824_1504_559_278}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to find the minimum cost of travelling from \(S\) to \(T\). You may wish to complete the table on Figure 3 as your solution.
2. State the minimum cost and the routes corresponding to this minimum cost.

2 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
Figure 1 shows the activity network and the duration in days of each activity for a particular project.

1. On Figure 1:
   1. find the earliest start time for each activity;
   2. find the latest finish time for each activity.
2. Find the critical paths and state the minimum time for completion.
3. The number of workers required for each activity is shown in the table.

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

   1. Given that each activity starts as early as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.
   2. It is later discovered that there are only 6 workers available at any time. Explain why the project will overrun, and use resource levelling to indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A truck has to transport stones from a quarry, \(Q\), to a builders yard, \(Y\). The network shows the possible roads from \(Q\) to \(Y\). Along each road there are bridges with weight restrictions. The value on each edge indicates the maximum load in tonnes that can be carried by the truck along that particular road. \includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-6_723_1280_589_372} The truck is able to carry a load of up to 20 tonnes. The optimal route, known as the maximin route, is that for which the possible load that the truck can carry is as large as possible.

1. Explain why the route \(Q A C Y\) is better than the route \(Q B E Y\).
2. By completing the table on Figure 3, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { Y }\), to find the optimal (maximin) route from \(Q\) to \(Y\). Write down the maximin route and state the maximum possible load that the truck can carry from \(Q\) to \(Y\).

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A construction project is to be undertaken. The table shows the activities involved.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. Find the critical path.
5. State the float time for each non-critical activity.
6. On Figure 2, draw a cascade diagram (Gantt chart) for the project, assuming each activity starts as late as possible.

6 Answer parts (i), (ii) and (iii) of this question on the insert provided. The activity network for a project is shown below. The durations are in minutes. The events are numbered 1, 2, 3, etc. for reference. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-06_747_1249_482_447}

1. Complete the table in the insert to show the immediate predecessors for each activity.
2. Explain why the dummy activity is needed between event 2 and event 3, and why the dummy activity is needed between event 4 and event 5 .
3. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Record your early event times and late event times in the table in the insert. Write down the minimum project completion time and the critical activities. Suppose that the duration of activity \(K\) changes to \(x\) minutes.
4. Find, in terms of \(x\), expressions for the early event time and the late event time for event 9 .
5. Find the maximum duration of activity \(K\) that will not affect the minimum project completion time found in part (iii). \section*{ADVANCED GCE
   MATHEMATICS} Decision Mathematics 2
   INSERT for Questions 5 and 6 (ii) Dummy activity is needed between event 2 and event 3 because \(\_\_\_\_\) Dummy activity is needed between event 4 and event 5 because \(\_\_\_\_\) (iii)

   Event	1	2	3	4	5	6	7	8	9	10
   Early event time
   Late event time

   Minimum project completion time = \(\_\_\_\_\) minutes Critical activities: \(\_\_\_\_\) \section*{Answer part (iv) and part (v) in your answer booklet.} OCR
   RECOGNISING ACHIEVEMENT

4. Construct an activity network to show the tasks involved in widening a bridge over the B451.

1. Find those tasks which lie on the critical path and list them in order.
2. State the minimum length of time needed to widen the bridge.
3. Represent the tasks on a Gantt diagram. Tasks \(F\) and \(J\) each require 3 workers, tasks \(B\), \(D\) and \(I\) each require 2 workers and the remaining tasks each require one worker.
4. Draw a resource histogram showing how it is possible for a team of 4 workers to complete the project in the minimum possible time.

\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]

\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]