Efficiently updating latest finish times via Critical-Path-Method

Question

For a Resource-Constrained-Project-Scheduling problem, I need to calculate Critical-Path-Method (CPM) values for each of the activities. These values are:

• Earliest Start (ES)
• Earliest Finish (EF)
• Latest Start (LS)
• Latest Finish (LF)

The activity network can be represented by an Activity On Node diagram, which is a directed graph $G = (V,A)$, with $V = \{1,2,\ldots, n\}$ being nodes that represent the activities, $A=\{(i,j)\}$ being the arcs indicating the end-start precedences between node $i$ and $j$. Furthermore, it is assumed that the network is such that node $1$ is a source and node $n$ is a sink node. This means that all nodes can be reached from node $1$ by a path and node $n$ is reachable from all nodes by a path.

The ES and EF values can then be calculated by a forward pass, where $ES_0 = 0$. The LS and LF values can thereafter be calculated by a backward pass with $LF_n = EF_n$. I use a topological ordering of the nodes in order to do this correctly. Python pseudo-code for this procedure is as follows, where p denotes the duration of an activity and G_reverse is the original graph G where the precedences are reversed:

# Forward pass ==================
Stack = topologicalSort(G)
ES[0] = 0

while len(Stack) > 0:
   u = Stack[0]
   del Stack[0]
   if ES[u] = updated:
      for i in successors[u]:
         ES[i] = max(ES[i], ES[u] + p[u])

EF = [ES[i] + p[i] for i in range(n)]

# Backward pass ==================
Stack = topologicalSort(G_reverse)
LF[n] = EF[n]

while len(Stack) > 0:
   u = Stack[0]
   del Stack[0]
   if LF[u] = updated:
      for i in predecessors[u]:
         LF[i] = min(LF[i], LF[u] - p[u])

LS = [LF[i] - p[i] for i in range(n)]

In my project, I am continuously adding new precedences $(i,j)$ to the graph (one by one), after which at each time I need to know the new LF time values of all activities. E.g. in the following example, the precedence $(3,4)$ is added to the original graph.

Currently, I do this by recalculating the ES, EF, LS and LF values each time for all nodes. Since this is an expensive part of my algorithm, I am wondering if this can be done more efficiently, e.g. by knowing beforehand which nodes will not have to be updated and exploiting this.

Answer 1

The added precedence (arc) will only affect ES and EF for the head node of the arc (node 4 in your example) and its descendants. So you can limit the ES/EF updates to all paths from the head node to the sink node. If the added arc does not change the ES/EF of the head node, no forward updates would be needed. If you do need to process paths from head node to sink, any time you bump into a node whose ES/EF does not change you can skip the remainder of any paths through it to the sink.

Assuming you do in fact update some ES/EF values, if the $EF_n$ does not change, you do not need a backward pass. If $EF_n$ increases, you will need to do the backward pass to update LS/LF values. I don't think there is a way to avoid a full backward pass, with the qualification that if LS/LF does not change at any node, you do not need to scan backward from that node.