1
$\begingroup$

I am probably just missing the correct term for my problem to find the solution but here it goes:

I have a set of tasks with a given duration and an interval for each task in which it has to be completed. I now need to find start times for the tasks, so that

  1. each tasks is completed within its interval
  2. no task overlaps with another task

Sketch:

enter image description here

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? Above all, what is your question? Also, even though this question looks like not complicated, can you add a url or reference to in the question? That will help people to answer your question faster and better. $\endgroup$ – Apass.Jack Oct 26 '18 at 1:31
  • $\begingroup$ I have added a different image that maybe explains the problem better. I need to shift the colored bars in positions so that no colored bar overlaps with another AND each colored bar is within its intrerval (black bars). $\endgroup$ – joekr Oct 26 '18 at 11:06
  • $\begingroup$ Can you tell us whether this is an open problem, tricky problem or an entry-level problem or just a complete new problem created by you? Context is just too important. That is why I am going to ask it again, can you add a url or reference? By the way, your image is really wonderful. $\endgroup$ – Apass.Jack Oct 26 '18 at 12:52
  • $\begingroup$ This seems an NP-complete problem by a reduction from 3-Partition, as suggested by this paper, but it does not give a detailed proof. $\endgroup$ – xskxzr Oct 26 '18 at 13:03
1
$\begingroup$

The deterministic version of your problem (i.e. to determine whether there is a valid arrangement) is strongly NP-complete by a reduction from 3-Partition, as suggested in [1].

Given an instance $x_1,x_2,\ldots,x_{3m}$ of 3-Partition, let the duration in your problem be $[0, mB+m]$ where $B=\sum_{i=1}^{3m} x_i/m$. For each element $x_i$, there is a task with duration $x_i$. The intervals for these tasks are all $[0, mB+m]$. In addition, there are additionally $m$ tasks with duration $1$, and their intervals are respectively $[B, B+1], [2B+1, 2B+2],\ldots,[mB+m-1,mB+m]$. Note the positions of these additional tasks are fixed.

Since we can assume $B/4<x_i<B/2$ for all $i$ in 3-Partition, we can see there is a valid partition if and only if there is a valid arrangement in your problem.


[1] Garey, M. R., & Johnson, D. S. (1977). Two-processor scheduling with start-times and deadlines. SIAM Journal on Computing, 6(3), 416-426.

$\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.