Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m disjoint subsets, $A = A_1 \cup A_2 \cup \ldots \cup A_m$ such that we have: $$ max \left\{ \sum _{a \in A_i} l(a): 1 \le i \le m \right\} \le D ? $$

My attempt(Also hint from Garey & Johnson) consider $m = 2$ and $D = \frac{1}{2} \sum _{a \in A} l(a)$. if so we have $$ max \left\{ \sum _{a \in A_1} l(a), \sum _{a \in A_2} l(a) \right\} \le \frac{1}{2} \sum _{a \in A} l(a) ? $$

this implies that we should have $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$ and also $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$**(if we have such a partition!)**, otherwise we will have a contradiction because if for example $max$ was $\sum _{a \in A_1} l(a)$ we had $$ \sum _{a \in A_1} l(a)< \frac{1}{2} \sum _{a \in A} l(a) \\ \sum _{a \in A_2} l(a)< \frac{1}{2} \sum _{a \in A} l(a) $$ and if we sum the last two inequalities we get this contradiction: $$ \sum _{a \in A} l(a) < \sum _{a \in A} l(a) $$

so now we know that they are equal, and we see that our problem is now an instance of partition(or subset sum with sum equal $B/2$ where $B$ is sum of all elements of A) and we know that partition is $NPC$ so our main problem is $NPC$ too by restriction.

Is my argument correct??

  • 1
    $\begingroup$ I think your analysis of equations is missing the concept of the Processors being parallel. If A1 is max that simply means that total time of all tasks in A1 set is less than A2 total time and A1 total time (along with A2 total time) is still less than or equal to total deadline time. $\endgroup$ – Ankur Dec 23 '14 at 13:29
  • $\begingroup$ I think this problem can be reduced to subset sum problem variation and that can be used to prove its NP-completness $\endgroup$ – Ankur Dec 23 '14 at 13:32
  • $\begingroup$ @Ankur do you agree with equal part? I have taken the deadline to be half of the time of all tasks, and $A_1$ and $A_2$ are partition of A it means that we should have $\sum_{a \in A_1} l(a)$ + $\sum_{a \in A_2} l(a)$ equal to sum of all tasks, and now I showed that this amount is less than it self which is a contradiction. $\endgroup$ – HFA Dec 23 '14 at 14:38

The deadline is maximum time a single processor can take to complete its tasks (the subset allocated to that processor) where as you are considering deadline as the total of each processor's time.

Let's say there are 6 tasks each with 1 unit of time. Then your example of taking deadline by half of total time of all tasks become 6/2 = 3. Now comes the number of processors which you take to be 2. The task now is to divide the 6 tasks into 2 groups such that the total time of each of the 2 groups is less than or equal to deadline. You cannot compare the sum of total time of each group time with the deadline as the deadline is about the maximum time a single group can take.

In terms of showing that the problem is NP-Complete, I guess you will have to show a reduction of your problem to any of the known NP-Complete problems. Intuitively, I think that this problem can be reduced to a form of subset sum problem which is NP-Complete.

  • $\begingroup$ web.cs.wpi.edu/~cs4123/1999a/HW/homework4.html $\endgroup$ – HFA Dec 24 '14 at 12:04
  • $\begingroup$ you are right that I cannot compare processor's time to deadline, but I assume that I have find such a partition that satisfy the constraint imposed by problem statement, after that I will conclude my results $\endgroup$ – HFA Dec 24 '14 at 12:27

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