<p>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.</p>

<p>If you <em>require</em> 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.</p>

CC BY-SA 3.0
2012-10-17T20:44:20.283Z
2012-10-17T20:44:20.283Z
András Salamon
<p>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."</p>

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

<p>Thanks!</p>

CC BY-SA 3.0
2012-10-17T10:38:58.410Z
Are zero overlaps allowed, or are all overlaps required to be strictly positive?
András Salamon
CC BY-SA 3.0
2012-10-17T13:02:08.583Z
@András Salamon: Zero overlaps are allowed sometimes. But for certain cases, all overlaps are required to be positive.
Fnatic
CC BY-SA 3.0
2012-10-17T19:51:25.987Z
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
CC BY-SA 3.0
2012-10-17T20:39:52.773Z
@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
CC BY-SA 3.0
2012-10-17T20:43:18.513Z
@AndrásSalamon: $m_i$ seems a typo of the [Wikipedia definition](http://en.wikipedia.org/wiki/Multiprocessor_scheduling) :)
Marzio De Biasi
CC BY-SA 3.0
2012-10-17T20:58:05.943Z
@Marzio De Biasi: OK, edited the question so it makes sense.
András Salamon
<cc.complexity-theory><np-hardness><optimization><scheduling>
Is this multiprocessor scheduling problem with overlaps NP-Hard?
Fnatic
# Is this multiprocessor scheduling problem with overlaps NP-Hard?

(Asked by: username_0 on 2012-10-16)

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!

**Tags:** cc.complexity-theory, np-hardness, optimization, scheduling
> **Comments:**
> **username_1**: Are zero overlaps allowed, or are all overlaps required to be strictly positive?  
> **username_0**: @András Salamon: Zero overlaps are allowed sometimes. But for certain cases, all overlaps are required to be positive.  
> **username_1**: 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?  
> **username_2**: @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.  
> **username_2**: @AndrásSalamon: $m_i$ seems a typo of the [Wikipedia definition](http://en.wikipedia.org/wiki/Multiprocessor_scheduling) :)  
> **username_1**: @Marzio De Biasi: OK, edited the question so it makes sense.  

---

## 1 answers

### Answer by username_1 on 2012-10-17. Score: 5

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.


---

