PERT Networks

A PERT network encodes a project as a vertex-weighted graph $G = (V, E, w)$.

• vertices $i \in V$ represent tasks.
• edges $(i, j) \in E$ represent precedence constraints: task $i$ must finish before task $j$ can start.
• vertex weights $w_i \in [0, \infty]$ represent durations: task $i$ takes $w_i$ days to complete.

The figure below shows a PERT network with eight tasks and ten precedence constraints.

We can represent the network as a matrix $A: V \times V \to [-\infty, \infty]$, where

\[A_{ij} = \begin{cases} w_i &\text{if } (i, j) \in E \\ -\infty &\text{if } (i, j) \notin E \end{cases}\]

for all pairs of tasks $(i, j) \in V \times V$.

using SemiringFactorizations, SparseArrays

# max-plus semiring
const MP = MaxPlus{Float64}

# durations
w = MP[3, 2, 4, 3, 5, 2, 6, 4]

# precedence constraints
#    1  1  2  2  3  4  4  5  6  7
#    ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
#    3  6  3  4  5  7  5  6  7  8
I = [1, 1, 2, 2, 3, 4, 4, 5, 6, 7]
J = [3, 6, 3, 4, 5, 7, 5, 6, 7, 8]

A = sparse(I, J, w[I], 8, 8)

8×8 SparseArrays.SparseMatrixCSC{MaxPlus{Float64}, Int64} with 10 stored entries:
  ⋅     ⋅     3.0   ⋅     ⋅     3.0   ⋅     ⋅  
  ⋅     ⋅     2.0   2.0   ⋅     ⋅     ⋅     ⋅  
  ⋅     ⋅     ⋅     ⋅     4.0   ⋅     ⋅     ⋅  
  ⋅     ⋅     ⋅     ⋅     3.0   ⋅     3.0   ⋅  
  ⋅     ⋅     ⋅     ⋅     ⋅     5.0   ⋅     ⋅  
  ⋅     ⋅     ⋅     ⋅     ⋅     ⋅     2.0   ⋅  
  ⋅     ⋅     ⋅     ⋅     ⋅     ⋅     ⋅     6.0
  ⋅     ⋅     ⋅     ⋅     ⋅     ⋅     ⋅     ⋅  

The Kleene star of $A$ is a matrix $A^*: V \times V \to [-\infty, \infty]$ whose entry

\[A^*_{ij} \in [-\infty, \infty]\]

is equal to the shortest possible interval between the start of $i$ and the start of $j$. In particular, if $j$ can precede $i$, then $A^*_{ij} = -\infty$. We can compute $A^*$ explicitly using the function star.

star(A)

8×8 Matrix{MaxPlus{Float64}}:
  0.0  -Inf   3.0  -Inf   7.0  12.0  14.0  20.0
 -Inf   0.0   2.0   2.0   6.0  11.0  13.0  19.0
 -Inf  -Inf   0.0  -Inf   4.0   9.0  11.0  17.0
 -Inf  -Inf  -Inf   0.0   3.0   8.0  10.0  16.0
 -Inf  -Inf  -Inf  -Inf   0.0   5.0   7.0  13.0
 -Inf  -Inf  -Inf  -Inf  -Inf   0.0   2.0   8.0
 -Inf  -Inf  -Inf  -Inf  -Inf  -Inf   0.0   6.0
 -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf   0.0

Alternatively, we can compute a factorized representation of $A^*$ using the function slu. This approach is generally faster than the previous one.

K = slu(A)

SparseStarLU{MaxPlus{Float64}, Int64}:
  maximum front-size: 4
  structural nonzeros: 34

Scheduling

We will also distinguish two sets of tasks.

• start tasks: $S \subseteq V$
• final tasks: $F \subseteq V$

Our goal is to complete the tasks in $F$, starting with the tasks in $S$.

S = [1, 2]; F = [8];

We can represent $S$ as a vector $s: V \to [-\infty, \infty]$, where

\[s_i = \begin{cases} 0 &\text{if } i \in S \\ -\infty &\text{if } i \notin S \end{cases}\]

s = zeros(MP, 8); s[S] .= 0
s

8-element Vector{MaxPlus{Float64}}:
  0.0
  0.0
 -Inf
 -Inf
 -Inf
 -Inf
 -Inf
 -Inf

We can represent $F$ as a vector $f: V \to [-\infty, \infty]$, where

\[f_i = \begin{cases} w_i &\text{if } i \in F \\ -\infty &\text{if } i \notin F \end{cases}\]

f = zeros(MP, 8); f[F] .= w[F]
f

8-element Vector{MaxPlus{Float64}}:
 -Inf
 -Inf
 -Inf
 -Inf
 -Inf
 -Inf
 -Inf
  4.0

Earliest Start and Finish Times

For all tasks $i \in V$, the earliest start time

\[s^e_i \in [0, \infty]\]

is the earliest time that $i$ can begin.

se = transpose(transpose(s) * K)

8-element Vector{MaxPlus{Float64}}:
  0.0
  0.0
  3.0
  2.0
  7.0
 12.0
 14.0
 20.0

The earliest finish time

\[f^e_i \in [0, \infty]\]

is the earliest time that $i$ can be completed.

fe = se .* w

8-element Vector{MaxPlus{Float64}}:
  3.0
  2.0
  7.0
  5.0
 12.0
 14.0
 20.0
 24.0

Makespan

The makespan is the earliest that the project can be completed. If the project takes longer than this time, then it is behind schedule.

c = transpose(se) * f

24.0

Latest Start and Finish Times

For all tasks $i \in V$, the latest start time

\[ s^l_i \in [0, \infty]\]

is the latest time that $i$ can begin without the project falling behind schedule.

sl = transpose(c / (K * f))

8-element Vector{MaxPlus{Float64}}:
  0.0
  1.0
  3.0
  4.0
  7.0
 12.0
 14.0
 20.0

The latest finish time

\[ f^l_i \in [0, \infty]\]

is the latest time that $i$ can finish without the project falling behind schedule.

fl = sl .* w

8-element Vector{MaxPlus{Float64}}:
  3.0
  3.0
  7.0
  7.0
 12.0
 14.0
 20.0
 24.0

Slack and Critical Tasks

For all tasks $i \in V$, the difference

\[ s^l_i - s^e_i \in [0, \infty]\]

is called the slack at $i$. It encodes how long $i$ can be delayed before the project falls behind schedule.

slack = sl ./ se

8-element Vector{MaxPlus{Float64}}:
 0.0
 1.0
 0.0
 2.0
 0.0
 0.0
 0.0
 0.0

A task $i \in V$ is called critical if its slack is zero. Critical tasks cannot be delayed without delaying the whole project.

critical = findall(isone, slack)

6-element Vector{Int64}:
 1
 3
 5
 6
 7
 8

This page was generated using Literate.jl.