Two Machines Can Hide Partition

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

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:

With two identical machines, the question changes. The problem

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 of positive integers, let

For each integer , create one job with processing time

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

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 , so the makespan is .

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

So 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 -way balancing. With fixed , the problem is still number-driven. When the number of machines is part of the input, the problem

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