# Multiprocessor Scheduling is NP-Complete [closed]

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??

• 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. – Ankur Dec 23 '14 at 13:29
• I think this problem can be reduced to subset sum problem variation and that can be used to prove its NP-completness – Ankur Dec 23 '14 at 13:32
• @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. – HFA Dec 23 '14 at 14:38