Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 - Îμ for any Îμ > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. Naval Research Logistics, 2011