# Critical Path Method (CPM) algorithm

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

• Your result is correct. Books contain errors occasionally. Jun 3, 2021 at 19:57