# Job Scheduling decision problem

I would like to know how to prove that the Job Scheduling decision problem is strongly NP-complete using 3-partition.

Input: A set of $$n$$ tasks of length $$t_1, t_2, \ldots t_n \in \mathbb N$$ and $$k$$ processors.

A feasible solution is a function $$\alpha: \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$$ which assigns each task to a processor.

The usage time $$u_j$$ of a processor $$j$$ is the sum of the lengths of all the tasks assigned to it, that is to say that $$u_j = \sum_{i: \alpha(i)=j}t_i$$.

We try to minimize $$\max_j u_j$$, that is to say the time of use of the most used processor.

In the JS$$_{dec}$$ decision problem corresponding to JS, the instance is accompanied by a target value $$T$$ and we are trying to find out if there is a solution where all the processors have a usage time limited by $$T$$.​

## 1 Answer

Let $$X = \{x_1, \dots, x_n\}$$ be an instance of $$3$$ partition where $$n$$ is a multiple of $$3$$ and each $$x_i$$ is strictly between $$\frac{3}{4n}\sum_{i=1}^n x_i$$ and $$\frac{3}{2n}\sum_{i=1}^n x_i$$. The problem remains NP-hard even with this restriction.

The instance of the job scheduling decision problem has $$n$$ jobs, $$t_i = x_i$$, $$k=\frac{n}{3}$$, and $$T=\frac{3}{n}\sum_{i=1}^n x_i$$.

If the 3-partition instance is a "yes" instance, then there is a partition of $$X$$ into $$\frac{n}{3}$$ sets $$X_1, X_2, \dots, X_{\frac{n}{3}}$$ such that, for each $$j=1, \dots, \frac{n}{3}$$, $$\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$$. Let $$\alpha(i)$$ be the index $$j$$ of the unique set $$X_j$$ containing $$x_i$$. Then $$\alpha$$ is an assignment for the job scheduling instance in which, for each $$j=1,\dots,\frac{n}{3}$$, $$u_j = \sum_{i : \alpha(i)=j} = \sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i = T$$. This shows that the job assignment instance is a "yes" instance.

If the job scheduling instance is a "yes" instance, then let $$\alpha$$ be a corresponding assignment. For each $$j=1,\dots,\frac{n}{3}$$:

• $$|\{i : \alpha(i)=j\}| \le 3$$, as otherwise $$u_i > 4 \cdot \frac{3}{4n}\sum_{i=1}^n x_i = T$$.
• $$|\{i : \alpha(i)=j\}| \ge 3$$, as otherwise $$u_i < 2 \cdot \frac{3}{2n}\sum_{i=1}^n x_i = T$$, implying that $$\max_{j' \neq j} u_j \ge \frac{\sum_{i=1}^n x_i - u_i}{\frac{n}{3}-1} > \frac{\sum_{i=1}^n x_i - T}{\frac{n}{3}-1} = \frac{\frac{n-3}{n}\sum_{i=1}^n x_i}{\frac{n-3}{3}} = \frac{3}{n}\sum_{i=1}^n x_i = T$$.

As a consequence, the sets $$X_1, \dots, X_{\frac{n}{3}}$$, where $$X_ j = \{x_i : \alpha(i)=j\}$$, contain $$3$$ elements each and form a partition of $$X$$. Moreover, $$\sum_{x \in X_j} x = u_j \le T = \frac{3}{n}\sum_{i=1}^n x_i$$ and an argument similar to the one above shows that $$\sum_{x \in X_j} x \ge \frac{3}{n}\sum_{i=1}^n x_i$$. This proves that $$\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$$ and hence that the $$3$$ partition instance is a "yes" instance.