3
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are zero overlaps allowed, or are all overlaps required to be strictly positive? $\endgroup$ – András Salamon Oct 17 '12 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 '12 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$ – András Salamon Oct 17 '12 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$ – Marzio De Biasi Oct 17 '12 at 20:39
  • $\begingroup$ @AndrásSalamon: $m_i$ seems a typo of the Wikipedia definition :) $\endgroup$ – Marzio De Biasi Oct 17 '12 at 20:43
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.