Article ID: | iaor201112784 |
Volume: | 58 |
Issue: | 8 |
Start Page Number: | 763 |
End Page Number: | 770 |
Publication Date: | Dec 2011 |
Journal: | Naval Research Logistics (NRL) |
Authors: | Nong Qingqin, Ng Chi To, Edwin Cheng T C |
Keywords: | scheduling, combinatorial optimization, game theory |
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.