Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynominal time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed number m of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would imply P = NP. Hence, our result draws a precise separating line between approximable cases (i.e., with m fixed) and non-approximable cases (i.e., with m part of the input) of this shop problem.