Question 8 of 9: CPM — Floats, LP/Network-Flow Formulations, and Crashing

Question 8: CPM — Floats, LP/Network-Flow Formulations, and Crashing (15 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. Eight activities with precedence, duration and (for (d)) a per-week speed-up (crash) cost, each crashable by up to 2 weeks:

Find. (a) Total float (TF) and free float (FF) for every activity. (b) An LP whose solution gives the critical-path length. (c) A minimum-cost network-flow formulation for the same purpose. (d) An LP that minimizes crash cost to finish by week 12.

Approach. (a) is a direct forward/backward CPM pass. (b) and (c) are two different, standard LP-based recastings of "find the longest path" (as a set of finish-time inequalities, and as a 1-unit min-cost flow on negated-duration arcs). (d) extends (b)'s finish-time formulation with crash-amount variables and a 12-week deadline constraint.

1. Part (a) — forward pass (earliest start/finish, $ES_j=\max_{i\in\text{pred}(j)}EF_i$, $EF_j=ES_j+d_j$):

   Forward pass

   Activity	A	B	C	D	E	F	G	H
   ES	0	0	6	9	11	5	14	18
   EF	6	5	9	11	14	7	18	20

   Project duration $T=\max(EF)=\boxed{20\text{ weeks}}$ (activity H finishes last).
2. Part (a) — backward pass (latest finish/start, $LF_i=\min_{j\in\text{succ}(i)}LS_j$, with $LF_H=T=20$; $LS_i=LF_i-d_i$):

   Backward pass

   Activity	A	B	C	D	E	F	G	H
   LS	0	11	6	9	11	16	14	18
   LF	6	16	9	11	14	18	18	20

3. Part (a) — total float $TF_i=LS_i-ES_i$ and free float $FF_i=\min_{j\in\text{succ}(i)}ES_j-EF_i$ (project duration minus $EF$ for the terminal activity H):

   Total float and free float by activity

   Activity	A	B	C	D	E	F	G	H
   TF (wk)	0	11	0	0	0	11	0	0
   FF (wk)	0	0	0	0	0	11	0	0

   $$\boxed{\text{Critical path: A -- C -- D -- E -- G -- H, duration 20 weeks (TF = FF = 0 throughout)}}$$ Only B and F carry float ($TF=11$ each), and it is shared along the chain B→F→H: B's free float is 0 (any delay to B pushes back F's earliest start, although the project itself is unaffected until the 11 weeks are used up), while F's 11 weeks are entirely free ($FF_F=TF_F=11$) because its only successor H cannot start before week 18 anyway.
4. Part (b) — LP to determine the critical path. Let $t_j\ge0$ = earliest completion time of activity $j$. Minimizing the project's completion time subject to "finish no earlier than predecessor-finish plus own duration" pushes every $t_j$ down to exactly its earliest-finish value, and the minimized $t_H$ equals the critical-path length: $$\text{Minimize } t_H$$ $$\text{s.t.}\quad t_A\ge6,\ \ t_B\ge5,\ \ t_C\ge t_A+3,\ \ t_D\ge t_C+2,$$ $$t_E\ge t_A+3,\ \ t_E\ge t_D+3,\ \ t_F\ge t_B+2,\ \ t_G\ge t_E+4,$$ $$t_H\ge t_G+2,\ \ t_H\ge t_F+2,\qquad t_j\ge0\ \forall j.$$ Solving this LP reproduces $t_H=20$ and every $t_j=EF_j$ from part (a) — the LP is not asked to be solved, but the check confirms the formulation.
5. Part (c) — minimum-cost network flow formulation. Add a dummy source node $St$ (arcs to A and B) and treat each activity as an arc into its own node (as drawn in the figure). Send exactly 1 unit of flow from $St$ to the sink H, with each arc's unit cost equal to the negative of its head activity's duration (so that minimizing total cost is equivalent to maximizing total duration, i.e. finding the longest = critical path): $$\text{Minimize}\ \sum_{(i,j)\in\text{Arcs}} c_{ij}\,x_{ij},\qquad c_{ij}=-d_j$$ $$\text{s.t.}\quad \sum_{j:(i,j)}x_{ij}-\sum_{k:(k,i)}x_{ki}=b_i\ \ \forall i\quad(b_{St}=1,\ b_H=-1,\ b_i=0\text{ otherwise}),$$ $$0\le x_{ij}\le1\ \ \forall (i,j).$$ The single unit of flow is forced along one source-to-sink path; because every arc cost is negative, the min-cost solver is pushed onto the path with the largest total duration — the critical path — and $-(\text{optimal cost})$ recovers the 20-week project length.
6. Part (d) — crashing LP for a 12-week deadline. Add crash variables $y_i\in[0,2]$ (weeks crashed) for every crashable activity, with H excluded ($y_H=0$, no speed-up cost given). Reuse part (b)'s finish-time network but with each duration reduced by its own crash amount, and cap the project at 12 weeks instead of minimizing it: $$\text{Minimize}\ 80y_A+60y_B+30y_C+60y_D+40y_E+30y_F+20y_G$$ $$\text{s.t.}\quad t_A\ge6-y_A,\ \ t_B\ge5-y_B,\ \ t_C\ge t_A+(3-y_C),\ \ t_D\ge t_C+(2-y_D),$$ $$t_E\ge t_A+(3-y_E),\ \ t_E\ge t_D+(3-y_E),\ \ t_F\ge t_B+(2-y_F),\ \ t_G\ge t_E+(4-y_G),$$ $$t_H\ge t_G+2,\ \ t_H\ge t_F+2,\qquad t_H\le12,$$ $$0\le y_A,y_C,y_D,y_E,y_G\le2,\quad 0\le y_B,y_F\le2,\quad t_j\ge0\ \forall j.$$ Only the critical-path activities (A, C, D, E, G — H is not crashable) can shorten the project on their own; B and F have 11 weeks of float each and would need to be crashed by more than their float before they could ever become part of a binding path, so an optimal solver will drive $y_B=y_F=0$.