Proving NP-hardness of scheduling problem (total weighted completion time)

Question

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this.

Just to be precise, this is the definition of $3$-Part in my notes. Given a set $S = \{a_1, \ldots, a_n\}$ of $n = 3m$ positive integers, does there exist a partition $S_0, \ldots S_{m-1}$ of $S$ such that $|S_i| = 3$ and

$$\sum_{j \in S_i} aj = B := \frac{1}{m} \sum_j a_j$$

So suppose we have an instance of $3$-Part, we construct an instance for $P \mid \mid \sum w_j C_j$ as follows. We have $m$ machines available. For each $a_i$, we have a corresponding job $i$ with $w_i = p_i = a_i$, where $p_i$ is the processing time of job $i$. This is what I have so far, but I am not sure how to proceed.

Suppose I have a yes-instance for $3$-part. How do I distribute the jobs amongst the machines in the most effective way? Is my choice for $w_i$ and $p_i$ correct?

Answer 1

Construct a scheduling instance as you mentioned, with $m$ machines and a job with weight and processing time $p_j=w_j=a_j$ for every $j=1,...,3m$.

For any schedule, let $J_i$ be the jobs assigned to machine $i$, and assume wlog that they are scheduled in order of index. Then the cost associated with jobs in $J_i$ is:

$$ \sum_{k\in J_i} w_k \sum_{j \leq k | j\in J_i} p_j = \sum_{j,k \in J_i| j\leq i} a_j a_k = \frac12 (\sum_{j \in J_i} a_j )^2 + \frac12 \sum_{j \in J_i} a_j^2 .$$ This is independent of the precise way the jobs are scheduled on the machine, only the total load $L_i = \sum_{j \in J_i} p_j$ matters.

It follows that if the 3-Partition is a yes-instance, if and only if there is a schedule with total load $L_i=B$ for every machine $i$ and therefore total cost: $$\frac12 m B^2 + \sum_{j=1}^{3m} \frac12 a_j^2 . $$