The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the same processor, then the length of $J_i$ and $J_k$ is less than $L_i+L_k$), what is the minimum possible time required to schedule all jobs in $J$ on $m$ processors."

Is the above problem NP_hard? I'd be happy to get a reference or a description of a reduction.


  • $\begingroup$ Are zero overlaps allowed, or are all overlaps required to be strictly positive? $\endgroup$ Oct 17, 2012 at 10:38
  • $\begingroup$ @András Salamon: Zero overlaps are allowed sometimes. But for certain cases, all overlaps are required to be positive. $\endgroup$
    – Fnatic
    Oct 17, 2012 at 13:02
  • $\begingroup$ Second question. What is the role of $m_i$? Does it restrict which processors job $J_i$ can run on, or does it specify how many processors are required for job $J_i$ to run, or is something else intended? $\endgroup$ Oct 17, 2012 at 19:51
  • 1
    $\begingroup$ @Fnatic: even if all overlaps are required to be positive, given an instance of a scheduling problem without overlaps, you can reduce it to your problem scaling the job lengths and the total time T and introducing a small amount of ininfluent overlap between jobs. For example multiply by (|J|+1) and add an overlap of 1. $\endgroup$ Oct 17, 2012 at 20:39
  • $\begingroup$ @AndrásSalamon: $m_i$ seems a typo of the Wikipedia definition :) $\endgroup$ Oct 17, 2012 at 20:43

1 Answer 1


Reduce Garey & Johnson problem [SS8], Multiprocessor Scheduling, to your problem. This is NP-complete, even if $m=2$. In this problem there are no overlaps, and a deadline is specified. Your problem is therefore NP-hard, even in the case of zero overlaps.

If you require non-zero overlaps, then it is still possible to reduce Multiprocessor Scheduling to your problem, by increasing the length of each task by 1, and specifying all overlaps to be exactly 1.


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.