Fixed Machines Hide Number Partitioning

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

For fixed , the problem

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

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

For each integer , create one job with processing time

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

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

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

This proves weak NP-hardness for fixed . It is weak because the hardness comes from number partitioning. For fixed , 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

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

The bounds in 3-partition force each machine load to contain exactly three jobs. Since is part of the input, the reduction gives strong NP-hardness for .