Preemptive job-shop scheduling problems with a fixed number of jobs (Q1299919)

The authors show that the two machine preemptive job-shop problems with mean flow-time or makespan objective function and three jobs are binary NP-hard in contrast to the polynomial solvability of the corresponding nonpreemptive problems with arbitrary but fixed number of jobs. A pseudopolynomial algorithm is constructed for the preemptive problems with fixed numbers of jobs and machines and the same objective functions.