# Reduction from partition to multiprocessor scheduling

I am kind of unsure about a reduction between two problems. Here are the two problems:

PARTITION: Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$. Question: Can the set $S$ be partitioned into two subsets $S_1$,$S_2$, s.t. the sum of the numbers in $S_1$ equals the sum of the numbers in $S_2$?

MULTIPROCESSOR SCHEDULING: Instance: A set $J$ of $k$ jobs where job $j_i$ has length $l_i$, and $m$ processors. Question: Can we schedule all jobs in $J$ on $m$ processors s.t.: (a) on each processor the next job in the sequence is started immediately after the preceding job is finished and (b) the total time to execute all jobs on each processor takes the minimum possible time $T_{min}=\big(\sum\limits_{i=1}^k l_i\big)/m$

I am a little bit unsure about my try to reduce Partition to multiprocessor scheduling. My attempt is posted as an answer.

• I have moved your attempt to an answer, because that fits the site format better. I will comment there about correctness/improvements. – FrankW May 12 '14 at 8:14

Let $S=\{a_1,...,a_n\}$ be an arbitrary instance of Partition. In our reduction we set $J=S$. if $\sum\limits_{a \in S} a$ is even, we set $m=2$. Note: If the sum of elements in $S$ is odd, there cannot be a Partitioning. Further, we set the length $l_i$ of job $j_i$ to the value of $a_i$.
So this is my reduction. But I am very unsure if this is just too easy? Note that I do not have to provide the correctness proof but just the reduction. Is this somehow a right reduction? I am very unsure if I have to distinguish between the two cases where the sum of elements of $S$ is odd or even. What if the sum is odd?