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.
