CPM Project Network and Crashing LP Formulation: 23-Ind-A1 Operations Research, Undated paper, Q10

Question 10: CPM Project Network and Crashing LP Formulation (25 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. 9 tasks with min (crash) time, normal time, marginal crashing cost $b_{i,j}$, and predecessors as tabulated.

Find. (a) The project (AON) diagram, earliest/latest times, and the critical path at normal durations. (b) An LP (not solved) for choosing activity durations to meet a specified deadline at minimum crashing cost.

Approach. (a) Forward pass (earliest start/finish) then backward pass (latest start/finish) using NORMAL durations; zero-slack tasks are critical. (b) Standard CPM time-cost trade-off (crashing) LP: one duration variable per activity bounded between its crash and normal time, one event-time variable per node enforcing precedence, and the deadline as an upper bound on the final event time.

AON project network at normal durations. Red nodes/arrows = critical path (zero slack); blue = non-critical (positive slack).

(a) Forward pass (earliest start/finish, normal durations $d_A{=}3,d_B{=}4,d_C{=}2,d_D{=}5,d_E{=}6,d_F{=}2,d_G{=}4,d_H{=}3,d_I{=}5$):
Forward pass (ES = max EF of predecessors)
Task A B C D E F G H I

ES 0 0 3 3 5 11 11 13 15

EF 3 4 5 8 11 13 15 16 20

Project duration = latest EF among tasks with no successors = $\max(16_H,\,20_I)=\boxed{20\text{ days}}$.
Backward pass (LF = min LS of successors; terminal tasks H, I both get $LF=20$):
Backward pass and slack (LS = LF − duration; slack = LS − ES)
Task A B C D E F G H I

LS 0 1 3 6 5 15 11 17 15

LF 3 5 5 11 11 17 15 20 20

Slack 0 1 0 3 0 4 0 4 0

$$\boxed{\text{Critical path: A}\to\text{C}\to\text{E}\to\text{G}\to\text{I}\ (3+2+6+4+5=20\text{ days}),\ \text{slack}=0\text{ throughout}}$$
(b) Crashing LP — decision variables. Let $x_j$ = the actual (chosen) duration of activity $j\in\{A,\dots,I\}$, bounded between its crash and normal time; let $y_i$ = the event (start) time of the node beginning activity $i$'s successors (equivalently, the earliest time all of $i$'s predecessors can finish under the chosen durations), with $y_{\text{start}}=0$ and $y_{\text{finish}}$ = project completion time.
Objective — minimize total crashing cost (each day saved below normal costs $b_j$): $$\min Z=\sum_{j\in\{A,\dots,I\}} b_j\,(\text{normal}_j-x_j)$$ $$=4(3{-}x_A){+}1(4{-}x_B){+}1(2{-}x_C){+}1(5{-}x_D){+}3(6{-}x_E){+}7(2{-}x_F){+}9(4{-}x_G){+}5(3{-}x_H){+}8(5{-}x_I)$$
Duration-bound constraints (each activity between its crash/min and normal time): $$1\le x_A\le3,\quad 2\le x_B\le4,\quad 0.5\le x_C\le2,\quad 2\le x_D\le5,\quad 1\le x_E\le6,$$ $$1\le x_F\le2,\quad 3\le x_G\le4,\quad 2\le x_H\le3,\quad 4\le x_I\le5$$
Precedence (event-timing) constraints, one per (predecessor, successor) arc — a successor's start event cannot occur before its predecessor finishes: $$y_C\ge y_A+x_A,\quad y_D\ge y_A+x_A,\quad y_E\ge y_B+x_B,\quad y_E\ge y_C+x_C,$$ $$y_F\ge y_D+x_D,\quad y_F\ge y_E+x_E,\quad y_G\ge y_D+x_D,\quad y_G\ge y_E+x_E,$$ $$y_H\ge y_F+x_F,\quad y_I\ge y_G+x_G$$ plus $y_A=y_B=0$ (no predecessors) and the project finishes when both terminal tasks H and I are done: $y_{\text{finish}}\ge y_H+x_H,\ y_{\text{finish}}\ge y_I+x_I$.
Deadline constraint and non-negativity, for a specified deadline $T$: $$y_{\text{finish}}\le T,\qquad x_j\ge 0,\ y_i\ge 0\ \ \forall j,i$$ (Not solved, per the question — this LP would be re-solved for whatever deadline $T$ is specified, e.g. $T<20$ to force crashing below the normal 20-day duration found in part (a).)

Forward pass (ES = max EF of predecessors)
Task	A	B	C	D	E	F	G	H	I
ES	0	0	3	3	5	11	11	13	15
EF	3	4	5	8	11	13	15	16	20

Backward pass and slack (LS = LF − duration; slack = LS − ES)
Task	A	B	C	D	E	F	G	H	I
LS	0	1	3	6	5	15	11	17	15
LF	3	5	5	11	11	17	15	20	20
Slack	0	1	0	3	0	4	0	4	0

Final results — Question 10
Item	Value
(a) Project duration (normal times)	20 days
(a) Critical path	A → C → E → G → I
(a) Non-critical tasks (slack)	B (1), D (3), F (4), H (4)
(b) LP model	min $\sum b_j(\text{normal}_j{-}x_j)$, s.t. duration bounds, precedence, $y_{\text{finish}}\le T$ (not solved)

Topic: Critical Path Method (CPM) scheduling and the LP formulation of time-cost trade-off ("crashing").

Key relations: Forward pass $EF_j=ES_j+d_j$, $ES_j=\max_{i\in\text{pred}(j)}EF_i$; backward pass $LS_j=LF_j-d_j$, $LF_j=\min_{k\in\text{succ}(j)}LS_k$; slack $=LS-ES$; crashing LP minimizes $\sum b_j(\text{normal}_j-x_j)$ subject to precedence and a deadline.

Why this works: The critical path is the longest path through the network and therefore lower-bounds the project duration; the crashing LP generalizes this by making each activity's duration a bounded decision variable and enforcing precedence directly as linear inequalities between event times, so the minimum-cost way to hit any deadline (including one shorter than the critical path length) is found by standard LP.

Common pitfall: Building the AON network from the (min, normal) column order as (crash, normal) time without checking which is which — the table's own column headers ("Min Task Time" first, "Normal Task Time" second) must be read literally since crash time is always the SMALLER of the two.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 9–10 (network optimization, CPM/PERT and project crashing as an LP).

Question 10 of 10: CPM Project Network and Crashing LP Formulation

Question 10: CPM Project Network and Crashing LP Formulation (25 marks)