Fixed Machines Hide Number Partitioning

The jump from two machines to $k$ machines does not change the basic shape of the reduction. It only changes the number of piles.

For fixed $k$, the problem

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

asks for a schedule on $k$ identical machines with minimum makespan. Here $k$ is a constant, not part of the input.

The matching number problem is k-partition: given a multiset $S$ of positive integers whose total sum is $kT$, can $S$ be partitioned into $k$ subsets, each of sum $T$?

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

$$p_s=s.$$

Then a schedule with makespan at most $T$ exists exactly when the integers can be split into $k$ groups of sum $T$.

The proof is the same as for two machines. If the $k$-partition exists, put each subset on one machine. Every machine has load $T$, so the makespan is $T$.

Conversely, suppose there is a schedule with makespan at most $T$. The total processing time is $kT$. Since there are $k$ machines and each machine has load at most $T$, the total load capacity before time $T$ is also $kT$. Therefore every machine must have load exactly $T$. The jobs assigned to each machine give the required $k$ subsets.

This proves weak NP-hardness for fixed $k$. It is weak because the hardness comes from number partitioning. For fixed $k$, the problem can also be solved in pseudo-polynomial time by dynamic programming over the machine loads.

The situation changes when the number of machines is part of the input. The problem

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

is strongly NP-hard. The reduction uses 3-partition. Given $3m$ integers with target triplet sum $T$, create one job per integer and use $m$ machines. Ask whether the makespan is at most $T$.

The bounds in 3-partition force each machine load $T$ to contain exactly three jobs. Since $m$ is part of the input, the reduction gives strong NP-hardness for $P\mid \varnothing \mid C_{\max }$.