# reference that minimum makespan on identical machines is NP-hard?

I need to cite a reference that the minimum makespan problem on ($$>2$$) identical machines is NP-hard. I've seen Garey and Johnson cited as a reference, but it I'm not sure which of the problems is exactly equivalent to this one.

• You can simply mention that reduction follows from Partition problem. How about that? Oct 25 at 12:09
• @InuyashaYagami thanks! Since $m>2$ I guess it is actually multiway number partitioning and the references I found for that just point back to the original work on job scheduling... I guess they are referring to SS8 from Garey and Johnson, but not completely sure
– dpdp
Oct 25 at 12:55
• All such hardness proofs follow from the subset sum problem. The NP-completeness proof of subset sum problem is given in CLRS using a reduction from 3SAT. Then, the reduction to partition problem with 2 sets and further to multiway number partitioning follows from there. Oct 25 at 17:52