Complexity of Machine Scheduling Problems 1: PARTITION Reduces to Makespan and to Weighted Completion Time on Two Identical MachinesResearch Paper
Deterministic machine scheduling asks how to process a set of jobs on a set of machines so that an overall criterion, such as the time at which the last job finishes, is as small as possible. In the early 1970s many such problems had efficient algorithms (Johnson's rule for the two-machine flow shop, Smith's ratio rule for a single machine, Lawler's rule…