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!
Reduce Garey &amp; 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.