# Efficiently updating latest finish times via Critical-Path-Method

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

while len(Stack) > 0:
u = Stack
del Stack
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
del Stack
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.

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.