Two Machines Can Hide Partition

On one machine, makespan minimisation has no real choice. The problem

$$1\mid \varnothing \mid C_{\max }$$

asks for the shortest time to finish all jobs on one machine. If every job must be processed and there are no release times or precedence constraints, then any schedule without idle time is optimal. The makespan is just the total work:

$$C_{\max }=\sum _{j\in J}{p}_j.$$

With two identical machines, the question changes. The problem

$$P_2\mid \varnothing \mid C_{\max }$$

must decide how to split the jobs between the two machines. Minimising makespan asks for the split whose larger side is as small as possible.

This hides 2-partition. Given a multiset $S$ of positive integers, let

$$T=\frac{1}{2}\sum _{s\in S}s.$$

For each integer $s\in S$, create one job with processing time

$$p_s=s.$$

Then there is a schedule on two identical machines with makespan at most $T$ exactly when the integers can be split into two subsets of sum $T$.

The direction from partition to schedule is direct: put the jobs from one subset on the first machine and the jobs from the other subset on the second machine. Both machines have load $T$, so the makespan is $T$.

The reverse direction is the important part. The total processing time is $2T$. If a two-machine schedule has makespan at most $T$, then each machine can carry load at most $T$. Since together they must carry total load $2T$, both machines must carry exactly $T$. The jobs assigned to one machine therefore form a subset of $S$ that sums to $T$.

So $P_2\mid \varnothing \mid C_{\max }$ is weakly NP-hard. The hardness is weak because it comes from the numerical sizes of the processing times, just as in 2-partition.

For more machines, the same idea becomes $k$-way balancing. With fixed $k$, the problem is still number-driven. When the number of machines is part of the input, the problem

$$P\mid \varnothing \mid C_{\max }$$

is strongly NP-hard by reductions from 3-partition.