Critical Path Method (CPM) algorithm

Question

I am reading the book "Planning and scheduling in manufacturing and services" by M.Pinedo

I am a little bit confuse at the Critical Path Method (CPM) in this book. There is an example (4.2.3) on page 58: Assume that we have 14 jobs with precedence constraints as in the below figure (in this example we use Job-on-node notion).

The duration of each job is given by:

where p_j is the duration (processing time) of job j.

For the forward procedure, the result which I calculate is the same as the book. (C_j' is the earliest possible completion time of job j)

However, for the backward procedure, everything is the same but one entry in column of job 5. The result for this column is 30 but I calculated the latest possible completion time of job 5 to be 26.

(C_j'' is the latest possible completion time of job j)

May I ask how this result is 30?

---

Update the algorithm

I would like to add the algorithm for the backward procedure and my calculation step to clarify my question:

So according to this algorithm, job 5 has two successors which are job 8 and job 9.

Thus C_5''= min {S_8'',S_9''}

Where

• S_8'' = C_8'' - p_8 = 36 - 6 = 30
• S_9'' = C_9'' - p_9 = 36 - 10 = 26.

Then C_5''= min {30,26} = 26

Answer 1

On the backward pass the latest possible completion time of job 5 is 26

You can see another example on the PMI site - Understanding the basics of CPM calculations

• Forward pass: For the earliest possible completion time of a job, you take the max of the predecessors' end time. This is because it has to wait for the last predecessor to finish before it can start.
• Backward pass: For the latest possible completion time of a job, you take the min of the successors' start time. This is because only after it finishes, either (any) of the successors can start.

Answer 2

Job 8 finishes at time 36 in the C_j'' table. Job 8 takes 6 time units, so the latest job 5, job 8's predecessor, can finish is 36 - 6 = 30.