Is this multiprocessor scheduling problem with overlaps NP-Hard?

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.

Thanks!

• Are zero overlaps allowed, or are all overlaps required to be strictly positive? – András Salamon Oct 17 '12 at 10:38
• @András Salamon: Zero overlaps are allowed sometimes. But for certain cases, all overlaps are required to be positive. – Fnatic Oct 17 '12 at 13:02
• 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? – András Salamon Oct 17 '12 at 19:51
• @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. – Marzio De Biasi Oct 17 '12 at 20:39
• @AndrásSalamon: $m_i$ seems a typo of the Wikipedia definition :) – Marzio De Biasi Oct 17 '12 at 20:43

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.