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.

enter image description here

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.


1 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.

  • $\begingroup$ Thank you, all of the points you mention make sense. I'll have to think about how to efficiently use these ideas. That is, I'll need to store somehow which nodes can be skipped since they're on a path from/to a node that is not updated during the forward/backward pass. $\endgroup$
    – Rutger
    Commented May 3, 2022 at 14:04
  • 1
    $\begingroup$ You already have the predecessors and successors of each node stored. You can use a FIFO queue as a "to do" list. On the forward pass, initialize the queue with the first affected node (4 in your diagram). At each step, remove the next node from the queue, update ES/EF for its successors and push any that have changed into the queue. On the reverse pass, initialize the queue with the sink node (assuming it changed) and, when processing each node in the queue, push any predecessors that changed. $\endgroup$
    – prubin
    Commented May 3, 2022 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.