Question 1 of 6: Scheduling — CPM Analysis and the Two-Excavator Limit

Question 1: Scheduling — CPM Analysis and the Two-Excavator Limit (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Ten activities A to J with fixed durations in weeks and a finish-to-start dependency list, reproduced from the exam table. Every activity occupies one mechanical excavator for the whole of its duration, and once started it cannot be interrupted (no splitting).

Find. (a) the unconstrained project duration and the critical path from a full forward and backward pass; (b) the shortest project duration that can be achieved when no more than two excavators are available at any time.

Approach. Do a forward pass to get every early start and early finish and hence the project duration, a backward pass to get late starts and total floats and hence the critical path; then treat part (b) as a resource-constrained problem, first proving a lower bound on the duration from the total excavator-weeks of work, then exhibiting a feasible schedule that attains it.

1. Part (a) — set the network up and run the forward pass. For each activity $j$ the early start is the largest early finish among its predecessors, and the early finish follows from the duration $d_j$:$$ES_j=\max_{i\in \text{pred}(j)}EF_i,\qquad EF_j=ES_j+d_j$$Starting from A at time zero, $ES_A=0$ and $EF_A=3$; the three successors B, C and D all start at week 3, finishing at 5, 5 and 6. E follows B ($5\to 9$), F follows C ($5\to 10$) and G follows D ($6\to 10$). Activity H waits on both C and E, so $ES_H=\max(5,9)=9$ and $EF_H=10$; I follows G ($10\to 13$). Finally J waits on F, H and I together, so $ES_J=\max(10,10,13)=13$ and $EF_J=15$.
2. Read the project duration off the terminal activity. No activity finishes later than J, so the earliest the project can complete is$$T=\max_j EF_j = EF_J = \boxed{15\ \text{weeks}}$$This is the answer to part (a) for duration; it assumes an unlimited supply of excavators, which is exactly the assumption part (b) removes.
3. Run the backward pass to obtain late dates and total float. Setting $LF_J=T=15$ and working right to left, $$\begin{aligned}LF_i&=\min_{j\in \text{succ}(i)}LS_j\\ LS_i&=LF_i-d_i\\ TF_i&=LS_i-ES_i\end{aligned}$$gives $LS_J=13$, hence $LF_F=LF_H=LF_I=13$. Then $LS_I=10$ so $LF_G=10$ and $LS_G=6$; $LF_D=6$ and $LS_D=3$. On the other branch $LS_H=12$, so $LF_E=12$ and $LS_E=8$, $LF_B=8$ and $LS_B=6$; $LS_F=8$ so $LF_C=8$ and $LS_C=6$. Every path back to A closes at $LS_A=0$.
4. Identify the critical path as the chain of zero-float activities. Tabulating the floats gives 0 for A, D, G, I and J, and 3 weeks for each of B, C, E, F and H. The zero-float activities form one continuous chain, so$$\text{critical path } = A\to D\to G\to I\to J,\qquad 3+3+4+3+2=15\ \text{weeks}$$The chain length equals the project duration, which is the arithmetic check that the two passes are consistent.

Forward and backward pass results (weeks)

Activity	Duration	ES	EF	LS	LF	Total float
A	3	0	3	0	3	0 (critical)
B	2	3	5	6	8	3
C	2	3	5	6	8	3
D	3	3	6	3	6	0 (critical)
E	4	5	9	8	12	3
F	5	5	10	8	13	3
G	4	6	10	6	10	0 (critical)
H	1	9	10	12	13	3
I	3	10	13	10	13	0 (critical)
J	2	13	15	13	15	0 (critical)

5. Part (b) — measure the excavator demand of the early-start schedule. Plotting every activity at its early start and counting how many run in each week gives a demand of one excavator in weeks 0 to 3, then three excavators continuously from week 3 to week 10, then one again to the end. The peak of three exceeds the limit of two, so the 15-week schedule is not feasible and the duration must lengthen.
Figure 1.2 — Early-start bar chart of the unconstrained 15-week schedule with its excavator histogram. The demand sits at three units for seven consecutive weeks, so the schedule cannot be built with two machines.
6. Derive a lower bound on the constrained duration from the total work content. The excavator-weeks of work are fixed by the durations, $\sum_j d_j = 29$ excavator-weeks. Over a project of length $T$ two machines can supply at most $2T$ excavator-weeks, so $$2T \ge \sum_j d_j + \text{(idle excavator-weeks)}$$Idle time is not zero here, and two blocks of it are unavoidable.
7. Quantify the unavoidable idle time at the two ends of the project. A is the only activity with no predecessor, so nothing else can run during its 3 weeks and one machine must stand idle throughout. At the other end, every one of A to I is a direct or transitive predecessor of J, so J must run alone for its 2 weeks. That is 5 excavator-weeks of forced idleness, giving $2T \ge 29+5 = 34$ and therefore$$T \ge 17\ \text{weeks}$$Any feasible two-machine schedule is at least 17 weeks long.
8. Construct a 17-week schedule that attains the bound. After A finishes at week 3, run the two machines as two continuous chains. Chain one takes B (3–5), D (5–8), G (8–12) and I (12–15); chain two takes C (3–5), E (5–9), H (9–10) and F (10–15). Each chain is exactly 12 weeks long, so neither machine is ever idle between weeks 3 and 15, and J then runs alone from 15 to 17.
9. Check the schedule against both constraint sets. Precedence: D and E start only after A and B respectively are complete; G follows D at week 8; I follows G at week 12; H starts at week 9, after both C (week 5) and E (week 9); F starts at week 10, well after C; and J starts at 15, after F (15), H (10) and I (15). Resources: exactly two activities are live in every week from 3 to 15 and one in every other week, so the demand never exceeds two. The schedule is feasible, and because it matches the lower bound it is optimal:$$T_{\min}\ (\text{2 excavators}) = \boxed{17\ \text{weeks}}$$
Figure 1.3 — The resource-levelled bar chart. Two continuous chains of 12 weeks each fill the interval between A and J, so the histogram sits flat on the limit of two and the 17-week bound is met exactly.

The two-week stretch is the price of the resource limit. It also destroys the original critical path as a management tool: D, G and I remain critical, but B, C, E and F have had their float consumed by the sequencing decision rather than by logic, so a delay to F now delays the project even though F carried three weeks of float in part (a). This is why resource-levelled schedules are usually re-analysed with the levelling decisions written back into the network as artificial links, so that the reported floats mean what the site team thinks they mean.

Question 1 — final results

Quantity	Value
Unconstrained project duration (CPM)	15 weeks
Critical path	A – D – G – I – J
Activities with float	B, C, E, F, H (3 weeks total float each)
Peak excavator demand at early start	3 machines (weeks 3 to 10)
Total work content	29 excavator-weeks
Minimum duration with two excavators	17 weeks
Extension caused by the resource limit	2 weeks