I have a problem with understanding the $P_2 \mid \mid C_\max$ problem which is also known as Tasks Scheduling on Multiple Processors.

In fact, in my case I need only one processor (but the problem is usually described for 2 or more so let it be). I understand what is all about: given a set of tasks with constant delay time and priority the algorithm should find the best permutation of them so that the total delay time is the smallest one.

And now is my question: if the delay is constant for each task, so how come different permutations provide different total delay?

  • 1
    $\begingroup$ 1. Can you edit the question to give a self-contained definition of your problem? (of your variant of the P2||CMax problem) 2. Then, tell us in the question what your thoughts are and what you've tried and why you're unable to work out the answer yourself. Have you worked through some small examples? $\endgroup$
    – D.W.
    Dec 3, 2015 at 23:28

1 Answer 1


Taking apart the notation, here is what we have:

  • Two identical machines.
  • $n$ jobs with equal duration $p$.
  • No release dates or deadlines, i.e. $r_i = 0$ and $d_i = \infty$ for all $i$.
  • No extra features.
  • Objective function is maximum completion time.

It is true that all schedules without idle time have the same completion time in this setting. However, it still takes linear time to actually write down a schedule.

I guess this an easy exercise that is supposed to get you accustomed to notation and working in the model, and will maybe be extended to more complicated $\beta$.

Also, algorithms for this problem may be used as a subroutine, for instance for computing lower bounds in branch-and-bound algorithms for $P_2 \mid \beta \mid C_\max$ problems with non-trivial $\beta$.

Note: The number of processors can make the (conjectured) difference between polynomial and NP-complete complexity.


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.