<p>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$. </p>

<p>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:</p>

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

<p>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 . $$</p>

CC BY-SA 3.0
2015-04-02T00:28:19.743Z
2018-03-06T19:42:52.067Z
2018-03-06T19:42:52.067Z
Thomas Bosman
<p>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.</p>

<p>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 </p>

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

<p>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. </p>

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

<np-hardness><scheduling>
Proving NP-hardness of scheduling problem (total weighted completion time)
user109536
# Proving NP-hardness of scheduling problem (total weighted completion time)

(Asked by: username_0 on 2015-03-29)

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?

**Tags:** np-hardness, scheduling

---

## 1 answers

### Answer by username_1 on 2015-04-02. Score: -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 . $$


---

