Question 3 of 10: CPM Network and Crashing — Nine-Task Project
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2014 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 150 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization (CPM), dynamic programming, decision analysis, Markov chains and queueing theory; Nahmias, Production and Operations Analysis (7th ed.) — EOQ and inventory-control models.
Given. Nine activities with (min/crash time, normal time, cost slope $b_{i,j}$ per unit-time saved, predecessors):
Given data — activity durations and crash slopes
Task
Crash time
Normal time
$b_{i,j}$ ($/day saved)
Predecessors
A
1
3
4
—
B
2
4
1
—
C
0.5
2
1
A
D
2
5
1
A
E
1
6
3
B, C
F
1
2
7
D, E
G
3
4
9
D, E
H
2
3
5
F
I
4
5
8
G
Find. (a) The activity-on-node project diagram and the critical path at normal durations; (b) an LP formulation (not solved) for choosing each activity's duration between its crash and normal time to hit a specified project deadline at minimum crashing cost.
Approach. Run a forward/backward CPM pass at normal durations to get the critical path (part a), then generalize the network's precedence structure into a time-cost-tradeoff LP with one continuous duration variable per activity, bounded between its crash and normal time (part b).
Activity-on-node network at normal durations (duration shown in parentheses). Arrows show precedence: A→C, A→D, B→E, C→E, D→F, D→G, E→F, E→G, F→H, G→I.
Forward pass (earliest start/finish). With no predecessors, $A$ and $B$ start at $t=0$: $EF_A=3$, $EF_B=4$. Then $EF_C=EF_A+2=5$, $EF_D=EF_A+5=8$, $EF_E=\max(EF_B,EF_C)+6=5+6=11$, $EF_F=\max(EF_D,EF_E)+2=11+2=13$, $EF_G=\max(EF_D,EF_E)+4=11+4=15$, $EF_H=EF_F+3=16$, $EF_I=EF_G+5=20$. Project duration $=\max(EF_H,EF_I)=\boxed{20\text{ days}}$.
Backward pass and slack. Setting $LF_I=LF_H=20$ and working back task-by-task (Python-verified) gives zero slack ($LS=ES$) on A, C, E, G, I and positive slack on B (1 day), D (3 days), F (4 days), H (4 days).
Part (a) — critical path. The zero-slack chain is $\boxed{A\rightarrow C\rightarrow E\rightarrow G\rightarrow I}$, length $3+2+6+4+5=20$ days, matching the project duration found above.
Part (b) — decision variables. Let $t_{ij}$ be the (continuous) duration actually used for activity $(i,j)$, bounded between its crash time $cr_{ij}$ and normal time $nr_{ij}$: $cr_{ij}\le t_{ij}\le nr_{ij}$. Let $x_{ij}=nr_{ij}-t_{ij}\ge0$ be the amount that activity is crashed, so the crashing cost is $b_{ij}x_{ij}$ (linear, per the given slopes).
Part (b) — event times and precedence. Introduce an event time $T_k$ at each node $k\in\{A,\dots,I,\text{Finish}\}$ (start node $T_0=0$). Precedence is enforced by $T_j\ge T_i+t_{ij}$ for every activity $(i,j)$ in the network above (e.g. $T_C\ge T_A+t_A$, $T_E\ge T_B+t_B$, $T_E\ge T_C+t_C$, $T_F\ge T_D+t_D$, $T_F\ge T_E+t_E$, and so on through $T_{\text{Finish}}\ge T_H+t_H$, $T_{\text{Finish}}\ge T_I+t_I$).
Part (b) — deadline and objective. With specified deadline $D_{\text{spec}}$, add $T_{\text{Finish}}\le D_{\text{spec}}$. The complete (unsolved) LP is:
$$\boxed{\text{Minimize } Z=\sum_{(i,j)} b_{ij}x_{ij}\ \text{ s.t. } T_j-T_i+x_{ij}\ge nr_{ij}\ \forall(i,j),\ 0\le x_{ij}\le nr_{ij}-cr_{ij},\ T_{\text{Finish}}\le D_{\text{spec}},\ T_k\ge0.}$$
(The constraint form $T_j-T_i+x_{ij}\ge nr_{ij}$ is the linearization of $T_j\ge T_i+(nr_{ij}-x_{ij})$, i.e. $T_j\ge T_i+t_{ij}$.)
