It is shown that the job-shop problem with two machines and a fixed number of k jobs with makespan criterion J2ℝn=kℝCmax is polynomially solvable. Sotskov and Shakhlevich have shown that problem J3ℝn=3ℝCmax is NP-hard. Furthermore it is well known that Jℝn=2ℝCmax in polynomially solvable. Thus, the present result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.
