3

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). enter image description here

The duration of each job is given by:

enter image description here

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)

enter image description here

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.

enter image description here

(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:

enter image description here

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

1
  • 1
    Your result is correct. Books contain errors occasionally. – Hans-Martin Mosner Jun 3 at 19:57
3

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

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.

1
  • Thank you for your comment. I just add the algorithm from the book and my calculation step for clarification. Since if I read the algorithm correctly the C_5'' should be 26. – flamingheart Jun 3 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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