ComputingComputer ScienceAlgorithmsOptimizationSchedulingJob SchedulingMachine SchedulingResource-constrained SchedulingScheduling TheoryMulti-resource SchedulingPreemptive Scheduling ModelScheduling Problems
We show that the problem of finding an optimal schedule for a set of jobs is polynomial complete even in the following two restricted cases.
6
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Optimal scheduling for two-processor systems
E. G. Coffman, Ronald Graham · Acta Informatica · 1972 · 610 citations
Complete register allocation problems
Ravi Sethi · 1973 · 72 citations · Full text