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?


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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